Proofs: FKS perfect hashing

FKS perfect hashing builds in O(n) expected time and uses O(n) space full

This proof shows: time.expected, space.extra.

We use one fact about the family $h_{a,b,m}(x) = ((ax + b) \bmod p) \bmod m$, with $a$ uniform in $\{1, \ldots, p - 1\}$ and $b$ uniform in $\{0, \ldots, p - 1\}$:

(U) For each $m \ge 1$ and each two distinct keys $x \ne y$ of $\{0, \ldots, p - 1\}$, $\Pr[h_{a,b,m}(x) = h_{a,b,m}(y)] \le 1/m$.

This is the universality of the Carter and Wegman family, proved in CLRS, Section 11.3 (fourth edition) and Section 11.3.3 (third edition). The model is the word RAM with $p < 2^w$, so each hash value costs $O(1)$.

Lemma 1 (collisions). Let $X \subseteq \{0, \ldots, p - 1\}$ have $k$ keys, let $h = h_{a,b,m}$ be random, and let $C$ be the number of unordered pairs $\{x, y\} \subseteq X$ with $x \ne y$ and $h(x) = h(y)$. Then $E[C] \le \binom{k}{2} / m$.

Proof. $C$ is the sum, over the $\binom{k}{2}$ pairs, of the indicator of the event $h(x) = h(y)$. By (U), each indicator has expectation at most $1/m$. By linearity of expectation, $E[C] \le \binom{k}{2}/m$. $\square$

Lemma 2 (sum of squares). If the buckets of $h$ on $X$ have sizes $k_0, \ldots, k_{m-1}$, then $\sum_j k_j^2 = k + 2C$.

Proof. For each integer $t \ge 0$, $t^2 = t + 2 \binom{t}{2}$. Bucket $j$ contains $\binom{k_j}{2}$ colliding pairs, and each colliding pair lies in exactly one bucket, so $C = \sum_j \binom{k_j}{2}$. Summing $k_j^2 = k_j + 2\binom{k_j}{2}$ over $j$ and using $\sum_j k_j = k$ gives the claim. $\square$

Claim 1 (first level). One trial of lines L3 to L5 succeeds with probability more than $1/2$.

Proof. If $n = 0$, the sum is $0 \le 0$ and the trial succeeds. Let $n \ge 1$, so $m = n$. By Lemmas 1 and 2, $E[\sum_j n_j^2] = n + 2E[C] \le n + 2 \binom{n}{2}/n = n + (n - 1) = 2n - 1$. The sum is a non-negative random variable, so by Markov's inequality $\Pr[\sum_j n_j^2 > 4n] \le \Pr[\sum_j n_j^2 \ge 4n] \le (2n - 1)/(4n) < 1/2$. $\square$

Claim 2 (second level). For a bucket with $n_j \ge 1$ keys and $m_j = n_j^2$, one trial of lines L9 and L10 succeeds with probability more than $1/2$.

Proof. If $n_j = 1$, there is no pair and each trial succeeds. Let $n_j \ge 2$, and let $C_j$ be the number of colliding pairs of $S_j$ under $h_j$. The choice of $h_j$ is independent of the choice of $h$, and $S_j$ is fixed once $h$ is fixed, so Lemma 1 applies to $X = S_j$: $E[C_j] \le \binom{n_j}{2}/n_j^2 = (n_j - 1)/(2 n_j) < 1/2$. $C_j$ is a non-negative integer, so by Markov's inequality $\Pr[C_j \ge 1] \le E[C_j] < 1/2$. The trial succeeds exactly when $C_j = 0$. $\square$

Theorem (time and space). FKS-BUILD runs in $O(n)$ expected time. The structure has at most $4n$ second-level slots and $O(n)$ words in total, in every run.

Proof. Space. The loop of lines L2 to L5 ends only when $\sum_j n_j^2 \le 4n$, and $\sum_j m_j = \sum_j n_j^2$. The first level stores $m = \max(n, 1)$ triples $(m_j, a_j, b_j)$ and the pair $(a, b)$. So the total is at most $4n + 3\max(n, 1) + 2 = O(n)$ words.

Time of the first level. A trial costs $O(n + m) = O(n + 1)$: one hash value for each key, and $m$ lists. By Claim 1 and the geometric distribution of the number of trials, the expected number of trials is less than 2. So the first level takes $O(n + 1)$ expected time.

Time of the second level. Condition on the accepted $h$, so that the sizes $n_j$ are fixed with $\sum_j n_j^2 \le 4n$. Bucket $j$ costs $O(1 + m_j)$ for line L7, and $O(n_j)$ for each trial of lines L9 and L10, since a trial writes at most $n_j$ slots and clears the ones it wrote. By Claim 2, the expected number of trials is less than 2. Line L11 costs $O(n_j)$. So the expected cost of bucket $j$ is $O(1 + m_j + n_j)$, and, by linearity of expectation, the second level costs $O(m + \sum_j m_j + n) = O(n + 1)$ in expectation, for each accepted $h$. Taking the expectation over $h$ keeps the bound.

Adding the two levels gives $O(n + 1)$ expected time, which is $O(n)$ for $n \ge 1$. $\blacksquare$

Search. FKS-SEARCH evaluates two hash functions and reads two arrays, so it takes $O(1)$ time in every case.

FKS-SEARCH answers membership correctly, and FKS-BUILD ends with probability 1 full

This proof shows: correctness, termination.

Let $S \subseteq \{0, \ldots, p - 1\}$ be a set of $n$ distinct keys, with $p$ prime. We write $n_j = |S_j|$ for the size of bucket $j$ after the loop of lines L2 to L5.

Lemma 1 (the stored table). When FKS-BUILD returns, for each $j$ with $n_j > 0$, the array $T_j$ holds exactly the keys of $S_j$, and each $x \in S_j$ is in the slot $T_j[h_j(x)]$. For each $j$ with $n_j = 0$, $m_j = 0$.

Proof. Fix $j$. Line L7 sets $m_j = n_j^2$, so $m_j = 0$ exactly when $n_j = 0$. If $n_j > 0$, the loop of lines L9 and L10 ends only with a function $h_j$ that gives distinct slots to distinct keys of $S_j$. Line L11 writes each $x \in S_j$ to $T_j[h_j(x)]$. Two keys of $S_j$ never write the same slot, so no write is lost, and after line L11 the slots of $T_j$ that are not NIL hold exactly the $n_j$ keys of $S_j$. No later step changes $T_j$. $\square$

Theorem 1 (search). After FKS-BUILD$(S)$, FKS-SEARCH$(x)$ returns true if $x \in S$ and false if $x \notin S$, for each $x \in \{0, \ldots, p - 1\}$.

Proof. Let $j = h(x)$, the value of line L12.

Case $x \in S$. By line L4, $x \in S_j$, so $n_j \ge 1$ and $m_j \ge 1$, and line L13 does not return. By Lemma 1, $T_j[h_j(x)] = x$, so line L14 returns true.

Case $x \notin S$. If $m_j = 0$, line L13 returns false. Else, by Lemma 1, the slot $T_j[h_j(x)]$ holds NIL or a key of $S_j \subseteq S$. Neither is equal to $x$, since $x \notin S$. So line L14 returns false. $\square$

Theorem 2 (termination). FKS-BUILD ends with probability 1, and the expected number of trials of each loop is less than 2.

Proof. The complexity proof shows that one trial of lines L3 to L5 meets the test of line L5 with probability $q > 1/2$, and that, for each $j$ with $n_j > 0$, one trial of lines L9 and L10 meets the test of line L10 with probability $q_j > 1/2$. The trials of one loop use independent random choices, so the probability that the first $t$ trials all fail is $(1 - q)^t < 2^{-t}$, which tends to 0. So each loop ends with probability 1, and the number of its trials has a geometric distribution with mean $1/q < 2$ (or $1/q_j < 2$). There are $m + 1$ loops, a finite number, so the build ends with probability 1. $\blacksquare$