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

StackOverflow https://stackoverflow.com/questions/299304

  •  08-07-2019
  •  | 
  •  

Pregunta

Según la documentación de Java, el 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 aritmética, donde s[i] es el     i el carácter de la cadena, n es la longitud de    la cadena, y ^ 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, 37 o incluso 97?

¿Fue útil?

Solución

Según Java eficaz (un libro que no puede ser) de Joshua Bloch lo suficientemente recomendado, y que compré gracias a las continuas menciones en stackoverflow):

  

El valor 31 fue elegido 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 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)

Otros consejos

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 de polinomios hash " 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 hay mucha diferencia, siempre que 32 vaya del 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 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 rellenan, para mezclarlos con el siguiente dato que va al 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 desempeño de diferentes funciones hash en relación con el resultado & "; Tamaño de cadena promedio &"; en una tabla hash P(31) fue una de las funciones comunes durante ese tiempo que encontró en el libro de K & amp; 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(33) ya que parecía funcionar lo suficientemente bien. Aunque <=> 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:

  

Del resto   cuatro, probablemente seleccionaría P (31), ya que es el más barato para calcular en un RISC   máquina (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 muchas de las respuestas aquí parecen implicar. Pero todos somos buenos para encontrar razones racionales después de 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 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, ya que conduce a código más denso : las dos instrucciones LEA solo toman 6 bytes frente a 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 Planchar el sesgo .

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

De JDK-4045622 , donde Joshua Bloch describe los motivos por qué se eligió esa (nueva) String.hashCode() implementación particular

  

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

     

1) Todas las palabras y frases con entradas en Merriam-Webster's          Segundo diccionario internacional íntegro (311,141 cadenas, longitud promedio 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 varios          horas anoche (28,372 cadenas, longitud promedio 49 caracteres).

     

La métrica de rendimiento que se muestra en la tabla es & "; tamaño de cadena promedio &";   sobre todos los elementos en la tabla hash (es decir, el valor esperado de   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 Weinberger   La función ofrece un rendimiento excelente, casi indistinguible. yo   conjetura fuertemente que este rendimiento es esencialmente el   " ideal teórico " ;, que es lo que obtendría si utilizara un verdadero aleatorio   generador de números 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 ninguno de los   funciones mucho más simples. Parece que cualquiera de las seis funciones restantes   excelentes opciones, pero tenemos que elegir una. Supongo que descartaría   La variante de Vo y la función de Weinberger debido a su agregado   complejidad, 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 poderes de dos). P (33) es igualmente barato para   calcular, pero su rendimiento es marginalmente peor, y 33 es   compuesto, lo que me pone un poco nervioso.

     

Josh

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.

Bloch no entra en esto, pero la lógica que siempre he escuchado / creído es que esto es á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 cubos en su tabla hash (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 debes 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/11/docs/api/java.base/java/lang/String.html#hashCode ()

El propósito de la cadena hash es

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

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

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

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top