Hash tables & maps

You keep the price of every fruit a shop sells and want the price of "plum". In a list of pairs, that means checking pairs one by one: O(n). An array would answer in one step, but only for a number index, and "plum" isn't a number.

A hash table makes it one. A hash function turns the key into a number, and that number, taken mod the array's length, picks a cell. The cells are called buckets. To store a pair you put it in its key's bucket; to find a key you compute the same bucket and look only there.

In the pseudocode on these pages, {} makes an empty map, m[k] ← v stores a value, m[k] reads it and k in m checks for a key. Underneath, that is a hash table.

A hash function for a table has three jobs:

• always give the same answer for the same key, or stored pairs can't be found again;
• give equal keys equal answers, even when they are different objects holding the same text;
• spread different keys evenly across the buckets, so no bucket fills up while others stay empty.

A common recipe for strings walks the characters, multiplying the running number by a small prime and adding each character's code. The tables on this page use h ← (h × 31 + code(c)) mod size. For "kiwi" and 5 buckets:

So "kiwi" goes in bucket 1. Real libraries use stronger functions than this, but the job is the same: the work depends on the key's length, not on how many items the table holds.

There are far more possible keys than buckets, so two different keys will sometimes land in the same bucket. That is a collision, and it happens sooner than intuition says: in a room of just 23 people, the chance that two share a birthday is already over 50%, with 365 possible "buckets".

The most common answer is chaining: each bucket holds a short list of the pairs that landed there. Putting a key means finding its bucket, checking the chain for the key (to update it) and appending a new pair if it isn't there. Watch "plum" land in kiwi's bucket:

The other family is open addressing: every bucket holds at most one pair, and a key whose bucket is taken tries other buckets in a fixed order until it finds a free one. It avoids the chains' extra objects and keeps everything in one array. Java's HashMap uses chaining; CPython's dict uses open addressing.

Finding a key repeats the put's first half: hash the key, go to its bucket, and compare it with the keys in that chain. Keys in other buckets are never looked at.

The cost is the hash plus the length of one chain. With keys spread evenly and chains kept short, that is a constant: O(1) on average, for finding, inserting and deleting alike.

The average chain length is the number of pairs divided by the number of buckets, the load factor. As pairs are added, it rises and lookups slow down. So a hash table watches it: Java's HashMap, for one, defaults to a limit of 0.75, and past it rebuilds itself with about twice as many buckets.

Growing isn't a plain copy. A key's bucket is its hash mod the number of buckets, so when that number changes, most keys belong in a different bucket. Every pair has to be hashed again and moved: a rehash.

A rehash is O(n), but like a dynamic array's copy, doubling makes it rare enough that inserts stay O(1) amortized. See Space & amortized analysis for why.

A hash set is the same table storing keys without values. It answers "have I seen this before?" in O(1), which is the first trick in a huge number of interview problems.

Three things to keep in mind:

• No sorted order. Buckets follow the hash, not the keys. Python's dict and JavaScript's Map do promise to iterate in insertion order, but Java's HashMap makes no promise about order at all.
• Don't change a key while it's in the table. Its hash would change, and the pair would sit in the wrong bucket, impossible to find.
• The worst case is O(n). If many keys land in one bucket, by bad luck or by an attacker choosing them on purpose, every lookup scans one long chain. That is why languages such as Python randomize their string hashes each time a program starts.