Perfekte Hash-Funktion

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

Im Gegensatz zu nicht perfektem Hashing, das amortisiert ${\displaystyle {\mathcal {O}}(1)}$ Zugriffszeit benötigt und im worst Case ${\displaystyle {\mathcal {O}}(\log n)}$, bietet perfektes Hashing selbst im worst Case einen Zugriff auf die Elemente in konstanter Zeit ${\displaystyle {\mathcal {O}}(1)}$, ist also deutlich schneller. Dies wird erreicht, indem die Werte ${\displaystyle s}$ der Schlüssel in einem von ${\displaystyle 0}$ bis ${\displaystyle \left\vert T\right\vert -1}$ indizierten Array an der Position ${\displaystyle h(s)}$ gespeichert werden; im Gegensatz zu normalem Hashing enthält jeder Eimer (Bucket) aufgrund der Injektivität von ${\displaystyle h}$ 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 ${\displaystyle {\mathcal {O}}(n)}$ Zeit, d. h. mit wachsender Schlüsselanzahl ${\displaystyle \left\vert S\right\vert }$ steigt die Zeit der Konstruktion linear.
• Evaluation in ${\displaystyle {\mathcal {O}}(1)}$, d. h. nach Konstruktion kann man einen Schlüssel ${\displaystyle s\in S}$ in konstanter Zeit auf einen Index ${\displaystyle h(s)}$ abbilden.
• Die Hashfunktion benötigt möglichst wenig Speicher.
• Die Hashfunktion soll minimal perfekt sein.

Derzeit gängige minimal perfekte Hashfunktionen arbeiten in ${\displaystyle O(n)}$ 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 ${\displaystyle S}$ 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).