Independent Uniform Hashing

A Hash Function $h$ has independent uniform hashing property:

• Uniform: any key is equally likely to hash into any of $m$ Bucket
• Independent: any key is hashed independently of where other keys have hashed to. Formally:
  • Sample space of keys $U$
  • $\forall 1\le i\le m,\forall k\in U,Pr(h(k)=i)=\frac{1}{m}$
• For all $k_1,k_2\in U$ with $k_1\ne k_2$ $Pr(h(k_1)=h(k_2)=i)=Pr(h(k_1)=i)\times Pr(h(k_2)=1)$