Binäre Bäume vs. verknüpfte Listen vs. Hash-Tabellen

72

Ich baue eine Symboltabelle für ein Projekt, an dem ich arbeite. Ich habe mich gefragt, wie die Meinungen der Menschen zu den Vor- und Nachteilen der verschiedenen Methoden zum Speichern und Erstellen einer Symboltabelle stehen.

Ich habe ein bisschen gesucht und am häufigsten werden Binärbäume oder verknüpfte Listen oder Hash-Tabellen empfohlen. Was sind die Vor- und / oder Nachteile aller oben genannten? (arbeitet in c ++)

benmcredmond
quelle

Antworten:

48

Ihr Anwendungsfall wird vermutlich darin bestehen, "die Daten einmal einzufügen (z. B. den Start der Anwendung) und dann viele Lesevorgänge durchzuführen, aber nur wenige, wenn überhaupt zusätzliche Einfügungen".

Daher müssen Sie einen Algorithmus verwenden, mit dem Sie schnell die benötigten Informationen abrufen können.

Ich würde daher denken, dass die HashTable der am besten geeignete Algorithmus ist, da sie einfach einen Hash Ihres Schlüsselobjekts generiert und diesen für den Zugriff auf die Zieldaten verwendet - es ist O (1). Die anderen sind O (N) (verknüpfte Listen der Größe N - Sie müssen die Liste einzeln durchlaufen, durchschnittlich N / 2 Mal) und O (log N) (Binärbaum - Sie halbieren den Suchraum mit Jede Iteration - nur wenn der Baum ausgeglichen ist. Dies hängt also von Ihrer Implementierung ab. Ein nicht ausgeglichener Baum kann eine erheblich schlechtere Leistung aufweisen.

Stellen Sie einfach sicher, dass in der HashTable genügend Leerzeichen (Buckets) für Ihre Daten vorhanden sind (Re, Soraz 'Kommentar zu diesem Beitrag). Die meisten Framework-Implementierungen (Java, .NET usw.) haben eine Qualität, bei der Sie sich keine Gedanken über die Implementierungen machen müssen.

Haben Sie an der Universität einen Kurs über Datenstrukturen und Algorithmen absolviert?

JeeBee
quelle
43
habe die High School nicht verlassen ... also nein. Alle Autodidakten :)
Benmcredmond
6
O (1) für Hashtable-Lookups gilt nur, wenn die Anzahl der Buckets einen guten Bruchteil des Gesamtsatzes ausmacht. Das heißt, wenn Sie 1 Million Einträge in 512 Buckets speichern, werden Sie immer noch 2048 direkte Vergleiche pro Suche durchführen, was mehr als log (n) von 1 Million (oder 13 direkte Vergleiche
pro
3
Eine Qualitätsimplementierung einer Hash-Tabelle mit einem Qualitäts-Hashing-Algorithmus ergibt O (1). Eine schlechte Implementierung des Binärbaums könnte auch schlechter sein als O (log N). Für die gestellte Fragestufe ist es wahrscheinlich mehr als gut genug, zu sagen, dass eine Hash-Tabelle O (1) ist.
Darron
Symboltabellen haben andere Eigenschaften, die Hash-Tabellen oft nicht am besten geeignet machen. -1
Stephan Eggermont
3
@Stephan: Ausarbeiten. Ich behaupte, dass Hash-Tabellen bei weitem die häufigste Datenstruktur für Symboltabellen sind.
Konrad Rudolph
76

Es gelten die Standardkompromisse zwischen diesen Datenstrukturen.

  • Binäre Bäume
    • mittlere Komplexität zu implementieren (vorausgesetzt, Sie können sie nicht aus einer Bibliothek erhalten)
    • Einfügungen sind O (logN)
    • Lookups sind O (logN)
  • Verknüpfte Listen (unsortiert)
    • geringe Komplexität zu implementieren
    • Einsätze sind O (1)
    • Lookups sind O (N)
  • Hash-Tabellen
    • hohe Komplexität zu implementieren
    • Einsätze sind im Durchschnitt O (1)
    • Lookups sind im Durchschnitt O (1)
Darron
quelle
3
Bei einer unsortierten verknüpften Liste sind Einfügungen O (1) und nicht O (N). Dies ist zusammen mit der Entfernung von O (1) bei doppelter Verknüpfung normalerweise die Motivation, sie zu verwenden, nicht ihre Implementierungskomplexität. Eine weitere Motivation ist, dass sie ohne Kopieren unbegrenzt wachsen können. Nicht, dass ich in diesem Fall einen vorschlagen würde.
P Daddy
4
Ich würde auch argumentieren, dass eine Hash-Tabelle ungefähr so ​​einfach zu implementieren ist wie ein korrekt ausgeglichener Binärbaum. Das ist aber sehr subjektiv.
Joel Borggrén-Franck
4
Ja, die Komplexität der Implementierung ist subjektiv. Aber ich denke, dass eine minimale verknüpfte Liste einfacher ist als eine minimale Hash-Tabelle. Wenn Sie dann Auto-Balancing im Vergleich zu Kollisionen hinzufügen und die Größe ändern, wenn sie voll ist, wird die Reihenfolge nicht ausgetauscht.
Darron
1
Ein Merkmal von Binärbäumen ist, dass sie eine (Schlüssel-) sortierte Iteration ermöglichen.
Jonatan Hedborg
Was ist mit Löschvorgängen?
anon58192932
43

Was jeder zu vergessen scheint, ist, dass für kleine Ns, dh wenige Symbole in Ihrer Tabelle, die verknüpfte Liste viel schneller sein kann als die Hash-Tabelle, obwohl theoretisch ihre asymptotische Komplexität tatsächlich höher ist.

Es gibt eine berühmte Qoute aus Pikes Anmerkungen zur Programmierung in C: "Regel 3. Ausgefallene Algorithmen sind langsam, wenn n klein ist, und n ist normalerweise klein. Ausgefallene Algorithmen haben große Konstanten. Bis Sie wissen, dass n häufig groß sein wird, keine Lust bekommen. " http://www.lysator.liu.se/c/pikestyle.html

Ich kann Ihrem Beitrag nicht entnehmen, ob Sie es mit einem kleinen N zu tun haben oder nicht, aber denken Sie immer daran, dass der beste Algorithmus für große N nicht unbedingt für kleine N gut ist.

Joel Borggrén-Franck
quelle
2
Das ist implementierungsabhängig. Wenn Sie den Algorithmus zur Berechnung der Hash-Werte kennen, können Sie festlegen, wie teuer er im Vergleich zu n / 2 Identitätsvergleichen (der Durchschnitt für eine verknüpfte Liste) oder log (n) Identitätsvergleichen (der Durchschnitt für einen Binärbaum) wäre. .
Hank Gay
1
Sie erwähnen nicht, in welcher Sprache Sie arbeiten, aber wenn es eine gute integrierte Unterstützung für Wörterbücher / Hashtabellen / wie auch immer-das-lang-es nennt, z. B. Python, ist es wahrscheinlich am einfachsten, einfach zu lernen, keine Sorgen mehr zu machen und liebe das eingebaute.
Hank Gay
Wie Hank schrieb, ist die Grenze für groß unmöglich zu erraten, ohne zu wissen: Ihr Eingabedatensatz, Ihr Hash-Algorithmus, Ihre Programmiersprache (ob Zeichenfolgen interniert sind oder nicht) usw. Oft können Sie es falsch machen, wenn Sie alle oben genannten Punkte kennen. Entscheiden Sie sich für das, was am einfachsten zu codieren ist, und beheben Sie es später, wenn es zu langsam ist.
Joel Borggrén-Franck
Auch der Durchschn. für einen binären Baum sollte (log n) / 2
Hank Gay
2
Auch die "Zeit zum Debuggen seltsamer Fehler" ist mit ausgefallenen Algorithmen viel höher. Halten Sie es einfach, bis sich einfach als unhaltbar herausstellt.
Jeff Allen
8

Es klingt so, als ob alles wahr sein könnte:

  • Ihre Schlüssel sind Zeichenfolgen.
  • Einfügungen werden einmal durchgeführt.
  • Suchvorgänge werden häufig durchgeführt.
  • Die Anzahl der Schlüssel-Wert-Paare ist relativ gering (z. B. weniger als ein K oder so).

In diesem Fall können Sie eine sortierte Liste über eine dieser anderen Strukturen ziehen. Dies würde beim Einfügen schlechter abschneiden als die anderen, da eine sortierte Liste beim Einfügen O (N) gegenüber O (1) für eine verknüpfte Liste oder Hash-Tabelle und O (Protokoll 2) istN) für einen ausgeglichenen Binärbaum. Die Suche in einer sortierten Liste ist jedoch möglicherweise schneller als jede dieser anderen Strukturen (ich werde dies kurz erläutern), sodass Sie möglicherweise die Nase vorn haben. Wenn Sie alle Einfügungen auf einmal ausführen (oder anderweitig keine Suche benötigen, bis alle Einfügungen abgeschlossen sind), können Sie die Einfügungen in O (1) vereinfachen und am Ende eine viel schnellere Sortierung durchführen. Darüber hinaus benötigt eine sortierte Liste weniger Speicher als jede dieser anderen Strukturen. Dies ist jedoch wahrscheinlich nur dann von Bedeutung, wenn Sie viele kleine Listen haben. Wenn Sie eine oder mehrere große Listen haben, übertrifft eine Hash-Tabelle wahrscheinlich eine sortierte Liste.

Warum können Suchvorgänge mit einer sortierten Liste schneller sein? Nun, es ist klar, dass es schneller ist als eine verknüpfte Liste, mit der O (N) -Suchzeit der letzteren. Bei einem Binärbaum bleiben Suchvorgänge nur dann O (log 2 N), wenn der Baum perfekt ausgeglichen bleibt. Wenn Sie den Baum im Gleichgewicht halten (z. B. rot-schwarz), erhöhen Sie die Komplexität und die Einfügezeit. Darüber hinaus ist jedes Element sowohl mit verknüpften Listen als auch mit Binärbäumen ein separat zugewiesener 1- Knoten. Dies bedeutet, dass Sie Zeiger dereferenzieren und wahrscheinlich zu potenziell stark variierenden Speicheradressen springen müssen, was die Wahrscheinlichkeit eines Cache-Fehlers erhöht.

Wie für Hash - Tabellen, sollten Sie vielleicht lesen ein paar von anderen Fragen hier auf Stackoverflow, aber die wichtigsten Sehenswürdigkeiten befinden sich hier:

  • Eine Hash-Tabelle kann im schlimmsten Fall zu O (N) degenerieren.
  • Die Kosten für das Hashing sind ungleich Null und können in einigen Implementierungen erheblich sein, insbesondere bei Zeichenfolgen.
  • Wie in verknüpften Listen und Binärbäumen ist jeder Eintrag ein Knoten, der mehr als nur Schlüssel und Wert speichert und in einigen Implementierungen auch separat zugewiesen wird, sodass Sie mehr Speicher verwenden und die Wahrscheinlichkeit eines Cache-Fehlers erhöhen.

Wenn Sie sich wirklich für die Leistung einer dieser Datenstrukturen interessieren, sollten Sie sie natürlich testen. Sie sollten kein Problem damit haben, gute Implementierungen für die meisten gängigen Sprachen zu finden. Es sollte nicht zu schwierig sein, einige Ihrer realen Daten auf jede dieser Datenstrukturen zu werfen und zu sehen, welche am besten funktioniert.

  1. Es ist möglich, dass eine Implementierung ein Array von Knoten vorab zuweist, was bei dem Cache-Miss-Problem helfen würde. Ich habe dies in keiner wirklichen Implementierung von verknüpften Listen oder Binärbäumen gesehen (natürlich nicht, dass ich jeden gesehen habe), obwohl Sie sicherlich Ihre eigenen rollen könnten. Sie hätten jedoch immer noch eine etwas höhere Wahrscheinlichkeit eines Cache-Fehlers, da die Knotenobjekte notwendigerweise größer als die Schlüssel / Wert-Paare wären.
P Papa
quelle
Für Hash-Tabellen (in diesem Fall) kann O (1) erreicht werden, da Sie im Voraus alle Daten kennen, die dort gehasht werden sollen. Ich denke also, dass der einzige Vorteil von sortierten Arrays die räumliche Komplexität ist.
Iulius Curt
7

Ich mag Bills Antwort, aber sie synthetisiert die Dinge nicht wirklich.

Aus den drei Möglichkeiten:

Verknüpfte Listen suchen relativ langsam nach Elementen aus (O (n)). Wenn Sie also viele Elemente in Ihrer Tabelle haben oder viele Suchvorgänge durchführen, sind diese nicht die beste Wahl. Sie sind jedoch einfach zu erstellen und auch leicht zu schreiben. Wenn die Tabelle klein ist und / oder Sie nach dem Erstellen immer nur einen kleinen Scan durchführen, ist dies möglicherweise die richtige Wahl für Sie.

Hash-Tabellen können unglaublich schnell sein. Damit dies funktioniert, müssen Sie jedoch einen guten Hash für Ihre Eingabe auswählen und einen Tisch auswählen, der groß genug ist, um alles ohne viele Hash-Kollisionen aufzunehmen. Das bedeutet, dass Sie etwas über die Größe und Menge Ihrer Eingabe wissen müssen. Wenn Sie dies vermasseln, erhalten Sie einen wirklich teuren und komplexen Satz verknüpfter Listen. Ich würde sagen, wenn Sie nicht im Voraus wissen, wie groß die Tabelle sein wird, verwenden Sie keine Hash-Tabelle. Dies stimmt nicht mit Ihrer "akzeptierten" Antwort überein. Es tut uns leid.

Das hinterlässt Bäume. Sie haben hier jedoch eine Option: Ausgleichen oder nicht ausgleichen. Was ich bei der Untersuchung dieses Problems mit C- und Fortran-Code festgestellt habe, ist, dass die Symboltabelleneingabe in der Regel so zufällig ist, dass Sie nur ein oder zwei Baumebenen verlieren, wenn Sie den Baum nicht ausgleichen. Angesichts der Tatsache, dass ausgeglichene Bäume langsamer Elemente einfügen und schwieriger zu implementieren sind, würde ich mich nicht darum kümmern. Wenn Sie jedoch bereits Zugriff auf nette debuggte Komponentenbibliotheken haben (z. B. STL von C ++), können Sie auch den ausgeglichenen Baum verwenden.

TED
quelle
Obwohl ich Ihrem Standpunkt zu HashTables zustimme, war meine Antwort für einen ganz bestimmten Anwendungsfall - einmal lesen, wenige Ergänzungen (falls vorhanden) und viele Lesevorgänge - und daher davon ausgehen, dass die HashTable die richtige Größe hatte (automatisch wachsen oder auf 1,2 eingestellt) x Größe der Eingabe) ist die beste Option.
JeeBee
Situationen, in denen Sie die Größe Ihrer Eingabe im Voraus kennen, sind ein eher ungewöhnlicher und besonderer Fall. Verwenden Sie in diesem speziellen Fall sicher eine Hash-Tabelle. Aber Ben gab keinerlei Hinweis darauf, dass sein Fall diese seltene Bedingung erfüllte.
TED
6

Ein paar Dinge, auf die Sie achten sollten.

  • Binäre Bäume haben nur dann eine O (log n) -Suche und fügen Komplexität ein, wenn der Baum ausgeglichen ist . Wenn Ihre Symbole ziemlich zufällig eingefügt werden, sollte dies kein Problem sein. Wenn sie der Reihe nach eingefügt werden, erstellen Sie eine verknüpfte Liste. (Für Ihre spezifische Anwendung sollten sie nicht in irgendeiner Reihenfolge angeordnet sein, daher sollten Sie in Ordnung sein.) Wenn die Wahrscheinlichkeit besteht, dass die Symbole zu ordentlich sind, ist ein rot-schwarzer Baum die bessere Option.

  • Hash-Tabellen geben O (1) durchschnittliche Komplexität beim Einfügen und Nachschlagen an, aber auch hier gibt es eine Einschränkung. Wenn Ihre Hash-Funktion schlecht ist (und ich meine wirklich schlecht), können Sie auch hier eine verknüpfte Liste erstellen. Jede vernünftige String-Hash-Funktion sollte jedoch funktionieren. Diese Warnung dient also nur dazu, sicherzustellen, dass Sie sich dessen bewusst sind, dass dies passieren kann. Sie sollten in der Lage sein, nur zu testen, ob Ihre Hash-Funktion nicht viele Kollisionen über Ihren erwarteten Eingabebereich aufweist, und es wird Ihnen gut gehen. Ein weiterer kleiner Nachteil ist, wenn Sie eine Hash-Tabelle mit fester Größe verwenden. Die meisten Hash-Tabellen-Implementierungen wachsen, wenn sie eine bestimmte Größe erreichen (genauer gesagt: Lastfaktor, siehe hier)für Details). Dies soll das Problem vermeiden, das beim Einfügen einer Million Symbole in zehn Eimer auftritt. Das führt nur zu zehn verknüpften Listen mit einer durchschnittlichen Größe von 100.000.

  • Ich würde eine verknüpfte Liste nur verwenden, wenn ich eine wirklich kurze Symboltabelle hätte. Es ist am einfachsten zu implementieren, aber die beste Leistung für eine verknüpfte Liste ist die schlechteste Leistung für Ihre beiden anderen Optionen.

Bill die Eidechse
quelle
Zu 1: Das ist ein guter Punkt. Wenn ich in der Vergangenheit Symboltabellen implementiert habe, habe ich im Allgemeinen festgestellt, dass meine Einträge in ziemlich zufälliger (alphabetischer) Reihenfolge angezeigt werden. Aus diesem Grund gab es wirklich nicht genug Auszahlung, um es wert zu sein, den Baum zu balancieren.
TED
1

Andere Kommentare haben sich auf das Hinzufügen / Abrufen von Elementen konzentriert, aber diese Diskussion ist nicht vollständig, ohne zu überlegen, was erforderlich ist, um die gesamte Sammlung zu durchlaufen. Die kurze Antwort lautet hier, dass Hash-Tabellen weniger Speicher benötigen, um sie zu durchlaufen, Bäume jedoch weniger Zeit benötigen.

Bei einer Hash-Tabelle hängt der Speicheraufwand für das Durchlaufen der (Schlüssel-, Wert-) Paare nicht von der Kapazität der Tabelle oder der Anzahl der in der Tabelle gespeicherten Elemente ab. Tatsächlich sollte das Iterieren nur eine oder zwei Indexvariablen erfordern.

Bei Bäumen hängt der erforderliche Speicherplatz immer von der Größe des Baums ab. Sie können entweder eine Warteschlange mit nicht besuchten Knoten während der Iteration verwalten oder dem Zeiger zusätzliche Zeiger hinzufügen, um die Iteration zu vereinfachen (der Baum verhält sich zum Zwecke der Iteration wie eine verknüpfte Liste). In beiden Fällen müssen Sie jedoch zusätzlichen Speicher für die Iteration zuweisen .

Beim Timing ist die Situation jedoch umgekehrt. Bei einer Hash-Tabelle hängt die Zeit für die Iteration von der Kapazität der Tabelle ab, nicht von der Anzahl der gespeicherten Elemente. Das Durchlaufen einer Tabelle, die mit 10% der Kapazität geladen ist, dauert also etwa zehnmal länger als eine verknüpfte Liste mit denselben Elementen!


quelle
0

Dies hängt natürlich von mehreren Dingen ab. Ich würde sagen, dass eine verknüpfte Liste richtig ist, da sie nur wenige geeignete Eigenschaften hat, um als Symboltabelle zu arbeiten. Ein Binärbaum funktioniert möglicherweise, wenn Sie bereits einen haben und keine Zeit damit verbringen müssen, ihn zu schreiben und zu debuggen. Meine Wahl wäre eine Hash-Tabelle, ich denke, das ist mehr oder weniger die Standardeinstellung für diesen Zweck.

entspannen
quelle
0

Diese Frage geht durch die verschiedenen Container in C #, sie sind jedoch in jeder von Ihnen verwendeten Sprache ähnlich.

Mats Fredriksson
quelle
0

Sofern Sie nicht erwarten, dass Ihre Symboltabelle klein ist, sollte ich mich von verknüpften Listen fernhalten. Eine Liste mit 1000 Elementen benötigt durchschnittlich 500 Iterationen, um ein Element darin zu finden.

Ein Binärbaum kann viel schneller sein, solange er ausgeglichen ist. Wenn Sie den Inhalt beibehalten, wird das serialisierte Formular wahrscheinlich sortiert, und wenn es erneut geladen wird, ist der resultierende Baum infolgedessen völlig unausgeglichen und verhält sich genauso wie die verknüpfte Liste - denn das ist im Grunde, was es geworden ist. Balanced Tree-Algorithmen lösen diese Angelegenheit, machen aber den gesamten Shebang komplexer.

Eine Hashmap (solange Sie einen geeigneten Hashing-Algorithmus auswählen) scheint die beste Lösung zu sein. Sie haben Ihre Umgebung nicht erwähnt, aber in fast allen modernen Sprachen ist eine Hashmap integriert.

Martin Cowie
quelle