¿Por qué el código hash () de Java en String usa 31 como multiplicador?

Según la documentación de Java, el código hash para un Stringobjeto se calcula como:

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

usando intaritmética, donde s[i]es el i- ésimo carácter de la cadena, nes la longitud de la cadena e ^indica exponenciación

¿Por qué se usa 31 como multiplicador?

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

Según el Java efectivo de Joshua Bloch (un libro que no se puede recomendar lo suficiente, y que compré gracias a las continuas menciones en stackoverflow):

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 bonita propiedad de 31 es que la multiplicación puede ser reemplazado por un cambio 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.

(del Capítulo 3, Elemento 9: Anular siempre el código hash cuando anula iguales, página 48)

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

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

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

En (en su mayoría) 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 una instrucción de desplazamiento y resta por separado. Sin embargo, si su multiplicador es lento, esto sigue siendo una victoria. Los procesadores modernos tienden a tener multiplicadores rápidos, por lo que no hace mucha diferencia, siempre que 32 vaya por 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 multiplicar, los bits se desplazan hacia la izquierda. Esto utiliza más del espacio disponible de códigos hash, lo que reduce las colisiones.

Al no utilizar una potencia de dos, los bits de orden inferior y más a la derecha también se completan, para mezclarlos con la siguiente pieza de datos que va al hash.

La expresión n * 31es 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 desempeño de diferentes funciones hash con respecto 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 provenía). Al final, básicamente tuvo que elegir uno y lo 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 suma), optó por 31 ya que 33 no es primo:

De los cuatro restantes, probablemente seleccionaría P (31), ya que es el más barato para 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.

Por lo tanto, 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 intestinales (e incluso Bloch podría ser propenso a eso).

En realidad, ¡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 esto es extremadamente rápido.

De hecho, la multiplicación con el primo aún más grande 73 se puede hacer a la misma velocidad mediante el ajuste y := x + 8 * x; z := x + 8 * y.

Usar 73 o 37 (en lugar de 31) podría ser mejor, ya que conduce a un código más denso : las dos instrucciones LEA solo toman 6 bytes versus los 7 bytes para mover + shift + restar para la multiplicación por 31. Una posible advertencia es que Las instrucciones LEA de 3 argumentos utilizadas aquí se hicieron más lentas en la arquitectura 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é 31 se usa en Eliminar el sesgo .

Básicamente, el uso de 31 le brinda una distribución de probabilidad de bits de ajuste más uniforme para la función hash.

De JDK-4045622 , donde Joshua Bloch describe las razones por las que String.hashCode()se eligió esa implementación (nueva) en particular

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 el 2.º diccionario internacional íntegro de Merriam-Webster (311.141 cadenas, longitud media 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 recopiladas por un rastreador web que se ejecutó durante varias horas anoche (28.372 cadenas, longitud promedio de 49 caracteres).

La métrica de rendimiento que se muestra en la tabla es el "tamaño promedio de la cadena" 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

Mirando 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. Supongo que este rendimiento es esencialmente el "ideal teórico", que es lo que obtendría si utilizara un verdadero generador de números aleatorios en lugar de una función hash.

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 parecen excelentes opciones, pero tenemos que elegir una. Supongo que descartaría la variante de Vo y la función de Weinberger debido a su complejidad añadida, aunque menor. De los cuatro restantes, probablemente seleccionaría P (31), ya que es el más barato para 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

Bloch no entra en esto, pero la lógica que siempre he escuchado / creído es que se trata de álgebra básica. Los hashes se reducen a 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 relativamente primos proporcionan una distribución uniforme de las respuestas.

Los números que se componen con un hash suelen ser:

• módulo del tipo de datos en el que lo pones (2 ^ 32 o 2 ^ 64)
• módulo del conteo de cubetas en su tabla hash (varía. En Java solía ser primo, ahora 2 ^ n)
• multiplique o cambie por un número mágico en su función de mezcla
• El valor de entrada

Realmente solo puede controlar un par de estos valores, por lo que se debe tener un poco de cuidado adicional.

En la última versión de JDK, 31 todavía se usa. https://docs.oracle.com/en/java/javase/12/docs/api/java.base/java/lang/String.html#hashCode ()

El propósito de la cadena hash es

• único (deje ver el operador ^en el documento de cálculo de código hash, ayuda único)
• costo barato para calcular

31 es el valor máximo puede poner en el registro de 8 bits (= 1 byte), es el número primo más grande puede poner en el registro de 1 byte, es el número impar.

Multiplicar 31 es << 5 luego restarlo, por lo tanto, necesita recursos baratos.

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

Esto se debe a que 31 tiene una buena propiedad: su multiplicación se puede reemplazar por un desplazamiento a nivel de bits que es más rápido que la multiplicación estándar:

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