Perfekte Hash-Funktion

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Eine perfekte Hash-Funktion ist eine Hashfunktion h: 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 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, bietet perfektes Hashing einen Zugriff auf die Elemente in konstanter Zeit \mathcal O(1) im worst Case. 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. Statt in \mathcal O(\log n)\, kann man auf die Elemente dann in konstanter Zeit, also deutlich schneller, zugreifen. 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 perfekte Hashfunktionen arbeiten in O(n) Zeit zur Konstruktion und benötigen etwa 0,3-mal so viel Speicher wie die Schlüsselmenge S.

(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,
  • in konstanter Zeit angefragt werden soll, ob ein Schlüssel in dem Hash vorhanden ist, und
  • zusätzlicher Speicher für die Hashfunktion vorhanden ist.

Ein Verfahren zur Konstruktion perfekter Hashfunktionen ist Hash and Displace.