vergleichen Hash mit binären Suchbaum

Question

Wir alle wissen, dass eine Hash-Tabelle O (1) Zeit für Inserts und Nachschlagen hat, wenn die Hash-Funktion gut gewählt wurde. Also, warum wollen wir den Binary Search Tree verwenden? Nur weil eine perfekte Hash-Funktion schwer zu gestalten war?

Hier, wie ich auf diese Frage komme? Ich merke, dass Standard C++ STL hat set und map, die mit Binär-Suchbaum implementiert sind, aber hat keinen Hash (nicht über nicht-Standard hash_set, hash_map). Ruby hat nur Hash. Ich möchte die Vernunft hinter diesem Unterschied verstehen.

Answer 1

Bäume ermöglichen Travertierung in der Reihenfolge.

Die Worst-Case-Leistung für eine Hash-Tabelle ist O (N) (lineare Suche durch einen Bucket), eine binäre Suche wird durch O (log N) gebunden.

Hinweis: Dies erfordert, dass der Baum ausgeglichen ist - deshalb verwenden typische Implementierungen einen selbstbalancierenden Baum, ähnlich einem rot-schwarzen Baum.

Während ein solcher Abbau unwahrscheinlich ist, ist es nicht unmöglich, und hängt stark von der Fähigkeit eine geeignete Hash-Funktion und die Verteilung der eigentlichen Daten zu wählen.

Eine Baumimplementierung wächst auch trivial auf die erforderliche Größe, während eine Hashmap anfängt, sich zu verschlechtern, wenn sie voll ist (für die meisten Implementierungen heißt es, dass 70% der Buckets gefüllt sind). Sie müssen entweder die gesamte Tabelle (noch einmal für Echtzeit-Apps) neu aufrüsten oder schrittweise in eine neue Tabelle verschieben, was keine einfache Implementierung ist.

Am Ende ging STL wahrscheinlich nur mit einer "Basis" -Containervorlage, dem Baum, um die zusätzliche Implementierungskomplexität zu vermeiden.

Answer 2

Nun Suchbäume sind bestellt, Hashes sind nicht.

Answer 3

Sie können auf die Daten in einem binären Suchbaum in der Reihenfolge zugreifen.

Answer 4

Um peterchen Antwort hinzuzufügen, Hash-Strukturen, obwohl theoretisch schneller bei der Einfügung und Entfernung hängt stark von den tatsächlichen Daten, die gewählte Hash-Funktion und die Menge der Daten.

• Eine perfekte Hash-Funktion hängt von der Menge und Verteilung der Daten ab.

große Leistungsschwankungen zwischen besten und schlechtesten Fälle zu haben, macht sie ungeeignet für Mehrzweckstrukturen. Binäre Bäume hingegen sind vorhersehbarer, unabhängig von der Menge/Art der verwendeten Daten, obwohl sie im besten Fall weniger effizient sind.

Answer 5

Die STL enthielt anfangs keine Hash-Tabelle unter den Containern, da Hash-Tabellen komplexer sind - Sie müssen zwischen offener und geschlossener Adressierung wählen, ganz zu schweigen von der Hash-Funktion usw. Zu dieser Zeit Stepanov und Stroustrup versuchten, den Fortschritt zu beschleunigen, so dass es schnell in den Standard aufgenommen wurde.

Bäume auf der anderen Seite, sind relativ einfacher. Es war bereits bekannt, dass, da es sich um In-Memory-Datenstrukturen handelt, wir einfach einen binären Baum anstelle eines B-Baums verwenden können.Dann war es eine Wahl zwischen AVL und RB Bäumen. RB-Bäume werden tendenziell aufgrund besserer Leistungsmerkmale ausgewählt, zu denen ich nicht in der Lage bin zu kommentieren, aber die Wikipedia-Artikel über beide Strukturen (AVL und RB) werden Ihnen mehr in relativ gutem Detail erzählen.

Ansonsten sind Bäume und Hash-Tabellen für verschiedene Dinge gut. Wenn Sie schnelle Einfügungen oder Abfragen benötigen und sich nicht um die Reihenfolge kümmern, in der sie gespeichert sind, sind Hashtabellen gut. Wenn Sie Merkmale für die Bestellung und starke Garantien für Einsätze und Abfragen benötigen, dann sind binäre Bäume gut. Eine weitere gute Faustregel ist das Profil. Da die meisten Anwendungen von beiden Schnittstellen-kompatibel sind, hilft auch das Profiling, das Ihnen eine bessere Leistung bietet.

Answer 6

Um einen Baum zu verwenden, benötigen Sie eine Möglichkeit, Elemente im Baum zu bestellen. Um eine Hash-Tabelle zu verwenden, benötigen Sie eine Funktion, um den Hash-Wert eines Elements in der Hash-Tabelle zu berechnen.

Interessanterweise erfordert das .NET-Framework, dass jede Klasse die GetHashCode-Funktion implementiert (oder erbt), die es ermöglicht, jedes Objekt in einer Hash-Tabelle zu speichern. Dies fügt jedoch auch eine zusätzliche Belastung für Entwickler ein, die semantisch korrekte Hash-Funktionen implementieren müssen, selbst wenn sie nicht beabsichtigen, die Klasse zu hashen. Eine Lösung besteht darin, einen konstanten Wert von GetHashCode zurückzugeben, der semantisch korrekt ist, aber nicht sehr effizient, sollte die Funktion jemals für das Hashing verwendet werden.

Answer 7

Zu der Zeit von C++ waren die Leute immer noch Fans des hardcore akademischen Ansatzes für Datenstrukturen und Algorithmen, deshalb bevorzugten sie Strukturen mit kleinerem Speicherbedarf und gut verstandenem Verhalten im besten und schlechtesten Fall.

Zu der Zeit Ruby erschien, und für die Zwecke des Scripting, Leute realisiert, dass sie Einfachheit gegenüber roher Leistung bevorzugen, und seit Hashtables Semantik beider Arrays (wenn Sie sequentiellen Index als Schlüssel verwenden) UND Wörterbücher (wenn Sie verwenden Sie den natürlichen Schlüssel), sie wurden als universellere Datenstruktur angesehen.

Answer 8

Wenn Sie damit durchkommen können, sollten Sie immer einen Hash über einen binären Suchbaum bevorzugen. Hashes hat einen höheren Speicheraufwand als Bäume, aber der gesamte von ihnen verwendete Speicher kann in einem großen Block zugewiesen werden. Für Bäume erfordert jeder hinzugefügte Knoten eine separate Zuweisung, die eine hohe Fragmentierung verursacht und für die Leistung schlecht ist. Ähnlich wie Sie lieber 1000 Bytes aus 1 Datei als 1 Byte aus 1000 verschiedenen Dateien lesen würden.

Der Fall, in dem Hashes nicht funktioniert, ist bei der Bestellung von Angelegenheiten. Angenommen, Sie schreiben einen Speicherzuordner und Sie speichern freie Speicherblöcke in einer Datenstruktur. Schlüssel sind die Größen der Blöcke und die Werte sind die Zeiger auf sie.

Eine Anforderung für Speicher umfasst, durch diese Datenstruktur zu suchen und den kleinsten Block zu finden, der die Anforderung erfüllt. Wenn Sie beispielsweise Blöcke mit den Schlüsseln 10, 20, 30 haben und eine Anforderung für 20 Byte Speicher eingeht, wählen Sie den zweiten Block aus. Ein hashmap kann das leicht tun.

Aber was ist, wenn die Anfrage für 22 Bytes ist? Da es keinen Schlüssel mit dem Wert 20 gibt, müssen Sie die ganze Hashmap iterieren, um den richtigen Schlüssel (30) zu finden, der eine O (n) -Operation ist. Wenn Sie jedoch einen Baum verwendet haben, dann ist "O der kleinste Schlüssel, der größer als ein bestimmter Schlüssel ist" eine Operation O (log n).