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

Question

Estoy escribiendo un programa en este momento que produce cuatro enteros de 32 bits sin signo como salida de una determinada función. Quiero desmenuzar estos cuatro enteros, para poder comparar la salida de esta función con salidas futuras.

Sin embargo, tengo problemas para escribir una función hash decente. Cuando originalmente escribí este código, agregué una simple adición de cada uno de los cuatro enteros, lo que sabía que no sería suficiente. He intentado varias otras técnicas, como cambiar y agregar, en vano. Obtengo un hash, pero es de baja calidad y la función genera un montón de colisiones.

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

¿Alguien puede ayudarme a descubrir cómo 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 a todos? El beneficio de hacer hash en este caso me parece dudoso, a menos que el almacenamiento sea un problema.

Si el problema es el almacenamiento, puede utilizar una de las funciones hash analizadas aquí .

Answer 2

Aquí hay una función hash bastante razonable de 4 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 una entrada distribuida uniformemente, proporciona una 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. Lo más probable es que sea más rápido que la función que produce la salida, en cuyo caso no hay problemas de rendimiento.

Hay otros hashes con otras características, pero acumular con multiplicación por cebado es un buen comienzo hasta que se demuestre lo contrario. Puede intentar acumular con xor en lugar de sumar si lo desea. De cualquier manera, es fácil generar colisiones (por ejemplo, {1, 0, a, b} colisiona con {0, 37, a, b} para todos a, b), por lo que es posible que desee elegir una prima 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 mucha aritmética de módulo 37, tal vez use 1000003 en su lugar.

Answer 3

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

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

Answer 4

Estoy totalmente de acuerdo con Vinko, solo compárelos a todos. Si aún desea una buena función de hash, debe analizar la distribución de sus 4 enteros sin codificar. Luego, debe crear su función de hash de manera que el resultado se distribuya incluso en todo el rango del valor de hashing 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 inferiores de cada función en su hash. La mayoría de las veces, encontraría el resultado directamente, solo algunas veces (cuando una función devuelve un resultado más grande) tendría una colisión.

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

Answer 5

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

Answer 6

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

También el beneficio 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 lo han sugerido otras personas, podría usar el valor original como clave en un conjunto . Realmente desea que el número de bits en el hash represente el número de valores que originalmente tenía. Por ejemplo, si su conjunto de datos tiene 100,000 valores de 4X32 bits, probablemente desee un valor de hash de 17 o 18 bits, no un hash de 64 bits.

Answer 7

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