Hash Tables

You run a login service with ten million accounts. A request arrives with the username "maya_k". A list would make you scan the accounts one by one: ten million comparisons in the worst case, for every login. A sorted list with binary search brings that down to about twenty-four comparisons, but now every new signup must be inserted in the middle and everything after it shifted.

There is a better idea, and it is the one behind Python dictionaries, JavaScript objects and maps, Java's HashMap and the lookup tables inside databases and compilers. Instead of searching for the key, compute where it lives. Turn the key into a number, use the number as a position in an array, and go straight there. Looking up, inserting and deleting take, on average, a constant number of steps, regardless of how many items are stored.

A hash function maps a key of any size to an integer. For a hash table it must have three properties. It must be deterministic: the same key always gives the same number, or you could never find your data again. It must be fast, since it runs on every operation. And it should spread keys evenly, so that keys do not crowd into the same few buckets.

The integer is usually huge, so the table reduces it to a valid slot with the remainder operator: index = hash(key) % number_of_buckets. Below is a deliberately simple string hash. It walks through the characters, mixing each into a running total. Real libraries use stronger functions (Python randomises string hashes per process, as a defence against attackers who craft colliding keys), but the shape of the idea is identical.

With 8 buckets and 9 keys, two keys must share a bucket, by the pigeonhole principle. Even with far more buckets than keys, the birthday paradox says collisions arrive sooner than intuition suggests: in a group of just 23 people, two share a birthday with probability above one half. So every hash table must have a plan for collisions. There are two classic plans.

Separate chaining keeps a small list in each bucket. Colliding keys are appended to the same list, and a lookup hashes to the bucket and scans its short list. Open addressing stores everything in the array itself: if the preferred slot is taken, probe the next slot (linear probing), or another computed one, until a free slot appears. Python's dictionary uses open addressing with a smarter probe sequence.

Both work well as long as the lists or probe sequences stay short, and that depends on one number.

The number that matters is the load factor: items stored divided by buckets. With a low load factor, chains are short and probes are brief, so operations are fast. As it climbs, chains lengthen and performance slides toward the O(n) of a list.

So a hash table watches its own load. When the load factor crosses a threshold (around 0.7 to 1.0 is typical, depending on the design), it allocates a larger array, usually double, and rehashes every key into the new array, since the bucket index depends on the array size. A resize is expensive, O(n), but it happens rarely: doubling means the total cost of all resizes across n inserts is O(n), so each insert is amortised O(1).

Build one yourself and the whole mechanism stops being magic. The class below uses chaining and doubles when the load factor exceeds 0.75. It also counts probes, the number of key comparisons per operation, so you can measure the effect of load instead of taking it on faith.

You rarely build one, because dict and set are hash tables. The rule for keys follows directly from the mechanism. A key must be hashable: its hash must never change while it is in the table, otherwise the stored position and the computed position diverge and the entry becomes unfindable. Immutable values (numbers, strings, tuples of hashables) qualify. A list or a dict does not, because its contents can change, so Python refuses it with a TypeError.

Two more consequences are worth knowing. Iteration order is not sorted order: a dict remembers insertion order (a language guarantee since Python 3.7) but that is a courtesy, not a sorted structure. And keys are compared with equality, so 1 and 1.0 and True are the same key.

Counting. Walk the data once and add one to a counter per key. Word frequencies, character counts and votes all become a single linear pass.

Grouping. Use a canonical form as the key. All words that are anagrams of each other share the same sorted letters, so sorting the letters gives you a key under which to group them.

Complement lookup. To find two numbers that sum to a target, store each number as you pass it; for each new number, ask whether target minus that number is already in the table. A quadratic search over pairs becomes one linear pass. This is the idea behind the famous first interview problem, and it generalises: whenever a problem asks "have I already seen something related to this?", a hash table answers in constant time.

The O(1) claim is an average. If every key lands in one bucket, a hash table degrades into a single linked list and each operation costs O(n). Good hash functions and resizing make that vanishingly unlikely for ordinary data, and randomised hashing makes it hard for an attacker to force. Resizing also means a single insert occasionally costs O(n), which matters in real-time systems with strict latency limits.

What a hash table cannot do is anything involving order. Finding the smallest key, the next key above a value or all keys in a range requires scanning every bucket. For those, use a balanced search tree or a sorted array. Memory is another trade: hash tables keep spare empty buckets and therefore use more space than a tightly packed array of the same data.

Think about the mechanism rather than the vocabulary.