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


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


74
2018-03-19 20:54


origen


Respuestas:


El 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^32 en el ejemplo) y no tiene factores en común con esto. De esta forma, la función hash cubre todo tu espacio hash uniformemente.

Editar: La mayor desventaja de esta función hash es que preserva la divisibilidad, por lo que si los enteros son divisibles por 2 o por 4 (lo que no es poco común), sus valores hash también lo serán. Este es un problema en las tablas hash: puede terminar con solo 1/2 o 1/4 de las cubetas que se usan.


31
2018-03-20 09:59



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 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 entera incorporada. Código C, asumiendo int es de 32 bits (para Java, reemplace >> con >>> y eliminar 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ó usando un programa especial de prueba de múltiples hilos que se ejecutó durante muchas horas, que calcula el efecto de avalancha (el número de bits de salida que cambia si se cambia un solo bit de entrada, debe ser casi 16 en promedio), independencia de los cambios del bit de salida (los bits de salida no deben depender el uno del otro) , y la probabilidad de un cambio en cada bit de salida si se cambia cualquier bit de entrada. Los valores calculados son mejores que el finalizador de 32 bits utilizado por MurmurHash, y casi tan bueno (no del todo) como cuando se usa AES. Una ligera ventaja es que la misma constante se usa dos veces (la última vez que lo probé, la hizo un poco más rápida, pero no estoy seguro si sigue siendo así).

Puede revertir el proceso (obtener el valor de entrada del hash) si reemplaza el 0x45d9f3b con 0x119de1f3 (el multiplicación inversa)

unsigned int unhash(unsigned int x) {
    x = ((x >> 16) ^ x) * 0x119de1f3;
    x = ((x >> 16) ^ x) * 0x119de1f3;
    x = (x >> 16) ^ x;
    return x;
}

Para los números de 64 bits, sugiero usar lo siguiente, incluso aunque no sea el más rápido. Este se basa en splitmix64, que parece estar basado en el artículo del blog Mejor mezcla de bits (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, agregar L a la constante, reemplazar >> con >>> y eliminar 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 Hash Function Prospector proyecto, donde se enumeran otras constantes (posiblemente mejores).


98
2017-10-21 08:01



Depende de cómo se distribuyen tus datos. Para un contador simple, la función más simple

f(i) = i

será bueno (sospecho que es óptimo, pero no puedo probarlo).


24
2018-03-19 20:57



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


7
2018-03-19 21:02



  • 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 entero

5
2018-06-14 10:03



Hay una buena descripción general de algunos algoritmos hash en Eternamente confuso. Recomiendo 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 eficaz de la tabla hash.


3
2018-03-19 21:31



La respuesta depende de muchas cosas como:

  • ¿Dónde piensas emplearlo?
  • ¿Qué estás tratando de hacer con el hash?
  • ¿Necesita una función hash criográficamente segura?

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


2
2018-03-19 21:02



¡No creo que podamos decir que una función hash es "buena" sin conocer sus datos con anticipación! y sin saber lo que vas a hacer con eso.

Hay mejores estructuras de datos que las tablas hash para tamaños de datos desconocidos (supongo que está haciendo hash para una tabla hash aquí). Yo personalmente usaría una tabla hash cuando sé que tengo una cantidad "finita" 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 distribuye, etc., antes de comenzar a pensar en mi función hash.


1
2017-10-25 20:20