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 der Praxis sucht man Hashfunktionen mit 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. (Minimale) perfekte Hashfunktionen sind in der Praxis dann 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.