Perfekte Hash-Funktion

Eine perfekte Hash-Funktion ist eine Hashfunktion $h:S\to T$, die unterschiedliche Elemente $x\ne x^{\prime }$ aus einer endlichen und festen Schlüsselmenge $S$ auf unterschiedliche Elemente $h(x)\ne h(x^{\prime })$ 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,\dots ,\left|S\right|-1\}$, d. h. $\left|S\right|=\left|T\right|$. 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 $𝒪(1)$ Zugriffszeit benötigt und im worst Case $𝒪(\log n)$, bietet perfektes Hashing selbst im worst Case einen Zugriff auf die Elemente in konstanter Zeit $𝒪(1)$, ist also deutlich schneller. Dies wird erreicht, indem die Werte $s$ der Schlüssel in einem von $0$ bis $\left|T\right|-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 $𝒪(n)$ Zeit, d. h. mit wachsender Schlüsselanzahl $\left|S\right|$ steigt die Zeit der Konstruktion linear.
• Evaluation in $𝒪(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.