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 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[Bearbeiten]

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

Literatur[Bearbeiten]

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