Algoritmo de hash para la implementación de la tabla hash

Estoy buscando una función de hash de alta velocidad con buena distribución (es decir, casi uniforme) para su uso en la implementación de una tabla hash.Algoritmo de hash para la implementación de la tabla hash

La tabla hash se usará exclusivamente para almacenar valores con una clave entera.

¿Puedo simplemente utilizar los pocos bits más pequeños del número entero como el hash?

e.g clave int = n & 15; y crea una matriz con 16 espacios para almacenarlos.

¿Alguna recomendación?

Fuente

2012-05-29 Anonymous

+12

No existe la función hash perfecta. Sin embargo, si desea algunos algoritmos con el código fuente correspondiente, consulte aquí: http://partow.net/programming/hashfunctions/index.html –

Tomar los bits más bajos es probablemente lo peor que se puede hacer. (pero: todo depende del rango de valores que esperas en tu clave int) Intenta mezclar también los bits superiores, o multiplica con un número lo suficientemente grande (impar, principal). Sepa qué esperar y medirlo. – wildplasser

Publique su comentario como respuesta y lo aceptaré. –

Se puede ver aquí xxhash

Su función hash mencionado es muy rápido, pero es muy malo también. Si quieres una función hash "estúpida", tal vez puedas considerar el módulo.

Ejemplo:

int key = item % size_of_hash_table

Fuente

2012-10-30 16:35:18

¿Por qué es "malo"? –

Bueno, anoche hizo una prueba de hash versátil (en C) que cubre varios hashers top-gun y 38 teclas diferentes.

Todos ustedes son bienvenidos a punto de referencia en: http://www.overclock.net/t/1319572/benchmarking-the-fastest-hash-function/0_20#post_18495990

Me alegraría por revelar cómo Intel vs AMD y Intel 12.1 compilador vs Microsoft 16 (VS2010) combinaciones compilador se comportan con tu ayuda.

Fuente

2012-10-31 15:47:05 Georgi

Algoritmo de hash para la implementación de la tabla hash

Respuesta

Cuestiones relacionadas