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

174

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

Ian Dallas
fuente
Esto es más o menos un duplicado de la pregunta stackoverflow.com/questions/1145217/… .
Hans-Peter Störr
1
Verifique mi respuesta en stackoverflow.com/questions/1145217/… Está relacionado con las propiedades de los polinomios sobre un campo (¡no un anillo!), Por lo tanto, los números primos.
TT_

Respuestas:

104

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

ILMTitan
fuente
9
Entonces, una función hash que se multiplica por 31 funcionará de manera no óptima. Sin embargo, consideraría que una implementación de tabla hash de este tipo está mal diseñada, dado lo común que es 31 como multiplicador.
ILMTitan
11
Entonces, ¿31 se elige en base al supuesto de que los implementadores de tablas hash saben que 31 se usa comúnmente en códigos hash?
Steve Kuo
3
31 se elige en base a la idea de que la mayoría de las implementaciones tienen factorizaciones de números primos relativamente pequeños. 2s, 3s y 5s generalmente. Puede comenzar a las 10 y crecer 3 veces cuando se llena demasiado. El tamaño rara vez es completamente al azar. E incluso si lo fuera, 30/31 no son malas probabilidades de tener algoritmos hash bien sincronizados. También puede ser fácil de calcular como han dicho otros.
ILMTitan
8
En otras palabras ... necesitamos saber algo sobre el conjunto de valores de entrada y las regularidades del conjunto, para poder escribir una función diseñada para despojarlos de esas regularidades, para que los valores en el conjunto no choquen en el mismo cubos de hash. Multiplicar / dividir / modular por un número primo logra ese efecto, porque si tienes un LOOP con elementos X y saltas espacios Y en el bucle, nunca volverás al mismo lugar hasta que X se convierta en un factor de Y Dado que X es a menudo un número par o una potencia de 2, entonces necesitas que Y sea primo para que X + X + X ... no sea un factor de Y, ¡entonces 31 yay! : /
Triynko
3
@FrankQ. Es la naturaleza de la aritmética modular. (x*8 + y) % 8 = (x*8) % 8 + y % 8 = 0 + y % 8 = y % 8
ILMTitan
136

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.

Advait
fuente
17
¿No estamos hablando del multiplicador utilizado para generar el código hash, no del módulo utilizado para clasificar esos códigos hash en cubos?
ILMTitan
3
Mismo principio En términos de E / S, el hash se alimenta a la operación de módulo de la tabla hash. Creo que el punto fue que si multiplicas por primos, obtendrás más entradas distribuidas aleatoriamente hasta el punto en que el módulo ni siquiera importará. Dado que la función hash toma el relevo de distribuir mejor las entradas, haciéndolas menos regulares, es menos probable que choquen, independientemente del módulo utilizado para colocarlas en un depósito.
Triynko
9
Este tipo de respuesta es muy útil porque es como enseñarle a alguien a pescar, en lugar de atrapar una para ellos. Ayuda a las personas a ver y comprender el principio subyacente detrás del uso de primos para hashes ... que consiste en distribuir las entradas de forma irregular para que caigan uniformemente en cubos una vez modulados :).
Triynko
29

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

poligenelubricantes
fuente
44
Eh, pero hay muchos adecuados números primos que son o bien 2 ^ n + 1 (los llamados números primos de Fermat ), es decir 3, 5, 17, 257, 65537o 2 ^ n - 1 ( números primos de Mersenne ): 3, 7, 31, 127, 8191, 131071, 524287, 2147483647. Sin embargo 31(y no, digamos 127) está optado.
Dmitry Bychenko
44
"porque es un prime prime" ... solo hay un prime prime: P
Martin Schneider
No me gusta la redacción "es menos clara, pero es tradicional" en "Java efectivo". Si no quiere entrar en detalles matemáticos, debería escribir algo como "tiene razones matemáticas [similares]". La forma en que escribe parece que solo tiene antecedentes históricos :(
Qw3ry
5

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.

Steve Kuo
fuente
¿Cómo podría el compilador optimizar de esa manera? x * 31 == x * 32-1 no es cierto para todos los x después de todo. Lo que querías decir era desplazamiento a la izquierda 5 (igual multiplicar por 32) y luego restar el valor original (x en mi ejemplo). Si bien esto puede ser más rápido que una multiplicación (que probaly no es para los procesadores CPU moderna por cierto), hay factores más importantes a considerar al elegir una multiplicación por un haschcode (distribución equitativa de los valores de entrada a cubos viene a la mente)
Grizzly
Haga un poco de búsqueda, esta es una opinión bastante común.
Steve Kuo
44
La opinión común es irrelevante.
fractor
1
@ Grizzly, es más rápido que la multiplicación. IMul ​​tiene una latencia mínima de 3 ciclos en cualquier CPU moderna. (consulte los manuales de agner fog) mov reg1, reg2-shl reg1,5-sub reg1,reg2puede ejecutarse en 2 ciclos. (el mov es solo un cambio de nombre y toma 0 ciclos).
Johan
3

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
Juan
fuente
3

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.

starblue
fuente
2

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.

Amar Magar
fuente
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.

DED
fuente
0

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.


fuente