validar - usuario y contraseña java
¿Por qué el código de hash de Java() en String usa 31 como multiplicador? (10)
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 más a la derecha y de menor orden también se rellenan, para mezclarse con la siguiente parte de datos que se incluyen en el hash.
La expresión n * 31 es equivalente a (n << 5) - n .
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 la aritmética int , donde s[i] es el i carácter de la cadena, n es la longitud de la cadena y ^ indica exponentiation.
¿Por qué se usa 31 como multiplicador?
Entiendo que el multiplicador debe ser un número primo relativamente grande. Entonces, ¿por qué no 29, o 37, o incluso 97?
Bloch no se adentra en esto, pero la razón que siempre he escuchado / creído es que se trata de álgebra básica. Los hash se reducen a las operaciones de multiplicación y módulo, lo que significa que nunca quieres usar números con factores comunes si puedes evitarlo. En otras palabras, los números relativamente primos proporcionan una distribución uniforme de respuestas.
Los números que forman un hash son típicamente:
- módulo del tipo de datos en el que lo pusiste (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)
- 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.
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 proporcionadas 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 en el medio de leer la sección "códigos hash polinómicos" cuando vi esta pregunta.
EDITAR: aquí hay un enlace al libro PDF de ~ 10mb. Me refiero a lo anterior. Consulte la sección 10.2 Tablas hash (página 413) de Estructuras de datos y algoritmos en Java.
Desde http://bugs.java.com/bugdatabase/view_bug.do?bug_id=4045622 , donde Joshua Bloch describe las razones por las cuales se eligió String.hashCode() implementación particular (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 el 2do diccionario íntegro internacional de Merriam-Webster (311,141 cadenas, longitud 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 de 21 caracteres).
3) Una lista de URL recopiladas por un rastreador web que se ejecutó durante varias horas la noche anterior (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.2439Mirando esta tabla, está claro que todas las funciones, excepto la actual función de Java y las dos versiones rotas de la función de Weinberger, ofrecen un rendimiento excelente, casi indistinguible. Conjeturo firmemente que este rendimiento es esencialmente el "ideal teórico", que es lo que obtendría si usara 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 opciones excelentes, 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 de calcular en una máquina RISC (porque 31 es la diferencia de dos potencias de dos). P (33) es similarmente barato de calcular, pero su rendimiento es ligeramente peor, y 33 es compuesto, lo que me pone un poco nervioso.
Josh
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 separada de cambio y resta. Sin embargo, si tu multiplicador es lento, esto sigue siendo una victoria. Los procesadores modernos tienden a tener multiplicadores rápidos, por lo que no hacen mucha diferencia, siempre y cuando 32 vayan 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).
En realidad, 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 prime 73 incluso mayor se podría hacer a la misma velocidad configurando y := x + 8 * x; z := x + 8 * y y := x + 8 * x; z := x + 8 * y .
El uso de 73 o 37 (en lugar de 31) podría ser mejor, ya que conduce a un código más denso : las dos instrucciones de LEA solo toman 6 bytes frente a los 7 bytes para mover + cambio + restar para la multiplicación por 31. Una posible advertencia es que las instrucciones de 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 explains por qué 31 se usa para eliminar el sesgo .
Básicamente, el uso de 31 le proporciona una distribución de probabilidad de bit de conjunto más uniforme para la función hash.
No estoy seguro, pero supongo que probaron algunas muestras de números primos y encontraron que 31 dieron la mejor distribución sobre algunas muestras de posibles cadenas.
Puede leer el razonamiento original de Bloch en "Comentarios" en http://bugs.java.com/bugdatabase/view_bug.do?bug_id=4045622 . Él investigó el desempeño de diferentes funciones hash con respecto al "tamaño promedio de cadena" 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 pudieron recordar de dónde vino). Al final, básicamente tuvo que elegir uno y, por lo tanto, tomó P(31) ya que parecía funcionar lo suficientemente bien. Aunque P(33) no era 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 un número 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 similarmente barato de calcular, pero su rendimiento es ligeramente peor, y 33 es compuesto, lo que me pone un poco nervioso.
Así que 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 instintivas (e incluso Bloch podría ser propenso a eso).
Según Effective Java de Joshua Bloch (un libro que no se puede recomendar lo suficiente y que compré gracias a las continuas menciones en ):
El valor 31 fue elegido 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 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 se puede reemplazar por un desplazamiento 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 reemplazas a iguales, página 48)