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

hash table in c example

Question

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

Pero, necesito un hash de un gran número (10K a 100k) de tokens strings (longitud de 5 a 40 bytes) para que la búsqueda dentro de esos sea más rápida.

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

Por lo tanto mi pregunta:

1. Lo que podría ser el algoritmo hash más simple que garantizará la prevención de colisiones en la mayoría de los casos prácticos.

2. ¿Cuántos bits usar 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. Con respecto a la implementación de las tablas hash en los lenguajes de scripting comunes: ¿la implementación verifica las colisiones o puedo evitar esa parte por completo?

Answer 1

1. Here hay una buena descripción de las funciones hash conocidas más notables.

2. 32bits deberían funcionar bien.

3. Siempre debes verificar las colisiones, a menos que quieras escribir una divertida tabla hash :)

Answer 2

Prueba Adler32 para cadenas largas o Murmur2 para cadenas cortas.

Answer 3

Puede encontrar una buena (y rápida) función hash y una lectura interesante en

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

Answer 4

Si está en un sistema similar a posix y se apega a la C simple, simplemente usaría lo que el sistema ya tiene para ofrecer. man 3 hcreate te ofrece todos los detalles o puedes encontrar una versión en línea aquí http://linux.die.net/man/3/hcreate

Answer 5

Una función hash general para la búsqueda de tabla hash . Especifica NO utilizar con fines criptográficos , pero como has especificado que no tienes intención de hacerlo, entonces deberías estar bien.

Se incluye una encuesta de funciones hash para probar

Answer 6

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

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

Es hash de 32 bits. Como len es int , para datos más grandes de más de 2^31-1 bytes, use estos:

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