¿Cuál es una buena función hash para palabras en inglés?

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 sum los valores ASCII de las letras y luego el tamaño de la tabla. Estoy buscando algo eficiente y simple.

Simplemente sumr 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 rendimiento, lea aquí .

Agregado: Estas son funciones hashing generales , donde el dominio de entrada no se conoce de antemano (excepto tal vez algunas suposiciones muy generales: por ejemplo, lo anterior funciona un poco mejor con la 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.

Tal vez algo como esto te ayude: http://www.gnu.org/s/gperf/

Genera una función hashing optimizada para el dominio de entrada.

Si no es necesario que sea 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 sugiero SHA1 a través de OpenSSL.

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

Un poco tarde, pero aquí hay una función hash con una tasa de colisión extremadamente baja para la versión de 64 bits a continuación, y ~ casi ~ como buena 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 agrupaciones que pude detectar; esto se comprobó utilizando solo las cadenas aleatorias.
[editar]
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 se compara con FNV1A_Hash_Yorikke, djb2 y MurmurHash2 en los mismos conjuntos: Yorikke y djb2 no lo hicieron bien; slash_hash lo hizo un poco mejor que MurmurHash2 en todas las pruebas)