What are pros and cons of linear probing, quadratic probing and double hashing?
Answers
Linear probing
It is a strategy for resolving collisions. In this the new key is placed in the closest following empty cell.
Advantage - It is faster due to locality of reference.
Disadvantage - It needs a five-way independence in the hash function.
Quadratic probing
It is used to resolve collisions in hash tables. It is an open addressing scheme in computer programming.
Advantage - It is more efficient for a closed hash table.
Disadvantage - It has secondary clustering. Two keys have the same probe sequence when they hash to the same location.
Double hashing
It is a popular collision-resolution technique used in open-addressed hash tables.
Advantages
1. It drastically reduces clustering.
2. It requires fewer comparisons.
3. Smaller hash tables can be used.
Disadvantage - As the table fills up the performance degrades.