Wie werden Hash-Tabellen intern in gängigen Sprachen implementiert?

Kann jemand bitte etwas Licht ins Dunkel bringen, wie populäre Sprachen wie Python, Ruby Hash-Tabellen intern für die Symbolsuche implementieren? Verwenden sie die klassische Methode „Array mit verknüpfter Liste“ oder verwenden sie einen ausgewogenen Baum?

Ich brauche eine einfache (weniger LOC) und schnelle Methode zum Indizieren der Symbole in einer in C geschriebenen DSL. Ich habe mich gefragt, was andere am effizientesten und praktischsten gefunden haben.

Das klassische “Array von Hash-Buckets”, das Sie erwähnen, wird in jeder Implementierung verwendet, die ich gesehen habe.

Eine der lehrreichsten Versionen ist die Hash-Implementierung in der Tcl-Sprache in Datei tcl/generic/tclHash.c. Mehr als die Hälfte der Zeilen in der Datei sind erklärende Kommentare alles im Detail: Allokation, Suche, verschiedene Hash-Tabellentypen, Strategien, etc. Nebenbemerkung: Der Code, der die Tcl-Sprache implementiert, ist Ja wirklich lesbar.

Perl verwendet ein Array mit verknüpften Listen, um Kollisionen zu halten. Es verfügt über eine einfache Heuristik, um die Größe des Arrays bei Bedarf automatisch zu verdoppeln. Es gibt auch Code, um Schlüssel zwischen Hashes zu teilen, um ein wenig Speicher zu sparen. Sie können darüber in der veralteten, aber immer noch aktuellen Version lesen Illustrierte Eingeweide von Perl unter “HV”. Wenn Sie wirklich abenteuerlustig sind, können Sie graben hv.c.

Früher war der Hashing-Algorithmus ziemlich einfach, aber mit Unicode ist er jetzt wahrscheinlich viel komplizierter. Da der Algorithmus vorhersehbar war, gab es einen DoS-Angriff, bei dem der Angreifer Daten generierte, die Hash-Kollisionen verursachten. Beispielsweise eine riesige Liste von Schlüsseln, die als POST-Daten an eine Website gesendet werden. Das Perl-Programm würde es wahrscheinlich aufteilen und in einen Hash ausgeben, der dann alles in einen Eimer schiebt. Der resultierende Hash war O(n) und nicht O(1). Werfen Sie eine ganze Menge POST-Anforderungen an einen Server, und Sie könnten die CPU verstopfen. Als Ergebnis stört Perl nun die Hash-Funktion mit ein paar Zufallsdaten.

Vielleicht möchten Sie sich auch ansehen wie Parrot grundlegende Hashes implementiert was deutlich weniger beängstigend ist als die Implementierung von Perl 5.

Verwenden Sie für “am effizientesten und praktischsten” die Hash-Bibliothek eines anderen. Schreiben Sie um Gottes willen nicht selbst einen für die Produktion. Es gibt bereits eine Unmenge robuster und effizienter da draußen.

Lua Tabellen verwenden ein absolut geniale umsetzung was sich für beliebige Schlüssel wie ein ‘Array von Eimern’ verhält, aber wenn Sie aufeinanderfolgende ganze Zahlen als Schlüssel verwenden, hat es die gleiche Darstellung und den gleichen Platzbedarf wie ein Array. In der Implementierung hat jede Tabelle eine Hash-Teil und ein Array-Teil.

Ich finde das total cool 🙂

Attraktives Chaos haben eine Vergleich von Hash-Tabellenbibliotheken und ein aktualisieren. Der Quellcode ist verfügbar und er ist in C und C++

Ausgeglichene Bäume machen den Zweck von Hash-Tabellen zunichte, da eine Hash-Tabelle eine Suche in (amortisierter) konstanter Zeit ermöglichen kann, während die durchschnittliche Suche in einem ausgeglichenen Baum O (log (n)) beträgt.

Separates Verketten (Array mit verknüpfter Liste) funktioniert wirklich gut, wenn Sie über genügend Buckets verfügen und Ihre Implementierung verknüpfter Listen einen Pooling-Allocator verwendet, anstatt jeden Knoten aus dem Heap einzeln mit malloc() zu verknüpfen. Ich habe festgestellt, dass es ungefähr so ​​​​leistungsfähig ist wie jede andere Technik, wenn es richtig eingestellt ist, und es ist sehr einfach und schnell zu schreiben. Versuchen Sie, mit 1/8 so vielen Buckets wie Quelldaten zu beginnen.

Sie können auch verwenden offene Adressierung mit quadratischer oder polynomialer Sondierung, wie Python es tut.

Wenn du lesen kannst Javasollten Sie sich insbesondere den Quellcode für die verschiedenen Kartenimplementierungen ansehen HashMap, TreeMap und ConcurrentSkipListMap. Die beiden letzteren sorgen für Ordnung in den Schlüsseln.

Javas HashMap verwendet die von Ihnen erwähnte Standardtechnik des Verkettens an jeder Eimerposition. Es verwendet ziemlich schwache 32-Bit-Hashcodes und speichert die Schlüssel in der Tabelle. Die Autoren von Numerical Recipes geben auch ein Beispiel (in C) einer Hash-Tabelle, die im Wesentlichen wie die von Java strukturiert ist, in der Sie jedoch (a) die Knoten der Bucket-Listen aus einem Array zuweisen und (b) einen stärkeren 64-Bit-Hash verwenden Code und verzichten auf das Speichern von Schlüsseln in der Tabelle.

Was Crashworks sagen wollte, war ….

Der Zweck von Hash-Tabellen ist das ständige Suchen, Hinzufügen und Löschen. In Bezug auf den Algorithmus ist die Operation für alle Operationen O(1) amortisiert. Wenn Sie dagegen einen Baum verwenden … beträgt die Betriebszeit im schlimmsten Fall O (log n) für einen ausgeglichenen Baum. N ist die Anzahl der Knoten. Aber haben wir wirklich Hash als Tree implementiert?