Worked solutionOne step at a time
Mod a power of two keeps only the low bits
4,096 is 2¹². Dividing by it shifts the key right by 12 bits, so the remainder is exactly the last 12 bits of the key.
Page addresses have no low bits
A memory page is 4 KB, so every page address is a multiple of 4,096. In binary it ends in twelve zeros, and the hash of every key is 0.
One chain holds everything
All 4,096 keys sit in bucket 0. A successful lookup walks the chain until it hits its key: on average half of it.
Answer: B, a prime number of buckets
key mod p for a prime p shares no factor with 4,096, so consecutive page numbers walk through every bucket. With 4,093 buckets the same keys need 1.001 comparisons per lookup. More generally, mix the bits before you reduce: production hash maps either use a prime size or run the key through a hash function that spreads high bits into low ones.
What the simulation showedSame table, two kinds of keys
The reel builds a real separate-chaining hash table in Python, 4,096 buckets with bucket = key mod 4,096, and inserts 4,096 keys twice.
- Random 64-bit IDs: the longest chain holds 6 keys, 1,510 buckets stay empty, and a lookup takes 1.51 comparisons on average.
- Page addresses, all multiples of 4,096: bucket 0 holds all 4,096 keys and every other bucket is empty. A lookup takes 2,048.5 comparisons, 1,354 times as many.
- Timed in Python, the difference is smaller but still huge: about 108 ns against 27 µs per lookup, roughly 250 times slower, because each comparison in a long list is cheap compared with the fixed cost of a lookup.
Wrong answersWhy each one is tempting
| Pick | What went wrong |
|---|---|
| A · Double the table | Still a power of two: 8,192 buckets put the keys in 2 buckets, 1,024.5 comparisons per lookup. |
| C · A faster CPU | Speeds up each comparison but leaves all 2,048 of them. |
| D · Sort the keys first | Insertion order does not change which bucket a key hashes to. |
Follow-ups an interviewer asks nextTry these before opening them
Why do so many hash maps use power-of-two sizes anyway?
key & (size − 1) is one instruction, while mod by a prime is a slow division. They keep the fast mask and fix the keys instead, by mixing the hash first (Java's HashMap XORs the high 16 bits into the low ones; others use a multiply-shift).
Would a prime size help if the keys were multiples of that prime?
No. Keys that are all multiples of p land in bucket 0 of a p-bucket table. Any fixed size has bad inputs; a well-mixed hash just makes them unlikely to show up by accident.
What does open addressing do with these keys?
It is worse. All keys want slot 0, so linear probing builds one long run, and inserts as well as lookups degrade towards a scan of the table.
How could an attacker exploit this?
If the hash is predictable, they can send keys that all collide and turn every request into a linear scan (hash flooding). That is why many languages seed their string hashes randomly per process.
