Hashing Structures Flashcards
give the three components of a hash map
bucket array
hashing function
collision resolution strategy
describe the hash map ADT
insert (k,v)
find(k)
describe a collision
two keys k, k’ such that h(k) = h(k’)
describe the two parts of a hash function
- compute the hash code
2. map to range using compression map
what is the division method
h(k) = k mod N
describe the MAD method
h(k) = ((ak + b ) mod p) mod N
where p is prime
describe separate chaining
collision resolved by inserting in the next free place
describe linear probing
scan through array for empty space
describe quadratic probing
try A[(i+j^2) mod N]
i = h(k)
j = 0,1,2,3,…
describe double hashing
try A[i + (j h’(k)]
i = h(h)
j = 0,1,2,3…
describe rehashing
if a hash table becomes too full we must rehash to make it larger
what is the load factor
how full the table is. This should be kept below 1.
k / n
k = number of items
n = capacity
give the worst and average time complexity for inserting
O(n)
O(1)
give the space complexity
O(n)
give the worst and average time complexities for find
O(n)
O(1)
give the worst and average time complexities for remove
O(n)
O(1)
