A good hash function must: Quick and easy to compute Minimise collisions Achieve an even distribution of keys Aim: Efficiency O(1) for storage and retrieval of data
The following slots are tried to find an empty slot: h + i2 (mod table size) for i = 1,2,3... ie: slots tried are: h, h+1, h+4, h+9, h+16 ...... (mod table size) Works well if the table size is prime.
what is Collision Resolution with Open Addressing using Add the hash Rehash
The hash value is added to the hashed value repetitively to find an empty slot. ie: slots tried are: h, 2h, 3h, 4h, ... (mod table size) Works well if the table size is prime.
what is Collision Resolution with Open Addressing using random Rehash
a pseudo‑random number generator is used to obtain the increments Uses a seed to initiate the sequence of random numbers. Excellent in avoiding collisions but slower