2 ms·
Cuckoo 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 f
by rurban 11y ago
Cuckoo 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.