Mastering the unordered_map in C++
summary
Benchmarks show std::unordered_map gives ~8–9x speedups over std::map at millions of keys (10M lookup example: map ~9× slower), but a poor hasher or crafted collisions can degrade it to O(n) — experiments show a bad hash making unordered_map ~100× slower than map and hash‑DOS attacks pinning a core with a few hundred KB of keys. Practical fixes: use reserve to avoid rehash spikes, write a good hash (hash_combine or salted/SipHash), and profile — a removed global lock doubled throughput in a real service. Alternatives: flat_map/Swiss tables trade insert cost for much better cache locality.
AI-written summary · about
chapters (17)
- 0:00Introduction
- 1:24unordered_map as default
- 3:28Map vs unordered_map
- 8:11How unordered_map works
- 13:33Ordering trap pitfall
- 18:11Bad hash function
- 23:43Collision catastrophes
- 24:46Hidden rehashing costs
- 27:17Hash DoS attacks
- 31:35Flat map and alternatives
- 35:06When to use map
- 35:26Open addressing & cache
- 39:25Memory overhead
- 42:20Profiling performance
- 45:58Real-world performance
- 47:23Container choice guide
- 49:54Summary & Q&A
related talks
57mThis Videogame Programmer Used the STL and You Will Never Guess What Happened Next
01h 00mThe Fine Details Behind C++ Containers And Algorithms
51m“Cache Optimized Hash Tables”
51mThe Holy Grail! A Hash Array Mapped Trie for C++
36mThe Holy Grail - A Hash Array Mapped Trie for C++
58mFrozen data structures in C++14
58mRefresher on Containers, Algorithms and Performance
55m “High Performance C++ Concurrent Transactional Data Structures"