Universal hash function

A universal hash function (sometimes referred to as a universal hash function) is a randomized algorithm for which the probability of a collision in a set with elements is. ${\displaystyle n}$ ${\displaystyle 1/n}$

The basic idea behind universal hashing is to randomize the hash function: the hash function is selected at random from a class of functions. This means that the probability of poor runtime behavior can be evenly distributed over all inputs.

definition

Let be a finite set of hash functions that map a set of keys to the set . Such a set is said to be universal if the number of hash functions for each pair of different keys is at most equal . In other words, with a hash function chosen at random , the probability of a collision between the keys and no greater than the probability of a collision if and are chosen randomly and independently from the set . ${\displaystyle H}$ ${\displaystyle K}$ ${\displaystyle \{0,1,\dotsc ,m-1\}}$ ${\displaystyle k,l\in K}$ ${\displaystyle h(k)=h(l)}$ ${\displaystyle \left|H\right|/m}$ ${\displaystyle H}$ ${\displaystyle k}$ ${\displaystyle l}$ ${\displaystyle 1/m}$ ${\displaystyle h(k)}$ ${\displaystyle h(l)}$ ${\displaystyle \{0,1,\dotsc ,m-1\}}$

If elements are stored in a hash table of the size using a random hash function from a universal family, then for each with at least one key the expected number of keys in in . ${\displaystyle n}$ ${\displaystyle T}$ ${\displaystyle m}$ ${\displaystyle h}$ ${\displaystyle c}$ ${\displaystyle T[i]}$ ${\displaystyle T[i]}$ ${\displaystyle O(1+c*(n/m))}$

literature

• Cormen et al .: Introduction to Algorithms . 2nd Edition. MIT Press, 2001, chapter 11.3.3

Individual evidence

1. ↑ Cormen et al., Op. Cit.