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 höchstens $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,\dotsc ,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,\dotsc ,m-1\}$ gewählt werden.

Falls $n$ Elemente in einer Hashtabelle $T$ der Größe $m$ mittels einer zufälligen Hashfunktion $h$ aus einer $c$-universellen Familie gespeichert werden, dann ist für jedes $T[i]$ mit mindestens einem Schlüssel die erwartete Anzahl Schlüssel in $T[i]$ in $O(1+c*(n/m))$.

Literatur

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