significado - tablas hash c++ codigo

¿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 escribirlas. ¿Cuál sería una buena función de hash? Hasta ahora, mi función de hashing suma los valores ASCII de las letras y luego modula el tamaño de la tabla. Estoy buscando algo eficiente y simple.

Answer 1

Si no necesita ser criptográficamente seguro, sugeriría el Murmur Hash. Es extremadamente rápido y tiene una 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, sugiero SHA1 a través de OpenSSL.

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

Answer 2

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

Este ( cse.yorku.ca/~oz/hash.html ) es bastante popular y funciona 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 here .

Agregado: estas son funciones de hashing generales , donde el dominio de entrada no se conoce de antemano (excepto quizás 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 fijas) que puede mejorar, vea la respuesta de Fionn.

Answer 3

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

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

Answer 4

Un poco tarde, pero aquí hay una función de hash con una tasa de colisión extremadamente baja para la versión de 64 bits a continuación, y ~ casi ~ tan 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 el rango posible, sin que se pueda detectar el agrupamiento, esto se verificó utilizando solo cadenas aleatorias.
[editar]
También se probó contra las palabras extraídas de los archivos de texto locales combinados con las 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 comparado con FNV1A_Hash_Yorikke, djb2 y MurmurHash2 en los mismos conjuntos: Yorikke & djb2 no lo hizo bien; slash_hash lo hizo ligeramente mejor que MurmurHash2 en todas las pruebas)