Module 10 · unordered_set and unordered_map: Hashing, Collisions and the Anti-Hash Test
Under the Hood: Chained Buckets, Prime Counts and the Anti-Hash Test
ProReading
Kenji's contest solution kept its numbers in an unordered_set<long long>, and 85,000 random numbers went in within 10 ms. After the contest, a rival added one test: 85,000 numbers, every one a multiple of 85,229. On that test the same inserts took 15.5 to 19.2 seconds on Compiler Explorer. Same container, same count, over a thousand times slower. Maria asks the question this lesson answers: "But why would the multiples of one number break a hash table?"
Checking what this lesson needs for you…
What is inside Under the Hood: Chained Buckets, Prime Counts and the Anti-Hash Test
- One list through every node, and buckets that point into it
- A node: one link, the key, and sometimes the hash code
- Growing: a prime count at least twice as large
- A rehash relinks every node and copies none
- The performance lab: unordered_map against map
- The anti-hash test: keys aimed at one bucket
- Two defences: a seed nobody knows, or a tree
- Why a fixed hash, however clever, is no defence