Hash Tables Under the Hood

We dissect the hash table from the inside: what actually happens on a lookup, why the load factor is the only knob that matters, and how cache behavior dominates everything else.

Topics covered:

• The three operations: hash, index, probe — each with its own cost model
• Load factor and its exponential effect on open addressing
• Separate chaining vs. linear probing vs. Robin Hood vs. cuckoo hashing
• Cache misses: why a 1ns algorithm becomes 200ns with bad locality
• Size classes and object headers: the hidden overhead of small keys
• Hash function quality: when distribution matters and when it doesn't
• HashDoS: why random seeds protect against adversarial inputs
• Practical tuning: when to resize, when to switch strategy, when to cache the hash code