Vorteile von binären Suchbäume über Hash Tables

StackOverflow https://stackoverflow.com/questions/4128546

Frage

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

Hash-Tabellen können ein beliebiges Element in Theta nachschlagen (1) Zeit, und es ist genauso einfach ein Element hinzuzufügen .... aber ich bin nicht sicher, der Vorteile in die andere Richtung um.

War es hilfreich?

Lösung

Beachten Sie, dass Binary Suchbäume (Referenz-basierte) sind speichereffizient. Sie haben nicht mehr Speicher reservieren, als sie müssen.

Zum Beispiel, wenn eine Hash-Funktion eine Reihe R(h) = 0...100 hat, dann müssen Sie eine Reihe von 100 (Zeiger-to) Elemente zuordnen, auch wenn Sie nur 20 Elemente Hashing. Wenn Sie einen binären Suchbaum zu verwenden, sind die gleichen Informationen zu speichern, würden Sie nur so viele Speicherplatz zuweisen, wie Sie benötigt wird, sowie einige Metadaten über Links.

Andere Tipps

Ein Vorteil, dass sonst niemand bemerkt hat, ist, dass binärer Suchbaum Sie Bereich Suche effizient tun können.

Um meine Idee zu illustrieren, möchte ich einen Extremfall machen. Sagen Sie bitte alle Elemente, deren Schlüssel zwischen 0 bis 5000. Und tatsächlich gibt es nur ein solches Element und 10000 andere Elemente, deren Schlüssel nicht im Bereich erhalten möchten. BST kann sehr effizient Bereich sucht tun, da es nicht einen Teilbaum durchsucht, was unmöglich ist, die Antwort zu haben.

Während, wie können Sie tun Bereich sucht in einer Hash-Tabelle? Sie müssen entweder auf Iterierte jeden Eimer Raum, der O (n) ist, oder Sie haben zu suchen, ob jeder von 1,2,3,4 ... bis zu 5000 existiert. (Was ist mit den Tasten zwischen 0 und 5000 ist eine unendliche Menge? ZB Schlüssel können Dezimalzahlen sein)

Ein „Vorteil“ eines binären Baum ist, dass es zur Liste aus allen Elementen, um durchlaufen werden kann. Dies ist mit einer Hash-Tabelle nicht unmöglich, aber ist kein normales Betrieb eines Design in eine Hash-Struktur.

Zusätzlich zu allen anderen guten Anmerkungen:

Hash-Tabellen haben im Allgemeinen eine bessere Cache-Verhalten erfordert weniger Speicher liest im Vergleich zu einem binären Baum. Für eine Hash-Tabelle entstehen Sie in der Regel nur einen einzigen lesen, bevor Sie Zugriff auf eine Referenz haben Halten Sie Ihre Daten. Der binäre Baum, wenn es sich um eine ausgewogene Variante ist, erfordert etwas in der Größenordnung von k * lg (n) Speicher liest für eine Konstante k.

Auf der anderen Seite, wenn ein Feind kennt Ihre Hash-Funktion kann der Feind Ihre Hash-Tabelle erzwingen Kollisionen zu machen, stark seine Leistung zu behindern. Die Abhilfe ist die Hash-Funktion zufällig aus einer Familie zu wählen, aber ein BST hat diesen Nachteil nicht. Auch wenn der Druck Hash-Tabelle zu viel wächst, neigen Sie dazu, oft enlargen und die Hash-Tabelle neu zuweisen, die eine teuere Operation sein können. Das BST hat einfachere Verhalten hier und neigt nicht plötzlich eine große Datenmenge zu verteilen und einen Aufguß Betrieb zu tun.

Bäume neigen dazu, die ultimative durchschnittliche Datenstruktur zu sein. Sie können als Listen handeln, kann leicht Split für den Parallelbetrieb sein, müssen schnelle Entfernung, Insertion und Nachschlagen in der Größenordnung von O (lg n) . Sie tun nichts besonders gut, aber sie haben kein allzu schlechtes Verhalten nicht.

Schließlich sind BSTs viel leichter in (rein) funktionalen Sprachen zu implementieren, verglichen mit Hash-Tabellen und sie benötigen kein destruktives Updates implementiert (von Pascal der Ausdauer Argument oben) werden.

Die wichtigsten Vorteile eines binären Baum über einen Hash-Tabelle ist, dass der binäre Baum Sie zwei zusätzliche Operationen gibt Ihnen nicht tun können (einfach, schnell) mit einer Hash-Tabelle

  • Sie das Element am nächsten (nicht notwendigerweise gleich) einen beliebigen Schlüsselwert (oder am nächst oben / unten)

  • iterate durch den Inhalt des Baumes in sortierter Reihenfolge

Die beiden sind verbunden -. Der binäre Baum hält seinen Inhalt in einer sortierten Reihenfolge, so dass Dinge, die sortierten Reihenfolge erfordern, sind einfach zu tun

A (symmetrisch) binärer Suchbaum hat auch den Vorteil, dass seine asymptotische Komplexität ist eigentlich eine obere Grenze, während die „Konstante“ Zeiten für Hash-Tabellen amortisieren Zeiten sind: Wenn Sie eine ungeeignete Hash-Funktion haben, könnten Sie erniedrigender am Ende um die lineare Zeit, anstatt konstant.

Eine Hash-Tabelle würde mehr Platz in Anspruch nehmen, wenn es zum ersten Mal erstellt wird - es verfügbare Slots für die Elemente hat, die noch eingeführt werden (ob sie jemals eingesetzt werden), ein binärer Suchbaum wird nur so groß sein, wie es muss sein. Auch wenn eine Hash-Tabelle mehr Platz benötigt, auf einem andere Struktur erweitert könnte zeitaufwändig sein, aber das könnte bei der Umsetzung abhängen.

Ein binärer Suchbaum kann mit einer persistent Schnittstelle implementiert werden, wobei ein neuer Baum zurückgegeben wird, aber der alte Baum weiter zu existieren. Umgesetzt sorgfältig, die alten und neuen Bäume Aktien den größten Teil ihrer Knoten. Sie können dies nicht mit einer Standard-Hash-Tabelle.

Ein Binärbaum ist langsamer zu suchen und einfügen in, hat aber die sehr nette Eigenschaft der Infix-Traversal, die im Wesentlichen bedeutet, dass Sie durch die Knoten des Baums in einer sortierten Reihenfolge durchlaufen können.

Iterieren durch die Einträge einer Hash-Tabelle einfach nicht viel Sinn machen, weil sie alle im Speicher verstreut sind.

BSTs auch die „findPredecessor“ bieten und „findSuccessor“ Operationen in O (log n) Zeit (auf die nächste kleinste und nächstgrößere Elemente zu finden), die auch sehr praktisch Operationen sein könnte. Hash-Tabelle nicht bieten kann in dieser Zeit Effizienz.

die Codierung Interview Cracking, 6. Auflage

Wir können die Hash-Tabelle mit einem ausgewogenen binären Suchbaum (BST) implementieren. Dies gibt uns eine O (lügen n) Lookup-Zeit. Der Vorteil dabei ist, mit potenziell weniger Platz, da wir nicht mehr ein großes Array zuweisen. Wir können auch über die Tasten, um durchlaufen, was nützlich manchmal sein kann.

Wenn Sie die Daten in einer sortierten Weise zugreifen möchten, dann eine sortierte Liste hat parallel zu der Hash-Tabelle beibehalten werden. Ein gutes Beispiel ist Wörterbuch in .Net. (Siehe http://msdn.microsoft.com/en-us/library/3fcwy8h6 aspx ).

Das hat den Nebeneffekt, nicht nur Einsätze verlangsamt, aber es verbraucht eine größere Menge an Speicher als ein B-Baum.

Da ferner ein B-Baum sortiert ist, ist es einfach reicht von Ergebnissen zu finden, oder Gewerkschaften oder verschmilzt auszuführen.

Es hängt auch von der Verwendung ermöglicht Hash genaue Übereinstimmung zu finden. Wenn Sie einen Bereich abgefragt werden sollen, dann ist BST die Wahl. Angenommen, Sie haben eine Menge Daten e1, e2, e3 ..... en.

Mit Hash-Tabelle, die Sie jedes Element in konstanter Zeit finden können.

Wenn Sie Bereichswerte größer als e41 finden wollen und weniger als e8, BST kann man erkennen, schnell finden.

Das Wichtigste ist, die Hash-Funktion verwendet, um eine Kollision zu vermeiden. Natürlich können wir nicht völlig um eine Kollision zu vermeiden, in diesem Fall werden wir auf Verkettungs oder andere Methoden zurückgreifen. Dies macht Retrieval nicht mehr konstant Zeit im schlimmsten Fall.

Wenn voll ist, hat Hash-Tabelle seine Eimer Größe zu erhöhen und wieder alle Elemente kopieren über. Dies ist eine zusätzliche Gebühr nicht vorhanden über BST.

A hashmap ist ein Set assoziative Array. So wird Ihr Array von Eingabewerten in Eimern gesammelt. In einem offenen Adressierungsschema, haben Sie einen Zeiger auf einen Eimer, und jedes Mal, wenn Sie einen neuen Wert in einen Eimer hinzufügen, können Sie herausfinden, wo in den Eimern dort Freiräume sind. Es gibt ein paar Möglichkeiten, this- Sie beginnen am Anfang des Eimers und erhöhen den Zeiger jedes Mal und testen, ob seine besetzt zu tun. Dies wird linear Sondieren genannt. Dann können Sie eine binäre Suche wie add tun, wo Sie den Unterschied zwischen dem Beginn des Eimers verdoppeln und wo Sie verdoppeln oder wieder nach unten jedes Mal, wenn Sie für einen freien Platz suchen. Dies wird quadratisches Sondieren genannt. IN ORDNUNG. Nun sind die Probleme in diesen beiden Verfahren besteht darin, dass, wenn der Eimer in den nächsten Eimer Adresse überläuft, dann müssen Sie -

  1. zweimal auf jedem Eimer größen- malloc (N Eimer) / ändern, um die Hash-funktions- Dauer: abhängig von malloc Implementierung
  2. Transfer / Kopieren Sie jede der früheren Eimer Daten in die neuen Eimer Daten. Dies ist ein O (n) -Operation, wobei N die gesamten Daten
    3. steht

OK. aber wenn Sie eine LinkedList verwenden soll es nicht so ein Problem sein, oder? Ja, verkettete Listen Sie dieses Problem nicht haben. Betrachtet man jeden Eimer mit einer verknüpften Liste zu beginnen, und wenn Sie 100 Elemente in einem Eimer haben es erfordert, dass Sie diese 100 Elemente zu durchqueren, um das Ende des LinkedList daher die List.add (Element E) erreichen wird einige Zeit dauern, um -

  1. Hash das Element auf einen Eimer-normal wie in allen Implementierungen
  2. Nehmen Sie sich Zeit das letzte Element zu finden in dem Eimer-O (N) Betrieb.

Der Vorteil der LinkedList Implementierung ist, dass Sie nicht brauchen, die Speicherzuordnungsoperation und O (N) Transfer / Kopie aller Eimer wie im Fall der offenen Adressierung Umsetzung.

Also, der Weg, um die O zu minimieren (N) Betrieb ist die Umsetzung derjenigen eines binären Suchbaum zu konvertieren, wo Operationen O (log (N)) und Sie fügen Sie das Element in seiner Position basierend auf seinen Wert . Die zusätzliche Funktion eines BST ist, dass es sortiert kommt!

Hash Tables sind zur Indizierung nicht gut. Wenn Sie für einen Bereich suchen, sind BSTs besser. Das ist der Grund, warum die meisten Datenbankindizes B + Bäume anstelle von Hash Tables

Binäre Suchbäume sind gute Wahl Wörterbuch zu implementieren, wenn die Tasten etwas Gesamtauftrag haben (Tasten vergleichbar sind) definiert auf sie und Sie die Reihenfolge Informationen zu erhalten.

Als BST die Auftragsinformationen erhält, bietet es Ihnen mit vier zusätzlichen dynamischen Set-Operationen, die nicht (effizient) durchgeführt werden kann Hash-Tabellen. Diese Operationen sind:

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

All diese Vorgänge wie jeder BST Betrieb haben Zeitkomplexität von O (H). Zusätzlich werden alle gespeicherten Schlüssel bleiben in der BST sortiert so dass Sie die sortierte Folge von Tasten bekommen nur durch den Baum in der Reihenfolge nach durchquert.

Zusammenfassend, wenn alles, was Sie wollen, ist Operationen einfügen, löschen und entfernen Sie dann Hash-Tabelle ist unschlagbar (die meiste Zeit) in der Leistung. Aber wenn Sie einige oder alle der oben aufgeführten Verfahren Sie sollten ein BST, vorzugsweise ein selbstausgleich BST.

Binäre Suchbäume können schneller sein, wenn sie mit String-Schlüsseln verwendet. Vor allem, wenn Strings sind lang.

Binäre Suchbäume anhand von Vergleichen für weniger / mehr, die für Saiten schnell sind (wenn sie nicht gleich sind). So ein BST kann schnell antworten, wenn eine Zeichenfolge nicht gefunden wird. Wenn es gefunden wird es braucht nur eine vollständigen Vergleich zu tun.

In einer Hash-Tabelle. Sie müssen den Hash der Zeichenfolge und das bedeutet, Sie durch alle Bytes zumindest gehen müssen berechnen, wenn der Hash zu berechnen. Dann wieder, wenn ein passender Eintrag gefunden wird.

Hauptvorteil der Hash-Tabelle ist, dass es fast alle ops in ~ = O (1). Und es ist sehr leicht zu verstehen und umzusetzen. Es tut löst effektiv viele „Interview Probleme“. Also, wenn u eine Codierung Interview knacken wollen, machen die besten Freunde mit Hash-Tabelle; -)

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top