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

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

Literatur

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

Einzelnachweise