¿Una función hash mínima para C?

Question

No puedo usar boost: hash porque tengo que seguir con C y no puedo usar C++.

Pero, necesito para discutir un número grande (10K a 100K) de cadenas de tokens (5 a 40 bytes de longitud) para que la búsqueda dentro de esos son más rápidos.

MD5, SHA1 o cualquier función hash larga parece demasiado pesada para una tarea sencilla, no estoy haciendo la criptografía. Además, está el costo de almacenamiento y computación.

Por lo tanto mi pregunta

1. Cuál podría ser el algoritmo de control más simple que asegure la prevención de colisiones en la mayoría de casos prácticos.

2. ¿Cuántos bits a utilizar para el valor hash? Estoy desarrollando sistemas de 32 bits. ¿El algoritmo hash en Perl/Python usa hashes de 32 bits también? ¿O tengo que saltar a 64?

3. cuanto a la aplicación de las tablas hash en lenguajes de script comunes: ¿El cheque de implementación para las colisiones o puedo evitar que una parte del todo?

Answer 1

se puede encontrar una buena (y rápido) función hash, y una lectura interesante, en http://www.azillionmonkeys.com/qed/hash.html

La única vez que no debe verificar las colisiones, es si usa un hash perfecto, una buena tabla de búsqueda pasada de moda, como gperf.

Answer 2

Una función hash general para hash table lookup. Especifica NO utilizar con fines criptográficos, pero como ha especificado que no tiene intención de hacerlo, debería estar bien.

Incluía es Una encuesta de funciones hash probar

Answer 3

1. Here es un buen resumen de los más notables funciones hash conocidas.

2. de 32 bits debería funcionar bien.

3. Siempre hay que comprobar las colisiones, a menos que desee escribir una tabla hash divertido :)

Answer 4

Pruebe Adler32 para cadenas largas o Murmur2 para cadenas cortas.

Answer 5

Si estás en un sistema POSIX por igual y ajustarse a C llana, simplemente usaría lo que el sistema ya tiene que ofrecer. man 3 hcreate le ofrece todos los detalles o puede encontrar una versión en línea aquí http://linux.die.net/man/3/hcreate

Answer 6

xxhash es una opción bastante rápida y fácil. Un simple código usaría XXH32 función:

unsigned int XXH32 (const void* input, int len, unsigned int seed); 

Es 32 bits hash.Desde len es int, para los datos más grandes más de 2^31-1 bytes utilizan éstos:

void*   XXH32_init (unsigned int seed); 
XXH_errorcode XXH32_update (void* state, const void* input, int len); 
unsigned int XXH32_digest (void* state);