MIT 6.1220 — Lecture 7

Hash Functions (Part II)

Here's another way to handle key collisions.

Solution. (Open Addressing) Every key $k \in \mathcal{U}$ is assigned not just one hash value in $\{0, 1, \dots, m - 1\}$ , but rather a permutation of $\{0, 1, \dots, m - 1\}$ called a probing sequence:

h: \mathcal{U} \times \{0, 1, \dots, m - 1\} \to \{0, 1, \dots, m- 1\} ~ \text{ such that } ~ k ~ \text{ has probing sequence } (h(k, 0), h(k, 1), \dots, h(k, m - 1)).

We implement our desired operations as follows:

$\textsc{Insert}(k, v)$ : Find the smallest $p$ such that $T[h(k, p)] = \textsc{Null} \text{ or } \textsc{Deleted}$ , then set $T[h(k, p)] = (k, v)$ .
$\textsc{Search}(k)$ : Find the smallest $p$ such that $T[h(k, p)].\textsc{Key} = k$ , then return $T[h(k, p)].\textsc{Value}$ .
$\textsc{Delete}(k)$ : Find the smallest $p$ such that $T[h(k, p)].\textsc{Key} = k$ , then set $T[h(k, p)] = \textsc{Deleted}$ .

Remark. Some CYU questions:

Why do we need a $\textsc{Deleted}$ type? What goes wrong if we set $T[h(k, p)] = \textsc{Null}$ when deleting?
What happens when $\alpha = \frac{n}{m}$ approaches $1$ , or exceeds $1$ ?

Claim. Suppose that every key receives an independently generated uniformly random sequence.

Then the expected number of $p$ we will need to check is $O\left(\frac{1}{1 - \alpha}\right)$ , where $\alpha := \frac{n}{m} < 1$ .

Proof: Handwaving… a guess for $p$ succeeds with probability $1 - \alpha$ , so the EV # of tries is $\frac{1}{1 - \alpha}$ . $\blacksquare$

The rigorous proof goes $\underset{h}{\mathbb{E}}[X] = \displaystyle\sum_{j = 1}^m j \cdot \underset{h}{\mathrm{Pr}}[X = j] = \displaystyle \sum_{j = 1}^m \underset{h}{\mathrm{Pr}}[X \geq j] \leq \displaystyle\sum_{j = 1}^m \alpha^{j - 1} \leq \frac{1}{1 - \alpha}$ , hooray. $\blacksquare$

Even more formally, we need to justify $\underset{h}{\mathrm{Pr}}[X \geq j] \leq \alpha^{j - 1}$ , so we should be writing something like the following, where $E_i$ is the event that the $i^{\text{th}}$ probe finds an occupied slot:

\underset{h}{\mathrm{Pr}}[X \geq j] = \underset{h}{\mathrm{Pr}}[E_1 \wedge E_2 \wedge \dots \wedge E_{j - 1}] = \underset{h}{\mathrm{Pr}}[E_1] \times \underset{h}{\mathrm{Pr}}[E_2 \mid E_1] \times \dots \times \underset{h}{\mathrm{Pr}}[E_{j - 1} \mid E_1 \wedge E_2 \wedge \dots \wedge E_{j - 2}].

And the $\ell^{\text{th}}$ term in this product is upper-bounded by $\frac{n - \ell + 1}{m - \ell + 1} \leq \frac{n}{m} = \alpha$ , as desired. $\blacksquare$

Generating probing sequences uniformly at random is hard, so in practice, we implement like so.

Solution. (Probing Methods) Pick any two hash functions $h_1, h_2: \mathcal{U} \to \{0, 1, \dots, m - 1\}$ . We can use:

Linear Probing. Take $h(k, p) := (h_1(k) + p) \%m$ .
Double Hashing Probing. Take $h(k, p) := (h_1(k) + p \cdot h_2(k)) \%m$ . (This is a permutation only when $\gcd(h_2(k), m) = 1$ .)

Now for something new. Let's try to implement…

Problem. (Static Dictionaries & Perfect Hashing) We are given $\{(k_1, v_1), \dots, (k_n, v_n)\}$ up front, after which point only $\textsc{Search}(k)$ may be called. We would like the following:

\text{Expected Pre-Processing Time: } O(n) ~~ \mid ~~ \text{Space: } O(n) ~~ \mid ~~ \text{Search Operations: } O(1) \text{ always}

In particular, we require perfect hashing: no collisions occur at all!

Here's a naive solution that passes all constraints except the space requirement.

Solution. (Suboptimal-Space Solution) Consider a universal hash family $\mathcal{H}$ , and take $m \geq n^2$ .

Then pick $h \in \mathcal{H}$ , and use $k_i \mapsto h(k_i)$ . If the first $h \in \mathcal{H}$ fails, pick another $h \sim \mathcal{H}$ until success.

Proof: This works in expected $O(n)$ pre-processing time because $\underset{h \sim \mathcal{H}}{\mathrm{Pr}}[\text{no collisions}] \geq \frac{1}{2}$ by Union Bound—try it yourself! (When does universality of $\mathcal{H}$ get used?) $\blacksquare$

Here's the smart solution by Fredman-Komlos-Szemeredi (1984) that passes the space requirement.

Solution. (Optimal-Space Solution) Sample a hash function $h_1 \in \mathcal{H}_1$ that goes $h_1: \mathcal{U} \to \{0, 1, \dots, n - 1\}$ .

Suppose $N_{\ell} := |h_1^{-1}(\ell) \cap \{k_1, \dots, k_n\}|$ for all $\ell \in \{0, 1, \dots, n - 1\}$ .
Use the suboptimal-space solution to fit $N_{\ell}$ key-value pairs in the $\ell^{\text{th}}$ bucket.

Using $O(N_{\ell})$ time and $O(N_{\ell}^2)$ space, give the $\ell^{\text{th}}$ bucket a sampled hash function $h_{2, \ell} \in \mathcal{H}_{2, \ell}$ that goes $h_{2, \ell}: h_1^{-1}(\ell) \to \{0, 1, \dots, N_{\ell}^2 - 1\}$ .

Our data structure is then a two-dimensional array: $n$ buckets, the $\ell^{\text{th}}$ of which has $N_{\ell}^2$ slots to hash into.

Proof: It's easy to see that this has $O(1)$ search time, and that we only need $O(n)$ pre-processing time once $h_1$ is chosen.

The hard part is achieving $O(n)$ space. If we choose $h_1$ unluckily, we won't actually get $O(n)$ space! However,

\textbf{Claim.} ~~~~~ \underset{h \sim \mathcal{H}_1}{\mathrm{Pr}} \left [ \left(\sum_{\ell = 0}^{n - 1} N_{\ell}^2\right) > 4n \right ] < \dfrac{1}{2}.

To prove this, note that by Markov's inequality, it suffices to show $\underset{h \sim \mathcal{H}_1}{\mathbb{E}}\left [ \sum_{\ell = 0}^{n - 1} N_{\ell}^2 \right ] < 2n$ . This takes some clever work:

\begin{align*}\underset{h \sim \mathcal{H}_1}{\mathbb{E}} \left [ \sum_{\ell = 0}^{n - 1} N_{\ell}^2 \right ] = \ & \underset{h \sim \mathcal{H}_1}{\mathbb{E}} \left [ \sum_{\ell = 0}^{n - 1} \left ( N_{\ell} + \sum_{j \neq j'} \mathds{1}\left [ h(k_j) = h(k_{j'}) = \ell \right ] \right ) \right ] \\ = \ & \underset{h \sim \mathcal{H}_1}{\mathbb{E}}\left [ \sum_{\ell = 0}^{n - 1} N_{\ell} \right ] + \underset{h \sim \mathcal{H}_1}{\mathbb{E}} \left [ \sum_{\ell = 0}^{n - 1} \sum_{j \neq j'} \mathds{1}\left [ h(k_j) = h(k_{j'}) = \ell \right ] \right ] \\ = \ & n + \sum_{j \neq j'} \left(\underset{h \sim \mathcal{H}_1}{\mathrm{Pr}}[h(k_j) = h(k_{j'})] \right) \\ \leq \ & n + \frac{n(n - 1)}{n} < 2n.\end{align*}

Thus, we can guarantee $O(n)$ space in expected $O(n)$ time by repeatedly resampling $h_1$ until the space is less than $4n$ . $\blacksquare$