|
Durch die Verwendung einer Hash-Funktion kann es vorkommen, daß mehreren verschiedenen Schlüsseln ein und dieselbe Adresse zugewiesen wird. Die Behandlung solcher Kollisionen kann auf verschiedenste Art und Weise geregelt werden.
2.1 Getrennte Verkettung
Bei der getrennten Verkettung wird für jede Tabellenadresse eine verkettete Liste erzeugt, die jene Datensätze enthält, deren Schlüssel auf diese Adresse abgebildet werden.
Beispiel:
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. Diese Methode führt zu einer Verallgemeinerung des elementaren Listensuchverfahrens. Anstatt eine einzige Liste mit einem Listenkopf zu führen, werden bei der getrennten Verkettung M Listen mit M Listenköpfen geführt.
Allgemein gilt: Eine getrennte Verkettung verringert die Anzahl der Vergleiche bei einer sequentiellen Suche durchschnittlich um den Faktor M. Es wird jedoch zusätzlicher Platz für die Verkettungen beansprucht.
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 die sequentielle Suche zur effizientesten Methode wird.
Als Faustregel gilt, M sollte etwa einem Zehntel der zu erwarteten Schlüssel entsprechen, so daß die Listen durchschnittlich je zehn Schlüssel enthalten.
Falls mehr Schlüssel als erwartet auftreten, dauern die Suchvorgänge ein wenig länger, bei weniger Schlüssel wurde vielleicht etwas mehr Speicherplatz verwendet.
2.2 Offene Adressierung
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 zusätzlich Platz zu lassen, dann lohnt es sich nicht, irgendwelche Verkettungen zu verwenden.
Bei der offenen Adressierung wird im Kollisionsfall der Adreßbereich entweder in konstanten oder in quadratisch ansteigenden Abständen nach freiem Speicherplatz durchsucht.
2.2.1 Lineares Austesten
Die einfachste Methode mit offener Adressierung wird lineares Austesten genannt. Im Falle einer Kollision wird einfach die nächste Position in der Hash-Tabelle untersucht. Ist diese leer, können die Daten dort gespeichert werden. Wenn auch diese Position belegt ist, wird wieder die nächste Position untersucht, solange bis eine leere Position erreicht wurde.
Beispiel:
Der Umfang der Tabelle für lineares Austesten ist größer als für getrennte Verkettung, doch die Gesamtgröße des verwendeten Speicherplatzes ist geringer, da keine Verkettungen benutzt werden.
Allgemein gilt: Für eine Hash-Tabelle, die zu weniger als zwei Dritteln gefüllt ist, erfordert lineares Austesten im Durchschnitt weniger als fünf Tests.
2.2.2 Doppeltes Hashing
Da beim linearen Austesten auch andere Schlüssel untersucht werden, speziell dann, wenn sich die Tabelle zu füllen beginnt, kann das eine drastische Erhöhung der Suchzeit bewirken. Solche Anhäufungen sorgen dafür das lineares Austesten für fast volle Tabellen sehr langsam abläuft.
Mit Hilfe des doppelten Hashing kann dieses Problem praktisch beseitigt werden. Beim Hash-hash-Verfahren wird im Kollisionsfall zur Suche eines freien Speicherplatzes wieder eine Hash-Funktion verwendet, die sich von der ersten unterscheiden sollte auftreten würde. Ansonsten ist dieses Verfahren das geeignetste, um die Anzahl der Kollisionen gering zu halten.
Für das folgende Beispiel wurde folgende Funktion als zweite Hash-Funktion verwendet:
h2 = 8 - (k mod 8).
Beispiel:
Allgemein gilt: Doppeltes Hashing erfordert im Durchschnitt weniger Tests als lineares Austesten.
Methoden der offenen Adressierung können in einer dynamischen Situation, bei der eine nicht vorhersagbare Anzahl von Einfüge- und Löschoperationen auszuführen sind, unzweckmäßig sein. Es muß beim Löschen mit Vorsicht vorgegangen werden, da ein Datensatz nicht einfach aus einer Tabelle entfernt werden kann, die mit Hilfe von linearem Austesten oder doppeltem Hashing erzeugt wurde. Es wurde eine Lücke entstehen, die bei der Suche nach einem anderen Datensatz dazu führt, daß an dieser Stelle abgebrochen wird, anstatt weiterzusuchen. Eine Lösung dieses Problems währe, spezielle Platzhalter zu verwenden.
Zu beachten ist, daß bei der getrennten Verkettung das Löschen eines Datensatzes kein besonderes Problem darstellte.
Die Wahl der besten Hashing-Methode für eine spezielle Anwendung kann sehr kompliziert sein. Im allgemeinen besteht die beste Strategie darin, die Methode der einfachen getrennten Verkettung anzuwenden, um die Suchzeit stark zu verkürzen, wenn die Anzahl der zu verarbeitenden Datensätze nicht im voraus bekannt ist, und doppeltes Hashing zu verwenden, um eine Menge von Schlüsseln zu suchen, deren Größe im voraus grob angegeben werden kann.
|
