k-Perfect Hashing: Theory, Practice, and Applications

In order to give a lower bound on the space usage of a minimal perfect hash function, we assume that the set of keys \(K\) is a uniform random subset of size \(n=|K|\) of a large universe \(U\) of size \(u=|U|\) with \(u\gg n^2\). (This restriction is needed to avoid cases like \(u=n\), where the MPHF can simply be the identity, and implies via the birthday paradox that random hash collisions between the \(n\) keys are rare.) The construction algorithm takes as input the set \(K\), and then outputs some function \(f_S: K \mapsto [n]\). We are interested in the entropy of the state (seed) \(s\) of \(f\).

The total number of inputs (keys sets) is \(X := \binom un\). On the other hand, a single function \(f_s\) is an MPHF for only \(\prod_{i\in [n]} |f_s^{-1}(i)|\) functions, when \(K\) has exactly one element mapping to each element of \([n]\). This is maximized when all \(|f_s^{-1}(i)|\) are equal to \(u/n\), from which it follows that any particular \(f_s\) works for at most \(Y:=(u/n)^n\) inputs.

It directly follows that at least \(X/Y\) different states are needed, and thus that there is an input that requires \(\lg (X/Y)\) bits to encode its state. We obtain

\begin{align*} \lg (X/Y) &= \lg \left(\binom un\right) / (u/n)^n \approx \lg ((u^n)/n!)/(u/n)^n \\ &= \lg (n^n/n!) = n \lg n - (n\lg n! + n \lg e + O(\lg n)) = n \lg e + O(\lg n) \end{align*}

where the first approximation holds because \(u \gg n^2\) and the second one is the Stirling approximation.

[TODO: replace \(\approx\) by \(+O()\)]

We now extend this proof beyond the worst case. Let \(p_s\) be the probability that the (possibly randomized) construction algorithm outputs \(f_s\). As before, we have \(p_s \leq Y/X\). It follows that the entropy satisfies

\begin{equation*} E = - \sum_s p_s \lg p_s = \sum_s p_s \lg (1/p_s) \geq \sum_s p_s \lg (X/Y) = \lg (X/Y) \approx n\lg e + O(\lg n), \end{equation*}

showing that the expected case equals the worst-case.

It turns out that a simple greedy randomized algorithm gives a matching upper bound: we can simply try random \(f_s\) for \(s=0,1,2,\dots\) until success. Each seed succeeds with probability \(p:=n!/n^n\), which means the first successful seed follows a geometric distribution with entropy \[ E = \frac 1p (-p\lg p - (1-p) \lg (1-p)) = \lg (1/p) + \frac {1-p}p \lg (1/(1-p)) \] The first term approaches \(\lg (1/p) = \lg (n^n/n!) = n \lg e + O(\lg n)\), again via Stirling approximation, while the second term converges to \(1 = O(\lg n)\).

If \(\alpha = k\) then \(E\) occurs if and only if every bin receives exactly \(d\) balls. The probability mass function of the multinomial distribution and Stirlings Approximation of \((kB)!\) gives

\begin{align*} \Pr[E] &= \Pr[(X₁,…,Xₙ) = (k,\dots, k)] = \frac{(kB)!}{(k!)^B} · B^{-kB}\\ &= \frac{Θ\big((kB)^{kB}·e^{-Bk}\sqrt{Bk}\big)}{(k!)^B B^{kB}} = Θ\bigg( \Big(\frac{k^{k}}{e^{k}k!}\Big)^B \sqrt{Bk} \bigg). \end{align*}

The standard technique of Poissonisation exploits that the multinomial distribution of \((X₁,…,X_B)\) can be attained by taking independent Poisson random variables \(Y_1,…,Y_B\) and conditioning them on \(\sum_{i = 1}^B Y_i = αB\). We use Poissonisation with a twist.

An outcome \((x₁,…,x_B) ∈ ℕ^B\) contributing to \(E\) must satisfy two conditions: The sum \(x₁+…+x_B\) must be \(αB\) and each \(x_i\) must be at most \(k\). The vector \((X₁,…,X_B)\) follows a multinomial distribution and automatically satisfies the sum condition, but not the minimum condition. The proof considers a sequence \(Z₁,…,Z_B \sim \Phi(\alpha,k)\) of independent truncated Poisson random variables. The vector \((Z₁,…,Z_B)\) automatically satisfies the minimum condition, but not the sum condition. This amounts to a mathematically simpler way to capture the outcomes we want.

[TODO: Add some context that the \(Z_i\) indeed are the distribution of the bin loads, and that the ‘residual’ probability of hitting the exact right size is large now at \(O(1/\sqrt B)\), whereas in the non-truncated setting, this is exponentially unlikely. On the scale of exponentially small probabilities, hitting the exact right number of balls when we independently put \(Z_i\) balls in each bin is nearly guaranteed to happen.]

Let \(R\) denote the set of possible outcomes of \(\vec{X} = (X₁,…,X_B)\) that are consistent with \(E\), meaning \[ R = \{ \vec{x} ∈ (ℕ \setminus \{0,1,…,k-1\})^B \mid \sum_{i = 1}^B x_i = n \}.\] Using that \((X₁,…,X_B)\) has multinomial distribution gives

\begin{align} \Pr[E] &= \Pr[\vec{X} ∈ R] = \sum_{\vec{x} ∈ R} \Pr[\vec{X} = \vec{x}] = \sum_{\vec{x} ∈ R} \binom{n}{x₁\,…\,x_B} B^{-n}\notag\\ &= \sum_{\vec{x} ∈ R} \frac{n!}{x₁!·…·x_B!} B^{-n} = \frac{n!}{B^{n}} \sum_{\vec{x} ∈ R} \frac{1}{x₁!·…·x_B!}.\label{eq:prob-E} \end{align}

Now consider independent \(Z₁,…,Z_B \sim \Phi(\alpha,k)\) for \(Φ(\alpha,k)\) as defined in \cref{eq:def-\Phi}. Let \(\vec{Z} = (Z₁,…,Z_B)\) and \(N_Z = \sum_{i = 1}^B Z_i\). By construction the events \(\vec{Z} ∈ R\) and \(N_Z = αB\) are equivalent. For any \(\vec{x} ∈ R\) we can compute

\begin{align*} \Pr[\vec{Z} &= \vec{x} \mid N_Z = n] = \frac{\Pr[\vec{Z} = \vec{x} ∧ N_Z = n]}{\Pr[N_Z = n]} = \frac{\Pr[\vec{Z} = \vec{x}]}{\Pr[N_Z = n]} = \frac{\prod_{i = 1}^B \Pr[Z_i = x_i]}{\Pr[N_Z = n]}\\ &= \frac{\prod_{i = 1}^B \frac{1}{ζ} · \frac{λ^{x_i }}{x_i!}}{\Pr[N_Z = n]} = \frac{λ^{n}}{ζ^n\Pr[N_Z = n]} \frac{1}{x₁!·…·x_B!}. \end{align*}

By summing this equation over all \(\vec{x} ∈ R\) we get \[ 1 = \frac{λ^{n}}{ζ^B\Pr[N_Z = n]} \sum_{\vec{x} ∈ R}\frac{1}{x₁!·…·x_B!} \] We rearrange this equation for \(\sum_{\vec{x} ∈ R}\frac{1}{x₁!·…·x_B!}\) and plug the result into \cref{eq:prob-E}. We now assume that \(α\) is constant, we use Stirling’s approximation of \(n!\) and we use that \(\Pr[N_Z = n] = \Theta(1/\sqrt{B})\), which follows directly from the Local Limit Theorem (Gnedenko 1948; Eq 1.9 Szewczak and Weber 2022; Thm 2.8 Giuliano 2012). This gives

\begin{align*} \Pr[E] &= \frac{n!}{B^{n}} \frac{ζ^B\Pr[N_Z = n]}{λ^{n}} = \frac{n^{n}e^{-n}\Theta(\sqrt{B})ζ^B \Theta(1/\sqrt{B})}{B^{n} λ^{n}} = \Big(\frac{\alpha^{\alpha}ζ}{e^{\alpha}λ^\alpha}\Big)^B·Θ(1), \end{align*}

concluding the proof.