I'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 a

I'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.