Hash Tables

This post extracts some knowledge from Introduction to Algorithms Chapter 11 – Hash Tables.

Overview

A hash table implements a dynamic set. It supports SEARCH, INSERT, and DELETE, with an expected running time of $O(1)$ per operation when the hash function distributes keys well.

Instead of using a key directly as an array index, a hash table uses a hash function

$$ h(k) = \text{the slot containing key } k $$

to map a key from a large universe into one of $m$ table slots.

Direct addressing

Direct addressing works when the universe of possible keys $U$ is small. The table has one position for every possible key:

$$ T[k] = \text{the element whose key is } k $$

Searching, inserting, and deleting all take $O(1)$ time. The drawback is space: direct addressing requires $\Theta(|U|)$ storage, even when only a few keys are present.

Hashing reduces this space requirement to $\Theta(m)$, where $m$ is usually proportional to the number of stored elements.

Collisions

A collision occurs when two different keys map to the same slot:

$$ k_1 \ne k_2, \quad \text{but} \quad h(k_1) = h(k_2) $$

Collisions cannot always be avoided when the key universe is larger than the table. A good hash function instead aims to distribute keys uniformly across the slots, making collisions infrequent and evenly spread.

The two principal ways to resolve collisions are chaining and open addressing.

Hash functions

Division method

The division method maps a key with

$$ h(k) = k \bmod m $$

The table size $m$ should avoid values that interact poorly with patterns in the keys. A prime number not too close to a power of $2$ is often a reasonable choice.

Multiplication method

Choose a constant $A$ such that $0 < A < 1$, and define

$$ h(k) = \left\lfloor m(kA \bmod 1) \right\rfloor $$

This method is less sensitive to the choice of $m$.

Universal hashing

Universal hashing chooses the hash function randomly from a carefully designed family of functions. For any two distinct keys, the probability that they collide is at most $1/m$. Random selection prevents a fixed, adversarial set of keys from consistently producing poor behavior.

Collision resolution by chaining

In chaining, each table slot stores a collection, commonly a doubly linked list, containing all elements that hash to that slot.

T[0] -> k1 -> k4
T[1] -> k2
T[2] -> k3 -> k5 -> k6

If the table stores $n$ elements in $m$ slots, its load factor is

$$ \alpha = \frac{n}{m} $$

The load factor is the average number of elements per chain. Under simple uniform hashing:

• unsuccessful search takes $\Theta(1 + \alpha)$ expected time;
• successful search takes $\Theta(1 + \alpha)$ expected time;
• insertion takes $O(1)$ time when inserted at the beginning of a chain;
• deletion takes $O(1)$ time when the element and a doubly linked list are used.

When $m$ is proportional to $n$, $\alpha$ remains bounded, so the expected time per operation is $O(1)$.

Collision resolution by open addressing

Open addressing stores every element directly in the table. When a collision occurs, the algorithm probes other slots until it finds the key or an empty slot.

A probe sequence depends on both the key and the probe number:

$$ h(k, i), \qquad i = 0, 1, \ldots, m - 1 $$

To guarantee that insertion can inspect every slot, the probe sequence must be a permutation of ${0, 1, \ldots, m - 1}$. Because each element occupies one slot, open addressing requires $\alpha = n/m < 1$.

Deletion needs special care. Clearing a slot could break the probe sequence of another key, so a deleted slot is marked with a special DELETED value. Searching continues past DELETED, while insertion may reuse it.

Linear probing

$$ h(k, i) = \bigl(h’(k) + i\bigr) \bmod m $$

Linear probing checks consecutive slots. It is simple and benefits from good cache locality, but it suffers from primary clustering: long runs of occupied slots form, and these runs tend to grow as more keys are inserted.

Quadratic probing

$$ h(k, i) = \bigl(h’(k) + c_1 i + c_2 i^2\bigr) \bmod m $$

Quadratic probing spreads probes more widely and reduces primary clustering. Keys with the same initial hash value still follow the same probe sequence, however, causing secondary clustering. The constants and table size must be chosen so that the desired slots are reachable.

Double hashing

$$ h(k, i) = \bigl(h_1(k) + i h_2(k)\bigr) \bmod m $$

Double hashing uses a second hash function to determine the probe step. It produces many more possible probe sequences than linear or quadratic probing and generally behaves closer to uniform hashing.

The value $h_2(k)$ must be relatively prime to $m$ so that the sequence can visit every slot. One common design uses a prime table size and chooses $h_2(k)$ from $1$ through $m - 1$.

Expected performance

Under uniform hashing, an unsuccessful search in an open-addressed table has expected cost at most

$$ \frac{1}{1 - \alpha} $$

probes. A successful search has expected cost at most

$$ \frac{1}{\alpha} \ln\left(\frac{1}{1 - \alpha}\right) $$

The cost rises quickly as $\alpha$ approaches $1$. Open-addressed tables therefore need free space and should be resized before becoming too full.

Chaining or open addressing?

In both designs, performance depends on a suitable table size, a well-distributed hash function, and keeping the load factor under control.