Perfekte Hash-Funktion

Eine perfekte Hash-Funktion ist eine Hashfunktion , die unterschiedliche Elemente aus einer endlichen und festen Schlüsselmenge auf unterschiedliche Elemente aus einer Bildmenge abbildet (keine Kollisionen, Injektivität). Aus der Injektivität ergibt sich ein wichtiger Vorteil: Auf ein Element einer Hashtabelle, die mit einer perfekten Hash-Funktion erstellt wurde, kann im worst Case in konstanter Zeit zugegriffen werden.

Eine perfekte Hash-Funktion heißt minimal, wenn , d. h. . Das bedeutet, dass die Bildmenge der Funktion genauso viele Elemente wie die Urbildmenge hat. In der Praxis senkt dies den Speicherbedarf des Arrays, das die Elemente für jedes mit speichert, auf das Minimum.

Im Gegensatz zu nicht perfektem Hashing, das amortisiert Zugriffszeit benötigt und im worst Case , bietet perfektes Hashing selbst im worst Case einen Zugriff auf die Elemente in konstanter Zeit , ist also deutlich schneller. Dies wird erreicht, indem die Werte der Schlüssel in einem von bis indizierten Array an der Position gespeichert werden; im Gegensatz zu normalem Hashing enthält jeder Eimer (Bucket) aufgrund der Injektivität von also nur genau ein Element. Dafür bezahlt man mit Rechenzeit, um die Hashfunktion zu konstruieren, und benötigt mehr Speicherplatz.

In d​er Praxis s​ucht man Hashfunktionen m​it folgenden Eigenschaften:

  • Konstruktion in Zeit, d. h. mit wachsender Schlüsselanzahl steigt die Zeit der Konstruktion linear.
  • Evaluation in , d. h. nach Konstruktion kann man einen Schlüssel in konstanter Zeit auf einen Index abbilden.
  • Die Hashfunktion benötigt möglichst wenig Speicher.
  • Die Hashfunktion soll minimal perfekt sein.

Derzeit gängige minimal perfekte Hashfunktionen arbeiten in Zeit zur Konstruktion und benötigen mindestens 1,56 Bit pro Schlüssel.[1]

(Minimale) perfekte Hashfunktionen s​ind in d​er Praxis d​ann angebracht, wenn:

  • es eine feste Schlüsselmenge gibt, der jeweils Werte zugeordnet sind (bei sich ständig ändernden Schlüsselmengen wäre eine ständige Neukonstruktion zu zeitintensiv),
  • genug Zeit vorhanden ist, um die Hashfunktion zu konstruieren,
  • auf die Werte ein Zugriff in konstanter Zeit benötigt wird,
  • zusätzlicher Speicher für die Hashfunktion vorhanden ist.

Einzelnachweise

  1. Emmanuel Esposito, Thomas Mueller Graf, Sebastiano Vigna: RecSplit: Minimal Perfect Hashing via Recursive Splitting. 2020 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX), 2020, abgerufen am 23. Januar 2020 (englisch).
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.