Función hashing para cuatro enteros sin signo (C++)

Question

Estoy escribiendo un programa en este momento que produce cuatro enteros sin signo de 32 bits como salida de una determinada función. Quiero analizar estos cuatro enteros, por lo que puedo comparar el resultado de esta función con los resultados futuros.

No obstante, tengo problemas para escribir una función hash decente. Cuando originalmente escribí este código, agregué una simple suma de cada uno de los cuatro enteros, que sabía que no serían suficientes. He intentado varias otras técnicas, como cambiar y agregar, sin éxito. Obtengo un hash, pero es de mala calidad y la función genera una tonelada de colisiones.

La salida de hash puede ser un entero de 32 o 64 bits. La función en cuestión genera muchos miles de millones de hash, por lo que las colisiones son un problema real aquí, y estoy dispuesto a usar una variable más grande para asegurar que haya tan pocas colisiones como sea posible.

¿Alguien me puede ayudar a encontrar la manera de escribir una función hash de calidad?

Answer 1

¿Por qué no almacena los cuatro enteros en una estructura de datos adecuada y los compara todos? El beneficio de mezclarlos en este caso me parece dudoso, a menos que el almacenamiento sea un problema.

Si el problema es el almacenamiento, puede usar una de las funciones hash analizadas here.

Answer 2

Dado que el hash puede generar colisiones, debe conservar las claves en la memoria de todos modos para descubrir estas colisiones. Hashmaps y otras estructuras de datos estándar hacen esto en su contabilidad interna.

Como la clave es muy pequeña, solo use la tecla directamente en lugar de hash. Esto será más rápido y garantizará que no haya colisiones.

Answer 3

¿Por qué un hash? Parece que un conjunto std :: set o std :: multi sería más adecuado para almacenar este tipo de resultados. Todo lo que necesitas hacer es envolver los cuatro enteros en una estructura y escribir una función de comparación simple.

Answer 4

Pruebe usar CRC o FNV. FNV es bueno porque es rápido y tiene un método definido de doblar bits para obtener valores hash "más pequeños" (es decir, 12 bits/24 bits/etc).

También la ventaja de generar un hash de 64 bits a partir de un número de 128 bits (4 X 32 bits) es un poco cuestionable porque como otras personas han sugerido, podría simplemente usar el valor original como clave en un conjunto. Realmente desea que la cantidad de bits en el hash represente el número de valores que originalmente tiene. Por ejemplo, si su conjunto de datos tiene 100.000 valores de 4X32 bits, probablemente desee un valor hash de 17 o 18 bits, no un hash de 64 bits.

Answer 5

Puede ser un poco exagerado, pero considere Boost.Hash. Genera código muy simple y buenos valores.

Answer 6

Estoy totalmente de acuerdo con Vinko, simplemente compárelas todas. Si aún desea una buena función de hashing, debe analizar la distribución de sus 4 enteros sin ligar. Luego tiene que crear su función de hash de forma que el resultado se distribuya uniformemente en todo el rango del valor de hash de 32 bits.

Un ejemplo simple: supongamos que la mayoría de las veces, el resultado de cada función está en el rango de 0 a 255. Luego, podría mezclar fácilmente los 8 bits más bajos de cada función en su hash. La mayoría de las veces, se obtiene el resultado directamente, solo algunas veces (cuando una función arroja un resultado mayor) se produce una colisión.

Para resumir: sin información de cómo se distribuyen los resultados de las 4 funciones, no podemos ayudarlo con una buena función de hashing.

Answer 7

Así es una función hash bastante razonable a partir de 4 números enteros a 1 entero:

unsigned int hash = in[0]; 
hash *= 37; 
hash += in[1]; 
hash *= 37; 
hash += in[2]; 
hash *= 37; 
hash += in[3]; 

Con la entrada distribuido uniformemente-da salida distribuida uniformemente. Todos los bits de la entrada participan en la salida, y cada valor de entrada (aunque no todos los bits de entrada) puede afectar a cada bit de salida. Es probable que sea más rápido que la función que produce la salida, en cuyo caso no afecta el rendimiento.

Hay otros hashes con otras características, pero accumulate-with-multiplication-by-prime es un buen comienzo hasta que se demuestre lo contrario. Podría intentar acumular con xor en lugar de agregarlo si lo desea. De cualquier manera, es fácil generar colisiones (por ejemplo, {1, 0, a, b} colisiona con {0, 37, a, b} para todo a, b), por lo que es posible que desee elegir un primo que cree que tiene nada que ver con ningún error de implementación plausible en su función. Entonces, si su función tiene una gran cantidad de aritmética modulo-37, tal vez use 1000003 en su lugar.