Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


16. Hashing



Hash-Funktionen

Das erste Problem, dem wir uns zuwenden müssen, ist die Berechnung der Hash-Funktion, die Schlüssel in Tabellenadressen umwandelt. Dies ist eine arithmetische Berechnung mit Eigenschaften, die den Zufallszahlengeneratoren ähneln, die wir in Kapitel 33 betrachten werden. Was benötigt wird, ist eine Funktion, welche Schlüssel (für gewöhnlich ganze Zahlen oder kurze Zeichenfolgen) in ganze Zahlen aus dem Intervall [0..M-1] transformiert, wobei M die Anzahl von Datensätzen ist, die in dem verfügbaren Speicher untergebracht werden kann. Eine ideale Hash-Funktion ist eine Funktion, die sich leicht berechnen läßt und einer »zufälligen« Funktion nahekommt: Für jede Eingabegröße sollte jede Ausgabegröße in gewissem Sinne gleich wahrscheinlich sein.

Da die Methoden, die wir benutzen wollen, arithmetisch sind, besteht der erste Schritt in der Transformation der Schlüssel in Zahlen, mit denen wir arithmetische Operationen ausführen können. Für kleine Schlüssel ist dies bei manchen Programmierumgebungen eventuell gar kein Problem, wenn wir die Möglichkeit haben, Binärdarstellungen von Schlüsseln als Zahlen zu verwenden (siehe die Bemerkungen zu Beginn von Kapitel 10). Für längere Schlüssel könnte man daran denken, Bits aus Zeichenfolgen zu entfernen und sie in einem Maschinenwort zu packen; weiter unten werden wir jedoch eine einheitliche Methode zur Behandlung von Schlüsseln beliebiger Länge kennenlernen.

Nehmen wir zunächst an, daß wir eine große ganze Zahl haben, die unmittelbar unserem Schlüssel entspricht. Die vielleicht gebräuchlichste Methode für das Hashing besteht darin, für M eine Primzahl zu wählen und für einen beliebigen Schlüssel k den Wert der Hash-Funktion nach der Formel h(k) = k mod M zu berechnen. Dies ist ein sehr einfaches Verfahren, das sich häufig leicht realisieren läßt und eine gute Verteilung der Schlüsselwerte ergibt.

Nehmen wir zum Beispiel an, daß die Größe unserer Tabelle 101 ist und wir eine Adresse für den aus vier Zeichen bestehenden Schlüssel A K E Y zu berechnen haben. Wenn der Schlüssel mit Hilfe des einfachen Fünf-Bit-Codes kodiert wird, den wir in Kapitel 10 benutzt haben (wobei der i-te Buchstabe im Alphabet durch die Binärdarstellung der Zahl i dargestellt wird), so können wir ihn als die Binärzahl

00001010110010111001

ansehen, welche äquivalent zu der Dezimalzahl 44217 ist. Nun gilt 44217 == 80 (mod 101), so daß der Schlüssel A K E Y durch die Hash-Funktion auf die Position 80 in der Tabelle abgebildet wird. Es gibt viele mögliche Schlüssel und relativ wenig Positionen in der Tabelle, daher werden viele andere Schlüssel auf die gleiche Position abgebildet (zum Beispiel hat der Schlüssel B A R H in dem oben verwendeten Code ebenfalls die Hash-Adresse 80).

Warum muß die Größe M der Tabelle beim Hashing eine Primzahl sein? Die Antwort auf diese Frage hängt mit den arithmetischen Eigenschaften der Funktion mod zusammen. Im Prinzip behandeln wir den Schlüssel als eine in einem Zahlensystem mit der Basis 32 dargestellte Zahl, mit einer Ziffer für jedes Zeichen im Schlüssel. Wir haben gesehen, daß unser Beispiel A K E Y der Zahl 44217 entspricht, die auch in der Form

1 * 323 + 11 * 322 + 5 * 321 + 25 * 320

geschrieben werden kann, da A der erste Buchstabe im Alphabet ist, K der elfte Buchstabe usw. Nehmen wir nun an, daß wir die unglückliche Wahl M = 32 treffen würden: Da der Wert von k mod 32 durch die Addition von Vielfachen von 32 nicht beeinflußt wird, ist dann die Hash-Funktion jedes beliebigen Schlüssels einfach gleich dem Wert seines letzten Zeichens! Sicher sollte eine gute Hash-Funktion alle Zeichen eines Schlüssels berücksichtigen. Der einfachste Weg, um das zu gewährleisten, ist die Wahl einer Primzahl für M.

Doch die typische Situation liegt dann vor, wenn die Schlüssel keine Zahlen und nicht notwendigerweise kurz, sondern (möglicherweise sehr lange) alphanumerische Zeichenfolgen sind. Wie berechnen wir die Hash-Funktion etwa für V E R Y L O N G K E Y ? In unserem Code entspricht dies der folgenden Kette aus 55 Bits:

1011000101100101100101100011110111000111010110010111001

oder der Zahl

22*3210+5*329+18*328+25*327+*326+15*325+14*324+7*323+11*322+5*321+25,

für die es aufgrund ihrer Größe in den meisten Computern keine für die normalen arithmetischen Funktionen geeignete Darstellung gibt (und wir sollten in der Lage sein, noch weit längere Schlüssel zu behandeln). Es zeigt sich, daß wir in einer solchen Situation trotzdem eine Hash-Funktion von der Art der obigen berechnen können, indem wir den Schlüssel Stück für Stück transformieren. Dabei benutzen wir erneut gewisse arithmetische Eigenschaften der Funktion mod sowie ein einfaches numerisches Verfahren, das Horner-Schema genannt wird (siehe Kapitel 36). Diese Methode beruht auf einer anderen Schreibweise der Zahl, die den Schlüsseln entspricht; für unser Beispiel schreiben wir den folgenden Ausdruck:

(((((((((22*32+5)32+18)32+25)32+12)32+15)32+14)32+7)32+11)32+5)32+25

Dies führt zu einer direkten arithmetischen Methode zur Berechnung der Hash-Funktion:

    h:=key[1];
    for j:=2 to keysize do 
      begin
      h:=((h*32)+key[j]) mod M;
      end;
Hierbei ist h der berechnete Wert der Hash-Funktion. Es wird angenommen, daß key[i] den Wert j enthält, falls das i-te Zeichen des Schlüssels der j-te Buchstabe des Alphabets ist. Um dies zu berechnen, kann die Pascal-Funktion ord zur Konvertierung von Zeichen benutzt werden (und bei Bedarf kann ein umfangreicheres Alphabet vorgesehen werden, indem 64 oder 128 statt 32 verwendet wird). Ohne die Berechnung mod würde dieses Programm die dem Schlüssel entsprechende Zahl wie in der obigen Gleichung berechnen, doch würde die Berechnung für lange Schlüssel zu einem Überlauf führen. Mit dem mod jedoch berechnet es aufgrund der arithmetischen Eigenschaften dieser Funktion genau den Wert der Hash-Funktion; ein Überlauf wird vermieden, da mod stets einen Wert liefert, der kleiner als M ist. Die mit diesem Programm berechnete Hash-Adresse für V E R Y L O N G K E Y mit M = 101 ist 97.

Im Interesse der Klarheit der folgenden Algorithmen setzen wir voraus, daß die Schlüssel ganze Zahlen sind und die Hash-Funktion einfach mod ist. Dadurch soll jedoch nicht der Eindruck erweckt werden, daß diese Situation in der Praxis häufig auftritt; in Wirklichkeit treten bei vielen Anwendungen Datenstrukturen mit längeren Schlüsseln auf, die die Benutzung der obigen Hash-Funktion erfordern. Entsprechende Modifikationen der unten angegebenen Programme für die grundlegenden Algorithmen sind jedoch sehr einfach.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]