¿Qué función hash entera es buena que acepta una clave hash entera?

¿Qué función hash entera es buena que acepta una clave hash entera?

Método multiplicativo de Knuth:

hash(i)=i*2654435761 mod 2^32

En general, debe elegir un multiplicador que esté en el orden de su tamaño de hash ( 2^32en el ejemplo) y no tenga factores en común. De esta manera, la función hash cubre todo su espacio hash de manera uniforme.

Editar: la mayor desventaja de esta función hash es que conserva la divisibilidad, por lo que si sus números enteros son todos 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 cubos en uso.

Encontré 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 elimínelo 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; debe ser casi 16 en promedio), independencia de cambios en los bits de salida (los bits de salida no deben depender unos de otros) y la probabilidad de un cambio en cada bit de salida si se cambia cualquier 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 pequeña ventaja es que la misma constante se usa dos veces (lo hizo un poco más rápido la última vez que lo probé, no estoy seguro de si sigue siendo así).

Puede revertir el proceso (obtener el valor de entrada del hash) si reemplaza el 0x45d9f3bcon 0x119de1f3(el 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 usar lo siguiente, aunque podría no ser el más rápido. Este 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;
}

Para Java, use long, agregue La la constante, reemplace >>con >>>y elimine unsigned. En este caso, invertir 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;
}

Actualización: es posible que también desee ver el proyecto Prospector de función Hash , donde se enumeran otras constantes (posiblemente mejores).

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

Las funciones hash rápidas y buenas se pueden componer a partir de permutaciones rápidas con cualidades menores, como

• multiplicación con un número entero desigual
• 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 rrxmrrxmsx_0 y murmur hash están usando, a sabiendas o sin saberlo.

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);
}

ser lo suficientemente bueno.

Una buena función hash debería

1. Sea biyectivo para no perder información, si es posible y tener la menor cantidad de colisiones.
2. en cascada tanto como sea posible, es decir, cada bit de entrada debe invertir cada bit de salida con una probabilidad de 0.5.

Veamos primero 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 no otros, por lo tanto son azules, dando una línea roja perfecta a través.

Un xorshift (n, 32) no es mucho mejor, ya que produce una línea y media. Aún satisfaciendo 1., porque es invertible con una segunda aplicación.

Una multiplicación con un entero sin signo es mucho mejor, en cascada con más fuerza y ​​volteando 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 desigual hay un inverso multiplicativo.

La combinación de los dos da el siguiente resultado, aún satisfaciendo 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];                                              
   }

Esta página enumera algunas funciones hash simples que tienden a funcionar decentemente en general, pero cualquier hash simple tiene casos patológicos en los que no funciona bien.

• Método multiplicativo de 32 bits (muy rápido) ver @rafal

  #define hash32(x) ((x)*2654435761)
  #define H_BITS 24 // Hashtable size
  #define H_SHIFT (32-H_BITS)
  unsigned hashtab[1<<H_BITS]  
  .... 
  unsigned slot = hash32(x) >> H_SHIFT

• 32 bits y 64 bits (buena distribución) en: MurmurHash

• Función de hash de entero

Hay una buena descripción general de algunos algoritmos hash en Eternally Confuzzled . Recomendaría el hash de uno a uno de Bob Jenkins, que alcanza rápidamente la avalancha y, por lo tanto, se puede utilizar para una búsqueda eficiente de la tabla hash.

La respuesta depende de muchas cosas como:

• ¿Dónde piensa emplearlo?
• ¿Qué intentas hacer con el hachís?
• ¿Necesita una función hash critográficamente segura?

Sugiero que eche un vistazo a la familia de funciones hash Merkle-Damgard como SHA-1, etc.

¡No creo que podamos decir que una función hash sea "buena" sin conocer sus datos de antemano! y sin saber qué vas a hacer con él.

Hay mejores estructuras de datos que las tablas hash para tamaños de datos desconocidos (supongo que está haciendo el hash para una tabla hash aquí). Personalmente, usaría una tabla hash cuando sé que tengo un número "finito" de elementos que necesitan almacenarse en una cantidad limitada de memoria. Intentaría hacer un análisis estadístico rápido de mis datos, ver cómo se distribuyen, etc. antes de comenzar a pensar en mi función hash.

Para valores de hash aleatorios, algunos ingenieros dijeron que el número primo de proporción áurea (2654435761) es una mala elección, con los resultados de mis pruebas, descubrí que no es cierto; en su lugar, 2654435761 distribuye bastante bien los valores hash.

#define MCR_HashTableSize 2^10

unsigned int
Hash_UInt_GRPrimeNumber(unsigned int key)
{
  key = key*2654435761 & (MCR_HashTableSize - 1)
  return key;
}

El tamaño de la tabla hash debe ser una potencia de dos.

He escrito un programa de prueba para evaluar muchas funciones hash para enteros, los resultados muestran que GRPrimeNumber es una opción bastante buena.

Yo he tratado:

1. total_data_entry_number / total_bucket_number = 2, 3, 4; donde total_bucket_number = tamaño de la tabla hash;
2. mapear el dominio de valor hash en el dominio de índice de cubo; es decir, convierta el valor hash en un índice de depósito mediante la operación lógica y con (hash_table_size - 1), como se muestra en Hash_UInt_GRPrimeNumber ();
3. calcular el número de colisiones de cada cubo;
4. registrar el depósito que no se ha asignado, es decir, un depósito vacío;
5. averigüe el número máximo de colisiones de todos los cubos; es decir, la longitud de cadena más larga;

Con los resultados de mis pruebas, descubrí que Golden Ratio Prime Number siempre tiene menos cubos vacíos o cero cubos vacíos y la longitud de cadena de colisión más corta.

Se afirma que algunas funciones hash para números enteros son buenas, pero los resultados de las pruebas muestran que cuando total_data_entry / total_bucket_number = 3, la longitud de cadena más larga es mayor que 10 (número máximo de colisión> 10) y muchos depósitos no están mapeados (depósitos vacíos ), lo cual es muy malo, en comparación con el resultado de un cubo vacío cero y la longitud de cadena más larga 3 según el hash de números primos de proporción áurea.

Por cierto, con los resultados de mis pruebas, encontré que una versión de las funciones de hash shifting-xor es bastante buena (la comparte mikera).

unsigned int Hash_UInt_M3(unsigned int key)
{
  key ^= (key << 13);
  key ^= (key >> 17);    
  key ^= (key << 5); 
  return key;
}

He estado usando splitmix64(señalado en la respuesta de Thomas Mueller ) desde que encontré este hilo. Sin embargo, recientemente me topé con rrxmrrxmsx_0 de Pelle Evensen , que produjo una distribución estadística tremendamente mejor que el finalizador original de MurmurHash3 y sus sucesores ( splitmix64y otras mezclas). Aquí está el fragmento de código en C:

#include <stdint.h>

static inline uint64_t ror64(uint64_t v, int r) {
    return (v >> r) | (v << (64 - r));
}

uint64_t rrxmrrxmsx_0(uint64_t v) {
    v ^= ror64(v, 25) ^ ror64(v, 50);
    v *= 0xA24BAED4963EE407UL;
    v ^= ror64(v, 24) ^ ror64(v, 49);
    v *= 0x9FB21C651E98DF25UL;
    return v ^ v >> 28;
}

Pelle también proporciona un análisis en profundidad del mezclador de 64 bits utilizado en el paso final MurmurHash3y las variantes más recientes.