Universelle Hashfunktion

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 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, ...,, 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.

Игры ⚽ Поможем решить контрольную работу

Schlagen Sie auch in anderen Wörterbüchern nach:

  • 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 n Elementen 1/n beträgt. Die Grundidee… …   Deutsch Wikipedia

  • Engstes Punktpaar — Das Problem des dichtesten bzw. engsten Punktpaares ist die Suche nach den zwei am dichtesten beieinander liegenden Punkten in einer Ebene. Inhaltsverzeichnis 1 Formale Beschreibung 2 Brute force Algorithmus 3 Divide Conquer Algorithmus 4… …   Deutsch Wikipedia

  • Dichtestes Punktpaar — Das Problem des dichtesten bzw. engsten Punktpaares (auch closest pair problem) ist die Suche nach den zwei am dichtesten beieinander liegenden Punkten in einer Ebene. Inhaltsverzeichnis 1 Formale Beschreibung 2 Brute force Algorithmus 3 Divide… …   Deutsch Wikipedia

  • Rainbow Table — Die Rainbow Table (zu Deutsch: Regenbogentabelle) ist eine von Philippe Oechslin entwickelte Datenstruktur, die eine schnelle, probabilistische Suche nach einem Element des Urbilds (i. d. R. ein Passwort) eines gegebenen Hashwerts… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”