9 ms·
Robin Hood Hashing should be the default hash table implementation (2013)
- doomrobo 10y agoA variant of this is the default for Rust's HashMap. http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/ http://codecapsule.com/2013/11/17/robin-hood-hashing-backwar...
- _nalply 10y agoSee: http://cglab.ca/~abeinges/blah/robinhood-part-1/ http://cglab.ca/~abeinges/blah/robinhood-part-1/ about the implementation in Rust.
- stcredzero 10y agoNeat idea! It's using the same generalized strategy as a Splay Tree. Not exactly the same of course, but there's an analogy here. The algorithm achieves a fast amortized (and average) time by continually shortening the "search paths." (In the case of the RH Hash, it's not actually a path, but a sequence of slots.)
- dlbucci 10y agoFound the CMU grad! I think this is very different from a splay tree, though. Open-address tables take advantage of the cache by removing linked lists from the data structure, which is why I think they tend to have good real-world performance. Splay trees, on the other hand, can only really be implemented using pointers and a linked structure (splaying a tree that's been implemented with an array sounds absolutely miserable). They don't have good cache usage, which is why they generally perform poorly outside of big-O notation.
- stcredzero 10y agoFound the CMU grad! Nope! Didn't go there. I think this is very different from a splay tree, though. Open-address tables take advantage of the cache Well, duh! That's why I said it's analogous. Of course something built on an array is likely going to have better cache behavior! My point is that you're using amortized work to shorten the average amount of work it takes to retrieve your data. My point was to talk about the generalized meta-strategy. Lose a point for poor reading comprehension because you so-badly-wanted-to-correct-someone.
- AustinScript 10y agoDial it back man.
- jabl 10y agoAlso, splay trees turn every read into several memory writes. Maybe not a good idea if the data structure is read by multiple threads (cacheline ownership bouncing back and forth all the time, rather than each core having it's own cached copy).
- stcredzero 10y agoBinary Trees are a bad idea from the POV of cache use, and from your analysis, Splay Trees are much worse. However, this has nothing to do with the generalized meta-strategy of continually reducing the amount of work it takes to fetch items. It has to do with why Binary Trees are bad from the POV of cache use.
- flatline 10y agoInteresting observation - I haven't thought about splay trees for a while, but I had a similar initial thought, that this was effectively an MRU optimization. On reading further though, that's not the point of the RH hash, which is reducing variance in the probe length. The splay operation comes with a lot more overhead than a swap, and the MRU-specific benefits with RH hashing are going to be averaged out over time.
- spike021 10y agoMy data structures and algorithms course was unfortunately taught by a pretty awful professor. But out of the entire course, he did have us implement a hash table using Robin Hood Hashing for a homework assignment once. It's the one part of the course that I enjoyed outside of my issues with it, and it's the one that, a couple years down the road, I still like to think and talk to coworkers about because it's an interesting topic.
- jabl 10y agoAnother slightly fancier than the usual textbook approaches is cuckoo hashing. Has anyone done a comparison with cuckoo vs. robinhood?
- doomrobo 10y agoThey're pretty similar in philosophy. I'd guess that Robin Hood would perform better on average just by virtue of linear probing. If you get a collision in a Cukoo hash, you're pretty much guaranteed a cache miss. With a Robin Hood hash, it's pretty likely that the element you're looking for is in the same cacheline as the collision.
- erichocean 10y ago> If you get a collision in a Cukoo hash, you're pretty much guaranteed a cache miss. Don't people usually use buckets with cuckoo hashing, so that each location houses 2 or more values (one right after the other)? I guess I'm not seeing how that's fundamentally different from linear probing...
- doomrobo 10y agoIt's the same problem though. As the other comment said, you have 2 uncorrelated memory locations. If you check the first one and your element isn't there, then checking the second one will probably incur a cache miss. The difference between linear probing and buckets is a big one: buckets are linked lists. That means that hitting a bucket doesn't pull everything else inside the bucket into the CPU cache. So iterating through the bucket may incur a cache miss for every element. On the other hand, linear probing in open addressing does away with buckets and instead searches the neighbors of the collision. Because they're nearby in memory, it's a lot quicker to search.
- pkhuong 10y agoYou can have preallocated buckets in an array. What's the difference you ask? When you have more elements per buckets, the variance becomes smaller as a fraction of the bucket's size. Imagine you had a hash table with buckets of 1000 elements. You'd probably feel comfortable with a 90% load even without any strategy to handle bucket overflow except growing and rehashing. Obviously, the downside is that we have to do more work to search in buckets.
- Bognar 10y agoThe post mentions using tombstones for deletion, but I was under the impression that the variance benefits of Robin Hood hashing weren't realized unless you performed a backwards shift on the remaining elements instead of using a tombstone. See these posts for more information: http://codecapsule.com/2013/11/11/robin-hood-hashing/ http://codecapsule.com/2013/11/11/robin-hood-hashing/ http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/ http://codecapsule.com/2013/11/17/robin-hood-hashing-backwar... Unfortunately there's not great information around the overall CPU performance impact of using a shift vs. tombstone.
- mcguire 10y agoI don't know the actual performance impact, but using backwards shifts and removing tombstones leaves the code much simpler. https://github.com/tmmcguire/rust-toys/blob/master/pony/anagrams/robinhood.pony https://github.com/tmmcguire/rust-toys/blob/master/pony/anag...
- scythe 10y agoI think you can obtain the same variance benefits if you delay the backwards shift until you insert into a tombstone bucket. In that case you backwards shift until the "new" element has a higher DIB than all of the "promoted" ones, or an empty bucket is reached, or a DIB zero bucket is reached. Of course you're not really saving much actual computation this way (you do save a little, since you avoid situations where an element is back-shifted and immediately front-shifted), just moving it around. (I'm not sure why fast deletions are necessary in the first place?)
- jzebedee 10y agoI was comparing hash performance for a hobby project when I first discovered Robin Hood hashing. I ended up making a demo implementation of the backwards-shifting variant in C# [1] and found that it wasn't the best performer for the load case I needed. I still think it's an incredibly clever algorithm and I would love to find a project where I could use it again. [1] https://github.com/jzebedee/rhbackshiftdict https://github.com/jzebedee/rhbackshiftdict
- doomrobo 10y agoOut of curiosity what did your load look like? What was the best performer?
- Bartweiss 10y agoI'm curious - what was your deletion strategy? The CodingCapsule links in the comments here suggest that tombstone deletion actually breaks the low-variance promise from the original paper, and only back shift deletion produces the theoretical performance.
- diziet 10y agoThere is also a great resource with more up do date stuff on hashing and benchmarks right here: https://github.com/rurban/smhasher/ https://github.com/rurban/smhasher/
- erichocean 10y agoThat compares hash functions, not hash tables (aka dictionaries, maps, key-value stores, etc.). Hash functions convert sparse keys to dense keys (with potential for collisions). Hash tables look up and store values by key using their hash (usually in-memory only, although this is not a requirement per se).
- Gankro 10y agoIt's also a terrible comparison of hash functions for the purpose of hashmaps, because it tries to reduce the performance characteristics to a single number. The performance characteristics of a hash function varies over the size of the input. FarmHash is super complicated because it's basically a huge stable of hash functions that are selected based on input size. For instance, looking at these numbers you might conclude XXHash is strictly faster than FNV, but in reality FNV performs much better for the more common case of small inputs (breaking even around 16-32 bytes).
- diziet 10y agoI disagree, as this simple test suite is not meant to be a definitive guide on which hash function is the best. I would venture to say that your criticism is similar to saying that the Hutter Prize[1] is a terrible idea for someone who will need to do compression on a dataset as they will choose to use PAQ and it will run really slowly. Yes, there are trade-offs and optimizations for different use cases, but to say that it's a terrible comparison is unfair. 1) http://prize.hutter1.net/ http://prize.hutter1.net/
- diziet 10y agoI understand there are difference between hash functions and hash tables* (and between implementations of hash maps, dictionaries, etc). I do not understand the need to down-vote the comment that I think is relevant to the discussion of hash functions as implementing a hash table requires choosing a hash function along with choosing strategies for collision avoidance, collision handling, resizing, chaining, etc.
- raymondh 10y agoHow is this different from "Brent's variation of Knuth's Algorithm D"? * https://books.google.com/books?id=e3wLBAAAQBAJ&pg=PA532#v=onepage&q&f=false https://books.google.com/books?id=e3wLBAAAQBAJ&pg=PA532#v=on... * http://maths-people.anu.edu.au/~brent/pd/rpb013.pdf http://maths-people.anu.edu.au/~brent/pd/rpb013.pdf
- jaswilder 10y agoThe author's thesis has some comparisons to Brent's method. See P51-53 https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf for conclusions.
- kmill 10y agoIf I remember correctly, Brent's variation considers both the chain of the element being inserted, and the chains for the elements being swapped, and then does a dynamic program to decide exactly what to swap. It sacrifices some insertion efficiency for fewer expected probes for lookups.
- qwertyuiop924 10y agoRHH is neat, and useful, but I don't know about making it your go-to hash implementation: If you're writing the code yourself, and don't have to worry about the cost of the occaisional cache miss, the simplicity of List or B-Tree chaining is a pretty big win. HoweverIf you're going to implement a general-purpose hashtable, or are in an environment where you really cannot afford that cache miss, RHH or similar seems like the right way to go.
- praxulus 10y ago> Just modify the standard search algorithm to ignore empty slots (rather than terminate the search) and keep going until you’ve probed longer than the known maximum probe length for the whole table. Why does it need to keep searching after it hits an empty slot? Can't it terminate the search if it hits the max probe length or an empty slot? Edit: Ah, that's part of the "even better version" shown later.
- jlebar 10y agoThe overhead of storing hashed values inside the hashtable is not to be neglected. If my key type has a fast hash function, maybe I don't need to store the hashed value. But if e.g. I have a hashset of char*s, I definitely don't want to rehash. Storing those hashes alongside the pointers effectively halves my load factor, from a cache-friendliness point of view. There goes the whole load-factor advantage. Maybe Robin Hood hashing still wins by letting me use linear probing, which is more cache-friendly than (say) the quadratic probing you'd normally have to do. But this is getting sketchier... In addition, it's not clear to me that the cost of the swaps is entirely negligible in the common case when the elements of the hashtable are more than one or two words wide. Certainly not if you have to run a constructor to do the move instead of just memcpy'ing the elements. I like the idea, but it is not (to me) obviously a knockout win.
- pkhuong 10y agoIf you don't need to store the hash value because your hash function is simple, you don't… Nothing about the (linear) robin hood collision handling strategy forces an explicit representation of the hash value. However, it is true that C++ makes some data structures slower than they should be.
- nikic 10y agoOne consideration to take into account when choosing your hash table implementation is how much it is susceptible to the quality of the used hash function. Hash tables using chaining are pretty robust against low-quality hash functions. Using the same with a Robin Hood table will land you in a catastrophic case very quickly. This is the issue I ran into when investigating use of RH hashing in PHP -- the average case had good performance, but there were pathological cases exhibiting extremely high clustering in a mostly empty table. The reason was the low-quality hash (for integer keys the identity function).
- xedarius 10y agoHe also wrote a follow up article addressing performance issues surrounding probe size increasing when erasing elements. http://www.sebastiansylvan.com/post/more-on-robin-hood-hashing-2/ http://www.sebastiansylvan.com/post/more-on-robin-hood-hashi...