An eine universelle Hashfunktion werden
folgende Anforderungen gestellt: Wenn man aus der Menge der Argumente eine
feste Anzahl Elemente wählt und deren Hashwerte
bestimmt, ist die Wahrscheinlichkeit einer Kollision für diese Elemente
höchstens so groß, wie die Wahrscheinlichkeit, bei der Auswahl
ein bestimmtes Argument zu wählen.
Um die Definition etwas zu veranschaulichen:
Man nehme ein Buch, zerschneide es und mische die Seiten. Dann gebe
man sich eine Funktion vor, die eine Anzahl von Buchstaben als Argument
hat und eine Zahl als Resultat. Die Menge aller möglichen Zahlen (Funktionswerte)
soll kleiner sein, als die Seitenzahl des Buches (sonst ist das Kriterium
einer Hashfunktion nicht erfüllt).
Man wähle zwei Seiten aus dem Haufen und wende auf die Buchstaben
jeder Seite die Funktion an. Dadurch erhält man zwei Zahlen. Die Wahrscheinlichkeit,
aus dem Stapel der Seiten eine bestimmte Seite herauszugreifen ist 1/Seitenzahl,
insofern man nicht schummelt. Die gewählte Funktion wäre dann
eine universelle Hashfunktion, wenn die Wahrscheinlichkeit,
daß die ermittelten Hashwerte -unsere zwei Zahlen- gleich sind (Kollision),
nicht größer als 1/Seitenzahl ist.