Universelle Hash-Funktion

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 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 | Quelltext bearbeiten]

Cormen et al. definieren universelle Hashfunktionen wie folgt (Übersetzung): „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.“

Literatur[Bearbeiten | Quelltext bearbeiten]

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