Pregunta ¿Por qué Java's hashCode () en String usa 31 como un multiplicador?


En Java, el código hash para String objeto se calcula como

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

utilizando int aritmética, donde s[i] es el ith carácter de la cuerda, n es la longitud de la cadena, y ^ indica exponenciación.

¿Por qué se usa 31 como un multiplicador?

Entiendo que el multiplicador debe ser un número primo relativamente grande. Entonces, ¿por qué no 29, o 37, o incluso 97?


396
2017-11-18 16:39


origen


Respuestas:


De acuerdo con Joshua Bloch Java efectivo (un libro que no se puede recomendar lo suficiente, y que compré gracias a las menciones continuas en stackoverflow):

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 la multiplicación por 2 equivale a un cambio. La ventaja de usar un primo es menos clara, pero es tradicional. Una buena propiedad de 31 es que la multiplicación se puede reemplazar por un cambio 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.

(del Capítulo 3, Artículo 9: Anule siempre el código de hash cuando anula el igual, página 48)


339
2017-11-18 18:53



Como Goodrich y Tamassia señale, si toma más de 50,000 palabras en inglés (formadas como la unión de las listas de palabras provistas en dos variantes de Unix), usar las constantes 31, 33, 37, 39 y 41 producirá menos de 7 colisiones en cada caso. Sabiendo esto, no debería sorprender que muchas implementaciones de Java elijan una de estas constantes.

Casualmente, estaba leyendo la sección "códigos hash polinomiales" cuando vi esta pregunta.

EDITAR: aquí hay un enlace al libro en PDF de ~ 10mb al que me refiero arriba. Consulte la sección 10.2 Tablas Hash (página 413) de Estructuras de datos y algoritmos en Java 


70
2017-11-18 20:56



En (la mayoría) de los procesadores antiguos, multiplicar por 31 puede ser relativamente barato. En un ARM, por ejemplo, es solo una instrucción:

RSB       r1, r0, r0, ASL #5    ; r1 := - r0 + (r0<<5)

La mayoría de los otros procesadores requerirían un turno y una instrucción de resta por separado. Sin embargo, si tu multiplicador es lento, esto sigue siendo una ganancia. Los procesadores modernos tienden a tener multiplicadores rápidos, por lo que no hace mucha diferencia, siempre y cuando 32 continúen en el lado correcto.

No es un gran algoritmo hash, pero es lo suficientemente bueno y mejor que el código 1.0 (¡y mucho mejor que la especificación 1.0!).


54
2017-11-18 17:01



Al multiplicarse, los bits se desplazan hacia la izquierda. Esto utiliza más espacio disponible de códigos hash, reduciendo las colisiones.

Al no usar una potencia de dos, los bits de más bajo orden y más a la derecha también se rellenan, para mezclarse con la siguiente pieza de datos que entra en el hash.

La expresion n * 31 es equivalente a (n << 5) - n.


27
2018-05-19 18:10



Puede leer el razonamiento original de Bloch en "Comentarios" en http://bugs.java.com/bugdatabase/view_bug.do?bug_id=4045622. Investigó el rendimiento de diferentes funciones hash en lo que respecta al "tamaño de cadena promedio" resultante en una tabla hash. P(31)fue una de las funciones comunes durante ese tiempo que encontró en el libro de K & R (pero incluso Kernighan y Ritchie no podían recordar de dónde venía). Al final, básicamente tuvo que elegir uno, y entonces tomó P(31) ya que parecía funcionar lo suficientemente bien. Aunque P(33) no fue realmente peor y la multiplicación por 33 es igualmente rápida de calcular (solo un cambio por 5 y una adición), optó por 31 ya que 33 no es un primo:

Del resto   cuatro, probablemente seleccionaría P (31), ya que es el más barato de calcular en un RISC   máquina (porque 31 es la diferencia de dos potencias de dos). P (33) es   similarmente barato de calcular, pero su desempeño es marginalmente peor, y   33 es compuesto, lo que me pone un poco nervioso.

Entonces el razonamiento no fue tan racional como parecen implicar muchas de las respuestas aquí. Pero todos somos buenos para encontrar razones racionales después de las decisiones viscerales (e incluso Bloch podría ser propenso a eso).


22
2018-02-10 00:46



¡De hecho, 37 funcionaría bastante bien! z: = 37 * x se puede calcular como y := x + 8 * x; z := x + 4 * y. Ambos pasos corresponden a una instrucción LEA x86, por lo que es extremadamente rápido.

De hecho, la multiplicación con el primo aún más grande 73 podría hacerse a la misma velocidad configurando y := x + 8 * x; z := x + 8 * y.

Usar 73 o 37 (en lugar de 31) podría ser mejor, porque conduce a código más denso: Las dos instrucciones LEA solo toman 6 bytes frente a los 7 bytes para move + shift + resta para la multiplicación por 31. Una posible advertencia es que las instrucciones LEA de 3 argumentos utilizadas aquí se volvieron más lentas en la arquitectura Sandy de Intel, con un aumento latencia de 3 ciclos

Además, 73 es el número favorito de Sheldon Cooper.


21
2017-07-27 19:37



Neil Coffey explica ¿por qué 31 se utiliza en virtud de Planificando el sesgo.

Básicamente, al usar 31 se obtiene una distribución de probabilidad de bit de bit más uniforme para la función hash.


18
2017-12-07 15:27