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

Question

Kann jemand bitte etwas Licht in die Frage bringen, wie populäre Sprachen wie Python, Ruby Hashtabellen intern für Symbolsuche implementiert? Verwenden sie die klassische "array with linked-list" -Methode oder verwenden Sie einen ausgewogenen Baum?

Ich brauche eine einfache (weniger LOC) und schnelle Methode für die Indexierung der Symbole in einem DSL in C geschrieben. Fragte sich, was andere am effizientesten und praktischsten gefunden haben.

Answer 1

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 der Datei tcl/generic/tclHash.c. Mehr als die Hälfte der Zeilen in der Datei sind Kommentare, die erklären, alles im Detail: Zuordnung, Suche, verschiedene Hash-Tabelle Typen, Strategien, etc. Sidenote: der Code die Tcl-Sprache implementieren ist wirklich lesbar.

Answer 2

Ausbalancierte Bäume besiegen den Zweck von Hashtabellen, da eine Hashtabelle eine Suche in (amortisierter) konstanter Zeit bieten kann, während die durchschnittliche Suche in einem ausgeglichenen Baum O (log (n)) ist.

Separate Verkettung (Array mit verknüpfter Liste) funktioniert wirklich gut, wenn Sie genügend Buckets haben, und Ihre Implementierung der verknüpften Liste verwendet einen Pooling Allocator statt malloc() jeden Knoten vom Heap einzeln. Ich habe festgestellt, dass es bei richtiger Abstimmung genauso leistungsfähig ist wie jede andere Technik, und es ist sehr einfach und schnell zu schreiben. Beginnen Sie mit 1/8 so vielen Buckets wie Quelldaten.

Sie können auch open addressing mit quadratischer oder polynomischer Antastung verwenden, as Python does.

Answer 3

Attractive Chaos haben eine comparison of Hash Table Libraries und eine update. Der Quellcode ist verfügbar, und es ist in C und C++

Answer 4

Was war Crashworks damit sagen ....

Der Zweck der Hash-Tabellen sind konstante Zeit Lookup, Hinzufügen und Löschen. In Bezug auf Algorithmus ist die Operation für alle Operationen O (1) amortisiert. Während für den Fall, dass Sie Tree verwenden, die Worst-Case-Operation wird O (log n) für einen ausgeglichenen Baum sein. N ist die Anzahl der Knoten. aber haben wir wirklich Hash implementiert als Tree?

Answer 5

Perl verwendet ein Array mit verknüpften Listen, um Kollisionen zu halten. Es hat eine einfache Heuristik, um die Größe des Arrays nach 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 datierten aber immer noch relevanten Perl Illustrated Guts unter "HV" lesen. Wenn Sie wirklich abenteuerlich sind, können Sie in hv.c graben.

Der Hashalgorithmus war ziemlich simpel, aber mit Unicode wahrscheinlich viel komplizierter. Da der Algorithmus vorhersehbar war, gab es einen DoS-Angriff, bei dem der Angreifer Daten erzeugte, die Hash-Kollisionen verursachten. Zum Beispiel eine riesige Liste von Schlüsseln, die als POST-Daten an eine Website gesendet werden. Das Perl-Programm würde es wahrscheinlich teilen und es in einen Hash ausgeben, der dann alles in einen Eimer schob. Der resultierende Hash war O (n) und nicht O (1). Werfen Sie eine ganze Menge POST-Anfragen auf einen Server und Sie könnten die CPU verstopfen. Als Ergebnis stört Perl die Hash-Funktion mit ein paar zufälligen Daten.

Sie könnten auch auf how Parrot implements basic hashes betrachten, die deutlich weniger erschreckend als die Perl 5-Implementierung ist.

Verwenden Sie für "am effizientesten und praktischsten" die Hash-Bibliothek von jemand anderem. Um Gottes Willen, schreibe keinen selbst für den Produktionseinsatz. Es gibt bereits eine große Anzahl robuster und effizienter Geräte.

Answer 6

Wenn Sie Java lesen können, könnten Sie den Quellcode für die verschiedenen Karten Implementierungen prüfen wollen, insbesondere HashMap, TreeMap und ConcurrentSkipListMap. Die letzten beiden halten die Schlüssel geordnet.

Javas HashMap verwendet die Standardtechnik, die Sie an jeder Schaufelposition verketten. Es verwendet ziemlich schwache 32-Bit-Hash-Codes 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 Java strukturiert ist, aber in der (a) Sie die Knoten der Bucket-Listen aus einem Array zuweisen und (b) Sie einen stärkeren 64-Bit-Hash verwenden Code und verzichten auf die Speicherung von Schlüsseln in der Tabelle.

Answer 7

Lua Tabellen verwenden einen utterly ingenious implemenation, der sich für beliebige Schlüssel wie 'Array von Buckets' verhält, aber wenn Sie aufeinanderfolgende Ganzzahlen als Schlüssel verwenden, hat er dieselbe Darstellung und denselben Platzbedarf wie ein Array. In der Implementierung hat jede Tabelle einen Hash-Teil und einen Array-Teil.

Ich denke, das :-) so cool ist