Proofs: CHD perfect hashing

CHD evaluates in O(1) time, uses O(n) words, and builds in O(n) expected time in an idealized model sketch

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

The model is the word RAM, with keys and hash values of $O(1)$ words. Let $\lambda = n/r$ be the average bucket size and $\alpha = n/m$ the load.

Claim 1 (evaluation). CHD-EVAL takes $O(1)$ time in the worst case.

Proof. Lines L12 and L13 compute $g$, $f_1$ and $f_2$ once each, read $\sigma[i]$, and do one division, one multiplication, two additions and one reduction. With $\sigma$ stored as a plain array, the read is one memory access. $\square$

Claim 2 (plain space). The function takes $r + O(1)$ words: the array $\sigma$ of $r = \lceil n/\lambda \rceil$ entries, each less than $m^2$, and the descriptions of $g$, $f_1$ and $f_2$. For a constant $\lambda$ this is $O(n)$ words. The build uses $O(n + m + r)$ more words for the buckets and the marks of the slots. $\square$

Lemma 3 (cost of one attempt). One attempt of lines L2 to L9 takes $O(n + m + r + \sum_i |B_i| \, t_i)$ time, where $t_i$ is the number of indices that line L7 tests for bucket $i$.

Proof. Line L3 takes $O(n + r)$ time. Line L4 takes $O(m)$. The order of line L5 is a sort of $r$ sizes between 0 and $n$, which counting sort does in $O(n + r)$. One test of line L7 computes $|B_i|$ slots, and checks that they are free and distinct in $O(|B_i|)$ time: it puts a temporary mark on each slot, stops at a slot that is used or already marked, and then removes the temporary marks. Line L9 takes $O(|B_i| + 1)$. Summing over the buckets gives the claim. $\square$

Lemma 4 (expected trials, idealized model). Assume that $g$ is fully random, and that for each bucket the slot vectors $(s_\ell(x))_{x \in B_i}$ for $\ell = 0, 1, 2, \ldots$ are independent, each with independent uniform entries in $[m]$, and independent of everything that happens before the bucket is placed. Let $\alpha \le \alpha_0 < 1$ for a constant $\alpha_0$, and ignore the cap $\ell < m^2$. Then $E[\sum_i |B_i| \, t_i] \le n c \, e^{\lambda (c - 1)}$, where $c = 1/(1 - \alpha_0)$.

Proof. Consider bucket $i$ with $k = |B_i| \ge 1$ keys, and let $u$ be the number of used slots when it is placed. The buckets not yet placed hold at least the $k$ keys of $B_i$, so $u \le n - k$. A test succeeds when $k$ independent uniform slots are distinct and free, which has probability

since each factor is at least $m - u - k + 1 \ge m - n + 1$. The tests are independent, so $t_i$ is geometric and $E[t_i \mid g] \le c^k$. So $E[\sum_i |B_i| t_i \mid g] \le \sum_i |B_i| c^{|B_i|}$. For fully random $g$, each $|B_i|$ is binomial with $n$ trials and success probability $1/r$, and for such a $K$, $E[K c^K] = (n/r) \, c \, (1 + (c - 1)/r)^{n - 1} \le \lambda c \, e^{(c - 1) n / r}$. Summing over the $r$ buckets gives $r \lambda c \, e^{\lambda (c - 1)} = n c \, e^{\lambda (c - 1)}$. $\square$

For constant $\lambda$ and $\alpha_0$, Lemmas 3 and 4 give $O(n + m) = O(n)$ expected time for one attempt in the idealized model. An attempt fails only if some bucket needs more than $m^2$ tests, which by Markov's inequality has probability at most $n c \, e^{\lambda(c - 1)} / m^2$, less than $1/2$ once $m$ is large enough. Then the expected number of attempts is at most 2, and the expected build time is $O(n)$.

What is a sketch here. Three steps are not proved on this page.

1. The idealized model. The real slot vectors $s_\ell$ for different $\ell$ are built from the same values $f_1(x)$ and $f_2(x)$, so they are not independent: the indices with the same $d_0$ are cyclic shifts of each other. The analysis of Belazzougui, Botelho and Dietzfelbinger (ESA 2009, LNCS 5757, pages 682 to 693) treats the hash functions as fully random and analyzes the scheme with its own assumptions; we do not reproduce it. The bound of Lemma 4 also grows like $e^{\lambda \alpha_0/(1 - \alpha_0)}$ and does not use the order of line L5; the paper's analysis of the placement in order of decreasing size gives much better constants.
2. The compressed space. The statement that the compressed $\sigma$ takes about 2 bits for each key, close to the lower bound for perfect hash functions, is from the same paper (its abstract gives about 1.4 bits for each key for $m = 1.23n$ and about 1.98 bits for $m = 1.01n$), together with the $O(1)$ access time of its compressed code.
3. The minimal case $m = n$. Lemma 4 needs $\alpha_0 < 1$. With $m = n$, the last buckets are placed in a table with very few free slots; a bucket of one key still always fits within $m$ tests, by the index $\ell = (t - f_1(x)) \bmod m$ for a free slot $t$, but no bound for buckets of two or more keys is proved here.

CHD-BUILD returns a perfect hash function, minimal when m = n, and ends with probability 1 for fully random hash functions full

This proof shows: correctness, termination.

Let $S$ be a set of $n$ distinct keys, let $m \ge \max(n, 1)$, and let $r \ge 1$. For an index $\ell \in \{0, \ldots, m^2 - 1\}$ write $s_\ell(x) = (f_1(x) + \lfloor \ell/m \rfloor f_2(x) + (\ell \bmod m)) \bmod m$. Then CHD-EVAL$(x) = s_{\sigma[g(x)]}(x)$, by lines L12 and L13.

Lemma 1 (invariant of the placement loop). Fix one attempt, that is, one pass of lines L2 to L9 with fixed $g$, $f_1$ and $f_2$. After each bucket that line L9 places, the following holds. Let $P$ be the set of buckets placed so far. The slots $s_{\sigma[i]}(x)$, for $i \in P$ and $x \in B_i$, are pairwise distinct, and the used slots are exactly these slots.

Proof. By induction on the buckets in the order of line L5. Before the first one, $P$ is empty and line L4 marks all slots free. Suppose the claim holds for $P$, and line L9 places bucket $i$ with index $\ell$. The loop of line L7 stopped at $\ell < m^2$ (otherwise line L8 would have left the loop), so its condition was false: the slots $s_\ell(x)$, $x \in B_i$, are pairwise distinct and none of them is used. By the hypothesis, the used slots are those of the keys of $P$, so the new slots are also distinct from all of these. Line L9 sets $\sigma[i] = \ell$ and marks exactly the new slots, so the claim holds for $P \cup \{i\}$. An empty bucket is placed with $\ell = 0$ and adds no slot. $\square$

Theorem 1 (the output is perfect). If CHD-BUILD returns, then CHD-EVAL maps $U$ into $[m]$, is one to one on $S$, and, when $m = n$, maps $S$ onto $[n]$.

Proof. Each value is reduced mod $m$, so it is in $[m]$. CHD-BUILD returns only after an attempt in which line L8 never set ok to false, so every bucket was placed. The buckets $B_0, \ldots, B_{r-1}$ partition $S$, since each key lies in exactly the bucket $g(x)$. By Lemma 1 with $P = [r]$, the slots $s_{\sigma[g(x)]}(x)$ for $x \in S$ are pairwise distinct, and these are the values of CHD-EVAL. So CHD-EVAL is one to one on $S$. If $m = n$, its $n$ distinct values on $S$ lie in a set of $n$ elements, so they are all of $[n]$. $\square$

Lemma 2 (a sufficient condition). If $f_1$ is one to one on $S$, the attempt succeeds.

Proof. We show that every bucket is placed with $\ell = 0$, the first index that line L7 tests. For $\ell = 0$, $s_0(x) = f_1(x)$. When bucket $i$ comes, the values $f_1(x)$ for $x \in B_i$ are pairwise distinct. By Lemma 1 the used slots are the values $f_1(y)$ of the keys $y$ of the buckets already placed, all different from the keys of $B_i$, so none of them equals any $f_1(x)$, $x \in B_i$. So the condition of line L7 is false at $\ell = 0$. $\square$

Theorem 2 (termination). If each attempt draws $f_1$ uniformly from all functions $U \to [m]$, independently of the earlier attempts, then CHD-BUILD ends with probability 1, after at most $m^n (m - n)!/m!$ attempts in expectation.

Proof. Each attempt runs at most $r$ buckets with at most $m^2$ values of $\ell$ each, so it ends. By Lemma 2, it succeeds when $f_1$ is one to one on $S$, which happens with probability $q = m(m - 1) \cdots (m - n + 1)/m^n > 0$ since $m \ge n$. The attempts are independent, so the number of attempts is at most a geometric random variable with mean $1/q$, which is finite. $\square$

The bound of Theorem 2 is very weak; it only shows that the restart loop cannot run forever. The expected number of attempts in practice is close to 1, see the complexity proof. For the polynomials of degree 2 of the Python version, Theorem 1 still holds, since it does not depend on how the functions are chosen, but Theorem 2 is not proved.