Una funzione hash minima per C?

Question

Non riesco a usare boost: hash perché devo stare con C e non posso usare C++.

Ma, ho bisogno di hash un numero elevato (da 10K a 100k) di stringhe di token (da 5 a 40 byte di lunghezza) in modo che la ricerca all'interno di quelle sia la più veloce.

MD5, SHA1 o qualsiasi funzione di hash lunga sembra troppo pesante per un'operazione semplice, non sto facendo crittografia. Inoltre, vi è il costo di archiviazione e di elaborazione.

Quindi la mia domanda:

1. Quale potrebbe essere il più semplice algoritmo di hash che garantirà la prevenzione collisioni nei casi più pratici.

2. Quanti bit utilizzare per il valore hash? Sto sviluppando per sistemi a 32 bit. L'algoritmo hash in Perl/Python usa anche gli hash a 32 bit? O devo saltare a 64?

3. Riguardo all'implementazione delle tabelle hash nei linguaggi di scripting comuni: il controllo dell'implementazione per le collisioni o posso evitare del tutto quella parte?

Answer 1

È possibile trovare una buona (e veloce) funzione di hash, e una interessante lettura, a http://www.azillionmonkeys.com/qed/hash.html

L'unica volta in cui non è necessario verificare la presenza di collisioni, è se si utilizza un hash perfetto: una tabella di ricerca vecchio stile, come gperf.

Answer 2

Una funzione di hash generale per hash table lookup. Specifica NON utilizzare per scopi di crittografia, ma dal momento che hai specificato di non avere alcun intento, dovresti essere ok.

E 'incluso è A Survey di funzioni hash di provare

Answer 3

1. Here è una bella panoramica delle più importanti funzioni di hash noti.

2. 32 bit dovrebbe funzionare bene.

3. È sempre necessario verificare la presenza di collisioni, a meno che non si vuole scrivere una tabella hash divertente :)

Answer 4

Prova Adler32 per stringhe lunghe o Murmur2 per stringhe corte.

Answer 5

Se si utilizza un sistema posix allo stesso modo e si applica semplicemente C, vorrei semplicemente utilizzare ciò che il sistema ha già da offrire. man 3 hcreate ti offre tutti i dettagli oppure puoi trovare una versione online qui http://linux.die.net/man/3/hcreate

Answer 6

xxhash è un'opzione abbastanza veloce e facile. Un semplice codice userebbe XXH32 funzione:

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

Si tratta di 32 bit di hash.Dal momento che è lenint, per i dati più grandi più di 2^31-1 byte utilizzano questi:

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