wake-up-neo.com

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

Was sind die Vorteile von binären Suchbäumen gegenüber Hashtabellen?

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

90
Devoted

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

Wenn zum Beispiel eine Hash-Funktion einen Bereich R(h) = 0...100 hat, müssen Sie ein Array von 100 (Zeiger auf) Elementen zuordnen, auch wenn Sie nur 20 Elemente hashen. Wenn Sie einen binären Suchbaum verwenden, um die gleichen Informationen zu speichern, müssen Sie nur so viel Speicherplatz zuweisen, wie Sie benötigen, als auch einige Metadaten zu Links.

83
Christian Mann

Niemand hat auf den Vorteil hingewiesen, dass der binäre Suchbaum eine effiziente Suche nach Reichweiten ermöglicht.

Um meine Idee zu veranschaulichen, möchte ich einen Extremfall anführen. Angenommen, Sie möchten alle Elemente erhalten, deren Schlüssel zwischen 0 und 5000 liegen. Und tatsächlich gibt es nur ein solches Element und 10000 andere Elemente, deren Schlüssel nicht im Bereich liegen. BST kann die Bereichsuche recht effizient durchführen, da keine Teilstruktur durchsucht wird, deren Antwort unmöglich ist.

Wie können Sie in einer Hashtabelle nach Reichweiten suchen? Sie müssen entweder jeden Bucket-Space durchlaufen, der O (n) ist, oder Sie müssen prüfen, ob jeweils 1,2,3,4 ... bis zu 5000 vorhanden sind. (Was ist mit den Tasten zwischen 0 und 5000 eine unendliche Menge? Zum Beispiel können Tasten Dezimalzahlen sein.)

106
Alex

Ein "Vorteil" eines binären Baums besteht darin, dass er durchlaufen werden kann, um alle Elemente nacheinander aufzulisten. Dies ist bei einer Hash-Tabelle nicht unmöglich, aber es ist keine normale Operation eines Entwurfs in einer Hash-Struktur.

74
NealB

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 Lesevorgang ausgeführt, bevor Sie auf eine Referenz mit Ihren Daten zugreifen können. Der Binärbaum benötigt, wenn es sich um eine ausgeglichene Variante handelt, etwas in der Größenordnung von k * lg (n) Speicherlesevorgänge für eine Konstante k.

Wenn ein Feind jedoch Ihre Hash-Funktion kennt, kann der Feind Ihre Hash-Tabelle zu Kollisionen zwingen, was die Leistung erheblich beeinträchtigt. Die Problemumgehung besteht darin, die Hash-Funktion zufällig aus einer Familie auszuwählen, aber eine 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 zuzuordnen, was eine teure Operation sein kann. Der BST hat hier ein einfacheres Verhalten und neigt nicht dazu, plötzlich viele Daten zuzuweisen und einen Wiederaufbereitungsvorgang durchzuführen.

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

Schließlich sind BSTs in (reinen) funktionalen Sprachen viel einfacher zu implementieren als Hash-Tabellen, und es müssen keine destruktiven Aktualisierungen implementiert werden (das Persistenz Argument von Pascal oben).

51

Der Hauptvorteil eines Binärbaums gegenüber einer Hashtabelle besteht darin, dass der Binärbaum zwei zusätzliche Vorgänge bietet, die Sie mit einer Hashtabelle (schnell und einfach) nicht ausführen können

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

  • durchlaufen Sie den Inhalt des Baums in sortierter Reihenfolge

Die beiden sind miteinander verbunden. Der binäre Baum enthält eine sortierte Reihenfolge für den Inhalt. Daher ist es einfach, Dinge zu erledigen, für die eine sortierte Reihenfolge erforderlich ist.

25
Chris Dodd

Ein (ausgeglichener) binärer Suchbaum hat auch den Vorteil, dass seine asymptotische Komplexität tatsächlich eine obere Schranke ist, während die "konstanten" Zeiten für Hashtabellen amortisiert sind: Wenn Sie eine ungeeignete Hash-Funktion haben, könnte dies zu einer linearen Zeit führen eher als konstant.

15
jamesnvc

Eine Hash-Tabelle würde mehr Platz in Anspruch nehmen, wenn sie zum ersten Mal erstellt wird. 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 werden). Ein binärer Suchbaum ist nur so groß wie erforderlich Sein. Wenn eine Hash-Tabelle mehr Platz benötigt, kann das Erweitern auf eine andere Struktur könnte zeitaufwändig sein, was jedoch von der Implementierung abhängt.

Ein binärer Suchbaum kann mit einer persistent - Schnittstelle implementiert werden, wobei ein neuer Baum zurückgegeben wird, der alte Baum jedoch weiterhin vorhanden ist. Sorgfältig implementiert, teilen die alten und neuen Bäume die meisten ihrer Knoten. Mit einer Standard-Hashtabelle ist dies nicht möglich.

8
Pascal Cuoq

Ein binärer Baum ist langsamer zum Suchen und Einfügen in, hat jedoch die sehr schöne Funktion des Infix-Durchlaufs, 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 keinen Sinn, da sie alle im Speicher verstreut sind.

6

From Cracking the Coding Interview, 6. Auflage

Wir können die Hash-Tabelle mit einem symmetrischen binären Suchbaum (BST) implementieren. Dies gibt uns eine O (log n) -Suchzeit. Dies hat den Vorteil, dass weniger Platz benötigt wird, da kein großes Array mehr zugewiesen wird. Wir können die Tasten auch nacheinander durchlaufen, was manchmal nützlich sein kann. 

4
Guy Kahlon

BSTs bieten auch die Operationen "findPredecessor" und "findSuccessor" (zum Finden der nächstkleinsten und nächstgrößeren Elemente) in O(logn) - Zeit, was auch sehr praktische Operationen sein kann. Hash Table kann in dieser Zeit keine Effizienz bieten.

4
Balaji

Wenn Sie auf die Daten sortiert zugreifen möchten, muss eine sortierte Liste parallel zur Hashtabelle gepflegt werden. Ein gutes Beispiel ist Dictionary in .Net. (Siehe http://msdn.Microsoft.com/de-de/library/3fcwy8h6.aspx ).

Dies hat den Nebeneffekt, dass die Einfügungen nicht nur verlangsamt werden, sondern auch mehr Speicher benötigt wird als bei einem B-Baum.

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

1
IamIC

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

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

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

Der Schlüssel ist die Hash-Funktion, mit der eine Kollision vermieden wird. Natürlich können wir eine Kollision nicht gänzlich vermeiden. In diesem Fall greifen wir auf Ketten oder andere Methoden zurück. Dies führt dazu, dass der Abruf im schlimmsten Fall nicht mehr konstant ist. 

Wenn die Hashtabelle voll ist, muss sie die Bucket-Größe vergrößern und alle Elemente erneut kopieren. Dies ist ein zusätzlicher Aufwand, der nicht über BST anfällt.

1
sreeprasad

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

Da BST die Bestellinformationen speichert, stehen Ihnen vier zusätzliche dynamische Satzoperationen zur Verfügung, die nicht (effizient) mithilfe von Hashtabellen 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 zeitliche Komplexität von O (H). Zusätzlich bleiben alle gespeicherten Schlüssel in der BST sortiert, sodass Sie die sortierte Reihenfolge der Schlüssel erhalten, indem Sie den Baum in der richtigen Reihenfolge durchlaufen. 

Zusammenfassend: Wenn Sie lediglich Operationen einfügen, löschen und entfernen möchten, ist die Hash-Tabelle (meistens) in ihrer Leistung unschlagbar. Wenn Sie jedoch eine oder alle der oben aufgeführten Operationen wünschen, sollten Sie eine BST verwenden, vorzugsweise eine selbstausgleichende BST.

0
mightyWOZ

Binäre Suchbäume können mit String-Schlüsseln schneller ausgeführt 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). Eine BST kann also schnell antworten, wenn keine Zeichenfolge gefunden wird. Wenn sie gefunden wird, muss sie nur einen vollständigen Vergleich durchführen.

In einer Hashtabelle. Sie müssen den Hashwert der Zeichenfolge berechnen. Dies bedeutet, dass Sie alle Bytes mindestens einmal durchlaufen müssen, um den Hashwert zu berechnen. Dann wieder, wenn ein passender Eintrag gefunden wird.

0
Calmarius

Die Klassen HashSet und Table sind ungeordnete Sammlungen. Es ist nicht offensichtlich von der Schnittstelle (und könnte anders sein), aber Hashtabellen wurden mit AVL Trees implementiert. Dies bedeutet, dass der Hash-Code nicht durch das Modulo eines Arrays reduziert wird (weniger Kollisionen) und dass das Array nicht erneut verwendet wird (glattere Leistung). Die Tatsache, dass es sich um ungeordnete Sammlungen handelt, bedeutet, dass Sie nur eine equals-Funktion und eine hashCode-Funktion bereitstellen - nicht einen vollständigen Vergleicher für Bäume. Ob Sie also eine Hashtabelle Table <K, T> oder einen Binärbaum Tree <K, T> verwenden, hängt von der Klasse K ab - ob sie vollständig oder nur mit Gleichheit vergleichbar ist.

Es gibt Fälle, in denen der Datentyp sowohl vergleichbar als auch gleichwertig ist - wie String. Dies bedeutet, dass sowohl HashSet <String> als auch Set <String> möglich sind. Suchen in einem Hash-Satz von Zeichenfolgen sind in der Regel etwa zehnmal schneller als Suchen in einem geordneten Satz von Zeichenfolgen. Wenn der Komparator teuer ist, werden Bäume im Vergleich zu HashTables langsamer. Wenn der Komparator schnell ist (wie bei Ganzzahlen und Floats), werden Bäume schneller als Hashtabellen ausgeführt.

0

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

0
ssD

Eine Hashmap ist ein satzassoziatives 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 einen neuen Wert in einen Bucket einfügen, stellen Sie fest, wo im Bucket freie Speicherplätze vorhanden sind. Hierfür gibt es verschiedene Möglichkeiten: Sie beginnen am Anfang des Buckets und erhöhen den Zeiger jedes Mal, um zu prüfen, ob er belegt ist. Dies wird als lineares Abtasten bezeichnet. Dann können Sie eine binäre Suche wie add ausführen, bei der Sie die Differenz zwischen dem Beginn des Buckets verdoppeln und bei der Sie jedes Mal, wenn Sie nach einem freien Speicherplatz suchen, eine Verdoppelung oder eine Zurücksetzung vornehmen. Dies wird als quadratisches Abtasten bezeichnet. OKAY. Nun besteht das Problem bei beiden Methoden darin, dass Sie Folgendes tun müssen, wenn der Bucket über die nächste Bucket-Adresse hinausläuft.

  1. Verdoppeln Sie die Größe jedes Buckets - Malloc (N Buckets)/ändern Sie die Hash-Funktion. Erforderliche Zeit: abhängig von der Implementierung von Malloc
  2. Übertragen/Kopieren Sie alle früheren Buckets-Daten in die neuen Buckets-Daten. Dies ist eine O(N) - Operation, bei der N die gesamten Daten darstellt

OKAY. 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 davon ausgehen, 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.

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

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

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

0