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

The efficiency depends on the kinds of clustering formed by the linear probing and quadratic probing.

Linear probing forms Primary Clustering which once formed, the bigger the cluster gets, the faster it grows. This reduces the performance severely. Robert Lafore has given a nice example: it's like the crowd that gathers when someone faints at the shopping mall. The first arrivals come because they saw the victim fall; later arrivals gather because they wondered what everyone else was looking at. The larger the crowd grows, the more people are attracted to it.

Where as Quadratic probing forms Secondary Clustering. It is an attempt to keep clusters from forming. The idea is to probe more widely separated cells, instead of those adjacent to the primary hash site. Following the analogy, it tries to prevent the first arrivals to avoid forming the crowd. Secondary Clustering is more subtle and not as severe in terms of performance compared to Primary Clustering.

Answer 2

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.