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!

Oversee

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.

Wickedness

Answer 2

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.

Paquito

Answer 3

Because of less cluster formation. The values will be more spread out so the average number of probes required will be less in the quadratic case.

Nonanonage

if equal number of data items are inserted with same hash value (value returned by hash function), then wouldnt the number of probes be equal in both the cases. – Oversee

please give more explanation – Oversee

@EJP: how will it be less? You won't probe linearly when looking up an element. You will probe quadratically, the same way you did it when you inserted the key. I understand that it will result in less cluster formation. But the argument you made is not sound. – Defeasible

@NeoMHacker But the same argument advanced by user2902179 is valid? – Nonanonage

If an element happens to be in a cluster of size k, then it requires O(k) iterations to get out of the cluster in the case of linear probing, but only O(sqrt(k)) in the case of quadratic probing – Amadaamadas