Quadratic probing over Linear probing

Question

For a given hash value, the indices generated by linear probing are as follows:

h, h+1, h+2, h+3, etc..

For a given hash value, the indices generated by quadratic probing are as follows:

h, h+1, h+4, h+9, etc..

There will be cluster formed in case of linear but not in case of quadratic.

But how come quadratic is more efficient than linear when both processes(methods) require taking same number of steps for insertion or searching. thanks!

Answer 1

You will stop searching the table when you hit an empty slot as you know that if you hit an empty slot, then the value you are looking for will not be in the hash table. Because of reduced clustering you will be more likely to hit an empty slot and stop searching. In addition, because of reduced clustering, you will be more likely when inserting to find an empty slot, causing in return to be able to more quickly search for that value.