4
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ Have you seen analyses of the average search time for both methods? $\endgroup$
    – Yuval Filmus
    Apr 10, 2020 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, 2020 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, 2020 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, 2020 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, 2020 at 8:32

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.