Hash Tables

Hashing, collisions, load factor, and expected-O(1) lookup.

The idea

A hash table is a dictionary: it stores a set of keys, usually each with an attached value, and supports insert, delete, and search in expected $O(1)$ time per operation — faster than any structure that locates a key by comparing it against the keys already stored.

The idea is to compute where a key belongs rather than search for it. Keep an array of $m$ slots and a hash function $h$ that maps every possible key $k$ to a slot index $h(k) \in \{0, 1, \ldots, m - 1\}$.

Since the universe of possible keys is far larger than $m$, the function $h$ must send some distinct keys to the same slot — a collision — so every hash table carries a collision-resolution scheme. Chaining keeps a linked list of all the keys hashed to a slot. Open addressing stores keys in the array itself and, on a collision, probes a sequence of alternative slots.

Algorithm.

Algorithm: Chaining Input: an array of m slots, each holding a linked list of the keys hashed there; a hash function h; a key k Output: for a search, the entry holding k, or NULL if absent 1. to insert k: add it to the front of the list in slot h(k) // a collision just grows the list by one 2. to search for k: walk the list in slot h(k), comparing each stored key with k 3. if a comparison matches, return that entry if the list ends without a match, return NULL

The cost depends on how full the table is. With $n$ keys stored, the load factor $\alpha = n/m$ is the average number of keys per slot. If $h$ scatters keys evenly across the slots, a chained search inspects about $\alpha$ of them, so an operation costs $\Theta(1 + \alpha)$ — constant, provided we grow the table to keep $\alpha$ bounded.

Ways to work on it

• Walkthrough. Hash functions, chaining, and the load factor.
• Practice. Apply the division-method hash function.
• Hardest. Trace linear probing and reason about the load factor.

Not sure where to start? Take the ten-question placement test.