3 ms·
I'd be interested to see a comparison of cuckoo hashing v.s. robin hood on these benchmarks. I chose to use Cuckoo in my implementation of a high performance f
by jlrubin 10y ago
I'd be interested to see a comparison of cuckoo hashing v.s. robin hood on these benchmarks.
I chose to use Cuckoo in my implementation of a high performance fixed-size cache for bitcoin signature validation (see https://github.com/bitcoin/bitcoin/blob/master/src/cuckoocache.h https://github.com/bitcoin/bitcoin/blob/master/src/cuckoocac...). Cuckoo is great in my experience if you want to use memory fully and can afford > 3 high quality hashes per entry. I also like cuckoo because you're able to use it pretty well for lockfree/high concurrency use cases (can make concurrent erases and reads lock free for example), which made it a good fit for the bitcoin workload. It seems that this hashtable's approach isn't quite amenable to concurrent operations, but perhaps there are some tricks that could work for that.
- exDM69 10y agoJust to clear up a common point of confusion: the "Robin Hood" scheme that is commonly used these days is not a multiple hashing solution like the original research paper from the 1980s (and Cuckoo hash table). What's used these days should be called "Robin Hood linear probing" or something else. It's just a variant of linear probing where an entry occupying a "better" slot than the one being inserted gets pushed back. It might still be an interesting comparison but I'm under the impression that Robin Hood is a very good solution for a general purpose hash table.
- rurban 10y agoCuckoo uses 2x memory, with constant cache trashing. It can be made fast with concurrent maps, but there Cliff Click's or Preshing's Leapfrog approaches are better.
- jlrubin 10y agoWhat makes you say that cuckoo uses 2x memory?
- rurban 10y agoThe most commonly used variant uses 2 arrays, indexed by the two hash functions. Or one array twice the size. While the current trend is to reduce the size of this array by using size-compressed indirect indices, e.g. the new ruby/python hashes.