Why exactly does quadratic probing lead to a shorter avg. search time than linear probing?

I fully get that linear probing leads to a higher concentration of used slots in the hash table (i.e. higher "clustering" of used consecutive indices). However, it's not immediately trivial (to me at least) why that translates into higher search times in expectation than in quadratic probing, since in both linear and quadratic probing the first value of the probing sequence determines the rest of the sequence.

I suppose this has to do more with the probability of collisions between different probing sequences. Perhaps different auxiliary hash values are less likely to lead to collisions early in the probing sequence in quadratic than in linear hashing, but I haven't seen this result derived or formalized.

  • 2
    $\begingroup$ Have you seen analyses of the average search time for both methods? $\endgroup$ – Yuval Filmus Apr 10 '20 at 8:53
  • 1
    $\begingroup$ I think here it would be very pertinent to consider as well the step-size of the probe. Consider for example, a step size defined as $\max \{i \leq \sqrt{n}: gcd(i,n) = 1$ for linear probing on a table of size $n$. Such a step size would not necessarily lead to obviously being more "clustered" than quadratic probes. $\endgroup$ – MotiNK Apr 11 '20 at 7:11
  • 2
    $\begingroup$ @YuvalFilmus I haven't. If you know of any texts doing it, I'd be highly interested. Thanks. $\endgroup$ – Amelio Vazquez-Reina Apr 11 '20 at 14:48
  • $\begingroup$ @MotiN that's an excellent point. My main reference here is CLRS which discusses these probing designs with a step size of 1, I'd be interested in learning how search times (successful or not) vary as a function of step size. $\endgroup$ – Amelio Vazquez-Reina Apr 11 '20 at 14:54
  • $\begingroup$ If you assume that the hash function is good, then linear probing is always better than quadratic probing because it has better cache locality. $\endgroup$ – Laakeri Apr 13 '20 at 8:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.