3 ms·
Also an interesting variation on hash tables is the Cuckoo Hash (https://en.wikipedia.org/wiki/Cuckoo_hashing https://en.wikipedia.org/wiki/Cuckoo_hashing). How
by herge 11y ago
Also an interesting variation on hash tables is the Cuckoo Hash (https://en.wikipedia.org/wiki/Cuckoo_hashing https://en.wikipedia.org/wiki/Cuckoo_hashing). However, I don't think it makes a lot of effort in keeping marching keys near to each other, so I suspect Leapfrog probing might cause less cache misses.
- rurban 11y agoCuckoo needs double space, and even if you add those two tables one after the other, it begs for cache misses with larger arrays, besides needing a much lower fill rate than leapfrog, which only needs 2 bytes extra. leapfrog looks really promising
- todd8 11y agoI'm not sure how Cuckoo hashing would compare with regard to cache misses, but it doesn't take double space. Each element makes can use a second hash function and in space efficient implementations (with a third hash function, etc.) the space utilization is over 90%. See the conclusion of "Space efficient hash tables with worst case constant access time" (http://www.itu.dk/people/pagh/papers/d-cuckoo.pdf); http://www.itu.dk/people/pagh/papers/d-cuckoo.pdf); it starts: > From a practical point of view, d-ary Cuckoo Hashing seems a very advantageous approach to space efficient hash tables with worst case constant access time. Both worst case access time and average insertion time are very good.