Lesson 2

Perfect hash function

For a pre-known set of keys \(K\), one can construct a hashing scheme that is collision-free and has size \(O(n)\), where \(n=|K|\) is the number of keys.

Take a number \(n^{2} \le m < 2n^{2}\) that is a power of two, and fix a universal family of hash functions \(\mathcal{H}=\{h \colon \mathbb{F}_{m} \to \mathbb{F}_{m}\}\). We will assume that all keys are distinct elements of the field \(\mathbb{F}_{m}\) (they can be embedded in any way): \(K \subseteq \mathbb{F}_{m}\). Then, when choosing a random hash function \(h \in \mathcal{H}\), there will be no collisions with a probability of at least \(1/2\). Indeed, let \(\alpha\) be the number of collisions: \[\alpha=|\{k < k' \in K \colon h(k)=h(k')\}| \ .\] Then \[E[\alpha]\le\binom{n}{2}\cdot \frac{1}{m}< 1/2\ .\] Thus, by Markov's inequality, \[\Pr[\alpha \ge 1] \le \frac{E[\alpha]}{1}< \frac{1}{2}\ .\]

Consequently, within a constant number of trials, one can obtain a hash function that has no collisions on the given set of keys. However, the table size in this case will be quadratic. To reduce memory consumption, we will use a two-level scheme: at the first level, we use a hash table of size \(n \le k < 2n\), and at the second level, for each chain, we use the collision-free quadratic scheme just constructed. It turns out that the memory will then be linear!

To estimate the memory consumption, let \(n_{i}\) denote the number of keys that received the value \(0 \le i < k\) at the top level. Then the total memory required for all cells of the first level will be \[\sum_{i=0}^{k-1}n_{i}^{2} \ .\] Let's estimate the expected value of this random variable: \[\begin{align*}E\left[\sum_{i=0}^{k-1}n_{i}^{2}\right]&=E\left[\sum_{i=0}^{k-1}n_{i} + \sum_{i=0}^{k-1}2\binom{n_i}{2}\right]=\\&=E\left[\sum_{i=0}^{k-1}n_{i}\right] + E\left[\sum_{i=0}^{k-1}2\binom{n_i}{2}\right]=\\&=n + 2E\left[\sum_{i=0}^{k-1}\binom{n_i}{2}\right]\end{align*}\] The sum \(\sum_{i=0}^{k-1}\binom{n_i}{2}\) is exactly the number of pairs of keys for which the first-level hash function produces a collision! Since a collision occurs for each pair of keys with a probability of at most \(1/k\), we have \[E\left[\sum_{i=0}^{k-1}\binom{n_i}{2}\right] \le \frac{1}{k}\binom{n}{2}\le \frac{1}{n}\binom{n}{2}<n \ .\] This means the expected size is no more than \(2n\). Then, by Markov's inequality, with probability at least \(1/2\), the total size will be no more than \(4n\). Thus, within a constant number of trials, a hash function will be found such that the required memory is linear.