- My goto these days (and afaik the state of the art) is boost::unordered_flat_set paired with rapidhash for hashing (since the GNU std::hash functions based on murmurhash are ridiculously slow)
The cacheline performance is pretty hard to beat (SIMD optimised linear scan before hopping), which is where all the wins come in the real world.
But basically any of the faster hash maps from absl, boost or folly are going to wreck the standard library in terms of perf
- google::dense_hash_map is faster than this new implementation according to their benchmark's diagram (google::dense_hash_map has the lowest runtime of all tested methods).
by stevefan1999
1 subcomments
- Ah, hopscotch hash, I tried using it on my CSGO cheat literally 10 years ago, for the object reflection (retrospection) system based on compiler type ID and unique hashing scheme with function signature. I merely used it for hopefully getting a performance on the "dependency injection" side of things, until I realized it is actually a service locator pattern and performance won't improve due to this architecture anyway.
It was 3 years later when I was in college I learned advanced data structures and came into Cuckoo Hashing, then Robinhood hash, and the combination of both Cuckoo and Robinhood hash => Hopscotch hashing
- How does it compare to boost unordered flat map?
Looks like the benchmarks were last updated in 2019.
- The concept is very similar to robin hood. In fact most of the performance charts show that the curves of hopscotch and robin hood are very close. I think I'd prefer robin hood as it's well known.
- The principle of "hopscotch hasing" is described, for example, here: https://en.wikipedia.org/wiki/Hopscotch_hashing
----
An point often missed by people who need to/want to do hashing:
In practice, with your real workloads, you can often make do with actually "giving up" on the hasing of some fraction of the elements, whose buckets, neighborhoods and such are already occupied - and instead put those aside for separate out-of-band handling. hash table implementations such as this one (or std::unordered_map and all the rest), absolutely _must_ succeed in inserting your values - and so must always allow for more collisions, resizing etc.
Hacker News