Hashing and hash tables

A hash table stores key-value pairs in an array of buckets. A hash function maps a key to an integer; the table reduces that integer to a valid bucket index, often by taking the remainder after dividing by the number of buckets. A good function is deterministic (the same key always gives the same number) and spreads keys evenly. Lookup, insert and delete all start by hashing the key.

There are far more possible keys than buckets, so by the pigeonhole principle some keys must share a bucket. Even with few keys, collisions appear sooner than intuition suggests: the birthday problem shows that among only 23 people, two share a birthday with probability a little over one half. So a design must assume collisions and handle them efficiently.

With chaining, each bucket stores a collection (often a linked list), and a lookup compares keys along that chain. With open addressing, every item sits directly in the array; a collision triggers probing, such as stepping to the next slot (linear probing) or following another deterministic sequence. Deleting under open addressing needs care, because simply emptying a slot can break the probe path of other items, so a marker is usually left behind. Open addressing keeps data compact, but its performance degrades sharply as the table fills.

The load factor is the number of stored items divided by the number of buckets. Tables keep it below a chosen limit by growing when it is exceeded. Growing means creating a larger array and re-inserting every item, which is O(n) for that one insert. If the size grows by a constant factor such as doubling, the cost spread over all the inserts is constant per insert, so inserts are amortised O(1). Where a table must never pause, some designs spread the re-hashing over many operations.

The O(1) average assumes a good hash function and a bounded load factor, so each bucket holds only a few items. The worst case is O(n): if every key lands in one bucket, a lookup is a linear scan of everything. (Some designs reduce the chain cost, for example by storing long chains in a balanced structure, but that is an implementation choice and not part of the basic idea.) Hash tables also do not keep keys in sorted order, so "give me the smallest key" or "all keys from A to F" is not what they are for.

For tables, a good function is deterministic, fast, and uniform: each bucket should be about equally likely, and small changes in a key should scatter the results. It must also agree with equality: keys that are equal must give equal hashes.

Non-cryptographic hashes are built for speed and spread, and suit tables and checksums. Cryptographic hashes add security goals, such as being infeasible to reverse or to find two inputs with the same output. Password storage needs more again: a hash that is slow and expensive to compute, designed to resist guessing at scale, plus a salt to defeat precomputed lists. A fast cryptographic hash is still the wrong tool for passwords.

If an attacker knows the hash function and can choose the keys (for example, names in a web request), they can pick many keys that all collide, forcing the table into its O(n) worst case and making each operation slow. Common defences in general terms: use a hash function with a secret random seed chosen at start-up, limit input sizes, or use a table design that bounds the damage of long chains. This is one more reason not to invent your own hash for untrusted input.