java - example - para que es el hashcode

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

Question

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

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

Referencias

Aquí hay una buena introducción a Hashcode y un artículo sobre cómo funcionan los hash que encontré (C # pero los conceptos son transferibles): Pautas y reglas de Eric Lippert para GetHashCode ()

Answer 1

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.

Answer 2

Aquí hay una citation 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

Answer 3

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

Answer 4

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 se extiende 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 principal vs. 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 usa un módulo primo vs. un módulo no primo.

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

Answer 5

Por lo general, ayuda a lograr una distribución más uniforme de los datos entre los depósitos de hash, especialmente para las claves de baja entropía.

Answer 6

Por lo que vale, Effective Java 2nd Edition renuncia manualmente a la cuestión de las matemáticas y simplemente dice que la razón para elegir 31 es:

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

Aquí está la cita completa, del Ítem ​​9: hashCode siempre el hashCode cuando anule el mismo valor :

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

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

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

Las VM modernas realizan este tipo de optimización de forma automática.

Si bien la receta de este elemento ofrece funciones hash razonablemente buenas, no proporciona funciones hash de última generación, ni las bibliotecas de la plataforma Java proporcionan funciones hash a partir del release 1.6. Escribir tales funciones hash es un tema de investigación, mejor dejado a los matemáticos y los informáticos teóricos.

Quizás un lanzamiento posterior de la plataforma proporcione funciones hash de última generación para sus clases y métodos de utilidad para permitir que los programadores promedio construyan dichas funciones hash. Mientras tanto, las técnicas descritas en este artículo 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á lugar a más colisiones hash . Dado que para el 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 distintos y positivos.

Preguntas relacionadas

• Java hashCode de un campo : la receta, más el ejemplo del uso de los desarrolladores de Apache Commons Lang
• ¿es incorrecto definir un hashcode de un objeto como suma, multiplicación, lo que sea, de todas las variables de clase hashcodes?
• ¿Guía absoluta para principiantes del cambio de bit?

Answer 7

Porque quiere el número por el que se está multiplicando y la cantidad de cubetas en las que se está insertando para tener factorizaciones primarias ortogonales.

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

31 es lo suficientemente grande como para que el número de cubos sea poco divisible (y de hecho, las implementaciones modernas de java HashMap mantienen el número de cubetas a una potencia de 2).

Answer 8

Primero, calcula el valor de hash modulo 2 ^ 32 (el tamaño de un int ), por lo que desea algo relativamente primo a 2 ^ 32 (primo relativo significa que no hay divisores comunes). Cualquier número impar serviría 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 primordial 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 asegura que el tamaño sea siempre una potencia de dos, por lo que un número impar sería suficiente aquí también. También hay un poco de masaje adicional de las teclas hash para limitar aún más las colisiones.

El efecto negativo si la tabla hash y el multiplicador tenían un factor n común podría ser que en ciertas circunstancias solo se usarían 1 / n entradas en la tabla hash.