¿Por qué utilizar un número primo en hashCode?
Me preguntaba por qué se utilizan números primos en el hashCode()método de una clase. Por ejemplo, cuando uso Eclipse para generar mi hashCode()método, siempre se 31utiliza el número primo:
public int hashCode() {
final int prime = 31;
//...
}
Referencias:
Aquí hay una buena introducción a 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()
Los números primos se eligen para distribuir mejor los datos entre los depósitos de hash. Si la distribución de las entradas es aleatoria y uniforme, entonces la elección del código/módulo hash no importa. Sólo tiene 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 números enteros de 32 bits están alineados con direcciones divisibles por 4. Consulte la siguiente tabla 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 es en gran medida artificial, 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.
Porque quieres que el número por el que estás multiplicando y el número de cubos en los que estás insertando tengan factorizaciones primas ortogonales.
Supongamos que hay 8 cubos para insertar. Si el número que estás usando para multiplicar es un múltiplo de 8, entonces el cubo insertado solo estará determinado por la entrada menos significativa (la que no se multiplica en absoluto). Entradas similares chocarán. No es bueno para una función hash.
31 es un número primo lo suficientemente grande como para que es poco probable que el número de depósitos sea divisible por él (y, de hecho, las implementaciones modernas de Java HashMap mantienen el número de depósitos en una potencia de 2).
Por si sirve de algo, Effective Java 2nd Edition ignora manualmente el tema de las matemáticas y simplemente dice que la razón para elegir 31 es:
- Porque es un número primo impar y es "tradicional" usar números 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 punto 9: Anular siempre hashCodecuando anulesequals :
Se eligió el valor 31 porque es un número primo impar. Si fuera par y la multiplicación se desbordara, se perdería información, ya que multiplicar por 2 equivale a desplazar. La ventaja de utilizar una prima es menos clara, pero es tradicional.
Una buena propiedad de 31 es que la multiplicación se puede reemplazar por un desplazamiento ( §15.19 ) y una resta para un mejor rendimiento:
31 * i == (i << 5) - iLas máquinas virtuales modernas realizan este tipo de optimización automáticamente.
Si bien la receta en este artículo produce funciones hash razonablemente buenas, no proporciona funciones hash de última generación, ni las bibliotecas de la plataforma Java proporcionan dichas funciones hash a partir de la versión 1.6. Escribir tales funciones hash es un tema de investigación que es mejor dejar en manos de matemáticos e informáticos teóricos.
Quizás una versión posterior de la plataforma proporcione funciones hash de última generación para sus clases y métodos de utilidad para permitir a los programadores promedio construir dichas funciones hash. Mientras tanto, las técnicas descritas en este punto deberían ser adecuadas para la mayoría de las aplicaciones.
De manera bastante simplista, se puede decir que el uso de un multiplicador con numerosos divisores dará como resultado más colisiones de hash . Dado que para un hash eficaz queremos minimizar el número de colisiones, intentamos utilizar un multiplicador que tenga menos divisores. Un número primo, por definición, tiene exactamente dos divisores positivos distintos.
Preguntas relacionadas
- Código hash de Java de un campo : la receta, más un 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 variables de clase?
- ¿Guía absoluta para principiantes sobre el cambio de bits?
Escuché que se eligió 31 para que el compilador pueda optimizar la multiplicación para desplazar 5 bits a la izquierda y luego restar el valor.
Primero calcula el valor hash módulo 2^32 (el tamaño de an int), por lo que desea algo relativamente primo con respecto a 2^32 (relativamente primo significa que no hay divisores comunes). Cualquier número impar serviría para eso.
Luego, para una tabla hash determinada, el índice generalmente se calcula a partir del módulo del 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 garantiza 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 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.
