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)
