c++ - tabla - tipos de datos enteros en programacion

Función Hashing 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 analizar estos cuatro enteros, por lo que puedo comparar el resultado de esta función con los resultados futuros.

Sin embargo, 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 hash puede ser un entero de 32 o 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 tan pocas colisiones como sea posible.

¿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 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 de hash analizadas aquí .

Answer 2

¿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 3

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 uniformemente distribuida, proporciona una salida uniformemente distribuida. 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.

Answer 4

Debido a que el hashing puede generar colisiones, 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 muy pequeña, solo usa la tecla directamente en lugar de hash. Esto será más rápido y garantizará que no haya colisiones.

Answer 5

Estoy totalmente de acuerdo con Vinko, simplemente compáralos todos. 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 combinar 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 6

Intente 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).

Además, 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 han sugerido otras personas, 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 7

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