Robert Sedgewick: Algorithmen

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


16. Hashing



Lineares Austesten

Falls die Anzahl der Elemente, die in die Hash-Tabelle aufgenommen werden sollen, im voraus geschätzt werden kann, und falls ausreichend zusammenhängender Speicherplatz zur Verfügung steht, um alle Schlüssel aufzunehmen und noch etwas Platz übrig zu behalten, lohnt es sich sicher nicht, in der Hash-Tabelle überhaupt irgendwelche Verkettungen zu verwenden. Es wurden verschiedene Verfahren entwickelt, bei denen N Datensätze in einer Tabelle der Größe M > N gespeichert werden, wobei man sich darauf verläßt, daß freie Plätze in der Tabelle bei der Kollisionsbeseitigung helfen können. Solche Verfahren werden Hashing-Methoden mit offener Adressierung genannt.

Die einfachste Methode mit offener Adressierung wird lineares Austesten (linear probing) genannt: Wenn eine Kollision vorliegt (wenn die Hash-Funktion einen Schlüssel auf einen Tabellenplatz abbildet, der bereits belegt ist und dessen Schlüssel nicht mit dem Suchschlüssel übereinstimmt), so teste man einfach die nächste Position in der Tabelle, das heißt, man vergleiche den Schlüssel des dort befindlichen Datensatzes mit dem Suchschlüssel. Es gibt drei mögliche Ergebnisse des Tests: Falls die Schlüssel übereinstimmen, ist die Suche erfolgreich beendet; falls auf dieser Position kein Datensatz vorhanden ist, ist die Suche erfolglos beendet; andernfalls teste man wiederum die nächste Position und fahre damit so lange fort, bis entweder der Suchschlüssel oder eine leere Position in der Tabelle gefunden wird. Falls ein Datensatz, der den Suchschlüssel enthält, im Anschluß an eine erfolglose Suche einzufügen ist, so kann er einfach auf dem leeren Tabellenplatz untergebracht werden, bei dem die Suche endete. Dieses Verfahren läßt sich leicht wie folgt implementieren:

    procedure hashinitialize;
      var i: integer;
      begin
      for i:=0 to M do a[i].key:=maxint;
      end;
    function hashinsert(v: integer): integer;
      var x: integer;
      begin
      x:=h(v);
      while a[x].key<>maxint do x:=(x+1) mod M;
      a[x].key:=v;
      hashinsert:=x;
      end;

Lineares Austesten erfordert einen speziellen Schlüsselwert, um eine leere Stelle in der Tabelle anzuzeigen; das angegebene Programm verwendet für diesen Zweck maxint. Die Berechnung x:=(x+1) mod M entspricht der Überprüfung der nächsten Position (mit zyklischer Rückkehr zum Anfang der Tabelle, wenn ihr Ende erreicht ist). Beachten Sie, daß dieses Programm nicht überprüft, ob die Tabelle vollständig gefüllt ist. (Was würde in diesem Falle passieren?)

Für unser Beispiel einer Menge von Schlüsseln mit M = 19 erhalten wir die in Abbildung 16.3 angegebenen Werte der Hash-Funktion. Wenn diese Schlüssel in der angegebenen Reihenfolge in eine ursprünglich leere Tabelle eingefügt werden, erhalten wir die in Abbildung 16.4 dargestellte Folge.

Abbildung 16.3
Abbildung 16.3 Eine Hash-Funktion (M=19).

Abbildung 16.4
Abbildung 16.4 Lineares Austesten.

Die Implementation von hashsearch ist ähnlich zu hashinsert: Man füge einfach der while-Schleife die Bedingung »a[x].key <> v« hinzu und lösche die nachfolgende Anweisung, mit der v gespeichert wird. Dabei wird der aufrufenden Routine die Aufgabe überlassen zu prüfen, ob die Suche erfolglos war, indem getestet wird, ob die zurückgegebene Tabellenposition tatsächlich v (erfolgreich) oder maxint (erfolglos) enthält. Es könnten auch andere Vereinbarungen getroffen werden; zum Beispiel könnte hashsearch bei einer erfolglosen Suche M zurückgeben. Aus Gründen, die noch klar werden, ist offene Adressierung nicht zweckmäßig, wenn große Mengen von Datensätzen mit mehrfach auftretenden Schlüsseln verarbeitet werden müssen, doch falls jeder Datensatz einen eindeutigen Identifikator besitzt, kann hashsearch leicht an die Behandlung gleicher Schlüssel angepaßt werden.

Der Umfang der Tabelle für lineares Austesten ist größer als für getrennte Verkettung, da M > N gelten muß, doch die Gesamtgröße des verwendeten Speicherplatzes ist geringer, da keine Verkettungen benutzt werden. Die durchschnittliche Anzahl der Elemente, die für eine erfolgreiche Suche überprüft werden müssen, beträgt für dieses Beispiel 33/17 rund 1,94.

Eigenschaft 16.2 Für eine Hash-Tabelle, die zu weniger als zwei Dritteln gefüllt ist, erfordert lineares Austesten im Durchschnitt weniger als fünf Tests.

Die exakte Formel für die durchschnittliche Anzahl der erforderlichen Tests, ausgedrückt unter Verwendung des »Auslastungsfaktors« der Hash-Tabelle Alpha = N/M, lautet 1/2 + 1/2(1-Alpha)2 für eine erfolglose und 1/2 + 1/2(1-Alpha) für eine erfolgreiche Suche. Demnach erhalten wir, wenn wir, wenn wir Alpha = 2/3 wählen, fünf Tests für eine durchschnittliche erfolglose Suche und zwei für eine durchschnittliche erfolgreiche Suche. Eine erfolglose Suche ist stets aufwendiger als eine erfolgreiche; eine erfolgreiche Suche erfordert weniger als fünf Tests, solange die Tabelle nicht mehr als etwa zu 90% gefüllt ist. In dem Maße, wie sich die Tabelle füllt (wenn sich 1 nähert), werden diese Zahlen sehr groß; dies sollte in der Praxis nicht zugelassen werden, wie wir im folgenden erläutern werden. w.z.b.w.


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