5
Was ist eine gute Hashtable-Implementierung für C? Ich muss es mit MPICC-Compiler verwenden. Die Löschfunktion ist nicht notwendig.Hashtable-Implementierung für C
A
Antwort
4
Die in glib ist sehr nett. Nicht sicher, ob es zu groß und/oder vom Rest von glib zu isolieren ist.
In diesem Fall scheint Pearson hashing ein guter Ausgangspunkt für die Implementierung Ihrer eigenen (es ist eine Hash-Funktion für Maschinen mit 8-Bit-Registern optimiert).
+0
glib ist nett, aber es ist so groß, dass ich nicht vorschlagen würde, es in Ihr Projekt nur dafür aufzunehmen. Wenn Sie auch alle anderen Funktionen von glib benötigen, stimme ich zu, dass dies der richtige Weg wäre. –
3
Wenn die Schlüssel alle im Voraus bekannt sind, können Sie einen perfect hash Generator verwenden, um den Platzbedarf zu vermeiden, der in Hashtabellen impliziert ist.
Wenn Sie hingegen eine vollständige Hash-Tabelle benötigen, würde ich eine Variation von Cuckoo Hashing vorschlagen (z. B. die d-ay-Version).
Ich habe mit Befriedigung eine vereinfachte Version der Hopscotch Hashing verwendet, die auch bei höheren Lastfaktoren ziemlich gut funktioniert.
Keine, eigentlich. Außerdem wäre die Hashtable unveränderlich. – Alex
Unveränderlich im Sinne "einmal erstellt und nicht später geändert". – Alex
Sind die Daten zur Kompilierzeit bekannt? Dann könnten Sie einen perfekten Hash-Generator verwenden, wie Remo.D vorgeschlagen hat. – quinmars