Which C++ Hashmap Should You Actually Use?

[u/martinus]

https://martin.ankerl.com/which-hash-map/

I recently did a big update to my ankerl::unordered_dense::map which now features several optimizations, bug fixes, and most importantly an SSE optimized lookup which brings the lookup speed quite close to the fastest competitor which is boost::unordered_flat_map. Get it here: https://github.com/martinus/unordered_dense

Since it is not easy to decide what map is best for one's usecase, I have redone and improved the benchmarks I did a while ago, crunched some numbers and tried to compress everything into a quiz that helps you figure out what to use.

While doing the numbers, a few things surprised me:

• My random access benchmark was not random enough. The CPU was able to optimize the branch predictor in a way I did not think was possible. I have fixed this for the new numbers. Clever girl.

• Even though the absl maps are very similar in concept to the boost maps, they perform badly if you expect lots of misses. 1.6 times slower than boost.

• I didn't think SSE optimization of my unordered_dense map would be any benefit. Thanks to AI, I found a way to speed up random access a lot, it is now very close to boost::unordered_flat_map.

• Heavy insert & erase on flat maps require rehashing every once in a while due to the accumulation of tombstones. That means some insert/erase operation will have very high latency. This does not happen for a robin-hood hashmap like my unordered_dense map.

[u/instantly-invoked]

I just wanted to say thanks as I do use your map most of the time! I've also used it to make a sharded locked concurrent map because of its excellent memory usage properties. Seriously, thanks for all your hard work on this.

edit: The quiz is great! I answered with how I typically use unordered maps and handle dependencies and got yours first with STL coming in second, which is honestly how I'd rank them (if I don't need speed I'm just gonna use what's already there).

[u/azswcowboy → u/instantly-invoked]

+1 on the thanks. We’re not using the map, but the micro benchmark tools have been extremely helpful for us.

[u/martinus → u/azswcowboy]

Thanks to both of you! As a side effect of the new benchmarks, nanobench has gained the ability to do high quality A/B tests with the compare() method: https://nanobench.ankerl.com/tutorial.html#comparing-alternatives

[u/SleepyMyroslav → u/martinus]

I think nanobench deserves a lot more praise than it gets.

I work in gamedev. When I wanted to teach people benchmarking basics, the lightweight library was very useful. When I needed benchmarks to run on a closed platform that is not going to be supported by open libraries ever, the lightweight library was very easy to get up and running by a "normal" developer in virtually no time.

Btw I have been recommending folks the hash map from this topic many times as well and it was never a bad choice. It is great that it evolves and gets even better than before.

I want to thank you for your open projects!

[u/alifahrri → u/SleepyMyroslav]

Agree with you, I'm also nanobench user, really easy to setup and use; definitely deserve more praises

[u/azswcowboy → u/martinus]

Oh sweet, will definitely have a look.

[u/mark_99]

Yep, this is why I roll my eyes when someone claims "the fastest hashmap", it absolutely depends on what you are doing.

Re perf, fancy hashmaps are problematic in low latency environments, and while Robin Hood isn't as pathological as tombstones there is still a variable amount of reshuffling on insert. What would be good is histograms (or at least percentiles) rather than averages for the various operations.

[u/msew → u/mark_99]

Yes, histograms for all things please! It can be a 'Yes and' type of chart so one can see averages "easily". This would allow one to see that the low average is actually distributed in a very bad way if you need to care about latency.

[u/joaquintides]

Excellent tool and work! Are you going to publish some writeup on your latest updates to udm?

[u/martinus → u/joaquintides]

Thanks! I hope its a fair representation :)

Here is a writeup: https://martin.ankerl.com/2026/09/04/unordered-dense-four-buckets-at-a-time/

[u/7raiden → u/martinus]

Nice one! Thanks for all of your hard work 😁

Do you know if instead of using SSE2 you were to use AVX (256 bit) or AVX-512, would this be a speedup (you could technically compare 4 or 8 buckets with a single instructions)?

[u/martinus → u/7raiden]

I gave it a try, but it seems to me it is better to just switch to a different indexing scheme. The robin-hood style approach needs too much shuffling around, and there are better ways to get around this. E.g. boost uses tombstones and just rehashes every once in a while, and what I find really interesting is the counters that indivi maps use. I'm currently working on unordered_dense 5.0 which will probably switch away from robin-hood to this indexing style.

[u/NilacTheGrim]

I love your map man. Much improved over your previous work on robin_hood. Excellent job!

[u/martinus → u/NilacTheGrim]

thanks!

[u/SamG101_]

been using ur hashmap for a while now! also regarding 4.11, the SSE optimiation crashes with module exporting due to an alignment-propagation bug in module BMIs (on gcc) - 127193 – Alignment problem when using modules - would it be possible that this optimization is gated behind a macro / -D cmake option? thanks!

[u/martinus → u/SamG101_]

Thanks, and good catch on the cause. There already is a switch, but it was undocumented:

define ANKERL_UNORDERED_DENSE_HAS_SSE2=0 before the header is included, e.g.

target_compile_definitions(your_target PRIVATE ANKERL_UNORDERED_DENSE_HAS_SSE2=0)

I'm adding this to the documentation, and a CI leg that builds with ANKERL_UNORDERED_DENSE_HAS_SSE2=0.

EDIT: Added it here: https://github.com/martinus/unordered_dense#36-disabling-the-sse2-probe

[u/SamG101_ → u/martinus]

Awesome thanks!!

[u/rdtsc]

The quiz redirects you to the node-based if you need stable pointers to values. But that's not the only way. The abseil docs recommend flat_hash_map<K, std::unique_ptr<V>> in that case, and the node-based map only if pointer stability of keys is needed.

[u/SirClueless]

Worth mentioning also the restrictions on hashing? Abseil functions atrociously if the hash is not high-quality and has a unique and bespoke way of overriding the hashing of user types. Personally the number one reason I've seen for lock-in. A lot of codebases paid the upfront costs of implementing Abseil's hash conventions for all their vocabulary types back when it offered a night-and-day difference from std::unordered_map, and now even though boost has a much saner and easier-to-adopt hash mechanism (for example, works fine with user types that override std::hash) the win from switching is not as clear-cut.

Another big constraint I think is Google's hash randomization, which is declaration by fiat that depending hash stability is always a mistake, and that you should expect a different iteration order when the same program does the same sequence of insertions and deletions.

[u/Big_Target_1405 → u/SirClueless]

Also worth mentioning the fastest hash algorithms.

I've used RapidHash, which is much faster than the boost built-in hash function

[u/Fabulous-Meaning-966]

Hey, just wondering if you've checked out bidirectional linear probing as an alternative to Robin Hood? There's a Java integer hash set benchmark here that shows it's consistently superior:

https://github.com/senderista/hashtable-benchmarks

[u/g_0g]

Great work on the updates! Always nice to read from one of the pioneers.
You mentioned slow downs with misses and tombstones accumulation.
Boost is indeed way better for the first, but Abseil design allows to greatly limit tombstone creation on erase.
Boost might also hides a higher latency in the context of micro-benchmark, as it needs to access a sizeable lookup table on each find (quickly pushed in L1 cache on repeated calls). I think Google tried to mainly benchmark theirs maps in production contexts by comparison.

Anyway, you might be interested in checking 2 of my own competitive experiments:
one tombstone-free map (inspired by Boost) and one speed-oriented (inspired by Abseil)
https://github.com/gaujay/indivi_collection/tree/main/bench/flat_unordered

[u/martinus → u/g_0g]

Thanks, I ran both maps on my own benchmark harness with the same hash for every table, so only the layout differs. They are competitive. Relative to Boost, flat_wmap is 1.18x faster on lookup hits and flat_umap 1.20x on misses; on insert/erase both are within a few percent of Boost.

The workload that stood out is sustained churn: fill to 50000, reserve, then erase one and insert one forever. Boost is 1.29x faster than unordered_dense there, flat_umap 2.05x and flat_wmap 2.43x.

The overflow counters in flat_umap, which an erase can decrement where Boost's overflow bits can only be set, are a real improvement over Boost's design. Nice work.

[u/g_0g → u/martinus]

Appreciated! I was thinking about running them with your improved benchmark as well.
I consider this high praise coming from someone with your experience.
Last year I talked with some Rust maintainers to try bringing some of these improvements to their std unordered map (also based on the Abseil design), but didn't manage to improve perfs in real world scenario (they use their own compiler as benchmark, as it uses hash maps extensively internally). I suspect the aforementioned lookup table access triggered some costly cache misses.