Sign in to watch this lesson
Algorithms - Linear Data Structures · 3:55
Hash Maps
We open up std::unordered_map on this Mac's libc++: integers hash to themselves, the bucket is the hash modulo a prime bucket count, colliding keys share a chain of heap nodes, and the table rehashes through a fixed list of primes. Knowing that list, an attacker sends 50,000 multiples of 51,437 and every key lands in one bucket, so inserts turn quadratic (over a second here, against a couple of milliseconds for random keys). A seeded splitmix64 hash scatters the same keys and keeps the clock flat; we finish with composite keys and when not to hash at all.
You will learn
- Describe how std::unordered_map stores keys (bucket array, chains of nodes, load factor 1, rehash to a larger prime) and why lookups are O(1) on average but O(n) in the worst case
- Explain and reproduce an anti-hash attack: with an identity hash and known prime bucket counts, keys that are multiples of the bucket count all share one chain
- Defend with a custom hasher (splitmix64 with a clock seed), reserve, and correct hashing of composite keys
- Choose between a direct array, std::map and a hash map, and avoid the operator[] and iteration-order pitfalls