Hash-Tabellen versus binäre Bäume

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.

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(\mathrm{lg}(n))$$\mathrm{log}_2(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.$2n$$O(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.

$k_1 \equiv k_2 \implies h(k_1) = h(k_2)$

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.