¿Por qué el hashCode() de Java en String usa 31 como multiplicador?
Según la documentación de Java, el código hash de un Stringobjeto se calcula como:
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]usando
intaritmética, dondes[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, 37 o incluso 97?
Según Effective Java, segunda edición de Joshua Bloch (un libro que no se puede recomendar lo suficiente y que compré gracias a las continuas menciones en Stack Overflow):
Se eligió el valor 31 porque es un primo impar. Si fuera par y la multiplicación se desbordara, se perdería información, ya que multiplicar por 2 equivale a desplazarse. La ventaja de utilizar una prima es menos clara, pero es tradicional. Una buena propiedad de 31 es que la multiplicación se puede reemplazar por un desplazamiento y una resta para un mejor rendimiento:
31 * i == (i << 5) - i. Las máquinas virtuales modernas realizan este tipo de optimización automáticamente.
(del Capítulo 3, Elemento 9: Anular siempre hashCodecuando anule equals, página 48)
Goodrich y Tamassia calcularon a partir de 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) que el uso de las constantes 31, 33, 37, 39 y 41 producirá menos de 7 colisiones en cada caso. Esta puede ser la razón por la que tantas implementaciones de Java eligen este tipo de constantes.
Consulte la sección 9.2 Tablas hash (página 522) de Estructuras de datos y algoritmos en Java .
