Robert Sedgewick: Algorithmen

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


16. Hashing



Ausblick

Die oben vorgestellten Methoden sind vollständig analysiert worden, und es ist möglich, einen sehr gründliche Vergleich ihrer Leistungsfähigkeit vorzunehmen. Die oben angegebenen Formeln wurden aus eingehenden Analysen abgeleitet, die von D. E. Knuth in seinem Buch über Sortieren und Suchen dargelegt wurden. Die Formeln zeigen, wie sehr sich das Verhalten bei offener Adressierung verschlechtert, wenn Alpha sich 1 nähert. Bei großen M und N und bei einer zu etwa 90% gefüllten Tabelle erfordert lineares Austesten ungefähr 50 Tests für eine erfolglose Suche gegenüber 10 bei doppeltem Hashing. In der Praxis sollte man jedoch niemals zulassen, daß sich eine Hash-Tabelle zu 90% füllt! Für kleine Auslastungsfaktoren sind nur wenige Tests erforderlich; wenn kleine Auslastungsfaktoren nicht gewährleistet werden können, sollte Hashing nicht angewandt werden.

Der Vergleich von linearem Austesten und doppeltem Hashing mit getrennter Verkettung ist komplizierter, da bei den Methoden mit offener Adressierung mehr Speicherplatz zur Verfügung steht (da keine Verkettungen vorhanden sind). Der verwendete Wert von Alpha sollte auf der Basis der jeweiligen Größe von Schlüsseln und Verkettungen so geändert werden, daß dies berücksichtigt wird. Dies bedeutet, daß es normalerweise nicht gerechtfertigt ist, getrennte Verkettung hinsichtlich der Leistungsfähigkeit höher einzustufen als doppeltes Hashing.

Die Wahl der besten Hashing-Methode für eine spezielle Anwendung kann sehr kompliziert sein. Die allerbeste Methode wird jedoch für eine gegebene Situation selten benötigt, und die verschiedenen Verfahren besitzen ähnliche Merkmale der Leistungsfähigkeit, solange der Speicherplatz nicht zu sehr beansprucht wird. Im allgemeinen besteht die beste Strategie darin, die Methode der einfachen getrennten Verkettung anzuwenden, um die Suchzeiten stark zu verkürzen, wenn die Anzahl der zu verarbeitenden Datensätze nicht im voraus bekannt ist (und eine gute Speicherzuweisungsstrategie zur Verfügung steht), und doppeltes Hashing zu verwenden, um eine Menge von Schlüsseln zu suchen, deren Größe im voraus grob angegeben werden kann.

Es wurden viele weitere Hashing-Methoden entwickelt, die Anwendung in verschiedenen speziellen Situationen finden. Auch wenn wir nicht ins Detail gehen können, wollen wir kurz zwei Beispiele betrachten, um den Charakter speziell angepaßter Hashing-Methoden zu veranschaulichen. Diese und viele weitere Methoden werden in den Büchern von Knuth und Gonnet vollständig beschrieben.

Die erste Methode, die geordnetes Hashing genannt wird, benutzt die Ordnung innerhalb einer Tabelle mit offener Adressierung. Beim gewöhnlichen linearen Austesten brechen wir die Suche ab, wenn wir eine leere Tabellenposition oder einen Datensatz, dessen Schlüssel mit dem Suchschlüssel übereinstimmt, vorfinden; beim geordneten Hashing brechen wir die Suche ab, wenn wir einen Datensatz mit einem Schlüssel finden, der größer oder gleich dem Suchschlüssel ist (die Tabelle muß geschickt aufgebaut werden, damit dies erreicht wird). Es erweist sich, daß sich bei dieser Methode die Zeit für eine erfolglose Suche etwa auf die Zeit für eine erfolgreiche Suche verkürzt. (Dies ist die gleiche Art von Verbesserung, die sich bei getrennter Verkettung ergibt.) Dieses Verfahren ist für Anwendungen nützlich, in denen häufig eine erfolglose Suche ausgeführt wird. Zum Beispiel könnte ein Textverarbeitungssystem einen Algorithmus zur Silbentrennung von Wörtern besitzen, der für die meisten Wörter einwandfrei abläuft, jedoch nicht für bestimmte Ausnahmefälle. In dieser Situation könnte so vorgegangen werden, daß alle Wörter in einem relativ kleinen Ausnahmewörterbuch nachgeschlagen werden, das Wörter enthält, die besonders behandelt werden müssen, wobei die meisten Suchvorgänge erfolglos sein dürften.

Weiterhin gibt es Verfahren, mit denen einige Datensätze während der erfolglosen Suche bewegt werden können, damit das erfolgreiche Suchen effizienter wird. So entwickelte R. P. Brent eine Methode, für die die durchschnittliche Zeit für eine erfolgreiche Suche durch eine Konstante begrenzt werden kann, womit sich eine sehr nützliche Methode für Anwendungen ergibt, in denen häufiges erfolgreiches Suchen in sehr großen Tabellen, wie etwa Wörterbüchern, erforderlich ist.

Dies sind nur zwei Beispiele aus einer großen Zahl von verbesserten Algorithmen, die für Hashing vorgeschlagen worden sind. Viele dieser Verbesserungen sind interessant und haben wichtige Anwendungen. Wie üblich müssen wir jedoch vor verfrühter Anwendung höherentwickelter Methoden warnen, die Spezialisten für ernsthafte Anwendungen des Suchens vorbehalten bleiben sollten, da getrennte Verkettung und doppeltes Hashing einfach, effizient und für die meisten Anwendungen durchaus annehmbar sind.

Hashing wird in vielen Anwendungsfällen den binären Baumstrukturen der beiden vorangegangenen Kapitel vorgezogen, da es etwas einfacher ist und sehr kurze (konstante) Suchzeiten gewährleisten kann, wenn Platz für eine genügend große Tabelle zur Verfügung steht. Binäre Baumstrukturen haben die Vorteile, daß sie dynamisch sind (es wird keine Information über die Anzahl der Einfügungen im voraus benötigt), daß bei ihnen eine Garantie für die Leistungsfähigkeit im ungünstigsten Fall gegeben werden kann (selbst bei der besten Hashing-Methode kann der Fall eintreten, daß die Hash-Funktion alles auf dieselbe Stelle abbildet) und daß sie ein breiteres Spektrum von Operationen unterstützen (was am wichtigsten ist, die Funktion des Sortierens). Wenn diese Faktoren nicht von Bedeutung sind, ist Hashing sicher die zu bevorzugende Suchmethode.


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