Vorteile von binären Suchbäumen gegenüber Hash-Tabellen

Was sind die Vorteile von binären Suchbäumen gegenüber Hash-Tabellen?

Hash-Tabellen können jedes Element in Theta (1) -Zeit nachschlagen, und es ist genauso einfach, ein Element hinzuzufügen ... aber ich bin mir nicht sicher, welche Vorteile umgekehrt auftreten.

Denken Sie daran, dass binäre Suchbäume (referenzbasiert) speichereffizient sind. Sie reservieren nicht mehr Speicher als nötig.

Wenn eine Hash-Funktion beispielsweise einen Bereich hat R(h) = 0...100, müssen Sie ein Array von 100 (Zeiger auf) Elementen zuweisen, selbst wenn Sie nur 20 Elemente hashen. Wenn Sie einen binären Suchbaum zum Speichern derselben Informationen verwenden würden, würden Sie nur so viel Speicherplatz zuweisen, wie Sie benötigen, sowie einige Metadaten zu Links.

Ein Vorteil, auf den noch niemand hingewiesen hat, ist, dass Sie mit dem binären Suchbaum effizient nach Bereichen suchen können.

Um meine Idee zu veranschaulichen, möchte ich einen Extremfall machen. Angenommen, Sie möchten alle Elemente erhalten, deren Schlüssel zwischen 0 und 5000 liegen. Tatsächlich gibt es nur ein solches Element und 10000 andere Elemente, deren Schlüssel nicht im Bereich liegen. BST kann Entfernungssuchen sehr effizient durchführen, da es keinen Teilbaum durchsucht, auf den die Antwort unmöglich ist.

Wie können Sie eine Bereichssuche in einer Hash-Tabelle durchführen? Sie müssen entweder jeden Bucket Space iterieren, der O (n) ist, oder Sie müssen prüfen, ob jeder von 1,2,3,4 ... bis zu 5000 vorhanden ist. (Was ist mit den Schlüsseln zwischen 0 und 5000, die unendlich sind? Zum Beispiel können Schlüssel Dezimalstellen sein.)

Ein "Vorteil" eines Binärbaums besteht darin, dass er durchlaufen werden kann, um alle Elemente der Reihe nach aufzulisten. Dies ist mit einer Hash-Tabelle nicht unmöglich, aber keine normale Operation, die in eine Hash-Struktur umgewandelt wird.

Neben all den anderen guten Kommentaren:

Hash-Tabellen weisen im Allgemeinen ein besseres Cache-Verhalten auf, das im Vergleich zu einem Binärbaum weniger Speicherlesevorgänge erfordert. Bei einer Hash-Tabelle wird normalerweise nur ein einziger Lesevorgang ausgeführt, bevor Sie auf eine Referenz zugreifen können, die Ihre Daten enthält. Der Binärbaum erfordert, wenn es sich um eine ausgeglichene Variante handelt, etwas in der Größenordnung von k * lg (n), das der Speicher für eine Konstante k liest.

Wenn andererseits ein Feind Ihre Hash-Funktion kennt, kann der Feind Ihre Hash-Tabelle dazu zwingen, Kollisionen zu verursachen, was seine Leistung erheblich beeinträchtigt. Die Problemumgehung besteht darin, die Hash-Funktion zufällig aus einer Familie auszuwählen, aber ein BST hat diesen Nachteil nicht. Wenn der Druck in der Hash-Tabelle zu stark ansteigt, neigen Sie häufig dazu, die Hash-Tabelle zu vergrößern und neu zuzuweisen, was eine teure Operation sein kann. Das BST hat hier ein einfacheres Verhalten und neigt nicht dazu, plötzlich viele Daten zuzuweisen und einen Aufwärmvorgang durchzuführen.

Bäume sind in der Regel die ultimative durchschnittliche Datenstruktur. Sie können als Listen fungieren, können für den Parallelbetrieb leicht aufgeteilt werden, können schnell entfernt, eingefügt und in der Größenordnung von O (lg n) nachgeschlagen werden . Sie machen nichts besonders gut, aber sie haben auch kein übermäßig schlechtes Verhalten.

Schließlich sind BSTs in (reinen) funktionalen Sprachen im Vergleich zu Hash-Tabellen viel einfacher zu implementieren und erfordern keine Implementierung destruktiver Aktualisierungen (das Persistenzargument von Pascal oben).

Die Hauptvorteile eines Binärbaums gegenüber einer Hash-Tabelle bestehen darin, dass der Binärbaum Ihnen zwei zusätzliche Operationen bietet, die Sie mit einer Hash-Tabelle nicht (einfach, schnell) ausführen können

• Finden Sie das Element, das einem beliebigen Schlüsselwert am nächsten liegt (oder nicht unbedingt gleich ist) (oder am nächsten über / unter).

• Durchlaufen Sie den Inhalt des Baums in sortierter Reihenfolge

Die beiden sind miteinander verbunden - der Binärbaum hält seinen Inhalt in einer sortierten Reihenfolge, sodass Dinge, die diese sortierte Reihenfolge erfordern, einfach zu erledigen sind.

Ein (ausgeglichener) binärer Suchbaum hat auch den Vorteil, dass seine asymptotische Komplexität tatsächlich eine Obergrenze darstellt, während die "konstanten" Zeiten für Hash-Tabellen amortisierte Zeiten sind: Wenn Sie eine ungeeignete Hash-Funktion haben, können Sie sich auf eine lineare Zeit verschlechtern eher als konstant.

Eine Hashtabelle würde beim erstmaligen Erstellen mehr Platz beanspruchen - sie verfügt über verfügbare Slots für die Elemente, die noch eingefügt werden müssen (unabhängig davon, ob sie jemals eingefügt wurden oder nicht). Ein binärer Suchbaum ist nur so groß, wie er benötigt wird Sein. Auch wenn eine Hash-Tabelle mehr Platz benötigt, auf einem andere Struktur erweitern könnte zeitaufwändig sein, aber das könnte bei der Umsetzung abhängen.

Ein binärer Suchbaum kann mit einer persistenten Schnittstelle implementiert werden, wobei ein neuer Baum zurückgegeben wird, der alte Baum jedoch weiterhin vorhanden ist. Sorgfältig implementiert, teilen sich die alten und neuen Bäume die meisten ihrer Knoten. Sie können dies nicht mit einer Standard-Hash-Tabelle tun.

Ein binärer Baum ist langsamer zu suchen und einzufügen, hat jedoch die sehr schöne Funktion der Infix-Durchquerung, was im Wesentlichen bedeutet, dass Sie die Knoten des Baums in einer sortierten Reihenfolge durchlaufen können.

Das Durchlaufen der Einträge einer Hash-Tabelle macht einfach nicht viel Sinn, da sie alle im Speicher verstreut sind.

Aus Cracking the Coding Interview, 6. Ausgabe

Wir können die Hash-Tabelle mit einem Balanced Binary Search Tree (BST) implementieren. Dies gibt uns eine O (log n) Suchzeit. Dies hat möglicherweise den Vorteil, dass weniger Speicherplatz benötigt wird, da kein großes Array mehr zugewiesen wird. Wir können die Schlüssel auch der Reihe nach durchlaufen, was manchmal nützlich sein kann.

BSTs bieten auch die Operationen "findPredecessor" und "findSuccessor" (um die nächstkleineren und nächstgrößeren Elemente zu finden) in O (logn) -Zeit, was ebenfalls sehr praktisch sein kann. Hash Table kann in dieser Zeit keine Effizienz bieten.

Wenn Sie sortiert auf die Daten zugreifen möchten, muss parallel zur Hash-Tabelle eine sortierte Liste geführt werden. Ein gutes Beispiel ist Dictionary in .Net. (Siehe http://msdn.microsoft.com/en-us/library/3fcwy8h6.aspx ).

Dies hat den Nebeneffekt, dass nicht nur Einfügungen verlangsamt werden, sondern auch mehr Speicher als ein B-Baum verbraucht wird.

Da ein B-Baum sortiert ist, ist es außerdem einfach, Ergebnisbereiche zu finden oder Gewerkschaften oder Zusammenführungen durchzuführen.

Es hängt auch von der Verwendung ab, Hash ermöglicht es, die genaue Übereinstimmung zu finden. Wenn Sie einen Bereich abfragen möchten, ist BST die richtige Wahl. Angenommen, Sie haben viele Daten e1, e2, e3 ..... en.

Mit der Hash-Tabelle können Sie jedes Element in konstanter Zeit lokalisieren.

Wenn Sie Bereichswerte finden möchten, die größer als e41 und kleiner als e8 sind, kann BST dies schnell finden.

Das Wichtigste ist die Hash-Funktion, mit der eine Kollision vermieden wird. Natürlich können wir eine Kollision nicht vollständig vermeiden. In diesem Fall greifen wir auf Verkettung oder andere Methoden zurück. Dadurch ist der Abruf im schlimmsten Fall nicht mehr konstant.

Sobald die Hash-Tabelle voll ist, muss sie ihre Bucket-Größe erhöhen und alle Elemente erneut kopieren. Dies sind zusätzliche Kosten, die gegenüber BST nicht anfallen.

Hash-Tabellen eignen sich nicht für die Indizierung. Wenn Sie nach einem Bereich suchen, sind BSTs besser. Aus diesem Grund verwenden die meisten Datenbankindizes B + -Bäume anstelle von Hash-Tabellen

Binäre Suchbäume sind eine gute Wahl, um ein Wörterbuch zu implementieren, wenn auf den Schlüsseln eine Gesamtreihenfolge (Schlüssel sind vergleichbar) definiert ist und Sie die Bestellinformationen beibehalten möchten.

Da BST die Bestellinformationen beibehält, stehen Ihnen vier zusätzliche dynamische Set-Operationen zur Verfügung, die mit Hash-Tabellen nicht (effizient) ausgeführt werden können. Diese Operationen sind:

1. Maximal
2. Minimum
3. Nachfolger
4. Vorgänger

Alle diese Operationen haben wie jede BST-Operation eine Zeitkomplexität von O (H). Darüber hinaus bleiben alle gespeicherten Schlüssel in der BST sortiert, sodass Sie die sortierte Reihenfolge der Schlüssel erhalten, indem Sie den Baum der Reihe nach durchlaufen.

Zusammenfassend lässt sich sagen, dass die Hash-Tabelle (meistens) in Bezug auf die Leistung unschlagbar ist, wenn Sie nur Operationen einfügen, löschen und entfernen möchten. Wenn Sie jedoch einige oder alle der oben aufgeführten Vorgänge ausführen möchten, sollten Sie eine BST verwenden, vorzugsweise eine selbstausgleichende BST.

Der Hauptvorteil der Hash-Tabelle besteht darin, dass fast alle Operationen in ~ = O (1) ausgeführt werden. Und es ist sehr einfach zu verstehen und umzusetzen. Es löst viele "Interviewprobleme" effizient. Also, wenn du ein Coding-Interview knacken willst, mache beste Freunde mit Hash-Tabelle ;-)

Eine Hashmap ist ein festgelegtes assoziatives Array. Ihr Array von Eingabewerten wird also in Buckets zusammengefasst. In einem offenen Adressierungsschema haben Sie einen Zeiger auf einen Bucket, und jedes Mal, wenn Sie einem Bucket einen neuen Wert hinzufügen, finden Sie heraus, wo im Bucket freie Speicherplätze vorhanden sind. Es gibt verschiedene Möglichkeiten, dies zu tun: Sie beginnen am Anfang des Buckets und erhöhen den Zeiger jedes Mal und testen, ob er belegt ist. Dies wird als lineare Abtastung bezeichnet. Anschließend können Sie eine binäre Suche wie "Hinzufügen" durchführen, bei der Sie die Differenz zwischen dem Anfang des Buckets verdoppeln und bei jeder Suche nach einem freien Speicherplatz nach oben oder unten verdoppeln. Dies wird als quadratische Abtastung bezeichnet. OK. Das Problem bei beiden Methoden besteht nun darin, dass Sie Folgendes tun müssen, wenn der Bucket in die nächste Bucket-Adresse überläuft.

1. Verdoppeln Sie jede Bucket-Größe - malloc (N Buckets) / ändern Sie die Hash-Funktion - Erforderliche Zeit: hängt von der malloc-Implementierung ab
2. Übertragen / kopieren Sie alle früheren Bucket-Daten in die neuen Bucket-Daten. Dies ist eine O (N) -Operation, bei der N die gesamten Daten darstellt

OK. Aber wenn Sie eine verknüpfte Liste verwenden, sollte es kein solches Problem geben, oder? Ja, in verknüpften Listen haben Sie dieses Problem nicht. Wenn Sie bedenken, dass jeder Bucket mit einer verknüpften Liste beginnt, und wenn Sie 100 Elemente in einem Bucket haben, müssen Sie diese 100 Elemente durchlaufen, um das Ende der verknüpften Liste zu erreichen. Daher dauert es einige Zeit, bis List.add (Element E)

1. Hash das Element zu einem Bucket-Normal wie in allen Implementierungen
2. Nehmen Sie sich Zeit, um das letzte Element in der Bucket-O (N) -Operation zu finden.

Der Vorteil der Linkedlist-Implementierung besteht darin, dass Sie nicht die Speicherzuweisungsoperation und die O (N) -Übertragung / Kopie aller Buckets benötigen, wie im Fall der Open-Addressing-Implementierung.

Um die O (N) -Operation zu minimieren, konvertieren Sie die Implementierung in die eines binären Suchbaums, in dem Suchoperationen O (log (N)) sind, und fügen Sie das Element basierend auf seinem Wert an seiner Position hinzu. Das zusätzliche Merkmal eines BST ist, dass es sortiert kommt!

Binäre Suchbäume können schneller sein, wenn sie mit Zeichenfolgenschlüsseln verwendet werden. Besonders wenn die Saiten lang sind.

Binäre Suchbäume mit Vergleichen für weniger / größer, die für Zeichenfolgen schnell sind (wenn sie nicht gleich sind). So kann eine BST schnell antworten, wenn eine Zeichenfolge nicht gefunden wird. Wenn es gefunden wurde, muss es nur einen vollständigen Vergleich durchführen.

In einer Hash-Tabelle. Sie müssen den Hash der Zeichenfolge berechnen. Dies bedeutet, dass Sie alle Bytes mindestens einmal durchlaufen müssen, um den Hash zu berechnen. Andererseits, wenn ein passender Eintrag gefunden wird.