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

Question

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

Answer 1

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

Questo (djb2) è piuttosto popolare e funziona perfettamente 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 avete bisogno di più alternative e alcune misure di perfomance, leggere here.

Aggiunto: Queste sono generali funzioni di hashing, in cui il dominio di ingresso non è nota in anticipo (tranne forse alcune ipotesi molto generali: ad esempio, le opere di cui sopra leggermente meglio con ingresso ASCII), che è lo scenario più usuale . Se hai un dominio limitato noto (set di input fissi) puoi fare di meglio, vedi la risposta di Fionn.

Answer 2

Forse qualcosa di simile potrebbe aiutare a: http://www.gnu.org/s/gperf/

Si genera una funzione di hashing ottimizzato per il dominio di ingresso.

Answer 3

Se non è necessario essere crittograficamente sicuro, 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 si ha bisogno di un hash crittograficamente sicuro, allora vi consiglio SHA1 via OpenSSL.

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

Answer 4

un po 'tardi, ma qui è una funzione di hashing con un tasso di collisione estremamente basso per la versione a 64 bit di seguito, e ~ quasi ~ come un bene 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 
} 

I numeri di hash sono anche distribuiti in modo molto uniforme nell'intervallo possibile, senza alcun grumo che potrei rilevare - questo è stato controllato usando solo le stringhe casuali.
[modifica]
Testato anche con parole estratte da file di testo locali combinati con le parole dizionario/thesaurus di LibreOffice (inglese e francese - oltre 97000 parole e costrutti) con 0 collisioni in 64-bit e 1 collisione in 32-bit:)

(anche confrontato con FNV1A_Hash_Yorikke, djb2 e MurmurHash2 on stessi set: Yorikke & djb2 non ha fatto bene; slash_hash ha fatto un po 'meglio rispetto MurmurHash2 in tutte le prove)