How Hash Tables Actually Work

A hash table is one of those data structures that feels like magic the first time you use it. You hand it a key, and it gives you back a value almost instantly, whether it holds ten items or ten million. The trick is surprisingly simple.

The core idea#

Underneath, a hash table is just an array. The problem is that keys are usually strings or objects, not array indices. So we use a hash function to turn any key into an integer, then take that integer modulo the array size to get a slot number.

For example, hashing the string "banana" might produce 8,421,903. If the array has 16 slots, then 8,421,903 mod 16 = 15, so the value for "banana" goes in slot 15. To look it up later, you run the same computation and jump straight to slot 15. No searching required, which is why lookups average O(1).

What makes a good hash function#

A good hash function has a few properties:

• Deterministic: the same key always produces the same hash.

• Uniform: keys spread evenly across slots, so no single slot gets crowded.

• Fast: it runs on every insert and lookup, so it can't be expensive.