I understand in open addressing hash tables some clustering will always happen just by random chance, even if the input data is perfectly random, leading to some "best possible" lookup performance hit (for an open addressing scheme).

If the hash function is of low quality, and we use linear or quadratic probing, we may observe "primary" and "secondary" clustering effects that make clustering, and therefore lookup performance, worse.

My question is: would using a cryptographic hash function result in linear / quadratic probing having the "best possible" lookup performance, effectively eliminating primary and secondary clustering problems?


Cryptographic hash functions are not better than any hash functions with good distribution and "avalanche effect" (eg xxHash) on this regard.

Do they ensure "best possible" lookup performance? In the way you defined that, yes.

Do they eliminate clustering problems? No, clustering is a probabilistic effect that becomes worse as you insert more entries into your hash table, even if they are perfectly distributed. And this effect is already accounted in formulas of average lookup complexities for linear/quadratic ht algorithm for a given ht load.

  • $\begingroup$ So with a good hash function, quadratic probing would perform no better than linear probing? $\endgroup$
    – max
    Dec 17 '16 at 1:19
  • $\begingroup$ On high hash table loads (approximately 0.8+ slots taken, but depends on the specific implementation) quadratic starts to perform better because it has weaker secondary clustering. On lower loads, linear probing is better because it is simpler and allows faster implementation. $\endgroup$
    – leventov
    Dec 17 '16 at 1:54

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.