Perfekte Hash-Funktion

Eine perfekte Hash-Funktion ist eine Hashfunktion <math>h\colon S \rightarrow T</math>, die unterschiedliche Elemente <math>x \neq x'</math> aus einer endlichen und festen Schlüsselmenge <math>S</math> auf unterschiedliche Elemente <math>h(x) \neq h(x')</math> aus einer Bildmenge <math>T</math> 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 <math>T = \{ 0, \dotsc, \left\vert S \right\vert - 1 \}</math>, d. h. <math>\left\vert S \right\vert = \left\vert T \right\vert\,</math>. 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 <math>h(s)</math> mit <math>s \in S</math> speichert, auf das Minimum.

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

In der Praxis sucht man Hashfunktionen mit folgenden Eigenschaften:

• Konstruktion in <math>\mathcal O(n)</math> Zeit, d. h. mit wachsender Schlüsselanzahl <math>\left\vert S \right\vert</math> steigt die Zeit der Konstruktion linear.
• Evaluation in <math>\mathcal O(1)</math>, d. h. nach Konstruktion kann man einen Schlüssel <math>s \in S</math> in konstanter Zeit auf einen Index <math>h(s)</math> abbilden.
• Die Hashfunktion benötigt möglichst wenig Speicher.
• Die Hashfunktion soll minimal perfekt sein.

Derzeit gängige minimal perfekte Hashfunktionen arbeiten in <math>O(n)</math> Zeit zur Konstruktion und benötigen mindestens 1,56 Bit pro Schlüssel.<ref>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 ().  </ref>

(Minimale) perfekte Hashfunktionen sind in der Praxis dann angebracht, wenn:

• es eine feste Schlüsselmenge <math>S</math> 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

<references />