# Homework 14

Due Friday, April 3 at 10:00 PM. Please refer to the homework policy here.

## Problems

1. Suppose we have a universal hash function $h: [n] \to [m]$.

1. Show that if $m \geq n^2$, then with probability $\geq 1/2$, $h$ is injective. (That is, $h(i) \neq h(j)$ for all $i \neq j$.)
2. Using part (a) show how to build a hash table over $n$ keys with $O(n^2)$ space that has max load 1 with constant probability (say $\geq 1/2$), using only a universal hash function.
2. The goal of this problem is to show how to get constant time access for $n$ keys with $O(n)$ space, using only universal hash functions.

The high level idea is similar to the hash tables discussed in lecture where we would use a universal hash into a smaller array and make a linked list out of the collisions. Here the array has size $m = n$. When we have a set of (say) $k$ collisions at an array cell, rather than making a linked list of length $k$, and we build a hash table of size $k^2$ with maximum load 1, using part (2). (We may have to retry if we fail.) If the total size (summing the lengths of the first array and each of the secondary arrays) comes out to bigger than (say) $4 n$, we try again.

1. For each $i = 1,\dots,m$ let $k_i$ be the number of keys that hash to the $i$th cell. Show that

2. Show that

1. Show that
1. Show that1

Together, (a), (b), (c), and (d), show that this approach will build a "perfect" hash table over the $n$ keys in $O(n)$ space with probability of success at least $1/2$, using only universal hash functions. We can then keep repeating the construction until it succeeds.

1 The "$5n$" used to be "$4n$", but this was a typo. Morally, any constant would be fine.