Hash Tables and Direct Addressing
Suppose a compiler needs to check, thousands of times per second, whether an identifier has already been declared. Suppose a web cache must answer "have I seen this URL?" in microseconds. Or a database must join two tables on a key column without scanning either one twice. All of these are instances of the same abstract problem. Maintain a dynamic set of keys, each carrying associated data. Support insert, delete, and search as fast as possible. Arrays give O(1) access but only when the index is the key itself. Balanced search trees give O(log n) for arbitrary keys. But they pay a logarithmic tax on every operation. Hash tables are the data structure that resolves this tension. They deliver expected O(1) time for all three operations over arbitrary key universes. The idea originates from a much simpler structure called direct addressing. This works perfectly when the universe of possible keys is small enough to allocate one array slot per key. Direct addressing is the conceptual seed. It shows that if you could afford an array indexed literally by key value, every dictionary operation collapses to array indexing — no comparisons, no traversals, just arithmetic. The entire achievement of hashing is to preserve this O(1) array-indexing behavior. At the same time, it shrinks the array from "one slot per possible key" down to "one slot per key actually present." This is done using a function that maps large key universes into small index ranges. This article builds the idea from the ground up. First, direct-address tables as the ideal but impractical baseline. Then, the hash-table abstraction that approximates that ideal using a hash function and a fixed-size array. Finally, the probabilistic assumption — simple uniform hashing — under which expected-case analysis gives the famous O(1) result. We deliberately stop short of specifying how collisions are resolved. That is the subject of the two structures this article sets up, Separate Chaining Collision Resolution and Open Addressing Collision Resolution. Here the focus is on the contract: what a hash table promises, why it can keep that promise only in expectation, and precisely what assumptions make the promise honest. Hash tables underlie nearly every high-throughput indexing system in modern computing: language runtime symbol tables, associative arrays in Python (`dict`), Java (`HashMap`), JavaScript (object property maps), database hash joins and hash indexes, deduplication in storage systems, and caches at every layer of the internet stack. Understanding the direct-addressing idea behind them is essential. So is the uniform-hashing assumption that makes their performance claims rigorous. Both are necessary before studying any specific collision-resolution scheme.
- Direct addressing stores each key at array index `key` itself, giving worst-case O(1) operations — but requires an array as large as the entire key universe.
- Hash tables compress a huge key universe `U` down to a small index range `{0, ..., m-1}` via a hash function `h`, trading a small chance of collisions for huge space savings.
- A collision occurs when two distinct keys map to the same slot; every hash table needs some collision-resolution policy (chaining or open addressing) layered on top.
- Under the simple uniform hashing assumption — each key is equally likely to hash to any slot, independently — expected O(1) time holds for search, insert, and delete.
- The load factor `α = n/m` (keys stored per slot) is the single number that controls expected performance; keeping `α = O(1)` is what makes O(1) time achievable in practice.
- Hash tables give up the ordered-traversal and worst-case guarantees that balanced trees offer, in exchange for much faster expected-case performance.
A hash table approximates the O(1) array-indexing behavior of direct addressing by using a hash function to compress a huge key universe into a small array, paying for the compression with occasional collisions that a resolution scheme must handle.
The idea
Direct addressing is the simplest possible dictionary implementation. Suppose keys are drawn from a universe `U = {0, 1, ..., N-1}` — for instance, keys are the ASCII codes 0–255, or employee IDs known to lie in `[0, 10000)`. A direct-address table `T` is an array of size `N`, where slot `T[k]` holds a pointer to the element with key `k` (or is empty/`NIL` if no such element exists). Search, insert, and delete are then single array operations: ``` DIRECT-ADDRESS-SEARCH(T, k): return T[k] DIRECT-ADDRESS-INSERT(T, x): T[x.key] ← x DIRECT-ADDRESS-DELETE(T, x): T[x.key] ← NIL ``` Each runs in worst-case `O(1)` time — not merely expected time. This is the ideal every dictionary structure aspires to. The catch is the space requirement: the table must have size `|U|`, regardless of how many keys are actually stored. If `U` is the set of 64-bit integers, or the set of all strings up to length 100, a direct-address table is physically impossible to build, even though the number of keys we actually want to store, `n`, might be tiny compared to `|U|`. A hash table rescues the O(1)-indexing idea from this space explosion. Instead of an array of size `|U|`, we use an array `T` of size `m`, where `m` is chosen roughly proportional to `n`, the number of keys we expect to store — typically `m = Θ(n)`. A hash function ``` h : U → {0, 1, ..., m-1} ``` maps each key to a slot in this much smaller array. An element with key `k` is (conceptually) stored at slot `T[h(k)]`. Because `|U|` is generally far larger than `m`, the hash function is necessarily many-to-one: distinct keys `k1 ≠ k2` can satisfy `h(k1) = h(k2)`. This event is a collision, and it is not a bug but an unavoidable consequence of the pigeonhole principle whenever `|U| > m`. Every real hash table therefore layers a collision-resolution strategy on top of the basic array-and-hash-function skeleton described here. The two dominant families — storing colliding elements in auxiliary linked structures (Separate Chaining Collision Resolution) or relocating them to other slots within the same array (open addressing, via probe sequences) — are developed in their own right elsewhere. What this article establishes is the shared foundation beneath both: what a hash table's contract is, how to reason about its performance in the presence of collisions in general, and the precise probabilistic assumption, simple uniform hashing, that makes the informal claim "hash tables are O(1)" into a theorem rather than a slogan.
How it works
A hash table's operations always follow the same two-stage pattern, regardless of which collision-resolution scheme sits underneath: 1. Locate: compute `h(k)` to find the slot (or starting slot) associated with key `k`. 2. Resolve: use the collision-resolution policy to find the actual location of `k`'s element among possibly several elements that hash to the same slot. Below is the generic skeleton for the three dictionary operations, written abstractly over an unspecified `RESOLVE` mechanism. This is intentionally the same shape whether `RESOLVE` performs a chained list traversal or a probe sequence. ``` // T is an array of size m; h maps keys to {0, ..., m-1}. // RESOLVE(T, k) returns the slot/position that does or should hold key k, // consulting the collision-resolution structure at T[h(k)]. HASH-SEARCH(T, k): slot ← h(k) return RESOLVE-SEARCH(T, slot, k) // examine slot's colliding elements for key k HASH-INSERT(T, x): slot ← h(x.key) RESOLVE-INSERT(T, slot, x) // place x among slot's colliding elements HASH-DELETE(T, x): slot ← h(x.key) RESOLVE-DELETE(T, slot, x) // remove x from slot's colliding elements ``` The cost of each operation is therefore: ``` cost(operation on key k) = O(1) [computing h(k)] + cost(RESOLVE on the elements colliding with k) ``` The first term is a constant assuming `h` can be evaluated in O(1) time (true for essentially all hash functions used in practice — modular arithmetic, multiplicative hashing, universal hash families, etc., as covered under Hash Functions). The entire performance question therefore reduces to: how many elements can collide with `k`, i.e., land in the same slot?
The load factor
Let `n` be the number of elements currently stored in the table and `m` the number of slots. Define the load factor ``` α = n / m ``` This is the average number of elements per slot. If elements distribute themselves "evenly" across slots — which is exactly what a good hash function tries to guarantee — then the expected number of elements colliding with any particular key is `Θ(α)`. Since we typically choose `m = Θ(n)`, we get `α = Θ(1)`, and hence expected `O(1)` resolution cost. This is the entire mechanism behind the celebrated O(1) claim: keep `α` bounded by a constant, and each slot holds O(1) elements on average.
Simple uniform hashing
To convert "elements distribute evenly" from a hopeful heuristic into a provable guarantee, we adopt the simple uniform hashing assumption (SUHA): > Each key is equally likely to hash to any of the `m` slots, independently of where other keys hash, and independently of the specific key value. Formally, for a key `k` drawn according to whatever process generates the keys, and for each slot `j ∈ {0, ..., m-1}`, ``` Pr[h(k) = j] = 1/m, ``` and the hash values of different keys are mutually independent random variables. Under SUHA, the number of keys hashing to any fixed slot, given `n` keys total, follows a distribution with mean `α = n/m` — this is the formal justification for the informal "Θ(α) elements per slot" statement above, and it is the assumption every expected-time analysis of hashing rests on. SUHA is, honestly, unrealizable in the strictest sense: any fixed hash function `h`, once an adversary knows it, can be attacked by choosing `n` keys that all hash to the same slot, destroying uniformity completely (this is exactly how algorithmic complexity attacks on naive hash tables work). In practice SUHA is treated as a modeling assumption justified either by (a) using cryptographic or well-mixing hash functions against non-adversarial key distributions, or (b) using universal hashing, where the hash function itself is randomly chosen from a family at runtime, so that no fixed adversarial key set can defeat it — a refinement introduced properly under Hash Functions. For this article's purposes, SUHA is the clean mathematical idealization that makes the O(1) expected-time claim precise and provable, exactly as the uniform-random-pivot assumption does for quicksort's expected running time.
The state machine of a slot
A useful way to see how a hash table's performance depends on `α` is to picture each slot as a small independent unit that can be empty, hold one key, or hold several colliding keys, and to see how a lookup's cost scales with slot occupancy:
Complexity & correctness
Space. A direct-address table over universe `U` uses `Θ(|U|)` space regardless of `n`, the number of keys actually stored — this is precisely its practical flaw. A hash table uses `Θ(m)` space for the slot array plus `Θ(n)` space for the stored elements and any collision-resolution overhead (list nodes, or nothing extra for open addressing since elements live in the array itself). Choosing `m = Θ(n)` gives total space `Θ(n)`, proportional to the actual data, independent of `|U|`. This is the entire point of the hash-table construction: O(n) space instead of O(|U|) space, at the cost of introducing collisions.
Time. Direct addressing gives worst-case `O(1)` for search, insert, delete — no assumption needed, because each key maps to a unique slot by construction (`h` is the identity function and injective on `U`). For a hash table, the time for `HASH-SEARCH`, `HASH-INSERT`, `HASH-DELETE` decomposes as ``` O(1) [evaluating h(k)] + O(cost of resolving collisions at that slot). ``` The second term is where all the interesting analysis lives, and it is genuinely dependent on which collision-resolution scheme is used — but the shape of the argument is identical in both cases, and can be stated at this level of generality: Claim: Under simple uniform hashing, with `n` keys stored in a table of `m` slots and load factor `α = n/m`, the expected number of keys examined during an unsuccessful search is `Θ(1 + α)`. Proof sketch. Fix a key `k` not in the table, and consider the slot `j = h(k)`. Under SUHA, every one of the `n` stored keys is, independently, equally likely to have landed in any of the `m` slots. So the number of stored keys that landed in slot `j` (and hence must be examined, or at least accounted for, to conclude `k` is absent) is a sum of `n` independent indicator random variables, each with success probability `1/m`. By linearity of expectation, the expected number of such keys is ``` E[# keys in slot j] = n · (1/m) = α. ``` Including the O(1) cost of computing `h(k)` and checking the slot itself, the total expected cost of an unsuccessful search is `Θ(1 + α)`. A symmetric (slightly more delicate, because the searched-for key itself is one of the `n`) argument gives the same `Θ(1 + α)` bound for a successful search, averaged over which of the `n` keys is being sought. ∎ Consequence. If `m` is chosen so that `n = O(m)`, i.e. the table is resized to keep `α` bounded by a constant (this is exactly what dynamic resizing — doubling `m` when `α` exceeds a threshold, shrinking when it falls too low — accomplishes, in the same amortized spirit as dynamic array growth), then `α = O(1)`, and search, insert, and delete all run in expected `O(1)` time.
Honesty about the guarantee. This is an expected-case, not worst-case, bound, and it depends on an assumption (SUHA) that no fixed hash function can satisfy against a fully adversarial key sequence. Three caveats deserve emphasis:
- Worst case is always bad. Regardless of collision-resolution scheme, if all `n` keys happen to hash to the same slot, operations degrade to `Θ(n)` — chaining degrades to a linked-list scan, and open addressing degrades to scanning nearly the whole table. This is unavoidable: it is a direct consequence of the pigeonhole principle whenever `|U| > m`, so no hash function can prevent it for all possible key sets. Well-designed hash functions only make this worst case rare or hard to trigger deliberately.
- Adversarial inputs are a real threat. If an attacker knows the fixed hash function used by a service (e.g., a web server's parameter-parsing hash map), they can submit keys engineered to all collide, turning O(1) operations into O(n) ones and causing a denial-of-service via algorithmic complexity — a documented class of vulnerability. Universal hashing, where the function is randomized at table-creation time from a family with a provable collision-probability bound, defends against this by making it impossible for an adversary (who doesn't know the random seed) to predict collisions in advance.
- The bound hides the resolution scheme's own overhead. Chaining's constant factor includes pointer-chasing and memory allocation for list nodes; open addressing's constant factor includes clustering effects that can make the variance of running time much higher, and both are quantified precisely in their own dedicated treatments.
Worked example
Trace inserting the keys `{18, 5, 32, 3, 9, 24}` into a hash table with `m = 8` slots, using `h(k) = k mod 8`, resolving collisions by separate chaining (previewed here only to make the trace concrete — full development is left to Separate Chaining Collision Resolution).
| Step | Key | h(key) = key mod 8 | Slot before | Action | Slot after |
|---|---|---|---|---|---|
| 1 | 18 | 18 mod 8 = 2 | empty | insert at slot 2 | `[18]` |
| 2 | 5 | 5 mod 8 = 5 | empty | insert at slot 5 | `[5]` |
| 3 | 32 | 32 mod 8 = 0 | empty | insert at slot 0 | `[32]` |
| 4 | 3 | 3 mod 8 = 3 | empty | insert at slot 3 | `[3]` |
| 5 | 9 | 9 mod 8 = 1 | empty | insert at slot 1 | `[9]` |
| 6 | 24 | 24 mod 8 = 0 | `[32]` (occupied!) | collision — append to chain | `[32, 24]` |
After all insertions: `n = 6`, `m = 8`, load factor `α = 6/8 = 0.75`. Slot 0 holds two keys (`32` and `24`, since both are `≡ 0 mod 8`); slots 4, 6, 7 remain empty; every other occupied slot holds exactly one key.
Search for key 24. Compute `h(24) = 0`. Examine slot 0's chain: first compare against `32` (mismatch), then against `24` (match) — 2 probes, cost `O(1 + chain length) = O(3)`.
Search for key 7 (absent). Compute `h(7) = 7`. Slot 7 is empty — 0 comparisons needed, immediate `O(1)` answer that `7` is not present.
Search for key 40 (absent, but collides). Compute `h(40) = 0`. Slot 0 is non-empty; must scan its entire chain (`32`, then `24`, both mismatches) before concluding `40` is absent — this unsuccessful search costs proportional to the full chain length at that slot, illustrating why unsuccessful searches are (in expectation) exactly as expensive as successful ones under SUHA, `Θ(1+α)`. This small trace already shows the two extremes bounded by the `Θ(1+α)` expected-cost claim: a lucky search hits an empty slot in `O(1)`, an unlucky one must walk a chain of length up to `n` in the worst case (if all keys happened to collide), but averaged over all keys and all random hash assignments, the expected chain length is `α = 0.75` — consistent with what was observed (one chain of length 2, five chains of length 1 or 0).
Common pitfalls & traps
| Pitfall | Why it happens | Fix | ||||
|---|---|---|---|---|---|---|
| Forgetting to resize the table as `n` grows | Treating `m` as fixed forever lets `α = n/m` grow unbounded, silently degrading O(1) claims to O(n) | Track `α` and resize (typically double `m`) once `α` exceeds a constant threshold, exactly as with [[Arrays and Dynamic Arrays | dynamic array]] growth | |||
| Confusing direct addressing's worst-case O(1) with hash tables' expected O(1) | Both "look like" array indexing, but only direct addressing is guaranteed collision-free by construction | Always state hashing bounds as expected/average-case unless a specific worst-case-safe scheme (e.g. perfect hashing, cuckoo hashing) is in use | ||||
| Assuming any fixed hash function is "good enough" against all inputs | SUHA can be violated deliberately; adversarial or even just unlucky key distributions can concentrate on few slots | Use well-mixing hash functions and, when facing untrusted input (e.g. web-facing key-value stores), use universal/randomized hashing | ||||
| Ignoring the difference between ` | U | `, `m`, and `n` | These three quantities play very different roles: universe size, table size, elements stored | Keep them notationally distinct; remember direct addressing needs `Θ( | U | )` space, hashing needs `Θ(m) = Θ(n)` |
| Treating "no collisions observed in testing" as a correctness guarantee | Collisions are probabilistic; rare inputs (or adversarial ones) can trigger them even if typical testing never does | Always reason about worst case and adversarial inputs separately from expected-case testing |
Pioneers & history
The direct-addressing idea long predates modern computing — it is essentially the principle behind any lookup table or index card system — but its formalization as a data-structure technique, and the invention of hashing to compress it, emerged from early work on associative memory and symbol-table design in the 1950s at IBM and Bell Labs.
Origins · 1 minHans Peter Luhn and how this was discovered
Luhn, an engineer at IBM, is widely credited with one of the earliest written descriptions of hashing (in internal IBM memoranda from the early 1950s), proposing that keys be mapped via an arithmetic function into a smaller table to speed up information retrieval — the germinal idea behind every hash table built since.
Where this matters
Hash tables (built on exactly the array-plus-hash-function skeleton described here) are the default associative-array implementation in nearly every widely used programming language: Python's `dict`, Java's `HashMap`, C++'s `unordered_map`, Go's `map`, and JavaScript's object property tables all rest on this foundation, layered with a specific collision-resolution scheme. Compilers and interpreters use hash tables for symbol tables, mapping identifier names to type and storage information in expected O(1) time per lookup — a design goal directly motivated by the analysis given here. Databases use hash indexes and hash joins, where matching rows across tables reduces to hashing join keys into buckets rather than sorting or nested-loop scanning. Distributed systems use variants of hashing (notably consistent hashing, a refinement of the ideas here) to shard data across many machines while minimizing data movement when machines are added or removed. Caching layers — CPU cache tag lookups, web caches, content-addressable storage and deduplication systems — all rely on the same principle: compress a huge key space down to a manageable index range, accept that collisions will occur, and resolve them with a bounded-cost mechanism, exactly the contract this article has laid out as the shared foundation beneath Separate Chaining Collision Resolution and Open Addressing Collision Resolution.
Ask the tutor: How does the choice between separate chaining and open addressing change the expected-cost analysis derived here from `Θ(1+α)`?
Why not just always use direct addressing if it gives worst-case O(1) time?
Direct addressing requires an array of size equal to the entire key universe `|U|`, not just the number of keys actually used. If keys are, say, arbitrary 64-bit integers or strings, `|U|` is astronomically larger than any number of keys you'd realistically store — allocating that array is physically impossible. Hash tables exist precisely to recover O(1)-style indexing while using space proportional to the actual number of stored keys, `Θ(n)`, rather than the size of the universe they're drawn from. The price paid for this space savings is that the O(1) guarantee becomes an expected-case rather than worst-case one, because compressing a huge universe into a small table necessarily creates collisions.
What exactly is "simple uniform hashing," and is it a realistic assumption?
Simple uniform hashing (SUHA) assumes each key is equally likely to hash to any of the `m` slots, independently of other keys' hash values. It's the assumption needed to make the "expected O(1+α) operations" claim mathematically rigorous, via a straightforward expectation calculation over indicator random variables. It is not fully realistic for a fixed hash function, since an adversary who knows the function can craft keys that all collide, but it's a reasonable model for non-adversarial, sufficiently varied real-world key distributions combined with well-designed hash functions. Universal hashing strengthens this by randomizing the function itself, giving provable average-case guarantees even against adversarial key choices.
How is the load factor α related to choosing the table size m?
`α = n/m` measures elements per slot on average; the expected-cost bound `Θ(1+α)` is only useful in practice if `α` stays bounded by a constant as `n` grows. Since `n` is often unknown in advance and changes over time, practical hash tables monitor `α` and dynamically resize `m` — typically doubling it once `α` crosses an upper threshold (e.g., 0.75) and possibly halving it if `α` drops very low — using the same amortized-doubling analysis as dynamic arrays. This keeps `α = O(1)` at all times, which is exactly the condition needed for expected `O(1)` operations to hold as the table grows or shrinks.
What's the actual difference between a "collision" and the hash table simply being "full"?
A collision is when two distinct keys map to the same slot under the hash function — it can happen at any load factor, even very low ones, purely due to the pigeonhole principle and randomness, and it is independent of whether the table has spare capacity elsewhere. "Full" refers to the table running out of slots (relevant mainly for open addressing, where every key must live directly in the array) or the load factor climbing high enough to warrant resizing. A table can have collisions while being nearly empty overall (bad luck, or a poor hash function), and conversely a table with a well-spread hash function can have few collisions even at moderately high load factors.
Does a hash table support ordered operations like "find the minimum key" or "find the next larger key"?
No, and this is one of the fundamental tradeoffs versus balanced binary search trees. A hash table scatters keys across slots according to the hash function's output, destroying any relationship between key order and slot position — two numerically adjacent keys can land in completely unrelated slots. Balanced search trees maintain sorted order at the cost of `O(log n)` operations; hash tables abandon order entirely to achieve expected `O(1)` operations. If you need both fast lookups and ordered traversal, you generally need a different structure (e.g., a balanced tree, or a hash table combined with an auxiliary sorted structure).
Why does the article separate "hash table" from "collision resolution scheme" as different concepts?
Because the hash table's basic contract — compute `h(k)`, then locate/resolve within that slot — is identical regardless of how collisions are resolved, and the expected-`Θ(1+α)` analysis under SUHA applies (with scheme-specific constants) to both major families. Separate chaining resolves collisions by linking multiple elements off each slot; open addressing resolves them by probing alternate slots within the same array. These have different space overheads, different worst-case behaviors under high load factor, and different cache performance, which is why each deserves its own dedicated treatment rather than being folded into the general hash-table contract described here.
What real vulnerability arises from misunderstanding the difference between expected-case and worst-case hashing performance?
Algorithmic complexity attacks: if a service uses a fixed, publicly known hash function to build hash tables from untrusted input (e.g., HTTP form field names, JSON keys), an attacker can precompute a large set of keys that all collide under that specific function. Submitting such a set forces the table into its `Θ(n)`-per-operation worst case for every one of `n` insertions, producing `Θ(n²)` total work instead of the expected `Θ(n)` — enough to make a server unresponsive with a modestly sized malicious request. This is a real, documented class of denial-of-service vulnerability, and it is precisely why production systems use randomized/universal hashing rather than a single fixed hash function for untrusted keys.