Universal hashing

Universal hash function ( sometimes referred to as a universal hash function ) is a randomized algorithm for which is that the probability of collision in an amount of items.

The basic idea behind universal hashing is to randomize the hash function: the hash function is selected from a class of functions randomly. Thus, the probability of a bad run-time behavior can be evenly distributed over all inputs.

Definition

Cormen et al. define universal hash functions as follows ( translation ): "Be a finite set of hash functions that map a set of keys on the amount. Such an amount is referred to as universal, if the number of hash functions, for which it holds for each pair of mutually different key, is at most equal. In other words, with a randomly selected from the hash function, the probability of a collision between the keys and not greater than the probability of collision, when and are selected from the set of random and independent. "