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

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

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

usando int arithmetic, donde s[i] es el carácter i th de la cadena, 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?

De acuerdo con Java efectivo de Joshua Bloch (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)

Como señalan Goodrich y Tamassia , 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

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

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 expresión n * 31 es equivalente a (n << 5) - n .

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, por lo que 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:

De los cuatro restantes, probablemente seleccionaría P (31), ya que es el más barato de calcular en una máquina RISC (porque 31 es la diferencia de dos potencias de dos). P (33) es igualmente barato de calcular, pero su rendimiento 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).

¡De hecho, 37 funcionaría bastante bien! z: = 37 * x se puede calcular como y := x + 8 * x; z := x + 4 * y 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 73 aún mayor podría hacerse a la misma velocidad estableciendo y := x + 8 * x; z := x + 8 * y y := x + 8 * x; z := x + 8 * y .

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

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

Neil Coffey explica por qué se usa 31 para Planchar 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.

No estoy seguro, pero supongo que probaron una muestra de números primos y encontraron que 31 dio la mejor distribución sobre alguna muestra de cadenas posibles.

Bloch no entra en esto, pero el razonamiento que siempre he escuchado / creído es que esto es álgebra básica. Los valores hash se reducen a las operaciones de multiplicación y módulo, lo que significa que nunca querrás usar números con factores comunes si puedes evitarlo. En otras palabras, los números primos relativamente proporcionan una distribución uniforme de respuestas.

Los números que componen usar un hash son típicamente:

  • módulo del tipo de datos en el que lo pones (2 ^ 32 o 2 ^ 64)
  • Módulo del recuento de cubo en tu hashtable (varía. En java solía ser primo, ahora 2 ^ n)
  • multiplica o cambia por un número mágico en tu función de mezcla
  • El valor de entrada

Realmente solo puedes controlar un par de estos valores, por lo que es necesario un poco de cuidado adicional.

De JDK-4045622 , donde Joshua Bloch describe los motivos por los que se eligió String.hashCode() implementación (nueva) de String.hashCode()

La siguiente tabla resume el rendimiento de las diversas funciones hash descritas anteriormente, para tres conjuntos de datos:

1) Todas las palabras y frases con entradas en Merriam-Webster’s 2nd Int’l Unabridged Dictionary (311,141 cadenas, promedio de 10 caracteres).

2) Todas las cadenas en / bin / , / usr / bin / , / usr / lib / , / usr / ucb / y / usr / openwin / bin / * (66,304 cadenas, longitud promedio 21 caracteres).

3) Una lista de URL recostackdas por un rastreador web que se ejecutó durante varias horas anoche (28,372 cadenas, longitud promedio 49 caracteres).

La métrica de rendimiento que se muestra en la tabla es el “tamaño de cadena promedio” sobre todos los elementos en la tabla hash (es decir, el valor esperado del número de claves se compara para buscar un elemento).

  Webster's Code Strings URLs --------- ------------ ---- Current Java Fn. 1.2509 1.2738 13.2560 P(37) [Java] 1.2508 1.2481 1.2454 P(65599) [Aho et al] 1.2490 1.2510 1.2450 P(31) [K+R] 1.2500 1.2488 1.2425 P(33) [Torek] 1.2500 1.2500 1.2453 Vo's Fn 1.2487 1.2471 1.2462 WAIS Fn 1.2497 1.2519 1.2452 Weinberger's Fn(MatPak) 6.5169 7.2142 30.6864 Weinberger's Fn(24) 1.3222 1.2791 1.9732 Weinberger's Fn(28) 1.2530 1.2506 1.2439 

Al observar esta tabla, está claro que todas las funciones, excepto la función Java actual y las dos versiones rotas de la función de Weinberger, ofrecen un rendimiento excelente, casi indistinguible. Fuertemente conjeturo que este rendimiento es esencialmente el “ideal teórico”, que es lo que obtendrías si usaras un verdadero generador de números aleatorios en lugar de una función hash.

Yo descartaría la función WAIS ya que su especificación contiene páginas de números aleatorios, y su rendimiento no es mejor que cualquiera de las funciones mucho más simples. Cualquiera de las seis funciones restantes parece una elección excelente, pero debemos elegir una. Supongo que descartaría la variante de Vo y la función de Weinberger debido a su complejidad añadida, aunque de menor importancia. De los cuatro restantes, probablemente seleccionaría P (31), ya que es el más barato de calcular en una máquina RISC (porque 31 es la diferencia de dos potencias de dos). P (33) es igualmente barato de calcular, pero su rendimiento es marginalmente peor, y 33 es compuesto, lo que me pone un poco nervioso.

Josh