How Do Hash Tables Achieve O(1) Expected Lookup Time?

Hash tables achieve constant expected lookup time by mapping keys directly to array indices using a deterministic hash function, allowing immediate access to stored values without searching through every element. When two different keys map to the same index, collision resolution strategies such as separate chaining or open addressing manage the overlap while keeping average operations fast as long as the table maintains a low load factor.

Mapping Keys with Hash Functions

In classical computing, an array provides \(O(1)\) random access because the memory address of any element at index \(i\) can be computed directly from the base address and element size. A hash table leverages this property by passing a key \(k\) through a hash function \(h(k)\) that produces an integer, which is then reduced modulo the table size \(m\):

\[\text{index} = h(k) \bmod m\]

For \(O(1)\) expected performance, the hash function must satisfy two properties:

  • Deterministic: The same key must always produce the same index.
  • Uniformity: Keys should be distributed as evenly as possible across all \(m\) buckets, approximating a uniform random distribution.

Computing \(h(k)\) typically takes \(O(1)\) time (or \(O(|k|)\) for variable-length keys like strings, which is treated as constant for bounded key lengths).

Handling Collisions

Because the space of possible keys is usually much larger than the array size \(m\), collisions—where \(h(k_1) \equiv h(k_2) \pmod m\) for \(k_1 \neq k_2\)—are inevitable. Hash tables use two primary strategies to resolve them.

Separate Chaining

In separate chaining, each slot in the array holds a pointer to a secondary data structure, most commonly a linked list, containing all key-value pairs that hash to that index.

  • Lookup: Compute \(i = h(k) \bmod m\), then traverse the list at slot \(i\) until the matching key is found.
  • Expected Cost: If \(n\) elements are stored in a table of size \(m\), the load factor is \(\alpha = \frac{n}{m}\). Under the assumption of simple uniform hashing, the expected length of any chain is \(\alpha\), giving an expected lookup time of \(O(1 + \alpha)\).

Open Addressing

In open addressing, all elements are stored directly within the array itself. When a collision occurs at index \(i\), the table probes a sequence of alternative slots \(h(k, 0), h(k, 1), h(k, 2), \dots\) until an empty slot or the target key is found. Common probing methods include:

  • Linear probing: \(h(k, j) = (h(k) + j) \bmod m\)
  • Quadratic probing: \(h(k, j) = (h(k) + c_1 j + c_2 j^2) \bmod m\)
  • Double hashing: \(h(k, j) = (h_1(k) + j \cdot h_2(k)) \bmod m\)

Under uniform hashing assumptions with \(\alpha < 1\), the expected number of probes for an unsuccessful search is at most \(\frac{1}{1 - \alpha}\), and for a successful search is at most \(\frac{1}{\alpha} \ln\left(\frac{1}{1 - \alpha}\right)\), both of which are \(O(1)\) when \(\alpha\) is bounded away from \(1\).

Maintaining Constant Time via Dynamic Resizing

If \(n\) grows without bound while \(m\) stays fixed, the load factor \(\alpha\) increases and lookup time degrades toward \(O(n)\). To prevent this, hash tables monitor \(\alpha\) and resize the underlying array (typically doubling \(m\)) whenever \(\alpha\) exceeds a chosen threshold, such as \(0.75\).

Although rehashing all \(n\) existing elements into a larger array takes \(O(n)\) time, doubling the capacity ensures that this cost is spread across \(\Omega(n)\) insertions. As a result, the amortized cost of insertion remains \(O(1)\), and the expected lookup time stays \(O(1)\).

Worst-Case Caveats

While the expected lookup time is \(O(1)\), the worst-case lookup time is \(O(n)\) if all keys collide into the same bucket or probe sequence. This can happen with poorly chosen hash functions or adversarial inputs. Using cryptographic hash functions or randomized universal hashing—where the hash function is chosen randomly from a family \(\mathcal{H}\) at runtime—prevents attackers from engineering collisions and guarantees \(O(1)\) expected time regardless of the input distribution.