attractivechaos / klib

A standalone and lightweight C library
http://attractivechaos.github.io/klib/
MIT License
4.18k stars 556 forks source link

klib overview states khash is based on double hashing, but it looks like this is no longer true #110

Closed bkerin closed 5 years ago

bkerin commented 5 years ago

It looks like it isn't true anymore because khash.h contains this comment:

2013-05-02 (0.2.8):

    * Use quadratic probing. When the capacity is power of 2, stepping function
      i*(i+1)/2 guarantees to traverse each bucket. It is better than double
      hashing on cache performance and is more robust than linear probing.

      In theory, double hashing should be more robust than quadratic probing.
      However, my implementation is probably not for large hash tables, because
      the second hash function is closely tied to the first hash function,
      which reduce the effectiveness of double hashing.

    Reference: http://research.cs.vt.edu/AVresearch/hashing/quadratic.php