- Let
be a finite collection of hash functions that map a given
universe U of keys into the range
{0, 1, 2,...,
*m*- 1}. -
is called
**universal**if for each pair of distinct keys*x*,*y**U*, the number of hash functions*h*for which*h*(*x*) =*h*(*y*) is precisely equal to - With a function randomly chosen from , the
chance of a collision between
*x*and*y*where*x**y*is exactly .

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

Let
*a* = (*a*_{0}, *a*_{1},..., *a*_{r}) denote a sequence of *r* + 1 elements chosen
randomly from the set
{0, 1,..., *m* - 1}. Define a hash function
*h*_{a}
by