3.5.3 Universal Hashing

This involves choosing a hash function randomly in a way that is independent of the keys that are actually going to be stored. We select the hash function at random from a carefully designed class of functions.

• Let $\Phi$ be a finite collection of hash functions that map a given universe U of keys into the range {0, 1, 2,..., m - 1}.
• $\Phi$ is called universal if for each pair of distinct keys x, y $\in$ U, the number of hash functions h $\in$ $\Phi$ for which h(x) = h(y) is precisely equal to
  $${\frac{\vert\Phi\vert}{m}}$$

• With a function randomly chosen from $\Phi$, the chance of a collision between x and y where x $\neq$ y is exactly ${\frac{1}{m}}$.

Example of a universal class of hash functions:

Let table size m be prime. Decompose a key x into r +1 bytes. (i.e., characters or fixed-width binary strings). Thus

x = (x₀, x₁,..., x_r)

Assume that the maximum value of a byte to be less than m.

Let a = (a₀, a₁,..., a_r) denote a sequence of r + 1 elements chosen randomly from the set {0, 1,..., m - 1}. Define a hash function h_a $\in$ $\Phi$ by

h_a(x) = $$\sum_{i=0}^{r}$$ a_ix_i mod m

With this definition, $\Phi$ = $\bigsqcup_{a}^{}${h_a} can be shown to be universal. Note that it has m^{r + 1} members.