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 Elementen höchstens 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 Bearbeiten
Sei eine endliche Menge von Hash-Funktionen, die eine Menge von Schlüsseln auf die Menge abbilden. Eine solche Menge wird als universell bezeichnet, wenn für jedes Paar voneinander verschiedener Schlüssel die Anzahl der Hash-Funktionen, für die gilt, höchstens gleich ist. Mit anderen Worten, mit einer zufällig aus ausgewählten Hash-Funktion ist die Wahrscheinlichkeit für eine Kollision zwischen den Schlüsseln und nicht größer als die Wahrscheinlichkeit einer Kollision, wenn und zufällig und unabhängig aus der Menge gewählt werden.
Falls Elemente in einer Hashtabelle der Größe mittels einer zufälligen Hashfunktion aus einer -universellen Familie gespeichert werden, dann ist für jedes mit mindestens einem Schlüssel die erwartete Anzahl Schlüssel in in .
Literatur Bearbeiten
- Cormen et al.: Introduction to Algorithms. 2. Auflage. MIT Press, 2001, Kapitel 11.3.3
Einzelnachweise Bearbeiten
- Cormen et al., op. cit.