Perfekte Hash-Funktion

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

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

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

• es eine feste Schlüsselmenge $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.