Hashing and Dictionaries

Finding Things Instantly

The dictionary (map) ADT stores key–value pairs and supports fast lookup, insertion, and deletion by key. The structure that makes this fast is the hash table.

A hash table keeps an array of buckets. A hash function takes a key and computes an integer, which (reduced modulo the array size) gives the index of the bucket where that key's value is stored. To look up a key, you hash it, jump to that bucket, and find the value — no scanning. When the hash function spreads keys evenly, lookup, insertion, and deletion are all $O(1)$ on average.

The complication is collisions: two different keys can hash to the same bucket. Every real hash table has a collision-resolution strategy. Chaining stores a small list at each bucket, holding all keys that landed there. Open addressing instead probes to a different bucket by a fixed rule when the first is taken. Either way, collisions must be handled, or values would overwrite each other.

Performance depends on the load factor (elements ÷ buckets). As the table fills, collisions grow and operations slow, so hash tables resize (allocate a larger array and rehash everything) when the load factor gets too high, keeping average operations $O(1)$. The worst case — many keys colliding into one bucket — is $O(n)$, but a good hash function makes that vanishingly unlikely.

Common pitfall: believing hash-table lookups are guaranteed $O(1)$. The $O(1)$ is an average under a good hash function and reasonable load factor. Bad hashing (or an adversary) can pile many keys into one bucket, degrading operations toward $O(n)$. Constant time is the expected case, not a guarantee.

A key flowing through a hash-function box to a number, then modulo the bucket count into one of several bucket slots; a second key colliding into the same slot forms an accent chain beneath it — hashing and chaining.

$$\text{index} = \text{hash(key)} \bmod m$$