hashing

Question 1

colisions

Answer 1

linear probing
quadratic probing
double hash probing

Question 2

linear probing advan and dis

Answer 2

H(k) = [h(k) + i] mod m
A = cache
B = clusters

Question 3

quadratic probing advan and dis

Answer 3

H(k) = [h(k) + i^2] mod m
A ~ clusters
D ~ cache

Question 4

double hash probing

Answer 4

H(k) = [h1(k) + ih2(k)] mod m
A = clusters
D = cache

Question 5

cuckoo hashing

Answer 5

utiliza 2 tablas de hash, en donde los elementos tienen 2 keys distintas para cada tabla
insert O(1)
delete O(1)
search O(1)

Question 6

hopscotch

Answer 6

the use of a bit map to see which positions their in
insert O(1)
delete O(1)
search O(1)