A generic hash table [LWN.net]

A generic hash table

Posted Aug 9, 2012 5:02 UTC (Thu) by alonz (subscriber, #815)
Parent article: A generic hash table

Re the pointer-chasing vs. simple table argument—has anyone tried to modify the hash tables to implement Cuckoo hash behavior? From my experience these provide nice gains over a simple hash table, and with zero added complexity.

to post comments

A generic hash table

Posted Aug 9, 2012 23:26 UTC (Thu) by nix (subscriber, #2304) [Link] (2 responses)

Ooo. I'd failed to notice cuckoo hashes: very nice (particularly with more than one item: 50% loading is rather cruddy, but 91% is close enough to 100% as makes no odds. Combine that with using three hash functions and you could get it *very* close to 100% for only a small constant slowdown. Downside: you still do need to resize now and then, which is hateful because it breaks active iterators unless you have crazy complexity to deal with that case alone. Yes, you *can* ban modification of hashes being iterated over, but I consider that a bad-quality implementation.)

A generic hash table

Posted Aug 10, 2012 2:17 UTC (Fri) by nybble41 (subscriber, #55106) [Link] (1 responses)

> Downside: you still do need to resize now and then, which is hateful because it breaks active iterators unless you have crazy complexity to deal with that case alone.

Even without resizing, keys can change location when other items are inserted, so you can't make very many guarantees. Even with a normal hash table it's difficult to say whether you will see the inserted key later on; with a cuckoo hash table you may miss _other_ keys, or even double-iterate them.

If you must modify a hash table with active iterators, perhaps you should collect the list of keys up front, atomically, and iterate over that instead. It may not be quite as efficient as iterating over the hash table directly, in memory or CPU time, but the result will be much more predictable. Or you could make a shallow copy of the hash table to iterate over.

A generic hash table

Posted Aug 10, 2012 16:28 UTC (Fri) by nix (subscriber, #2304) [Link]

Yeah. There are hash designs which don't have this problem -- e.g. any based on trees (you can even arrange that deletion of the key you're currently iterating over will only impose the same overhead on the next iteration as a normal hash lookup). Downside: trees often involve a lot of pointer chasing, and some of them are write-heavy on update and even on read (e.g. splay trees: nice self-optimizing data structure, shame about your cacheline contention).