Hashing and Hash Functions

A dictionary stores a set of keys (each possibly with satellite data) and supports INSERT, SEARCH and DELETE. A sorted array answers SEARCH in $\Theta(\lg n)$ time and a balanced search tree does all three in $O(\lg n)$. Hashing does all three in $O(1)$ expected time under reasonable assumptions, by computing where a key lives instead of searching for it.

The price is order. A hash table scatters keys on purpose, so it cannot report the minimum, the successor of a key or all keys in a range without examining the whole table.

This note covers direct addressing, the hash table, the load factor, the standard hash functions (division, multiplication, mid-square, folding, strings and universal hashing) and the probability that keys collide. What a table does after a collision (chaining, linear, quadratic and double probing, and their expected costs) is the subject of Collision Resolution.

Collisions are unavoidable. If $|U| > m$, the pigeonhole principle forces at least two keys of $U$ into one slot, so no hash function avoids collisions for every possible key set. A good hash function only makes them rare and evenly spread; a collision-resolution method handles the ones that happen.

Slot numbering convention. Hash table slots are numbered $0$ to $m - 1$, because every standard hash function produces a remainder. Other arrays in these notes are 1-based.

When $U = \{0, 1, \ldots, |U| - 1\}$ is small, use a direct-address table $T[0..|U|-1]$ with one slot per possible key: slot $k$ holds the element with key $k$, or NIL.

Pseudocode uses <- for assignment, x.key for the key of element x, NIL for an empty slot, and 0-based slots $T[0..m-1]$.

Each operation is $\Theta(1)$ in the worst case, and space is $\Theta(|U|)$. This is the right choice when $|U|$ is comparable to $n$ (for example, keys are roll numbers 0 to 999). When $|U|$ is huge and $n$ is small, the space is wasted, and hashing replaces $T[k]$ by $T[h(k)]$ with $m = \Theta(n)$ slots.

The load factor of a table holding $n$ keys in $m$ slots is

With chaining $\alpha$ can exceed 1; with open addressing $\alpha \le 1$ always.

Simple uniform hashing is the assumption that each key is equally likely to hash to any of the $m$ slots, independently of where other keys hash. It is an idealisation (a fixed $h$ is deterministic), but it is the model in which expected costs such as $\Theta(1 + \alpha)$ for search with chaining are proved. Under it, two fixed distinct keys collide with probability exactly $1/m$.

Expected versus worst case. Chaining under simple uniform hashing gives $O(1)$ expected time per operation when $\alpha=O(1)$. For open addressing, require $\alpha\le1-\varepsilon$ for fixed $\varepsilon>0$ and the appropriate uniform-hashing assumptions. The worst case is still $\Theta(n)$ per search: if all $n$ keys land in one slot, the table degenerates into a list.

One division, so it is fast. Its quality depends entirely on $m$.

EDGE CASE. For negative keys, the mathematical $k \bmod m$ lies in $0..m-1$ (for example $-3 \bmod 11 = 8$), but C's % operator gives $-3$ for -3 % 11. A question that uses C code means C's operator.

Choose a constant $A$ with $0 < A < 1$ and set

where $kA \bmod 1 = kA - \lfloor kA \rfloor$ is the fractional part of $kA$. The value of $m$ is not critical, so a power of 2 is fine and convenient. The golden-ratio choice $A = (\sqrt{5} - 1)/2 \approx 0.6180339887$ is the usual recommendation and works well in practice.

Fixed-point form (word size $w$, $m = 2^p$). Assume integer $1\le p\le w$ and a nonnegative $w$-bit key. Let $s=\lfloor A\cdot2^w\rfloor$ and $A\prime=s/2^w$. This word method implements multiplication hashing for the fixed-point constant $A\prime$, approximating the chosen real $A$. Multiply the $w$-bit key by $s$ to get a $2w$-bit product $r_1 2^w + r_0$. Then $h(k)$ is the most significant $p$ bits of the low word $r_0$, that is $h(k) = \lfloor r_0 / 2^{w-p} \rfloor$.

Evaluation costs. On a word model with constant-time sufficiently wide multiplication, masking and shifting, HASH-MULTIPLY takes $\Theta(1)$ time and $O(1)$ auxiliary words in best, average and worst cases. A constant number of words must hold the exact $2w$-bit product (or a primitive must return its low word exactly); signed overflow is not a substitute. The input key and one-word hash output are excluded. These are word-operation costs, not bit-complexity bounds as $w$ grows.

Evaluate the string polynomial $\sum_i \operatorname{code}(c_i)R^{L-1-i}$ modulo $m$ using Horner's rule. The stored $h$ is in $0,\ldots,m-1$; before reduction, $hR+\operatorname{code}(c)\le(m-1)R+C_{\max}$, where $C_{\max}$ is the largest character code. The simpler bound $<Rm$ requires every code to be less than $R$. Choosing $R=31$ with ASCII is a polynomial hash, not an assertion that ASCII codes are base-31 digits:

The result equals $\left(\sum_{i=0}^{L-1} \mathrm{code}(c_i)\, R^{L-1-i}\right) \bmod m$, because reduction modulo $m$ commutes with addition and multiplication. Summing the character codes without the powers of $R$ is a poor hash: every anagram ("TEA", "EAT", "ATE") collides.

Evaluation costs. HASH-STRING takes $\Theta(L+1)$ time in best, average and worst cases, including the empty string, and $O(1)$ auxiliary words excluding the input string and scalar hash output. Each character lookup, multiply-add and modulo must be constant time and exact at the chosen widths: an intermediate register must hold $(m-1)R+C_{\max}$, or use an equivalent overflow-safe modular primitive. Arbitrary-precision arithmetic has additional bit costs; silent machine overflow need not preserve the hash.

An adversary knowing a fixed $h$ may choose colliding keys when a bucket contains enough of them. By the pigeonhole principle, some bucket has at least $\lceil |U|/m\rceil$ keys; an all-colliding $n$-set is guaranteed only for $n\le\lceil |U|/m\rceil$. The universal-hashing guarantee below is for a fixed key set chosen independently of the random hash. Universal hashing picks $h$ at random, at run time, from a family $\mathcal{H}$. The family is universal if for every pair of distinct keys $k \ne l$,

A standard universal family. Restrict this family to integer keys in $U\subseteq\{0,\ldots,p-1\}$, with prime $p$ and integer $m\ge1$. Choose $a$ and $b$ uniformly and independently from their respective sets, and for $a \in \{1, \ldots, p-1\}$, $b \in \{0, \ldots, p-1\}$ set

There are $p(p-1)$ equally likely parameter pairs $(a,b)$; for some allowed $U$ and $m$, different pairs represent the same map. For example, with $p = 17$, $m = 6$, $h_{3,4}(8) = ((24 + 4) \bmod 17) \bmod 6 = 11 \bmod 6 = 5$. With chaining and a universal family, the expected chain length seen by a search is at most $1 + \alpha$ for every key set, because the randomness is in the choice of $h$, not in the input.

Insert $54, 26, 93, 17, 77, 31, 44, 20$ into a table with $m = 11$ and $h(k) = k \bmod 11$.

Two collisions occur: $44$ with $77$ at slot 0, and $20$ with $31$ at slot 9. The load factor is $\alpha = 8/11 \approx 0.727$. Under simple uniform hashing the expected number of colliding pairs among 8 keys is $\binom{8}{2}/11 = 28/11 \approx 2.55$, so two pairs is typical.

For $k = 123456$, $A = (\sqrt{5} - 1)/2$ and $m = 10000$: $kA \approx 76300.0041151$, so $kA \bmod 1 \approx 0.0041151$ and $h(k) = \lfloor 10000 \times 0.0041151 \rfloor = 41$.

In fixed point with $w = 32$, $p = 14$ ($m = 16384$) and $s = 2654435769$ (so $s / 2^{32} \approx 0.6180339886$): $ks = 327706022297664 = 76300 \cdot 2^{32} + 17612864$, so $r_1 = 76300$, $r_0 = 17612864$, and $h(k) = \lfloor 17612864 / 2^{18} \rfloor = 67$ (Figure 1).

Hash "GATE" with ASCII codes (G = 71, A = 65, T = 84, E = 69), $R = 31$ and $m = 13$:

Check without intermediate reduction: $71 \cdot 31^3 + 65 \cdot 31^2 + 84 \cdot 31 + 69 = 2180299$, and $2180299 \bmod 13 = 4$.

For integers $m\ge1$ and $0\le n\le m$, the formula below applies; for $n>m$, $P(\text{no collision})=0$.

Under simple uniform hashing, the probability that $n$ keys in $m$ slots are all in different slots is

and the expected number of colliding pairs is $\binom{n}{2} / m = n(n-1)/(2m)$ (exact, by linearity of expectation over the $\binom{n}{2}$ pairs). With $m = 365$ and $n = 23$, $P(\text{no collision}) \approx 0.4927$, so a collision is more likely than not: this is the birthday paradox. Collisions appear once $n$ is around $\sqrt{m}$, long before the table is full.

Two more quantities follow from the same independence.

Write $k = q \cdot 2^p + r$ with $0 \le r < 2^p$. Then $k \bmod 2^p = r$, the last $p$ bits. Keys that agree in their low bits collide regardless of their high bits; for example, all multiples of $2^p$ go to slot 0. A prime $m$ far from a power of 2 makes $k \bmod m$ depend on all bits of $k$.

Common factors. If keys share a factor $d$ with $m$ (all keys even and $m$ even), then $k \bmod m$ is also a multiple of $\gcd(d, m)$, so only $m/\gcd(d, m)$ slots are ever used. With $m$ prime, $\gcd(d, m) = 1$ for every $d < m$.

Under simple uniform hashing with chaining, an unsuccessful search examines on average $\alpha$ keys (the expected length of one chain) plus the cost of computing $h$, so it takes $\Theta(1 + \alpha)$ time. If $m$ grows with $n$ so that $\alpha = O(1)$ (for example, double $m$ and rehash when $\alpha$ passes a threshold), every operation is $O(1)$ expected. Doubling makes the rehashing cost $O(1)$ amortised per insertion, because the sizes $m, 2m, 4m, \ldots$ form a geometric series. The full analysis, including open addressing, is in Collision Resolution.

Common misconceptions.

Hashing versus search trees. Use a hash table for pure lookup by key. Use a search tree when the question needs order: sorted output, the minimum, the predecessor or successor, or a range query. A binary search tree answers those in time proportional to its height.