¿Qué función hash de enteros es buena y acepta una clave hash de enteros?
¿Qué función hash de enteros es buena y acepta una clave hash de enteros?
Descubrí que el siguiente algoritmo proporciona una muy buena distribución estadística. Cada bit de entrada afecta a cada bit de salida con aproximadamente un 50% de probabilidad. No hay colisiones (cada entrada da como resultado una salida diferente). El algoritmo es rápido excepto si la CPU no tiene una unidad de multiplicación de enteros incorporada. Código C, asumiendo que intes de 32 bits (para Java, reemplácelo >>con >>>y elimine unsigned):
unsigned int hash(unsigned int x) {
x = ((x >> 16) ^ x) * 0x45d9f3b;
x = ((x >> 16) ^ x) * 0x45d9f3b;
x = (x >> 16) ^ x;
return x;
}
El número mágico se calculó utilizando un programa de prueba especial de subprocesos múltiples que se ejecutó durante muchas horas, que calcula el efecto de avalancha (el número de bits de salida que cambian si se cambia un solo bit de entrada; debería ser casi 16 en promedio), independencia de cambios de bits de salida (los bits de salida no deben depender entre sí) y la probabilidad de un cambio en cada bit de salida si se cambia algún bit de entrada. Los valores calculados son mejores que los del finalizador de 32 bits utilizado por MurmurHash y casi tan buenos (no del todo) como cuando se utiliza AES . Una ligera ventaja es que la misma constante se usa dos veces (lo hizo un poco más rápido la última vez que probé, no estoy seguro si sigue siendo así).
Puede revertir el proceso (obtener el valor de entrada del hash) si reemplaza con 0x45d9f3b( 0x119de1f3el inverso multiplicativo ):
unsigned int unhash(unsigned int x) {
x = ((x >> 16) ^ x) * 0x119de1f3;
x = ((x >> 16) ^ x) * 0x119de1f3;
x = (x >> 16) ^ x;
return x;
}
Para números de 64 bits, sugiero utilizar lo siguiente, aunque puede que no sea el más rápido. Éste está basado en splitmix64 , que parece estar basado en el artículo del blog Better Bit Mixing (mezcla 13).
uint64_t hash(uint64_t x) {
x = (x ^ (x >> 30)) * UINT64_C(0xbf58476d1ce4e5b9);
x = (x ^ (x >> 27)) * UINT64_C(0x94d049bb133111eb);
x = x ^ (x >> 31);
return x;
}
En este caso, revertir es más complicado:
uint64_t unhash(uint64_t x) {
x = (x ^ (x >> 31) ^ (x >> 62)) * UINT64_C(0x319642b2d24d8ec3);
x = (x ^ (x >> 27) ^ (x >> 54)) * UINT64_C(0x96de1b173f119089);
x = x ^ (x >> 30) ^ (x >> 60);
return x;
}
Todo lo anterior es para C. Para Java, use long, agregue La la constante, reemplace >>con >>>y elimine unsigned.
Actualización: es posible que también desee consultar el proyecto Hash Function Prospector , donde se enumeran otras constantes (posiblemente mejores).
El método multiplicativo de Knuth:
hash(i)=i*2654435761 mod 2^32
En general, debes elegir un multiplicador que esté en el orden del tamaño de tu hash ( 2^32en el ejemplo) y que no tenga factores comunes. De esta manera, la función hash cubre todo el espacio hash de manera uniforme.
Editar: La mayor desventaja de esta función hash es que preserva la divisibilidad, por lo que si todos sus números enteros son divisibles por 2 o por 4 (lo cual no es raro), sus hashes también lo serán. Este es un problema en las tablas hash: puede terminar con solo 1/2 o 1/4 de los depósitos en uso.
Depende de cómo se distribuyan sus datos. Para un contador simple, la función más simple
f(i) = i
Será bueno (sospecho que es óptimo, pero no puedo probarlo).
Se pueden componer funciones hash rápidas y buenas a partir de permutaciones rápidas con menores cualidades, como
- multiplicación con un entero impar
- rotaciones binarias
- xorshift
Para producir una función hash con cualidades superiores, como se demostró con PCG para la generación de números aleatorios.
De hecho, esta es también la receta que utilizan rrxmrrxmsx_0 y murmur hash, a sabiendas o sin saberlo.
Yo personalmente encontré
uint64_t xorshift(const uint64_t& n,int i){
return n^(n>>i);
}
uint64_t hash(const uint64_t& n){
uint64_t p = 0x5555555555555555ull; // pattern of alternating 0 and 1
uint64_t c = 17316035218449499591ull;// random uneven integer constant;
return c*xorshift(p*xorshift(n,32),32);
}
para ser lo suficientemente bueno.
Una buena función hash debería
- ser biyectivo para no perder información, si es posible y tener la menor cantidad de colisiones
- conecte en cascada tanto y tan uniformemente como sea posible, es decir, cada bit de entrada debe invertir cada bit de salida con una probabilidad de 0,5.
Primero veamos la función de identidad. Satisface 1. pero no 2. :
El bit de entrada n determina el bit de salida n con una correlación del 100% (rojo) y ningún otro; por lo tanto, son azules, lo que da una línea roja perfecta.
Un xorshift(n,32) no es mucho mejor, ya que produce una línea y media. Sigue siendo satisfactorio 1., porque es invertible con una segunda aplicación.
Una multiplicación con un entero sin signo ( "método multiplicativo de Knuth" ) es mucho mejor, ya que se realiza en cascada con más fuerza y se invierten más bits de salida con una probabilidad de 0,5, que es lo que desea, en verde. Satisface 1. ya que para cada entero impar hay un inverso multiplicativo.
La combinación de los dos da el siguiente resultado, que aún satisface 1. ya que la composición de dos funciones biyectivas produce otra función biyectiva.
Una segunda aplicación de multiplicación y xorshift producirá lo siguiente:
O puede usar multiplicaciones de campo de Galois como GHash , se han vuelto razonablemente rápidas en las CPU modernas y tienen cualidades superiores en un solo paso.
uint64_t const inline gfmul(const uint64_t& i,const uint64_t& j){
__m128i I{};I[0]^=i;
__m128i J{};J[0]^=j;
__m128i M{};M[0]^=0xb000000000000000ull;
__m128i X = _mm_clmulepi64_si128(I,J,0);
__m128i A = _mm_clmulepi64_si128(X,M,0);
__m128i B = _mm_clmulepi64_si128(A,M,0);
return A[0]^A[1]^B[1]^X[0]^X[1];
}
