Hash -Tische gegen binäre Bäume

Question

Bei der Implementierung eines Wörterbuchs ("Ich möchte Kundendaten nach ihren Kunden -IDs suchen) sind die verwendeten typischen Datenstrukturen Hash -Tabellen und binäre Suchbäume. Ich weiß zum Beispiel, dass die C ++ STL -Bibliothek Wörterbücher (sie nennen sie Karten) mit (ausgewogen) binären Suchbäumen implementiert, und das .NET -Framework verwendet Hash -Tabellen unter der Motorhaube.

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

Beachten Sie, dass ich nicht besonders an Fällen interessiert bin, in denen die Schlüssel eine stark zugrunde liegende Struktur haben, beispielsweise alle Ganzzahlen zwischen 1 und n oder so.

Answer 1

Eine ganze Abhandlung könnte zu diesem Thema geschrieben werden; Ich werde nur einige herausragende Punkte abdecken, und ich werde die Diskussion anderer Datenstrukturen auf ein Minimum halten (es gibt in der Tat viele Varianten). In dieser Antwort ist $ n $ die Anzahl der Schlüssel im Wörterbuch.

Die kurze Antwort ist das Hash -Tabellen sind in den meisten Fällen schneller, kann aber im schlimmsten Fall sehr schlecht sein. Bäume suchen haben viele Vorteile, einschließlich zahmes schlechtestes Verhalten, sind aber in typischen Fällen etwas langsamer.

Ausgeglichene binäre Suchbäume Haben Sie eine ziemlich einheitliche Komplexität: Jedes Element nimmt einen Knoten in den Baum (typischerweise 4 Speicherwörter), und die grundlegenden Operationen (Suchvorgänge, Einfügung, Löschen) nehmen $ o ( mathrm {lg} (n)) $ Zeit (garantiert garantiert Asymptotische Obergrenze). Genauer gesagt dauert ein Zugriff auf den Baum ungefähr $ mathrm {log} _2 (n) $ Vergleiche.

Hash -Tische sind etwas variabler. Sie benötigen eine Reihe von ca. 2n $ Zeiger. 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 zerstreuen. Eine Hash -Tabelle „funktioniert“, wenn alle Elemente, die Sie darin speichern möchten, unterschiedliche Hashes haben. Wenn dies der Fall ist, dauern die grundlegenden Operationen (Suche, Einfügung, Löschung) $ O (1) $ Zeit, mit einer ziemlich kleinen Konstante (eine Hash -Berechnung plus eine Zeiger -Suche). Dies macht Hash -Tabellen in vielen typischen Fällen sehr schnell.

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

• Für zusätzlich gibt es einen Punkt, an dem die Tabelle voll wird. Wenn dies geschieht (oder, besser, nur vor diesem Fall), muss der Tisch vergrößert werden, was erfordert, dass alle Elemente für einen $ O (n) $ Kosten verschoben werden. Dies kann ein „ruckartiges“ Verhalten einführen, wenn viele Elemente hinzugefügt werden.
• Es ist möglich, dass die Eingabe über einige Hash -Werte kollidiert. Dies geschieht selten natürlich, aber es kann ein Sicherheitsproblem sein, wenn die Eingaben von einem Angreifer ausgewählt werden: Es ist eine Möglichkeit, einige Server erheblich zu verlangsamen. Dieses Problem hat einige Programmiersprache -Implementierungen (wie Perl und Python) dazu veranlasst, von einer einfachen alten Hash -Tabelle zu einer Hash -Funktion zu wechseln, die eine zufällige Zahl beinhaltet (was die multiplikative Konstante in $ O (1) $) oder an einem binären Suchbaum erhöht. Während Sie Kollisionen durch die Verwendung eines kryptografischen Hashs vermeiden können, wird dies in der Praxis nicht geschehen, da kryptografische Hashes vergleichsweise sehr langsam berechnet werden.

Wenn du wirfst Datenlokalität In der Mischung machen Hash -Tabellen schlecht. Sie arbeiten gerade, weil sie verwandte Elemente weit auseinander speichern. Wenn die Anwendung Elemente nachlässt, die ein Präfix nacheinander teilen, profitiert sie nicht von Cache -Effekten. Dies ist nicht relevant, wenn die Anwendung im Wesentlichen zufällige Lookups vornimmt.

Ein weiterer Faktor für Suchbäume ist, dass sie eine sind unveränderlich Datenstruktur: Wenn Sie eine Kopie eines Baumes nehmen und einige Elemente darin ändern müssen, können Sie den größten Teil der Datenstruktur teilen. Wenn Sie eine Kopie einer Hash -Tabelle nehmen, müssen Sie die gesamte Spitze von Zeigern kopieren. Wenn Sie in rein funktionalen Sprachen arbeiten, sind Hash -Tabellen häufig keine Option.

Wenn Sie über Strings hinausgehen, stellen Hash -Tabellen und binäre Suchbäume unterschiedliche Anforderungen am Datentyp des Schlüssels: Hash -Tabellen erfordern eine Hash -Funktion (eine Funktion von den Schlüssel zu den Ganzzahlen, so dass $ k_1 äquiv k_2 impliziert H (k_1 ) = H (k_2) $, während binäre Suchbäume eine Gesamtreihenfolge erfordern. Hashes können manchmal zwischengespeichert werden, wenn in der Datenstruktur genügend Platz vorhanden ist Unpraktisch. Andererseits können Vergleiche von Abkürzungen profitieren: Wenn Schlüssel in den ersten Bytes häufig unterscheiden, kann ein negativer Vergleich sehr schnell sein.

Insbesondere, wenn Sie das brauchen werden bestellen Wenn Sie beispielsweise in der Lage sein möchten, die Schlüssel in alphabetischer Reihenfolge aufzulisten, sind Hash -Tabellen keine Hilfe (Sie müssen sie sortieren), während Sie einen Suchbaum einfach in Ordnung durchqueren können.

Sie können binäre Suchbäume und Hash -Tabellen in Form von kombinieren Haschbäume. Ein Hash -Baum speichert Schlüssel in einem Suchbaum nach ihrem Hash. Dies ist beispielsweise in einer rein funktionalen Programmiersprache nützlich, in der Sie an Daten arbeiten möchten, die keine leicht zu erfundene Ordnung haben.

Wenn die Schlüssel Strings (oder Ganzzahlen) sind, a Trie Kann eine weitere Option sein. Ein Trie ist ein Baum, aber anders als ein Suchbaum indiziert: Sie schreiben den Schlüssel in Binärer und gehen nach links für eine 0 und rechts für einen 1. Die Kosten eines Zugangs sind somit proportional zur Länge des Schlüssels. Versuche können komprimiert werden, um Zwischenknoten zu entfernen. Dies ist als a bekannt Patricia Trie oder Radixbaum. Radix -Bäume können ausgewogene Bäume übertreffen, insbesondere wenn viele Schlüssel ein gemeinsames Präfix haben.