Quiero una función hash que toma un número largo (64 bits) y produce un resultado de 10 bits. ¿Cuál es la mejor función hash para tal fin? Las entradas son básicamente direcciones de variables (las direcciones son de 64 bits u 8 bytes en Linux), por lo que mi función hash debe optimizarse para ese fin.Función hash para 64 bit a 10 bits
diría somethig así:
uint32_t hash(uint64_t x)
{
x >>= 3;
return (x^(x>>10)^(x>>20)) & 0x3FF;
}
El temor significativos 3 bits no son muy útiles, como la mayoría de las variables son de 4 bytes u 8 bytes alineados, por lo que eliminarlos. Luego tomamos los siguientes 30 bits y los mezclamos juntos (XOR) en bloques de 10 bits cada uno.
Naturalmente, también puede tomar el (x>>30)^(x>>40)^(x>>50) pero no estoy seguro de si harán alguna diferencia en la práctica.
Dado que usa xor-shift para mezclar, yo recomendaría usar uno de los 277 trillizos conocidos con un período de 2^64-1 en su matriz de 64x64 como lo describe Marsaglia, por ejemplo (7, 11, 10) o (21, 17,48). Como esto mezcla los bits de una manera pseudoaleatoria sin rarezas conocidas, es válido combinar todas las palabras antes de hacer el & 0x3ff. De esta forma, cada bit de entrada debería tener la posibilidad de influir en todos los bits de salida. Quizás no sea tan perfectamente 50:50 distribuido como en un hash criptográfico, pero tan bueno como puedas obtener. Aparte de eso, sigue siendo una excelente idea, +1 – Damon
La mejor opción para la mayoría de las distribuciones es mod por prima, 1021 es la primo más grande de 10 bits. No hay necesidad de quitar los bits bajos.
static inline int hashaddress(void *v)
{
return (uintptr_t)v % 1021;
}
Si cree que el rendimiento puede ser una preocupación, tienen unos suplentes en la mano y les raza en su programa real. Microbenchmarks son residuos; es casi seguro que una diferencia de unos pocos ciclos se inunde con los efectos de caché, y el tamaño sí importa.
me escribió un juguete programa a ver algunas direcciones reales en la pila, área de datos, y el montón. Básicamente, declaro 4 globales, 4 locales e hice 2 mallocs. Dejé caer los dos últimos bits al imprimir las direcciones. Aquí es un salida de una de las carreras:
20125e8
20125e6
20125e7
20125e4
3fef2131
3fef2130
3fef212f
3fef212c
25e4802
25e4806
Lo que esto me dice:
Qué haría después:
/* Drop two LSBs. */
a >>= 2;
/* Get rid of the MSBs. Keep 46 bits. */
a &= 0x3fffffffffff;
/* Get the 14 MSBs and fold them in to get a 32 bit integer.
The MSBs are mostly 0s anyway, so we don't lose much entropy. */
msbs = (a >> 32) << 18;
a ^= msbs;
Ahora pasamos a través de una decent 'half avalanche' hash function, en vez de rodar nuestra propia. 'Half avalancha' significa que cada bit de la entrada para crear una oportunidad de afectar a los bits en la misma posición y superior:
uint32_t half_avalanche(uint32_t a)
{
a = (a+0x479ab41d) + (a<<8);
a = (a^0xe4aa10ce)^(a>>5);
a = (a+0x9942f0a6) - (a<<14);
a = (a^0x5aedd67d)^(a>>3);
a = (a+0x17bea992) + (a<<7);
return a;
}
Para un hash de 10 bits, utilice los 10 MSB de la uint32_t devuelto.La función hash continúa funcionando bien si selecciona N MSBs para un hash de bit N, duplicando efectivamente el conteo del cubo con cada bit adicional.
Estaba un poco aburrido, así que escribí un punto de referencia de juguete para esto. Nada elegante, asigna un montón de memoria en el montón y prueba el hash que describí anteriormente. La fuente se puede tener desde here. Un resultado ejemplo:
1024 cubos, 256 valores generados, 29 collissions
1024 cubos, 512 valores generados, 103 collissions
1024 cubos, 1024 valores generados, 370 collissions
Siguiente: Probé los otros dos hashes respondidos aquí. Ambos tienen un rendimiento similar. Parece: simplemente elija el más rápido;)
¿Qué información sobre la distribución de valores de 64 bits en su universo nos puede dar? –
No existe la "mejor" función hash para todos los casos. Tienes que estudiar la distribución y las características de tus números de entrada. –
La entrada es direcciones de variables en Linux. – MetallicPriest