resolucion - hashing programacion

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

Question

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

Answer 1

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

Answer 2

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

Answer 3

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 él. 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.

Answer 4

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, suponiendo que int es de 32 bits (para Java, reemplaza >> por >>> y elimina 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 especial de prueba de múltiples subprocesos 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 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 buenos (no del todo) como cuando se usa AES .

Puede revertir el proceso (obtener el valor de entrada del hash) si reemplaza el 0x45d9f3b con 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 los números de 64 bits, sugiero usar lo siguiente, incluso aunque no sea el más rápido. Este está basado en splitmix64 , que parece estar basado en el artículo de 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 L a 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;
}

Answer 5

Hay una buena descripción de algunos algoritmos de hash en Eternally Confuzzled . 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.

Answer 6

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 familia Merkle-Damgard de funciones hash como SHA-1, etc.

Answer 7

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.

Answer 8

• 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