Universal Hashing

The idea of picking a random Hash Function from a family for functions that have a universal property.

Universal Property

A family $H$ of Hash Function is universal iff:

• For any two keys $j,k$ with $j\ne k$.
• Randomly pick $h$ from $H$ with Uniform Probability
• $Pr(h(j)=h(k))\le \frac{1}{m}$ ($m$ is array length)
  • (Equivalently, at most $\frac{|H|}{m}$ functions satisfy $h(j)=h(k)$)