Warum verwendet Python eine Hash-Tabelle, um Diktate zu implementieren, nicht jedoch Red-Black Tree? [geschlossen]

Warum verwendet Python eine Hash-Tabelle, um Diktate zu implementieren, nicht jedoch Red-Black Tree?

Was ist der Schlüssel? Performance?

Dies ist eine allgemeine, nicht Python-spezifische Antwort.

Algorithmischer Komplexitätsvergleich

       | Hash Table  |   Red-Black Tree    |
-------+-------------+---------------------+
Space  | O(n) : O(n) | O(n)     : O(n)     |
Insert | O(1) : O(n) | O(log n) : O(log n) |
Fetch  | O(1) : O(n) | O(log n) : O(log n) |
Delete | O(1) : O(n) | O(log n) : O(log n) |
       | avg  :worst | average  : worst    |

Das Problem mit Hash-Tabellen ist, dass Hashes kollidieren können. Es gibt verschiedene Mechanismen zum Auflösen von Kollisionen, z. B. offene Adressierung oder separate Verkettung. Der absolut schlimmste Fall ist, dass alle Schlüssel den gleichen Hash-Code haben. In diesem Fall wird eine Hash-Tabelle in eine verknüpfte Liste umgewandelt.

In allen anderen Fällen ist eine Hash-Tabelle eine großartige Datenstruktur, die einfach zu implementieren ist und eine gute Leistung liefert. Ein Nachteil ist, dass Implementierungen, die die Tabelle schnell vergrößern und ihre Einträge neu verteilen können, wahrscheinlich fast so viel Speicher verschwenden, wie tatsächlich verwendet wird.

RB-Bäume sind selbstausgleichend und ändern im schlimmsten Fall ihre algorithmische Komplexität nicht. Sie sind jedoch schwieriger zu implementieren. Ihre durchschnittliche Komplexität ist auch schlechter als die einer Hash-Tabelle.

Einschränkungen für Schlüssel

Alle Schlüssel in einer Hash-Tabelle müssen hashbar und vergleichbar sein, um die Gleichheit untereinander zu gewährleisten. Dies ist besonders einfach für Zeichenfolgen oder Ganzzahlen, lässt sich aber auch recht einfach auf benutzerdefinierte Typen ausweiten. In einigen Sprachen wie Java sind diese Eigenschaften per Definition garantiert.

Schlüssel in einem RB-Baum müssen eine Gesamtreihenfolge haben: Jeder Schlüssel muss mit jedem anderen Schlüssel vergleichbar sein, und die beiden Schlüssel müssen entweder kleiner, größer oder gleich sein. Diese Ordnungsgleichheit muss der semantischen Gleichheit entsprechen. Dies ist für Ganzzahlen und andere Zahlen unkompliziert, für Zeichenfolgen auch recht einfach (die Reihenfolge muss nur konsistent und nicht extern beobachtbar sein, sodass die Reihenfolge keine Gebietsschemas berücksichtigen muss ^[1] ), für andere Typen, die keine inhärente Reihenfolge haben, jedoch schwierig . Es ist absolut unmöglich, Schlüssel unterschiedlicher Typen zu haben, es sei denn, ein Vergleich zwischen ihnen ist möglich.

^{[1]: Eigentlich irre ich mich hier. Zwei Zeichenfolgen sind möglicherweise nicht bytegleich, entsprechen jedoch nach den Regeln einer bestimmten Sprache. Siehe z. B. Unicode-Normalisierungen für ein Beispiel, bei dem zwei gleiche Zeichenfolgen unterschiedlich codiert sind. Ob die Zusammensetzung von Unicode-Zeichen für Ihren Hash-Schlüssel von Bedeutung ist, kann eine Implementierung einer Hash-Tabelle nicht wissen.}

Man könnte denken, dass eine billige Lösung für RB-Tree-Schlüssel darin besteht, zuerst die Gleichheit zu testen und dann die Identität zu vergleichen (dh Zeiger zu vergleichen). Diese Reihenfolge wäre jedoch nicht transitiv: Wenn a == bund id(a) > id(c), dann muss auch diese folgen id(b) > id(c), was hier nicht garantiert ist. Stattdessen können wir den Hash-Code der Schlüssel als Suchschlüssel verwenden. Hier funktioniert die Reihenfolge korrekt, aber es kann vorkommen, dass mehrere unterschiedliche Schlüssel mit demselben Hash-Code vorhanden sind, die demselben Knoten im RB-Baum zugewiesen werden. Um diese Hash-Kollisionen zu lösen, können wir wie bei Hash-Tabellen eine separate Verkettung verwenden, dies erbt jedoch auch das Worst-Case-Verhalten für Hash-Tabellen - das Schlimmste aus beiden Welten.

Andere Aspekte

• Ich erwarte von einer Hash-Tabelle eine bessere Speicherlokalität als ein Baum, da eine Hash-Tabelle im Wesentlichen nur ein Array ist.

• Einträge in beiden Datenstrukturen haben einen ziemlich hohen Overhead:

  • Hash-Tabelle: Schlüssel, Wert und nächster Eintragszeiger bei separater Verkettung. Auch das Speichern des Hash-Codes kann die Größenänderung beschleunigen.
  • RB-Baum: Schlüssel, Wert, Farbe, linker untergeordneter Zeiger, rechter untergeordneter Zeiger. Beachten Sie, dass, obwohl Farbe ein einzelnes Bit ist, Ausrichtungsprobleme bedeuten können, dass Sie immer noch genug Platz für fast einen ganzen Zeiger oder sogar fast vier Zeiger verschwenden, wenn nur Speicherblöcke mit Zweierpotenzen zugewiesen werden können. In jedem Fall verbraucht ein RB-Baumeintrag mehr Speicher als ein Hash-Tabelleneintrag.

• Einfügungen und Löschungen in einem RB-Baum beinhalten Baumrotationen. Diese sind nicht wirklich teuer, aber mit einem Overhead verbunden. In einem Hash ist das Einfügen und Löschen nicht teurer als ein einfacher Zugriff (obwohl das Ändern der Größe einer Hash-Tabelle beim Einfügen ein O(n)Unterfangen ist).

• Hash-Tabellen sind von Natur aus veränderbar, während ein RB-Baum auch unveränderlich implementiert werden könnte. Dies ist jedoch selten nützlich.

Es gibt eine ganze Reihe von Gründen, die zutreffen könnten , aber die wichtigsten sind wahrscheinlich:

• Hash-Tabellen sind einfacher zu implementieren als Bäume. Beides ist nicht ganz trivial, aber Hash-Tabellen sind etwas einfacher, und die Auswirkungen auf die Domäne der legalen Schlüssel sind weniger streng, da Sie nur eine Hashing-Funktion und eine Gleichheitsfunktion benötigen. Bäume erfordern eine Gesamtordnungsfunktion, und das ist viel schwieriger zu schreiben.
• Hash-Tabellen haben (möglicherweise) eine bessere Leistung bei kleinen Größen. Dies ist sehr wichtig, da ein erheblicher Teil der Arbeit nur theoretisch mit großen Datenmengen befasst ist. In der Praxis funktioniert vieles tatsächlich nur mit zehn oder Hunderten von Schlüsseln, nicht mit Millionen. Die Leistung im kleinen Maßstab ist sehr wichtig, und Sie können keine asymptotische Analyse verwenden, um herauszufinden, was dort am besten ist. Sie müssen tatsächlich implementieren und messen.

Einfacher zu schreiben / zu warten und in typischen Anwendungsfällen ein Leistungssieger? Melde mich bitte an!