Donnerschlag
Wie kann man eine Hashmap in C von Grund auf neu erstellen, wie sie in C++ STL vorhanden ist?
Welche Parameter würden berücksichtigt und wie würden Sie die Hashmap testen? Was wären die Benchmark-Testfälle, die Sie ausführen würden, bevor Sie sagen könnten, dass Ihre Hashmap vollständig ist?
Unbekannt
Nun, wenn Sie die Grundlagen dahinter kennen, sollte es nicht zu schwer sein.
Im Allgemeinen erstellen Sie ein Array namens “Buckets”, das den Schlüssel und den Wert enthält, mit einem optionalen Zeiger zum Erstellen einer verknüpften Liste.
Wenn Sie mit einem Schlüssel auf die Hash-Tabelle zugreifen, verarbeiten Sie den Schlüssel mit einer benutzerdefinierten Hash-Funktion, die eine ganze Zahl zurückgibt. Sie nehmen dann den Modul des Ergebnisses und das ist die Position Ihres Array-Index oder “Eimers”. Dann vergleichst du den ungehashten Schlüssel mit dem gespeicherten Schlüssel, und wenn er übereinstimmt, dann hast du die richtige Stelle gefunden.
Andernfalls hatten Sie eine “Kollision” und müssen die verknüpfte Liste durchsuchen und Schlüssel vergleichen, bis Sie übereinstimmen. (Beachten Sie, dass einige Implementierungen einen binären Baum anstelle einer verknüpften Liste für Kollisionen verwenden).
Schauen Sie sich diese schnelle Hash-Tabellenimplementierung an:
Neben LLs und Bäumen können Sie eine Hash-Map pro Bucket haben, die einen anderen Hash verwendet, um Kollisionen zu behandeln.
– sudo
6. Oktober 2016 um 3:57 Uhr
TStampfer
Der beste Ansatz hängt von der erwarteten Schlüsselverteilung und der Anzahl der Kollisionen ab. Wenn relativ wenige Kollisionen zu erwarten sind, spielt es keine Rolle, welches Verfahren verwendet wird. Wenn viele Kollisionen erwartet werden, hängt die zu verwendende Methode von den Kosten für das Rehashing oder Sondieren im Vergleich zur Manipulation der erweiterbaren Bucket-Datenstruktur ab.
Aber hier ist ein Beispiel für den Quellcode Eine Hashmap-Implementierung in C
Wie der spätere Beitrag sagt, müssen wir auch mit Kollisionen umgehen. Außerdem hat die Hash-Implementierung eine Tabellengröße, die wie fest ist. Wenn wir die Größe der Hashmap dynamisch erhöhen wollen, ohne dass der Programmierer weiß, wie es gemacht wird. Können Sie etwas vorschlagen?
– Donnerschlag
8. Mai 2009 um 5:58 Uhr
Das Ändern der Größe des Schlüsselraums bedeutet, dass die Hash-Funktion oder zumindest die Parameter der Funktion geändert und alle Einträge erneut gehasht werden. Jede Karte mit unterschiedlicher Größe erfordert einen anderen Satz von Hash-Funktionen, um die gewünschte Schlüsselverteilung aufrechtzuerhalten.
– TStamper
8. Mai 2009 um 6:03 Uhr
Der verlinkte Code wurde von einem Studenten geschrieben. “Es ist die erste Datenstruktur, die ich in C geschrieben habe”. Aus irgendeinem Grund fügte er Synchronisationscode hinzu, um es Thread-sicher zu machen.
– Andreas Häferburg
4. April 2019 um 19:52 Uhr
Das Hauptziel einer Hashmap besteht darin, einen Datensatz zu speichern und mit einem eindeutigen Schlüssel eine nahezu konstante Zeitsuche darauf bereitzustellen. Es gibt zwei gängige Arten der Hashmap-Implementierung:
Eine getrennte Verkettung ist vorzuziehen, wenn die Hashmap möglicherweise eine schlechte Hash-Funktion hat, es nicht wünschenswert ist, Speicher für potenziell ungenutzte Slots vorab zuzuweisen, oder Einträge eine variable Größe haben können. Diese Art von Hashmap kann weiterhin relativ effizient funktionieren, selbst wenn der Lastfaktor 1,0 übersteigt. Offensichtlich wird in jedem Eintrag zusätzlicher Speicher benötigt, um Zeiger auf verknüpfte Listen zu speichern.
Hashmaps mit offener Adressierung haben potenzielle Leistungsvorteile, wenn der Lastfaktor unter einem bestimmten Schwellenwert (im Allgemeinen etwa 0,7) gehalten wird und eine einigermaßen gute Hash-Funktion verwendet wird. Dies liegt daran, dass sie potenzielle Cache-Fehlschläge und viele kleine Speicherzuweisungen vermeiden, die einer verknüpften Liste zugeordnet sind, und alle Operationen in einem zusammenhängenden, vorab zugewiesenen Array ausführen. Die Iteration durch alle Elemente ist auch billiger. Der Haken an der Sache ist, dass Hashmaps, die offene Adressierung verwenden, einer größeren Größe neu zugewiesen und erneut gehasht werden müssen, um einen idealen Lastfaktor aufrechtzuerhalten, oder dass sie mit einer erheblichen Leistungseinbuße konfrontiert sind. Ihr Belastungsfaktor darf 1,0 nicht überschreiten.
Einige wichtige Leistungsmetriken, die beim Erstellen einer Hashmap zu bewerten sind, umfassen:
Hier ist eine flexible Hashmap-Implementierung, die ich erstellt habe. Ich habe offene Adressierung und lineares Sondieren für die Kollisionsauflösung verwendet.
Es gibt andere Mechanismen, um mit Überlauf umzugehen, als die einfältige verkettete Liste von Überlaufeinträgen, die zB viel Speicher verschwendet.
Welcher Mechanismus zu verwenden ist, hängt unter anderem davon ab, ob Sie die Hash-Funktion auswählen und möglicherweise mehr als eine auswählen können (um z. B. doppeltes Hashing zur Behandlung von Kollisionen zu implementieren); wenn Sie erwarten, häufig Elemente hinzuzufügen, oder wenn die Karte nach dem Füllen statisch ist; ob Sie beabsichtigen, Elemente zu entfernen oder nicht; …
Der beste Weg, dies zu implementieren, besteht darin, zuerst über all diese Parameter nachzudenken und es dann nicht selbst zu programmieren, sondern eine ausgereifte vorhandene Implementierung auszuwählen. Google hat ein paar gute Implementierungen – zB http://code.google.com/p/google-sparsehash/
