¿Por qué usar un número primo en hashCode?

Me preguntaba por qué los primos se usan en el hashCode()método de una clase . Por ejemplo, cuando utilizo Eclipse para generar mi hashCode()método, siempre se 31usa el número primo :

public int hashCode() {
     final int prime = 31;
     //...
}

Referencias

Aquí hay un buen manual sobre Hashcode y un artículo sobre cómo funciona el hashing que encontré (C # pero los conceptos son transferibles): Pautas y reglas de Eric Lippert para GetHashCode ()

Porque desea que el número por el que está multiplicando y el número de cubos en los que está insertando tengan factorizaciones primas ortogonales.

Supongamos que hay 8 cubos para insertar. Si el número que está utilizando para multiplicar es un múltiplo de 8, entonces la cubeta insertada solo estará determinada por la entrada menos significativa (la que no está multiplicada en absoluto). Entradas similares colisionarán. No es bueno para una función hash.

31 es un número primo lo suficientemente grande como para que sea poco probable que el número de depósitos sea divisible (y de hecho, las implementaciones modernas de Java HashMap mantienen el número de depósitos a una potencia de 2).

Los números primos se eligen para distribuir mejor los datos entre los cubos hash. Si la distribución de entradas es aleatoria y se distribuye uniformemente, entonces la elección del código / módulo hash no importa. Solo tiene un impacto cuando hay un cierto patrón en las entradas.

Este suele ser el caso cuando se trata de ubicaciones de memoria. Por ejemplo, todos los enteros de 32 bits están alineados con direcciones divisibles por 4. Consulte la tabla a continuación para visualizar los efectos del uso de un módulo primo frente a un módulo no primo:

Input       Modulo 8    Modulo 7
0           0           0
4           4           4
8           0           1
12          4           5
16          0           2
20          4           6
24          0           3
28          4           0

Observe la distribución casi perfecta cuando se utiliza un módulo primo frente a un módulo no primo.

Sin embargo, aunque el ejemplo anterior está en gran parte ideado, el principio general es que cuando se trata de un patrón de entradas , el uso de un módulo de números primos producirá la mejor distribución.

Para lo que vale, la segunda edición efectiva de Java evita el problema de las matemáticas y solo dice que la razón para elegir 31 es:

• Porque es un primo extraño, y es "tradicional" usar primos
• También es uno menos que una potencia de dos, lo que permite la optimización bit a bit

Aquí está la cita completa, del Artículo 9: Anular siempre hashCodecuando anulaequals :

Se eligió el valor 31 porque es un primo impar. Si fuera uniforme y la multiplicación se desbordara, la información se perdería, ya que la multiplicación por 2 es equivalente al desplazamiento. La ventaja de usar un prime es menos clara, pero es tradicional.

Una buena propiedad de 31 es que la multiplicación puede ser reemplazada por un turno ( §15.19 ) y una resta para un mejor rendimiento:

 31 * i == (i << 5) - i

Las máquinas virtuales modernas hacen este tipo de optimización automáticamente.

---

Si bien la receta en este artículo produce funciones hash razonablemente buenas, no ofrece funciones hash de última generación, ni las bibliotecas de la plataforma Java proporcionan tales funciones hash a partir de la versión 1.6. Escribir tales funciones hash es un tema de investigación, mejor dejarlo a matemáticos y científicos teóricos de la computación.

Quizás una versión posterior de la plataforma proporcionará funciones hash de última generación para sus clases y métodos de utilidad para permitir a los programadores promedio construir tales funciones hash. Mientras tanto, las técnicas descritas en este ítem deberían ser adecuadas para la mayoría de las aplicaciones.

De manera bastante simplista, se puede decir que usar un multiplicador con numerosos divisores dará como resultado más colisiones de hash . Dado que para un hashing efectivo queremos minimizar el número de colisiones, tratamos de usar un multiplicador que tenga menos divisores. Un número primo por definición tiene exactamente dos divisores positivos distintos.

Preguntas relacionadas

• Java hashCode de un campo : la receta, más el ejemplo del uso de los constructores de Apache Commons Lang
• ¿Es incorrecto definir un código hash de un objeto como la suma, multiplicación, lo que sea, de todos los códigos hash de las variables de clase?
• ¿Guía absoluta para principiantes sobre el desplazamiento de bits?

Escuché que se eligió 31 para que el compilador pueda optimizar la multiplicación para desplazar a la izquierda 5 bits y luego restar el valor.

Aquí hay una cita un poco más cerca de la fuente.

Se reduce a:

• 31 es primo, lo que reduce las colisiones
• 31 produce una buena distribución, con
• una compensación razonable en velocidad

Primero calcula el valor hash módulo 2 ^ 32 (el tamaño de un int), por lo que desea algo relativamente primo a 2 ^ 32 (relativamente primo significa que no hay divisores comunes). Cualquier número impar sería suficiente para eso.

Luego, para una tabla hash dada, el índice generalmente se calcula a partir del módulo de valor hash del tamaño de la tabla hash, por lo que desea algo que sea relativamente primo para el tamaño de la tabla hash. A menudo, los tamaños de las tablas hash se eligen como números primos por ese motivo. En el caso de Java, la implementación de Sun se asegura de que el tamaño sea siempre una potencia de dos, por lo que aquí también sería suficiente un número impar. También hay un poco de masaje adicional de las claves hash para limitar aún más las colisiones.

El efecto negativo si la tabla hash y el multiplicador tuvieran un factor común npodría ser que, en determinadas circunstancias, solo se utilizarían 1 / n entradas en la tabla hash.

La razón por la cual se usan números primos es para minimizar las colisiones cuando los datos exhiben algunos patrones particulares.

Lo primero es lo primero: si los datos son aleatorios, entonces no hay necesidad de un número primo, puede hacer una operación de modificación contra cualquier número y tendrá el mismo número de colisiones para cada valor posible del módulo.

Pero cuando los datos no son aleatorios, suceden cosas extrañas. Por ejemplo, considere los datos numéricos que siempre son múltiplos de 10.

Si usamos mod 4 encontramos:

10 mod 4 = 2

20 mod 4 = 0

30 mod 4 = 2

40 mod 4 = 0

50 mod 4 = 2

Entonces, de los 3 valores posibles del módulo (0,1,2,3) solo 0 y 2 tendrán colisiones, eso es malo.

Si usamos un número primo como 7:

10 mod 7 = 3

20 mod 7 = 6

30 mod 7 = 2

40 mod 7 = 4

50 mod 7 = 1

etc.

También notamos que 5 no es una buena opción, pero 5 es primo, la razón es que todas nuestras claves son múltiplos de 5. Esto significa que tenemos que elegir un número primo que no divida nuestras claves, elegir un número primo grande es generalmente suficiente.

Por lo tanto, al ser repetitivo, la razón por la que se usan los números primos es para neutralizar el efecto de los patrones en las teclas en la distribución de colisiones de una función hash.

31 también es específico de Java HashMap, que utiliza un int como tipo de datos hash. Por lo tanto, la capacidad máxima de 2 ^ 32. No tiene sentido usar primos Fermat o Mersenne más grandes.

En general, ayuda a lograr una distribución más uniforme de sus datos entre los cubos hash, especialmente para las claves de baja entropía.