5

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!

Yogesh Umesh Vaity
  • 41,009
  • 21
  • 145
  • 105
hoder
  • 257
  • 1
  • 3
  • 14

3 Answers3

12

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.

Community
  • 1
  • 1
Yogesh Umesh Vaity
  • 41,009
  • 21
  • 145
  • 105
8

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.

user2902179
  • 104
  • 1
  • 1
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.

user207421
  • 305,947
  • 44
  • 307
  • 483
  • 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. – hoder Jun 30 '13 at 01:36
  • please give more explanation – hoder Jun 30 '13 at 02:01
  • @hoder What part of 'the average number of probes will be less' don't you understand?. – user207421 Feb 02 '14 at 11:51
  • 3
    @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. – Neo M Hacker Sep 22 '14 at 18:52
  • @NeoMHacker But the same argument advanced by user2902179 is valid? – user207421 Jun 20 '15 at 23:02
  • 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 – fdermishin Oct 27 '22 at 10:07