Eine minimale Hash-Funktion für C?

Ich kann boost:hash nicht verwenden, weil ich bei C bleiben muss und C++ nicht verwenden kann.

Aber ich muss eine große Anzahl (10.000 bis 100.000) von Token-Strings (5 bis 40 Bytes Länge) hashen, damit die Suche in diesen am schnellsten ist.

MD5, SHA1 oder jede lange Hash-Funktion scheint für eine einfache Aufgabe zu schwer zu sein, ich mache keine Kryptografie. Hinzu kommen die Speicher- und Rechenkosten.

Daher meine Frage:

1. Was könnte der einfachste Hash-Algorithmus sein, der in den meisten praktischen Fällen eine Kollisionsvermeidung gewährleistet?

2. Wie viele Bits sollen für den Hashwert verwendet werden? Ich entwickle für 32-Bit-Systeme. Verwendet der Hash-Algorithmus in Perl/Python auch 32-Bit-Hashes? Oder muss ich auf 64 springen?

3. In Bezug auf die Implementierung von Hash-Tabellen in gängigen Skriptsprachen: Prüft die Implementierung auf Kollisionen oder kann ich diesen Teil ganz vermeiden?

Eine gute (und schnelle) Hash-Funktion und eine interessante Lektüre finden Sie unter http://www.azillionmonkeys.com/qed/hash.html

Die einzige Zeit, in der Sie nicht auf Kollisionen prüfen sollten, ist, wenn Sie einen perfekten Hash verwenden – eine gute altmodische Nachschlagetabelle, wie z gperf.

1. Hier ist ein schöner Überblick über die bemerkenswertesten bekannten Hash-Funktionen.

2. 32bit sollte problemlos funktionieren.

3. Sie müssen immer nach Kollisionen suchen, es sei denn, Sie möchten eine lustige Hashtabelle schreiben 🙂

Eine allgemeine Hash-Funktion für Hash-Tabellensuche. Es spezifiziert NICHT für kryptografische Zwecke verwendenaber da Sie angegeben haben, dass Sie dies nicht beabsichtigen, sollten Sie in Ordnung sein.

Es ist inbegriffen Eine Übersicht über Hash-Funktionen ausprobieren

Wenn Sie auf einem posixähnlichen System arbeiten und sich an einfaches C halten, würde ich einfach verwenden, was das System bereits zu bieten hat. man 3 hcreate bietet Ihnen alle Details oder Sie finden hier eine Online-Version http://linux.die.net/man/3/hcreate

Versuchen Adler32 für lange Saiten bzw Murmeln2 für kurze Saiten.

xxhash ist eine ziemlich schnelle und einfache Option. Ein einfacher Code würde verwenden XXH32 Funktion:

unsigned int XXH32 (const void* input, int len, unsigned int seed);

Es ist ein 32-Bit-Hash. Seit len ist intfür größere Daten mehr als 2^31-1 Bytes verwenden diese:

void*         XXH32_init   (unsigned int seed);
XXH_errorcode XXH32_update (void* state, const void* input, int len);
unsigned int  XXH32_digest (void* state);