Hash-Tabellen versus binäre Bäume

30

Bei der Implementierung eines Wörterbuchs ("Ich möchte Kundendaten anhand ihrer Kunden-IDs nachschlagen") werden typischerweise Hash-Tabellen und binäre Suchbäume verwendet. Ich weiß zum Beispiel, dass die C ++ STL-Bibliothek Wörterbücher (sie nennen sie Maps) mithilfe von (ausgeglichenen) binären Suchbäumen implementiert und das .NET-Framework Hash-Tabellen unter der Haube verwendet.

Was sind die Vor- und Nachteile dieser Datenstrukturen? Gibt es eine andere Option, die in bestimmten Situationen sinnvoll ist?

Beachten Sie, dass mich Fälle nicht sonderlich interessieren, in denen die Schlüssel eine starke Grundstruktur haben, zum Beispiel ganze Zahlen zwischen 1 und n oder so.

Alex ten Brink
quelle
1
Ich werde Sie verärgern, aber Sie können nicht einfach "Ganzzahlen zwischen 1 und n" sagen, da in diesem Fall ein Array alle anderen Datenstrukturen übertrifft :-). "Strings" scheint fair und deckt die meisten Situationen ab.
Jmad
@jmad er sagte, dass er nicht an diesem Fall interessiert ist.
Joe
@ Joe Ich dachte, es sei klar, dass ich das berücksichtigt habe. Jedenfalls ist das kein Grund, das schlechteste Beispiel für einen Schlüssel zu nennen.
Jmad
1
Tatsächlich wurden in .NET sowohl Wörterbücher unter Verwendung von Bäumen als auch Wörterbücher unter Verwendung von Hash-Tabellen implementiert (und seit 2011 auch in C ++).
13.
Mögliches selbes
Ciro Santilli am

Antworten:

26

Zu diesem Thema könnte eine ganze Abhandlung geschrieben werden. Ich werde nur einige wichtige Punkte behandeln und die Diskussion über andere Datenstrukturen auf ein Minimum beschränken (es gibt tatsächlich viele Varianten). In dieser Antwort ist die Anzahl der Schlüssel im Wörterbuch.n

Die kurze Antwort ist, dass Hash-Tabellen in den meisten Fällen schneller sind , aber im schlimmsten Fall sehr schlecht sein können. Suchbäume haben viele Vorteile, einschließlich zahmes Worst-Case-Verhalten , sind jedoch in typischen Fällen etwas langsamer.

Symmetrische binäre Suchbäume haben eine ziemlich einheitliche Komplexität: jedes Element nimmt einen Knoten in dem Baum (typischerweise 4 Speicherworte) und die Grundoperationen (lookup, Insertion, Deletion) nimmt Zeit (garantiert asymptotische obere Grenze). Genauer gesagt erfolgt ein Zugriff in dem Baum zu l o g 2 ( n ) Vergleichen.O(lg(n))log2(n)

Hash-Tabellen sind etwas variabler. Sie benötigen ein Array von ca. Zeigern. Der Zugriff auf ein Element hängt von der Qualität der Hash-Funktion ab. Der Zweck einer Hash-Funktion besteht darin, die Elemente zu dispergieren. Eine Hash-Tabelle „funktioniert“, wenn alle Elemente, die Sie darin speichern möchten, unterschiedliche Hashes haben. Wenn dies der Fall ist, benötigen die Grundoperationen (Nachschlagen, Einfügen, Löschen) 0 ( 1 ) Zeit mit einer ziemlich kleinen Konstante (eine Hash-Berechnung plus eine Zeigersuche). Dies macht Hash-Tabellen in vielen typischen Fällen sehr schnell.2nO(1)

Ein allgemeines Problem bei Hash-Tabellen ist, dass die -Komplexität nicht garantiert ist.O(1)

  • Außerdem gibt es einen Punkt, an dem die Tabelle voll wird. Wenn dies geschieht (oder besser, kurz davor), muss der Tisch vergrößert werden, was das Verschieben aller seiner Elemente zu einem -Kosten erfordert . Dies kann zu ruckeligem Verhalten führen, wenn viele Elemente hinzugefügt werden.O(n)
  • O(1)

Wenn Sie werfen Datenlokalität in die Mischung, tun Hash - Tabellen schlecht. Sie funktionieren genau deshalb, weil sie verwandte Elemente weit voneinander entfernt speichern. Wenn die Anwendung also nach Elementen sucht, die nacheinander ein Präfix verwenden, werden Cache-Effekte nicht wirksam. Dies ist nicht relevant, wenn die Anwendung im Wesentlichen zufällige Suchen durchführt.

Ein weiterer Faktor für Suchbäume ist die unveränderliche Datenstruktur: Wenn Sie eine Kopie eines Baums erstellen und einige Elemente darin ändern müssen, können Sie den größten Teil der Datenstruktur gemeinsam nutzen. Wenn Sie eine Kopie einer Hash-Tabelle erstellen, müssen Sie das gesamte Array von Zeigern kopieren. Wenn Sie in einer rein funktionalen Sprache arbeiten, sind Hash-Tabellen häufig keine Option.

k1k2h(k1)=h(k2)

Insbesondere wenn Sie die Reihenfolge der Schlüssel benötigen , beispielsweise wenn Sie die Schlüssel in alphabetischer Reihenfolge auflisten möchten, sind Hash-Tabellen keine Hilfe (Sie müssen sie sortieren), wohingegen Sie kann einen Suchbaum direkt durchlaufen.

Sie können binäre Suchbäume und Hash-Tabellen in Form von Hash-Bäumen kombinieren . Ein Hash-Baum speichert Schlüssel in einem Suchbaum entsprechend ihrem Hash. Dies ist beispielsweise in einer rein funktionalen Programmiersprache nützlich, in der Sie Daten bearbeiten möchten, für die es keine einfach zu berechnende Ordnungsbeziehung gibt.

Wenn die Schlüssel Zeichenfolgen (oder ganze Zahlen) sind, kann ein Versuch eine andere Option sein. Ein Trie ist ein Baum, der jedoch anders indiziert ist als ein Suchbaum: Sie schreiben den Schlüssel binär und gehen nach links für eine 0 und nach rechts für eine 1. Die Kosten für einen Zugriff sind somit proportional zur Länge des Schlüssels. Versuche können komprimiert werden, um Zwischenknoten zu entfernen. Dies ist als Patricia Trie oder Radix-Baum bekannt . Radix-Bäume können ausgeglichene Bäume übertreffen, insbesondere wenn viele Schlüssel ein gemeinsames Präfix haben.

Gilles 'SO - hör auf böse zu sein'
quelle
2
Haben BSTs nicht auch eine schlechte Datenlokalität?
Svick
@svick Je nachdem, wie die Knoten zugeordnet sind, können sie dies auch tun oder nicht. Das Erhöhen der Arität des Baums kann helfen, ohne die Laufzeit zu beeinträchtigen (die Kosten sind größer und komplexer Code).
Gilles 'SO - hör auf böse zu sein'
2
Bei einer BST ist es einfach, die Elemente "in Ordnung" zu bringen, bei einer Hash-Tabelle kommt dies nicht in Frage.
Vonbrand
Warum ist es wichtig, dass Hash-Tabellen aus Sicherheitsgründen eine schlechte Worst-Case-Zeit haben, wenn ihr Durchschnittsfall besser ist als der von Binärbäumen? Ich stelle mir vor, dass der Nutzerkomfort in einem ungefähr linearen Verhältnis dazu steht, wie lange es dauert, bis der Baum fertig ist. Daher sollte der erwartete (durchschnittliche) Wert alles sein, was zählt.
Kelmikra
@ Kyth'Py1k Was meinst du mit "der Baum zum Beenden"? Der Sinn von Hash-Tabellen besteht darin, auf jeweils einen Wert und nicht auf den gesamten Baum zuzugreifen, da sonst eine Liste oder ein Array besser funktioniert. Selbst in Situationen, in denen es auf den Durchschnittswert ankommt (was nicht immer der Fall ist, z. B. wenn Sie Echtzeitbeschränkungen haben), ist es der Durchschnitt über die Anforderungen, die in einer bestimmten Situation gestellt werden und die häufig überhaupt nicht einheitlich über den Tisch verteilt sind - zB auf ein bestimmtes Präfix voreingenommen.
Gilles 'SO- hör auf böse zu sein'