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.
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 .
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 .
literature
- Cormen et al .: Introduction to Algorithms . 2nd Edition. MIT Press, 2001, chapter 11.3.3
Individual evidence
- ↑ Cormen et al., Op. Cit.