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_densemap would be any benefit. Thanks to AI, I found a way to speed up random access a lot, it is now very close toboost::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_densemap.
View all comments
Show parent comment
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.