--- title: Hash Tables module: Data Structures moduleNumber: 4 lessonNumber: 2 order: 402 summary: | A hash table implements the dictionary — insert, search, delete — in expected $O(1)$ time by scattering keys across an array with a hash function. We build up from direct addressing, handle collisions by chaining and by open addressing, analyze the load factor $\alpha$, and see how universal hashing achieves its expected-time guarantee against every input. topics: [Hashing] sources: - book: CLRS ref: "Ch. 11 — Hash Tables" - book: Skiena ref: "§3.7 — Hashing and Strings" - book: Erickson ref: "Ch. 5 — Hash Tables" practice: - title: 'Two Sum' slug: two-sum difficulty: Easy - title: 'Group Anagrams' slug: group-anagrams difficulty: Medium - title: 'Longest Consecutive Sequence' slug: longest-consecutive-sequence difficulty: Medium - title: 'LRU Cache' slug: lru-cache difficulty: Medium - title: 'Design HashMap' slug: design-hashmap difficulty: Easy --- Many problems need only three operations on a set of records, each identified by a **key**: insert a record, search for the record with a given key, and delete a record. This is the **dictionary** abstract data type (also called an associative array or map), and it is one of the most heavily used data structures in all of computing: symbol tables in compilers, routing tables in networks, the `dict` in your favorite scripting language. A [balanced search tree](/algorithms/data-structures/balanced-trees) does all three in $O(\log n)$ time. A **hash table** does them in _expected_ $O(1)$ time: constant, independent of how many keys are stored.[^clrs-hash] The cost is that it gives up the _ordering_ a tree provides: there is no efficient "next larger key" or "all keys in $[a,b]$", only fast point operations. ## From direct addressing to hashing Start with the easy case. Suppose every key is drawn from a small **universe** $U = \set{0, 1, \dots, m-1}$. Then we can keep an array $T[0..m-1]$, a **direct-address table**, and store the record with key $k$ in slot $T[k]$. Insert, search, and delete are each a single array access: worst-case $O(1)$, unbeatable. ```algorithm caption: Direct-address dictionary operations on table $T$ Direct-Address-Insert(T, x): $T[key(x)] \gets x$ Direct-Address-Search(T, k): return $T[k]$ Direct-Address-Delete(T, x): $T[key(x)] \gets \text{nil}$ ``` ::impl{algo="direct_address_table"} Direct addressing fails the moment the universe is large. To store $64$-bit integers we would need an array of $2^{64}$ slots, impossible, even though we may hold only a few thousand keys, leaving $T$ almost entirely empty. To address this, use a table $T[0..m-1]$ that is only as big as the number of keys we expect, and compute a slot from the key with a **hash function** $$ h : U \to \set{0, 1, \dots, m-1}. $$ The key $k$ lives in slot $h(k)$. We say $k$ **hashes** to slot $h(k)$, and $h(k)$ is the **hash value**. Because $|U| > m$, the function $h$ cannot be injective: two distinct keys can map to the same slot. That event is a **collision**, and hash-table design is largely the design of collision handling. ## Collision resolution by chaining The most natural fix is **chaining**: each slot $T[j]$ holds a [linked list](/algorithms/data-structures/elementary-structures) of all the keys that hash to $j$. To insert, prepend to the list at $T[h(k)]$; to search, scan that one list; to delete, splice the record out of its list. $$ % caption: Chained hash table where colliding keys share a linked list per slot \begin{tikzpicture}[ slot/.style={draw, minimum width=8mm, minimum height=7mm}, cell/.style={draw, minimum width=9mm, minimum height=6mm, fill=acc!12}, >=stealth] \definecolor{acc}{HTML}{2348F2} \foreach \i in {0,...,5} { \node[slot] (s\i) at (0,{-0.8*\i}) {\i}; } \node[cell] (a) [right=8mm of s1] {$k_2$}; \node[cell] (b) [right=6mm of a] {$k_7$}; \draw[->] (s1.east) -- (a.west); \draw[->] (a.east) -- (b.west); \node[cell] (c) [right=8mm of s3] {$k_4$}; \draw[->] (s3.east) -- (c.west); \node[cell] (d) [right=8mm of s4] {$k_1$}; \node[cell] (e) [right=6mm of d] {$k_5$}; \node[cell] (f) [right=6mm of e] {$k_9$}; \draw[->] (s4.east) -- (d.west); \draw[->] (d.east) -- (e.west); \draw[->] (e.east) -- (f.west); \end{tikzpicture} $$ Slots $1$, $3$, and $4$ hold chains; the rest are empty. Keys $k_1$, $k_5$, $k_9$ all collided at slot $4$, so they share a list. ```algorithm caption: Chained-hash dictionary operations on table $T$ Chained-Hash-Insert(T, x): insert $x$ at the head of list $T[h(key(x))]$ Chained-Hash-Search(T, k): search the list $T[h(k)]$ for an element with key $k$ Chained-Hash-Delete(T, x): delete $x$ from the list $T[h(key(x))]$ ``` Insertion is $O(1)$ (prepend, assuming the key is not already present). Deletion is $O(1)$ given a pointer to the record in a doubly linked list. Search costs time proportional to the length of the chain it scans, and _that_ is what we must analyze. For a worked trace, take $m = 7$ with the division hash $h(k) = k \bmod 7$, and insert the keys $19, 26, 13, 48, 5$ in that order: | insert | $h(k)$ | action | | --- | --- | --- | | $19$ | $19 \bmod 7 = 5$ | slot $5$ empty: chain becomes $19$ | | $26$ | $26 \bmod 7 = 5$ | collision: prepend, chain $26 \to 19$ | | $13$ | $13 \bmod 7 = 6$ | slot $6$ empty: chain becomes $13$ | | $48$ | $48 \bmod 7 = 6$ | collision: prepend, chain $48 \to 13$ | | $5$ | $5 \bmod 7 = 5$ | collision: prepend, chain $5 \to 26 \to 19$ | Five keys, two occupied slots, chains of length $3$ and $2$. A successful search for $26$ computes $h(26) = 5$ and scans that chain: compare against $5$ (no), then $26$ (yes), two comparisons total. An unsuccessful search for $12$ also lands on slot $5$ ($12 \bmod 7 = 5$), scans all three keys, hits the end of the list, and reports absence. Keys hashing to the five empty slots are rejected after zero comparisons. The spread between these cases, and how it grows with the table's fullness, is what the next section quantifies. ### The load factor and expected search time Let $n$ be the number of keys stored in a table of $m$ slots. The ratio $$ \alpha = \frac{n}{m} $$ is the **load factor**, the average number of keys per slot. With chaining $\alpha$ may exceed $1$; it is the average chain length. To say anything about _expected_ chain length we need an assumption about how keys spread out. The standard one is **simple uniform hashing**: each key is equally likely to hash to any of the $m$ slots, independently of the others.[^erickson-hash] Under this assumption a chain has expected length $\alpha$, and a search examines on average $\alpha$ keys plus the cost of computing $h$ and indexing the table: > **Theorem.** Under simple uniform hashing, an unsuccessful search in a chained > hash table takes expected time $\Theta(1 + \alpha)$, and so does a successful > search. > **Proof.** _Unsuccessful:_ a search for an absent key $k$ scans the entire > chain $T[h(k)]$. Each of the $n$ stored keys lands in that slot with > probability $1/m$ independently, so the chain's expected length is $n/m = > \alpha$; add $\Theta(1)$ to compute $h(k)$, giving $\Theta(1 + \alpha)$. > > _Successful:_ suppose the key sought is equally likely to be any of the $n$ > stored keys, and let $k_i$ denote the $i$-th key inserted. Because inserts > prepend, the keys ahead of $k_i$ in its chain are precisely those inserted > _after_ it that hashed to the same slot. Searching for $k_i$ therefore > examines $1$ element for $k_i$ itself plus, in expectation, $(n - i)/m$ > later-inserted colliders. Averaging over which key we seek: > > $$ > \frac{1}{n}\sum_{i=1}^{n}\parens{1 + \frac{n-i}{m}} > = 1 + \frac{1}{nm}\sum_{i=1}^{n}(n-i) > = 1 + \frac{1}{nm}\cdot\frac{n(n-1)}{2} > = 1 + \frac{\alpha}{2} - \frac{\alpha}{2n}, > $$ > > which is $\Theta(1 + \alpha)$. $\qed$ The two bounds differ in their constants: an unsuccessful search scans a _whole_ chain (expected $\alpha$ keys), while a successful one scans on average about _half_ a chain ($1 + \alpha/2$), since the sought key sits somewhere in the middle of the insertion order. At $\alpha = 1$, a plausible operating point for a chained table, that is $2$ expected comparisons for a hit and about $1$ chain-length for a miss: constants small enough that the hash computation itself is often the dominant cost. If we keep the table size proportional to the number of keys, $m = \Theta(n)$ so $\alpha = O(1)$, then _every_ dictionary operation runs in [expected $\Theta(1)$ time](/algorithms/foundations/asymptotic-analysis). Keeping $\alpha$ bounded is the job of **dynamic resizing**: when $\alpha$ grows past a threshold (say $1$), allocate a table of double the size and rehash every key into it. A single resize costs $\Theta(n)$, but it is triggered only after $\Theta(n)$ cheap operations, so the _amortized_ cost per operation stays $O(1)$, the same doubling argument that makes a dynamic array's append amortized $O(1)$. ::impl{algo="chained_hash_table"} ## Collision resolution by open addressing Chaining stores keys outside the table. **Open addressing** stores every key _inside_ the array itself: there are no lists and no pointers, so $\alpha \le 1$ always. When a key's preferred slot is occupied, we **probe** a deterministic sequence of alternative slots until we find an empty one. The probe sequence is defined by extending the hash function with a probe number $i$: $$ h : U \times \set{0, 1, \dots, m-1} \to \set{0, 1, \dots, m-1}, $$ so the slots tried for key $k$ are $h(k,0), h(k,1), h(k,2), \dots$, which must form a permutation of all $m$ slots so that probing can examine every slot. ```algorithm caption: $\textsc{Hash-Insert}(T, k)$ — open addressing, returns the slot used $i \gets 0$ repeat $j \gets h(k, i)$ if $T[j] = \text{nil}$ then $T[j] \gets k$ return $j$ $i \gets i + 1$ until $i = m$ error "hash table overflow" ``` Search follows the _same_ probe sequence, stopping when it finds $k$ (success) or an empty slot (failure, since $k$ is not present, because insertion would have used that empty slot). Deletion is the awkward case: simply emptying a slot would break the probe chains of other keys, so deleted slots are marked with a special `deleted` sentinel that search skips over but insertion may reuse. Heavy deletion is the classic reason to prefer chaining. $$ % caption: Why deletion needs a tombstone. Keys $k_1,k_2,k_3$ probed into a run ending at % slot $5$. Erasing $k_2$ to $\text{nil}$ (top) would make a later search for % $k_3$ stop early at the gap; marking it $\textsc{deleted}$ (bottom) lets search % probe past while insertion may reuse the slot. \begin{tikzpicture}[ slot/.style={draw, minimum width=10mm, minimum height=7mm, font=\small, inner sep=1pt}, >=stealth] \definecolor{acc}{HTML}{2348F2} \foreach \name/\yy/\mid in {% {erase to nil}/{0}/{nil},% {tom\/bstone}/{-1.5}/{\textsc{del}}% }{ \begin{scope}[yshift=\yy cm] \node[font=\scriptsize, anchor=east] at (-0.4,0) {\name}; \node[slot] (a) at (0,0) {$k_1$}; \node[slot, right=0mm of a] (b) {\mid}; \node[slot, right=0mm of b] (c) {$k_3$}; \node[slot, right=0mm of c] (d) {}; \end{scope} } \node[font=\scriptsize, acc] at (5.0,0) {search $k_3$: stops at gap}; \node[font=\scriptsize, acc] at (5.4,-1.5) {search $k_3$: prob\/es past, found}; \draw[->, acc] (1.0,-1.05) to[bend left=40] (2.0,-1.05); \end{tikzpicture} $$ Three probing schemes are standard: - **Linear probing.** $h(k, i) = (h'(k) + i) \bmod m$ for an ordinary hash function $h'$. Simple and cache-friendly, but it suffers **primary clustering**: long runs of occupied slots build up and grow ever faster, since any key hashing anywhere into a run must walk to its end. $$ % caption: Primary clustering. A run of four occupied slots (shaded) absorbs any new key % whose hash $h'(k)$ lands on slot $3$, $4$, $5$, or $6$ — four of the eleven % slots, each forcing a walk to the run's right end at slot $7$ (accented arc). Every such % insertion lengthens the run, so clusters snowball: the bigger the run, the % likelier the next key extends it. \begin{tikzpicture}[ slot/.style={draw, minimum width=7mm, minimum height=7mm, font=\scriptsize, inner sep=0}, >=stealth] \definecolor{acc}{HTML}{2348F2} \foreach \j in {0,...,10} { \ifnum\j>2 \ifnum\j<7 \fill[black] ({\j*0.78-0.35},-0.35) rectangle ({\j*0.78+0.35},0.35); \fi\fi \node[slot] (c\j) at ({\j*0.78},0) {\j}; } % brace under the run \draw[black, thick] (3*0.78-0.35,-0.55) -- (3*0.78-0.35,-0.75) -- (6*0.78+0.35,-0.75) -- (6*0.78+0.35,-0.55); \node[black, font=\scriptsize, below] at (4.5*0.78,-0.78) {run of $4$: any hit here walks to slot $7$}; % probe arc from a hit at slot 4 to landing at 7 \draw[->, acc] (4*0.78,0.42) to[bend left=40] node[above, font=\scriptsize, fill=white, inner sep=1pt] {prob\/e} (7*0.78,0.42); \node[draw=acc, very thick, minimum width=7mm, minimum height=7mm, inner sep=0] at (7*0.78,0) {}; \end{tikzpicture} $$ - **Quadratic probing.** $h(k, i) = (h'(k) + c_1 i + c_2 i^2) \bmod m$. The quadratic step spreads probes out, eliminating primary clustering, but two keys with the same initial slot follow the _same_ sequence, a milder **secondary clustering**. The constants and $m$ must be chosen so the sequence hits every slot. - **Double hashing.** $h(k, i) = (h_1(k) + i \cdot h_2(k)) \bmod m$, using a second hash function to set the step size. Different keys with the same start get _different_ step sizes, so probe sequences rarely coincide. Double hashing comes closest to the ideal of **uniform hashing** (every key's probe sequence equally likely to be any of the $m!$ permutations), and is the strongest of the three. $$ % caption: Three probe sequences from $h'(k)=7$ in a table of size $m=11$ with slots % $\{0,7,8,10\}$ occupied (shaded). Labels $0,1,2,\dots$ give probe order; the % boxed slot is where the key lands. Linear walks $+1$ (lands $9$); quadratic % adds $i^2$ (lands $5$); double hashing steps by $h_2(k)=3$ (lands $2$). \begin{tikzpicture}[ slot/.style={draw, minimum width=6.5mm, minimum height=6.5mm, font=\scriptsize, inner sep=0}, pn/.style={font=\scriptsize, acc}, land/.style={draw=acc, very thick, minimum width=6.5mm, minimum height=6.5mm, inner sep=0}, >=stealth, node distance=0mm] \definecolor{acc}{HTML}{2348F2} \foreach \name/\yy/\occ/\probes/\landed in {% {linear}/{0}/{0,7,8,10}/{7/0,8/1,9/2}/{9},% {quadratic}/{-1.4}/{0,7,8,10}/{7/0,8/1,0/2,5/3}/{5},% {double $h_2{=}3$}/{-2.8}/{0,7,8,10}/{7/0,10/1,2/2}/{2}% }{ \begin{scope}[yshift=\yy cm] \node[font=\scriptsize, anchor=east] at (-0.3,0) {\name}; \foreach \o in \occ { \fill[black] ({\o*0.72-0.325},-0.325) rectangle ({\o*0.72+0.325},0.325); } \fill[acc!15] ({\landed*0.72-0.325},-0.325) rectangle ({\landed*0.72+0.325},0.325); \foreach \j in {0,...,10} { \node[slot] (c\j) at ({\j*0.72},0) {\j}; } \node[land] at ({\landed*0.72},0) {}; \foreach \s/\i in \probes { \node[pn, above=1mm] at ({\s*0.72},0.2) {\i}; } \end{scope} } \end{tikzpicture} $$ ### A full insertion trace Linear probing on the same five keys used for chaining shows the displacement mechanics end to end. Table size $m = 7$, $h'(k) = k \bmod 7$, keys $19, 26, 13, 48, 5$ in order: | insert | $h'(k)$ | probe sequence | lands in | probes | | --- | --- | --- | --- | --- | | $19$ | $5$ | $5$ | $5$ | $1$ | | $26$ | $5$ | $5, 6$ | $6$ | $2$ | | $13$ | $6$ | $6, 0$ | $0$ | $2$ | | $48$ | $6$ | $6, 0, 1$ | $1$ | $3$ | | $5$ | $5$ | $5, 6, 0, 1, 2$ | $2$ | $5$ | Two things happen that chaining never shows. First, the probe for $13$ steps off the right end of the table and wraps to slot $0$, the same modular arithmetic as a [circular buffer](/algorithms/data-structures/elementary-structures). Second, the cluster snowballs: after four inserts the run spans slots $5, 6, 0, 1$, so the fifth key, whose home slot merely _touches_ the run, must walk its entire length before finding an empty slot at $2$. Five keys in, a table that is $71\%$ full already costs five probes per insert, and a search for $5$ retraces the same five slots. $$ % caption: The cluster snowballing, one insert at a time ($m=7$, $h'(k)=k \bmod 7$). Small % accent numerals give each insert's probe order; the boxed slot is where the key % lands. Insert $13$ wraps past the table end to slot $0$; insert $5$ walks the % whole run $5,6,0,1$ before landing at $2$. \begin{tikzpicture}[ >=stealth, slot/.style={draw, minimum width=7.5mm, minimum height=7mm, font=\scriptsize, inner sep=0}, land/.style={draw=acc, very thick, minimum width=7.5mm, minimum height=7mm, inner sep=0}, pn/.style={font=\tiny, acc}] \definecolor{acc}{HTML}{2348F2} \foreach \row/\lbl/\filled/\keys/\probes/\landed in {% 0/{insert 19}/{5}/{5/19}/{5/1}/{5},% 1/{insert 26}/{5,6}/{5/19,6/26}/{5/1,6/2}/{6},% 2/{insert 13}/{0,5,6}/{0/13,5/19,6/26}/{6/1,0/2}/{0},% 3/{insert 48}/{0,1,5,6}/{0/13,1/48,5/19,6/26}/{6/1,0/2,1/3}/{1},% 4/{insert 5}/{0,1,2,5,6}/{0/13,1/48,2/5,5/19,6/26}/{5/1,6/2,0/3,1/4,2/5}/{2}% }{ \begin{scope}[yshift={-1.45*\row cm}] \node[font=\scriptsize, anchor=east] at (-0.55,0) {\lbl}; \foreach \f in \filled { \fill[acc!12] ({\f*0.75-0.375},-0.35) rectangle ({\f*0.75+0.375},0.35); } \foreach \j in {0,...,6} { \node[slot] at ({\j*0.75},0) {}; } \foreach \s/\k in \keys { \node[font=\scriptsize] at ({\s*0.75},0) {\k}; } \node[land] at ({\landed*0.75},0) {}; \foreach \s/\i in \probes { \node[pn] at ({\s*0.75},0.52) {\i}; } \foreach \j in {0,...,6} { \node[font=\tiny, black] at ({\j*0.75},-0.52) {\j}; } \end{scope} } \end{tikzpicture} $$ The final states of the two strategies, side by side on identical input, make the structural difference plain: chaining grows lists and leaves the table sparse, while open addressing keeps everything in the array at the cost of displaced keys sitting far from home. $$ % caption: The same f\/ive keys under both strategies. Chaining (left) leaves f\/ive of % seven slots empty and grows two lists. Linear probing (right) packs all keys % into the array; muted annotations mark each displaced key's home slot — four % of f\/ive keys sit away from home. \begin{tikzpicture}[ >=stealth, slot/.style={draw, minimum width=8mm, minimum height=7mm, font=\scriptsize, inner sep=0}, cell/.style={draw, minimum width=8mm, minimum height=6mm, fill=acc!12, font=\scriptsize}] \definecolor{acc}{HTML}{2348F2} % chaining, left \begin{scope} \node[font=\small] at (1.4,0.9) {chaining}; \foreach \j in {0,...,6} { \node[slot] (L\j) at (0,{-0.78*\j}) {\j}; } \node[cell] (c5a) [right=5mm of L5] {$5$}; \node[cell] (c5b) [right=4mm of c5a] {$26$}; \node[cell] (c5c) [right=4mm of c5b] {$19$}; \draw[->] (L5.east) -- (c5a.west); \draw[->] (c5a.east) -- (c5b.west); \draw[->] (c5b.east) -- (c5c.west); \node[cell] (c6a) [right=5mm of L6] {$48$}; \node[cell] (c6b) [right=4mm of c6a] {$13$}; \draw[->] (L6.east) -- (c6a.west); \draw[->] (c6a.east) -- (c6b.west); \end{scope} % open addressing, right \begin{scope}[xshift=6.6cm] \node[font=\small] at (1.2,0.9) {op\/en addressing}; \foreach \j/\k in {0/13,1/48,2/5,5/19,6/26} { \fill[acc!12] (-0.4,{-0.78*\j-0.35}) rectangle (0.4,{-0.78*\j+0.35}); } \foreach \j in {0,...,6} { \node[slot] (R\j) at (0,{-0.78*\j}) {}; } \foreach \j/\k in {0/13,1/48,2/5,5/19,6/26} { \node[font=\scriptsize] at (0,{-0.78*\j}) {\k}; } \node[font=\tiny, black, anchor=west] at (0.55,0) {home 6}; \node[font=\tiny, black, anchor=west] at (0.55,-0.78) {home 6}; \node[font=\tiny, black, anchor=west] at (0.55,-1.56) {home 5}; \node[font=\tiny, black, anchor=west] at (0.55,-4.68) {home 5}; \foreach \j in {0,...,6} { \node[font=\tiny, black, anchor=east] at (-0.55,{-0.78*\j}) {\j}; } \end{scope} \end{tikzpicture} $$ ### Cost of open addressing Under the uniform-hashing assumption, with load factor $\alpha = n/m < 1$, the expected number of probes is $$ \text{unsuccessful search:} \quad \frac{1}{1 - \alpha}, \qquad \text{successful search:} \quad \frac{1}{\alpha}\ln\frac{1}{1 - \alpha}. $$ Both bounds are worth deriving, because the derivations expose _why_ the costs behave so differently.[^clrs-open] > **Theorem (unsuccessful search).** Under uniform hashing with $\alpha < 1$, an > unsuccessful search makes at most $1/(1-\alpha)$ probes in expectation. > **Proof.** Let $X$ be the number of probes. The search makes an $i$-th probe > only if the first $i-1$ probes all hit occupied slots. The first probe hits an > occupied slot with probability $n/m$; given that, the second hits one of the > remaining $n-1$ occupied among $m-1$ unprobed slots, probability > $(n-1)/(m-1) < n/m$; and so on. Hence > > $$ > \Pr\brackets{X \ge i} > = \frac{n}{m}\cdot\frac{n-1}{m-1}\cdots\frac{n-i+2}{m-i+2} > \le \parens{\frac{n}{m}}^{i-1} = \alpha^{i-1}, > $$ > > and summing the tail probabilities gives a geometric series: > > $$ > \mathbb{E}[X] = \sum_{i=1}^{\infty} \Pr\brackets{X \ge i} > \le \sum_{i=1}^{\infty} \alpha^{i-1} > = \frac{1}{1-\alpha}. \qed > $$ The bound has a clean reading: with probability $1 - \alpha$ each probe is the last, so the probe count is dominated by a geometric random variable with success probability $1 - \alpha$. Inserting a key costs the same, since insertion is an unsuccessful search that writes into the empty slot it finds. > **Theorem (successful search).** Under uniform hashing, a successful search > makes at most $\frac{1}{\alpha}\ln\frac{1}{1-\alpha}$ probes in expectation. > **Proof (sketch).** Searching for a key retraces the probes made when it was > inserted. If $k$ was the $(i+1)$-st key inserted, its insertion was an > unsuccessful search in a table of load $i/m$, costing at most $\frac{1}{1 - > i/m} = \frac{m}{m-i}$ expected probes. Averaging over the $n$ keys: > > $$ > \frac{1}{n}\sum_{i=0}^{n-1}\frac{m}{m-i} > = \frac{1}{\alpha}\sum_{j=m-n+1}^{m}\frac{1}{j} > \le \frac{1}{\alpha}\int_{m-n}^{m}\frac{dx}{x} > = \frac{1}{\alpha}\ln\frac{m}{m-n} > = \frac{1}{\alpha}\ln\frac{1}{1-\alpha}. \qed > $$ The asymmetry between the two results is the practical takeaway. Plug in numbers: at $\alpha = 0.5$, an unsuccessful search expects $2$ probes and a successful one $2\ln 2 \approx 1.39$; at $\alpha = 0.9$, an unsuccessful search expects $10$ probes while a successful one expects only $\frac{1}{0.9}\ln 10 \approx 2.56$. Hits stay cheap even in a crowded table, because most keys were inserted while the table was still relatively empty and therefore sit early in their probe sequences. Misses (and inserts) pay the full $1/(1-\alpha)$, which explodes as $\alpha \to 1$. Open addressing is fast only when the table is kept comfortably below full; a practical rule of thumb is to resize once $\alpha$ exceeds about $0.7$. These formulas assume ideal uniform hashing, which double hashing approximates well. Linear probing is measurably worse because of primary clustering: its expected probe counts are roughly $\frac{1}{2}\parens{1 + \frac{1}{(1-\alpha)^2}}$ for an unsuccessful search and $\frac{1}{2}\parens{1 + \frac{1}{1-\alpha}}$ for a successful one. At $\alpha = 0.9$ that is about $50$ probes per miss instead of $10$, a $5\times$ penalty for the same load. Its saving grace is the cache: the probed slots are adjacent, so those $50$ probes may touch only a handful of cache lines while double hashing's $10$ probes take $10$ misses. On modern hardware, linear probing at moderate load ($\alpha \le 0.5$, where the formulas give $\le 2.5$ probes) is often the fastest scheme in practice. The three strategies, summarized at a glance: | | chaining | linear probing | double hashing | | --- | --- | --- | --- | | expected miss cost | $1 + \alpha$ | $\tfrac{1}{2}\parens{1 + \tfrac{1}{(1-\alpha)^2}}$ | $\tfrac{1}{1-\alpha}$ | | expected hit cost | $1 + \tfrac{\alpha}{2}$ | $\tfrac{1}{2}\parens{1 + \tfrac{1}{1-\alpha}}$ | $\tfrac{1}{\alpha}\ln\tfrac{1}{1-\alpha}$ | | load factor range | any ($\alpha > 1$ fine) | $\alpha < 1$, keep $\le 0.5$ | $\alpha < 1$, keep $\le 0.7$ | | deletion | $O(1)$ splice | tombstones | tombstones | | cache behavior | poor (pointer chasing) | excellent | moderate | | space overhead | one pointer per key | none | none | Chaining degrades _gracefully_ (linearly in $\alpha$) and deletes cleanly; open addressing wins on memory and locality but demands headroom and careful deletion. That tension is why both families appear in standard libraries. $$ % caption: Expected probes for an unsuccessful search against load factor $\alpha$. % Chaining's $1+\alpha$ (muted) stays linear; open addressing's $1/(1-\alpha)$ % (accent) is flat while the table is half-empty, turns sharply upward near the % resize threshold $\alpha=0.7$ (dashed), and diverges as $\alpha\to 1$ — the % reason open addressing must never run near full. \begin{tikzpicture}[>=stealth, x=7cm, y=0.42cm] \definecolor{acc}{HTML}{2348F2} \useasboundingbox (-0.18,-1.2) rectangle (1.32,12.6); % axes \draw[->] (0,0) -- (1.05,0) node[right, font=\small] {load factor}; \draw[->] (0,0) -- (0,11) node[above, font=\small] {probes}; \foreach \a in {0,0.5,1} { \node[font=\scriptsize, below] at (\a,0) {\a}; } \foreach \p in {2,5,10} { \draw[black] (0,\p) -- (1,\p); \node[font=\scriptsize, left=1mm] at (0,\p) {\p}; } % resize threshold \draw[black, dashed] (0.7,0) -- (0.7,10); \node[font=\scriptsize, black, anchor=south, align=center] at (0.7,10) {resize\\at 0.7}; % open addressing: 1/(1-a), sampled to a=0.9 \draw[acc, very thick, samples=60, domain=0:0.9, smooth] plot (\x, {1/(1-\x)}); \node[acc, font=\scriptsize, anchor=east] at (0.67,4.6) {op\/en addressing}; % chaining: 1 + a \draw[black, thick, domain=0:1] plot (\x, {1+\x}); \node[black, font=\scriptsize, anchor=north west] at (0.79,1.55) {chaining}; % markers \fill[acc] (0.5,2) circle (1.1pt); \fill[acc] (0.9,10) circle (1.1pt); \end{tikzpicture} $$ ::impl{algo="open_addressing_hash_table"} ## Resizing and rehashing Every bound in this lesson conditions on $\alpha$ staying moderate, and **resizing** is the mechanism that enforces it. When the load factor crosses its threshold ($1$ is a common trigger for chaining, around $0.5$ for linear probing, $0.7$ for double hashing), allocate a new table roughly twice the size, for the division method the next prime past $2m$, and re-insert every key. The keys cannot simply be copied across: $h(k)$ _depends on_ $m$, so growing the table changes every key's home slot. Each key is **rehashed**, its hash recomputed against the new modulus, and inserted fresh. Continuing the running example, growing from $m = 7$ to the prime $m = 17$ sends the five keys to entirely new homes: $$ 19 \bmod 17 = 2, \quad 26 \bmod 17 = 9, \quad 13 \bmod 17 = 13, \quad 48 \bmod 17 = 14, \quad 5 \bmod 17 = 5. $$ All five now land in distinct slots, so the probe-displaced keys of the crowded table return to their home positions and every chain (or run) dissolves. $$ % caption: Rehashing on growth. The crowded $m=7$ open-addressed table (top, % $\alpha\approx 0.71$, four keys displaced from home) is rebuilt into $m=17$ % (bottom, $\alpha\approx 0.29$): every key's hash is recomputed against the new % modulus, and all f\/ive land in distinct home slots. \begin{tikzpicture}[ slot/.style={draw, minimum width=6.2mm, minimum height=6.2mm, font=\scriptsize, inner sep=0}] \definecolor{acc}{HTML}{2348F2} % old table m=7 \node[font=\scriptsize, anchor=east] at (-0.55,0) {old, m=7}; \foreach \j/\k in {0/13,1/48,2/5,5/19,6/26} { \fill[acc!12] ({\j*0.62-0.31},-0.31) rectangle ({\j*0.62+0.31},0.31); } \foreach \j in {0,...,6} { \node[slot] at ({\j*0.62},0) {}; } \foreach \j/\k in {0/13,1/48,2/5,5/19,6/26} { \node[font=\scriptsize] at ({\j*0.62},0) {\k}; } \foreach \j in {0,...,6} { \node[font=\tiny, black] at ({\j*0.62},-0.52) {\j}; } % new table m=17 \begin{scope}[yshift=-1.9cm] \node[font=\scriptsize, anchor=east] at (-0.55,0) {new, m=17}; \foreach \j/\k in {2/19,5/5,9/26,13/13,14/48} { \fill[acc!12] ({\j*0.62-0.31},-0.31) rectangle ({\j*0.62+0.31},0.31); } \foreach \j in {0,...,16} { \node[slot] at ({\j*0.62},0) {}; } \foreach \j/\k in {2/19,5/5,9/26,13/13,14/48} { \node[font=\scriptsize] at ({\j*0.62},0) {\k}; } \foreach \j in {0,2,5,9,13,14,16} { \node[font=\tiny, black] at ({\j*0.62},-0.52) {\j}; } \end{scope} \end{tikzpicture} $$ A resize costs $\Theta(n + m)$: touch every key, plus scan the old table. It is still cheap on average, by the same argument that gives a dynamic array its [amortized $O(1)$ append](/algorithms/data-structures/elementary-structures): after doubling, the table holds $n$ keys with capacity for about $2n$, so at least $\Theta(n)$ cheap inserts must occur before the next resize, and the $\Theta(n)$ rebuild spreads to $O(1)$ per insert. Shrinking mirrors growth with hysteresis, rebuilding smaller only when $\alpha$ falls to something like $1/4$ of the threshold, so a workload oscillating at the boundary cannot trigger a rebuild per operation. Rehashing also serves a second purpose for open-addressed tables: it is the only way to _clear tombstones_. A `deleted` marker still lengthens probe sequences, since searches must walk past it, so the cost of operations is governed by the **effective load**, occupied slots _plus_ tombstones, over $m$. A long-lived table under heavy insert/delete churn can have few live keys yet terrible searches, its array full of tombstones. The standard policy tracks both counts and rebuilds, at the same size or smaller, once tombstones exceed a fixed fraction of the table, restoring the true load factor. When deletions dominate the workload and rebuilds are unwelcome, chaining, whose deletes are genuine $O(1)$ splices with nothing left behind, is the safer default. ## What makes a hash function good Simple uniform hashing is an _assumption_; a real hash function must approximate it on real data. A good $h$ should scatter keys so that any regularities in the input, such as sequential integers, common prefixes, or similar strings, do not pile up in the same slots. Two classic constructions: - **The division method.** $h(k) = k \bmod m$. Fast, but sensitive to $m$: choosing $m$ a power of $2$ makes $h$ depend only on the low bits of $k$, and values near a power of $10$ are bad for decimal data. A prime $m$ not close to a power of $2$ is the safe choice. - **The multiplication method.** $h(k) = \floor{m \cdot (kA \bmod 1)}$ for a constant $0 < A < 1$ ($A = (\sqrt{5}-1)/2$ is a good choice). It is insensitive to the value of $m$, so $m$ can be a power of $2$ for fast bit shifts. For string keys, treat the string as a base-$b$ number and fold it down, e.g. Horner's rule, $h = (h \cdot b + c) \bmod m$ over the characters $c$, so that every character and its position influence the result.[^skiena-hash] Skiena stresses the engineer's view: a hash function turns an arbitrary key into a pseudo-random slot, and the quality of that pseudo-randomness is what protects the $O(1)$ bound. ::impl{algo="hash_functions"} ## Universal hashing: a guarantee against every input Any _fixed_ hash function has a weakness: there exists a set of keys that all collide, and an adversary (or merely unlucky data) can hand it to us, degrading every operation to $\Theta(n)$. **Universal hashing** avoids this by choosing $h$ _at random_ from a carefully designed family $\mathcal{H}$ of hash functions at runtime, so no single input is bad for all choices. > **Definition (universal family).** A family $\mathcal{H}$ of functions from $U$ > to $\set{0,\dots,m-1}$ is **universal** if, for every pair of distinct keys > $k \ne \ell$, > > $$ > \Pr_{h \in \mathcal{H}}\brackets{h(k) = h(\ell)} \le \frac{1}{m}, > $$ > > where the probability is over the random choice of $h$. That is, a randomly chosen $h$ collides any fixed pair no more often than picking two random slots would. This single property suffices to prove that, for _any_ input set of keys, the expected length of the chain holding a given key is at most $1 + \alpha$, recovering the $\Theta(1 + \alpha)$ bound _without_ assuming anything about the data.[^clrs-universal] The randomness lives in our coin flips, not in an assumption about the world. > **Theorem.** If $h$ is drawn from a universal family and $n$ keys are stored > in $m$ slots by chaining, then for any key $k$ the expected number of keys in > $k$'s chain is at most $1 + \alpha$. > **Proof.** For each stored key $\ell \ne k$, let $X_\ell$ be the indicator > that $h(\ell) = h(k)$. Universality gives $\mathbb{E}[X_\ell] = > \Pr\brackets{h(\ell) = h(k)} \le 1/m$. The chain holding $k$ contains $k$ > itself plus the colliding keys, so by linearity of expectation its expected > size is at most > > $$ > 1 + \sum_{\ell \ne k} \mathbb{E}[X_\ell] > \;\le\; 1 + \frac{n}{m} > \;=\; 1 + \alpha. \qed > $$ The proof is two lines of linearity, which is the point: universality is the _weakest_ property that makes the chaining analysis go through, so it is the right definition. No adversary can defeat it, because a bad input would have to be chosen after our random draw of $h$. A concrete universal family: pick a prime $p > |U|$, draw random $a \in \set{1,\dots,p-1}$ and $b \in \set{0,\dots,p-1}$, and set $$ h_{a,b}(k) = \parens{(a k + b) \bmod p} \bmod m. $$ The collection $\set{h_{a,b}}$ over all valid $a, b$ is universal. > **Proof (sketch).** Fix distinct keys $k \ne \ell$ and let $r = (ak + b) \bmod > p$ and $s = (a\ell + b) \bmod p$. First, $r \ne s$: their difference satisfies > $r - s \equiv a(k - \ell) \pmod{p}$, and neither $a$ nor $k - \ell$ is > divisible by the prime $p$, so the product is not either. Second, the map from > $(a, b)$ to $(r, s)$ is a bijection onto ordered pairs of _distinct_ values > (given $(r,s)$ one can solve uniquely for $a$ then $b$), so a random $(a,b)$ > makes $(r,s)$ a uniformly random distinct pair. A collision $h_{a,b}(k) = > h_{a,b}(\ell)$ happens only if $r \equiv s \pmod{m}$, and for any fixed $r$ > the number of values $s \ne r$ in $\set{0,\dots,p-1}$ congruent to $r$ modulo > $m$ is at most $\ceil{p/m} - 1 \le (p-1)/m$. Dividing by the $p - 1$ > equally likely choices of $s$ gives collision probability at most $1/m$. > $\qed$ To use the family, pick $a$ and $b$ once, at table-creation time, and keep them for the table's lifetime (rehashing on resize is a natural moment to redraw them). A tiny instance: with $p = 17$ and $m = 7$, the keys $k = 1$ and $\ell = 8$ collide under $h_{1,0}$ (since $1 \bmod 7 = 8 \bmod 7 = 1$) but not under $h_{3,4}$ (which sends them to $(7 \bmod 17) \bmod 7 = 0$ and $(28 \bmod 17) \bmod 7 = 4$). No fixed pair is unlucky for more than a $1/m$ fraction of the draws, so an adversary who knows the family, but not the draw, cannot manufacture collisions. Universal hashing is the rigorous foundation under the everyday claim that "hashing is $O(1)$": it is $O(1)$ _in expectation, on every input_, precisely because we randomize the hash function. ::impl{algo="universal_hashing"} ## Modern hashing Two developments past the textbook show up throughout real systems. **Worst-case constant lookups.** Chaining and open addressing give expected $O(1)$, but a long chain can still slow a query. **Cuckoo hashing** (Pagh and Rodler, 2001) uses two hash functions, guaranteeing each key sits in one of _two_ fixed slots, so lookup is worst-case $O(1)$; inserts may relocate a resident key, but the read path is unconditionally fast. **Robin Hood hashing** and Swiss Tables (`absl::flat_hash_map`) reach the same goal from open addressing, equalizing probe lengths to stay fast at high load. **Consistent hashing.** When the table is a _cluster_ of servers, ordinary $h(k) \bmod m$ is catastrophic: changing $m$ rehashes nearly every key. **Consistent hashing** (Karger et al., 1997) maps keys and servers onto a circle and assigns each key to the next server clockwise, so adding or removing a server moves only $O(1/m)$ of the keys, the same collision-management problem lifted from one array to a fleet of machines.[^btb-hash] ## Takeaways - A **hash table** implements the **dictionary** ADT — insert, search, delete — in expected $O(1)$ time by mapping keys into an array with a **hash function**, trading away the ordered queries a search tree supports. - **Direct addressing** is perfect but needs one slot per possible key; hashing shrinks the table to $\Theta(n)$ and resolves the resulting **collisions**. - **Chaining** keeps a list per slot (search cost $\Theta(1 + \alpha)$); **open addressing** stores keys in the array and probes (linear, quadratic, or double hashing), with cost governed by $1/(1-\alpha)$. - Keeping the **load factor** $\alpha = n/m$ bounded, via resizing, keeps every operation expected $O(1)$. - A good hash function scatters structured keys; **universal hashing** randomizes the choice of $h$ so the $O(1)$ expectation holds against _every_ input, not just under an assumption. [^clrs-hash]: **CLRS**, Ch. 11 — Hash Tables (§11.1–11.2): the dictionary ADT and the expected $O(1)$ guarantee from hashing. [^erickson-hash]: **Erickson**, Ch. 5 — Hash Tables: the simple uniform hashing assumption and expected chain length. [^clrs-open]: **CLRS**, Ch. 11 — Hash Tables (§11.4): open addressing and the expected-probe bounds $1/(1-\alpha)$ (unsuccessful) and $\frac{1}{\alpha}\ln\frac{1}{1-\alpha}$ (successful) under uniform hashing. [^skiena-hash]: **Skiena**, §3.7 — Hashing and Strings: hashing string keys via Horner's-rule polynomial evaluation. [^clrs-universal]: **CLRS**, Ch. 11 — Hash Tables (§11.3.3): universal families and the $\Theta(1+\alpha)$ bound without distributional assumptions. [^btb-hash]: Pagh & Rodler, "Cuckoo hashing" (2001); Celis, "Robin Hood hashing" (1986); Karger, Lehman, Leighton, Panigrahy, Levine & Lewin, "Consistent hashing and random trees" (1997).