|
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, daß 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 würde 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äre, 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.
|
