Ich versuche, eine effiziente Nachschlagetabelle in C zu erstellen.
Ich habe eine Ganzzahl als Schlüssel und eine variable Länge char* als Wert.
Ich habe mir uthash angeschaut, aber das erfordert einen char* -Wert fester Länge. Wenn ich dies zu einer großen Zahl mache, benutze ich zu viel Speicher.
Hat jemand irgendwelche Hinweise? Jede Einsicht sehr geschätzt.
Danke für die Antworten. Ich bin mit uthash gegangen und habe meine eigene benutzerdefinierte Struktur definiert, um meine Daten unterzubringen.
Deklarieren Sie das value -Feld als void *value .
Auf diese Weise können Sie beliebige Daten als Wert angeben, aber die Verantwortung für das Zuweisen und Freigeben wird an den Client-Code delegiert.
Sie müssen zuerst an Ihre Kollisionsstrategie denken:
Wir wählen 1 aus.
Dann müssen Sie eine schön verteilte Hash-Funktion wählen. Für das Beispiel wählen wir
%Vor%Wenn Sie etwas Besseres brauchen, schauen Sie sich vielleicht die Methode im mittleren Quadrat an .
Dann müssen Sie entscheiden, was eine Hash-Tabelle ist.
%Vor%Dann müssen wir definieren, wie einzufügen und abzurufen.
%Vor%Und am wenigsten eine Methode zum Entfernen:
%Vor% Es hängt wirklich von der Verteilung Ihres Schlüsselfeldes ab. Wenn es beispielsweise ein eindeutiger Wert ist, der immer zwischen 0 und 255 liegt, verwenden Sie key % 256 , um den Bucket auszuwählen, und Sie haben einen perfekten Hashwert.
Wenn es gleichmäßig über alle möglichen int -Werte verteilt ist, wird jede Funktion, die Ihnen einen gleichmäßig verteilten Hash-Wert liefert (wie oben erwähnt key % 256 ), jedoch mit mehreren Werten in jedem Bucket.
Ohne die Verteilung zu kennen, ist es ein wenig schwierig, über effiziente Hashes zu sprechen.