Universal hash function

Let the Universal Hashing function $F$ be defined as a family or set of functions $f$ which maps $\{0,1\}^{n}\rightarrow \{0,1\}^{m}$, where for any $x,y\in \{0,1\}^{n}$,$x\neq y$ and $x^{'},y^{'}\in \{0,1\}^{m}$.

The probability that $f\in F$ which follows from this construction is given by $Prob_{f\in F}[f\left(x\right)=x^{'}\wedge f\left(y\right)=y^{'}]={\frac {1}{2^{2m}}}$

The implication of such a hashing function is that collisions only happen with the above given probability. Thus yielding an average case performance even if the keys are carefully chosen.

---

References Wolfram