Qual è una buona funzione di hash per le parole inglesi?

Ho una lunga lista di parole inglesi e vorrei scriverle. Quale sarebbe una buona funzione di hashing? Finora la mia funzione di hashing sum i valori ASCII delle lettere e quindi modulo le dimensioni della tabella. Sto cercando qualcosa di efficiente e semplice.

Sommare semplicemente le lettere non è una buona strategia perché una permutazione dà lo stesso risultato.

Questo ( djb2 ) è abbastanza popolare e funziona bene con le stringhe ASCII.

unsigned long hashstring(unsigned char *str) { unsigned long hash = 5381; int c; while (c = *str++) hash = ((hash << 5) + hash) + c; /* hash * 33 + c */ return hash; } 

Se hai bisogno di più alternative e alcune misure di perfomance, leggi qui .

Aggiunti: si tratta di funzioni di hashing generali , in cui il dominio di input non è noto in anticipo (tranne forse alcune ipotesi molto generali: ad esempio, quanto sopra funziona leggermente meglio con input ASCII), che è lo scenario più comune. Se hai un dominio limitato noto (set di input fissi) puoi fare di meglio, vedi la risposta di Fionn.

Forse qualcosa del genere potrebbe aiutarti: http://www.gnu.org/s/gperf/

Genera una funzione di hash ottimizzata per il dominio di input.

Se non ti serve essere crittograficamente sicuro, ti suggerirei il Murmur Hash. È estremamente veloce e ha un’elevata diffusione. Facile da usare.

http://en.wikipedia.org/wiki/MurmurHash

http://code.google.com/p/smhasher/wiki/MurmurHash3

Se hai bisogno di un hash crittograficamente sicuro, allora suggerisco SHA1 tramite OpenSSL.

http://www.openssl.org/docs/crypto/sha.html

Un po ‘tardi, ma qui c’è una funzione di hashing con un tasso di collisione estremamente basso per la versione a 64 bit di seguito, e ~ quasi ~ buono per la versione a 32 bit:

 uint64_t slash_hash(const char *s) //uint32_t slash_hash(const char *s) { union { uint64_t h; uint8_t u[8]; }; int i=0; h=strlen(s); while (*s) { u[i%8] += *s + i + (*s >> ((h/(i+1)) % 5)); s++; i++; } return h; //64-bit //return (h+(h>>32)); //32-bit } 

Anche i numeri di hash sono distribuiti in modo molto uniforms su tutta la gamma ansible, senza grumi che potrei rilevare – questo è stato controllato usando solo le stringhe casuali.
[modificare]
Testato anche contro parole estratte da file di testo locali combinati con le parole dizionario / thesaurus di LibreOffice (inglese e francese – più di 97000 parole e costrutti) con 0 collisioni in 64-bit e 1 collisione in 32-bit 🙂

(Anche rispetto a FNV1A_Hash_Yorikke, djb2 e MurmurHash2 sugli stessi set: Yorikke e djb2 non hanno funzionato bene, slash_hash ha fatto leggermente meglio di MurmurHash2 in tutti i test)