¿Qué es una buena función hash para palabras en inglés?

Question

Tengo una larga lista de palabras en inglés y me gustaría tenerlas. ¿Cuál sería una buena función hash? Hasta ahora, mi función hash suma los valores ASCII de las letras y luego el tamaño de la tabla. Estoy buscando algo eficiente y simple.

Answer 1

Simplemente sumar las letras no es una buena estrategia porque una permutación da el mismo resultado.

Este (djb2) es bastante popular y funciona muy bien con cadenas 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; 
} 

Si necesita más alternativas y algunas medidas de perfomance, leer here.

Agregado: Estos son generales funciones de hash, donde el dominio de entrada no se conoce de antemano (excepto tal vez algunos supuestos muy generales: por ejemplo, lo anterior funciona ligeramente mejor con entrada ASCII), que es el escenario más habitual . Si tiene un dominio restringido conocido (conjunto de entradas corregidas) puede hacerlo mejor, vea la respuesta de Fionn.

Answer 2

Tal vez algo como esto le ayudaría a: http://www.gnu.org/s/gperf/

Se genera una función hash optimizado para el dominio de entrada.

Answer 3

Si no lo necesita es criptográficamente seguro, sugeriría el Murmur Hash. Es extremadamente rápido y tiene alta difusión. Fácil de usar.

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

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

Si necesita un hash criptográficamente seguro, entonces le sugiero SHA1 través de OpenSSL.

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

Answer 4

Un poco tarde, pero aquí es una función hash con una tasa de colisiones extremadamente baja para la versión de 64 bits a continuación, y ~ casi ~ tan bueno para la versión de 32 bits:

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 
} 

Los números hash también se distribuyen de manera muy uniforme en todo el rango posible, sin agrupar que pude detectar; esto se comprobó utilizando solo las cadenas aleatorias.
[edit]
También probado contra palabras extraídas de archivos de texto locales combinados con palabras del diccionario/tesauro de LibreOffice (inglés y francés - más de 97000 palabras y construcciones) con 0 colisiones en 64 bits y 1 colisión en 32 bits:)

(también compararon con FNV1A_Hash_Yorikke, djb2 y MurmurHash2 el mismo conjunto: Yorikke & djb2 no le fue bien; slash_hash hizo un poco mejor que MurmurHash2 en todas las pruebas)