Universelle Hash-Funktion

Eine Universelle Hash-Funktion (manchmal auch als universale Hash-Funktion bezeichnet) ist ein Randomisierter Algorithmus, für welchen gilt, dass die Wahrscheinlichkeit einer Kollision in einer Menge mit n Elementen 1/n beträgt.

Die Grundidee hinter universellem Hashing ist, die Hash-Funktion zu randomisieren: die Hash-Funktion wird aus einer Klasse von Funktionen zufällig ausgewählt. Somit kann die Wahrscheinlichkeit für schlechtes Laufzeitverhalten gleichmäßig über alle Eingaben verteilt werden.

Definition

Sei H eine endliche Menge von Hash-Funktionen, die eine Menge K von Schlüsseln auf die Menge {0, 1, ..., m-1} abbilden. Eine solche Menge wird als universell bezeichnet, wenn für jedes Paar voneinander verschiedener Schlüssel $k,l\in K$ die Anzahl der Hash-Funktionen für die h(k)=h(l) gilt, höchstens gleich $\left| H \right|/m$ ist. Mit anderen Worten, mit einer zufällig aus H ausgewählten Hash-Funktion ist die Wahrscheinlichkeit für eine Kollision zwischen den Schlüsseln k und l nicht größer als die Wahrscheinlichkeit 1/m einer Kollision, wenn h(k) und h(l) zufällig und unabhängig aus der Menge {0, 1, ..., m-1} gewählt werden.

Literatur

• Cormen et al.: Introduction to Algorithms. 2. Auflage. MIT Press, 2001, Kapitel 11.3.3