CSC 111 Lecture Notes - Lecture 17: Linked List, Hash Table, Unique Key
13 Nov 2017
School
Department
Course
Professor
Document Summary
On everything from past exam until end of semester. Idea behind hash table is to map data to a unique location in an array. H(7: h(7) : hash table of size 7, conditions, 1. 4 n-1: data: 14, 3, 11, 21, 13, 7, h (x) = x%7; h (7) 13: linear probing, search for next available location starting from hash index. 13 h(x) = 0 h(y) = 0 because x is already 0 y will go to 1 even though it equals 0 because 0 is occupied 21 goes to 1 because 0 and 1 are occupied, 7 goes to. Insert: done, search, separate chaining search linked list. Linear probing search until found of available: will go from its index at h (n) and search following indexes until it is found or it reaches an open spot, delete, separate chaining remove form linked list. Linear probing: put in deactivate symbol, et (cid:862)deactive(cid:863) (cid:373)arker, hash table performance.
