Robert Sedgewick: Algorithmen

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


16. Hashing



Getrennte Verkettung

Die obige Hash-Funktion wandelt Schlüssel in Tabellenadressen um; wir müssen noch entscheiden, wie der Fall zu behandeln ist, wenn zwei Schlüssel hierbei auf die gleiche Adresse abgebildet werden. Die einfachste Methode besteht darin, für jede Tabellenadresse eine verkettete Liste zu erzeugen, die die Datensätze enthält, deren Schlüssel auf diese Adresse abgebildet werden. Da die Schlüssel, die auf ein und dieselbe Tabellenposition abgebildet werden, in einer verketteten Liste abgelegt werden, können sie ebensogut geordnet gespeichert werden. Dies führt unmittelbar zu einer Verallgemeinerung des elementaren Listensuchverfahrens, das wir in Kapitel 14 erörtert haben. Anstatt eine einzige Liste mit einem einzigen Listenkopf head zu führen, wie es dort der Fall war, führen wir M Listen mit M Listenköpfen, die wie folgt initialisiert werden:

    type link=^node;
         node=record key,info: integer; next: link end;
    var heads: array[0..M] of link;
        t,z: link;
    procedure initialize;
      var i: integer;
      begin
      new(z); z^.next:=z;
      for i:=0 to M-1 do
        begin new(heads[i]); heads[i]^.next:=z end;
      end;

Nun können die Prozeduren aus Kapitel 14 unverändert benutzt werden, und zur Auswahl zwischen den Listen kann eine Hash-Funktion verwendet werden. Beispielsweise kann listinsert (v, heads[v mod M]) verwendet werden, um v zur Tabelle hinzuzufügen, und t:= listsearch (v, heads[v mod M]) kann benutzt werden, um den ersten Datensatz mit dem Schlüssel v zu finden; anschließend kann sukzessive t:=listsearch (v, t) gesucht werden, bis t=z ist, um die weiteren Datensätze mit dem Schlüssel v zu finden.

Wenn zum Beispiel die Schlüssel aus unserem Beispiel nacheinander unter Benutzung der Hash-Funktion aus Abbildung 16.1 in eine ursprünglich leere Tabelle eingefügt werden, ergibt sich die in Abbildung 16.2 dargestellte Menge von Listen. Diese Methode wird gewöhnlich getrennte Verkettung (separate chaining) genannt, da kollidierende Datensätze zu getrennten verketteten Listen »verkettet« werden.

Abbildung 16.1
Abbildung 16.1 Eine Hash-Funktion (M=11).

Abbildung 16.2
Abbildung 16.2 Getrennte Verkettung.

Offenbar hängt die für eine Suche erforderliche Zeit von der Länge der Listen ab (und von den jeweiligen Positionen der Schlüssel in ihnen). Die Listen könnten auch ungeordnet gelassen werden; das Führen von sortierten Listen ist für diesen Anwendungsfall nicht so wichtig wie beim elementaren sequentiellen Suchen, da die Listen sehr kurz sind.

Für eine »erfolglose Suche« (eine Suche nach einem Datensatz mit einem Schlüssel, der nicht in der Tabelle ist) können wir annehmen, daß durch die Hash-Funktion ausreichend Zufall ins Spiel gebracht wird, so daß jede der M Listen mit gleicher Wahrscheinlichkeit durchsucht wird, und daß die durchsuchte Liste ebenso wie beim sequentiellen Durchsuchen von Listen nur (durchschnittlich) zur Hälfte durchlaufen wird. Die durchschnittliche Länge der untersuchten Liste bei einer erfolglosen Suche beträgt in unserem Beispiel (z nicht mitgerechnet) (0+4+2+2+0+4+0+2+2+1+0)/11 rund 1,55. Dies wäre die durchschnittliche Dauer einer erfolglosen Suche bei ungeordneten Listen; wenn wir für geordnete Listen sorgen, wird diese Zeit etwa halbiert. Für eine »erfolgreiche Suche« (eine Suche nach einem der Datensätze in der Tabelle) nehmen wir an, daß jeder Datensatz mit gleicher Wahrscheinlichkeit gesucht werden soll; sieben der Schlüssel würden als erstes betrachtetes Element einer Liste gefunden, sechs würden als das zweite betrachtete Element gefunden usw., so daß man im Durchschnitt (7*1 + 6*2 + 2*3 + 2*4)/17 rund 1,94 erhält. (Bei dieser Rechnung wird vorausgesetzt, daß gleiche Schlüssel mit einem eindeutigen Identifikator oder einem anderen Mechanismus unterschieden werden und die Suchroutine in geeigneter Weise modifiziert wird, so daß sie in der Lage ist, nach jedem einzelnen Schlüssel zu suchen.)

Eigenschaft 16.1 Eine getrennte Verkettung verringert die Anzahl der Vergleiche bei einer sequentiellen Suche (durchschnittlich) um den Faktor M, wobei zusätzlicher Platz für M Verkettungen beansprucht wird.

Falls N, die Anzahl der Schlüssel in der Tabelle, wesentlich größer als M ist, so ist N/M eine gute Näherung für die durchschnittliche Länge der Listen, da jeder der M Werte der Hash-Funktion aufgrund ihrer Konstruktion »gleich wahrscheinlich« ist. Wie in Kapitel 14 kann erwartet werden, daß erfolglose und erfolgreiche Suchvorgänge sich in einer Liste ungefähr bis zur Mitte abwärts bewegen. w.z.b.w.

Die oben angegebene Implementation verwendet eine Hash-Tabelle von Verkettungen, die auf die Kopfknoten der die eigentlichen Schlüssel enthaltenden Listen zeigen. Eine Alternative zur Verwendung von M Kopfknoten ist, auf diese zu verzichten und heads zu einer Tabelle von Verkettungen zu machen, die auf die ersten Schlüssel in den Listen zeigen. Dies führt jedoch zu gewissen Komplikationen im Algorithmus. Zum Beispiel wird das Hinzufügen eines neuen Datensatzes am Anfang einer Liste zu einer Operation, die sich vom Hinzufügen eines neuen Datensatzes an irgendeiner anderen Stelle einer Liste unterscheidet, da es die Änderung eines Eintrags in der Tabelle der Verkettungen und nicht die Änderung eines Feldes eines Datensatzes erfordert. Eine weitere Implementation besteht darin, den ersten Schlüssel mit in die Tabelle zu nehmen. Obwohl diese Alternativen in manchen Situationen weniger Platz erfordern, ist M gewöhnlich im Vergleich zu N klein genug, daß die zusätzliche Vereinbarung, Kopfknoten zu verwenden, wahrscheinlich gerechtfertigt ist.

Bei einer Implementation der getrennten Verkettung wird für M gewöhnlich ein relativ kleiner Wert gewählt, damit kein großer zusammenhängender Speicherbereich belegt wird. Doch es ist sicher am besten, M genügend groß zu wählen, so daß die Listen kurz genug sind, damit sequentielle Suche zur effizientesten Methode für sie wird; »Hybrid«-Methoden (wie etwa die Verwendung binärer Bäume anstelle verketteter Listen) rechtfertigen den erforderlichen Aufwand sicher nicht. Eine Faustregel lautet, M etwa gleich einem Zehntel der zu erwartenden Schlüssel in der Tabelle zu wählen, so daß zu erwarten ist, daß die Listen ungefähr je zehn Schlüssel enthalten. Einer der Vorzüge der getrennten Verkettung ist, daß diese Entscheidung nicht kritisch ist: Falls mehr Schlüssel als erwartet auftreten, dauern die Suchvorgänge ein wenig länger; falls weniger Schlüssel in der Tabelle sind, wurde vielleicht etwas zusätzlicher Speicherplatz verwendet. Falls Speicherplatz tatsächlich eine kritische Ressource ist, wird bei noch vertretbarem M immerhin noch eine Verbesserung der Leistungsfähigkeit um den Faktor M erzielt.


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