P-4.4 Hash Tables

What this is and why it exists

The hash table is the workhorse of practical programming. The dictionary or map in whichever language you prefer is almost certainly one.

Its guarantee is average-case, not worst-case, and that distinction is not academic. A badly distributed hash function degrades the whole structure to a list with extra steps.

There is also one trap that catches everyone once: using something you will later modify as a key.

The vocabulary

• Key — the value you look things up by.
• Hash function — turns a key into a number.
• Position — that number reduced into the table's range.
• Collision — two keys landing in the same position.
• Chaining — each position holds a small list of entries.
• Open addressing — on a collision, probe onward for the next free slot.
• Load factor — how full the table is.
• Rehash — recompute every position after growing the table.

The mental model

Hashing computes a number from the key and reduces it into the table's range. A lookup then goes straight to one place instead of searching. That is the whole trick, and everything else is about the ways it can go wrong.

Collisions are not a flaw; they are arithmetic. There are more possible keys than positions, so two keys will land together. Two standard answers exist. Chaining puts a small list at each position. Open addressing probes onward until it finds a free slot. Both work, and they fail differently under load, which is why implementations differ.

As the table fills, collisions rise and performance falls. So implementations grow and rehash past a threshold called the load factor. This is the doubling argument from growable arrays, arriving a second time in a different costume. Noticing that it is the same argument is worth more than either instance alone.

Now the guarantee. Lookups are constant on average and linear in the worst case. If every key hashed to the same position, the structure would be a list. That is not only theoretical: input chosen deliberately can force it, which is why some systems randomise their hash function at startup. The randomisation is not for correctness. It is so that nobody can predict the collisions.

Finally the trap. The position was computed from the key at the moment of insertion. Change the key afterwards and the entry stays where it was put, which is no longer where a lookup will go looking. The entry is still there, and it is unreachable. Languages that require immutable keys are preventing exactly this, and it is worth recognising that as a design choice rather than a restriction.

What you should now be able to explain or do

Explain how a hash function turns a key into a position, and what good distribution buys. Describe chaining and open addressing and say how they differ under load. Say what the load factor is and connect the resize to the growable-array argument. State the average and worst-case costs, and say why some systems randomise their hash function. Explain why a mutable key loses its entry.

Check yourself