- Universelle Hashfunktion
-
Eine Universelle Hash-Funktion ist ein Randomisierter Algorithmus für den 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
Sei H eine endliche Menge von Hash-Funktionen, die eine Menge K von Schlüsseln auf die Menge {0, 1, ..., m-1} abbildet. Eine solche Menge wird als universell bezeichnet, wenn für jedes Paar voneinander verschiedener Schlüssel die Anzahl der Hash-Funktionen für die h(k)=h(l) gilt, höchstens gleich 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, ...,, m-1} gewählt werden.
In der Kryptologie werden universelle Hash-Funktionen durch Einweg-Hashfunktionen realisiert.
Literatur
- Cormen et al.: Introduction to Algorithms. 2. Auflage. MIT Press, 2001, Kapitel 11.3.3
Wikimedia Foundation.