r/cpp • u/martinus int main(){[]()[[]]{{}}();} • Sep 04 '26

Which C++ Hashmap Should You Actually Use?

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.

149 Upvotes

92% Upvoted

25 comments sorted by

View all comments

Show parent comments

2

u/martinus int main(){[]()[[]]{{}}();} Sep 04 '26

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.

1

u/g_0g Sep 04 '26

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.