algoritmo - encriptar y desencriptar md5 java
¿Cuál es una ventaja sensible para el cálculo de código hash? (6)
Elegiría 7243. Lo suficientemente grande como para evitar colisiones con números pequeños. No se desborda a números pequeños rápidamente.
Esta pregunta ya tiene una respuesta aquí:
Eclipse 3.5 tiene una característica muy buena para generar funciones Java hashCode (). Generaría por ejemplo (un poco acortado :)
class HashTest {
int i;
int j;
public int hashCode() {
final int prime = 31;
int result = prime + i;
result = prime * result + j;
return result;
}
}
(Si tiene más atributos en la clase, result = prime * result + attribute.hashCode(); se repite para cada atributo adicional. Para ints, se puede omitir .hashCode ().)
Esto parece estar bien, pero para la opción 31 para el primo. Probablemente se tome de la implementación hashCode de Java String , que se usó por razones de rendimiento que han desaparecido mucho después de la introducción de los multiplicadores de hardware. Aquí tiene muchas colisiones hashcode para valores pequeños de i y j: por ejemplo (0,0) y (-1,31) tienen el mismo valor. Creo que es una mala cosa (TM), ya que los valores pequeños ocurren a menudo. Para String.hashCode también encontrará muchas cadenas cortas con el mismo código hash, por ejemplo "Ca" y "DB". Si toma una prima grande, este problema desaparece si elige el derecho principal.
Entonces mi pregunta: ¿cuál es el mejor momento para elegir? ¿Qué criterios aplica para encontrarlo?
Esto se entiende como una pregunta general, por lo que no quiero dar un rango para i y j. Pero supongo que en la mayoría de las aplicaciones los valores relativamente pequeños ocurren con mayor frecuencia que los valores grandes. (Si tiene valores grandes, la elección del primo probablemente no sea importante.) Puede que no suponga una gran diferencia, pero una mejor opción es una manera fácil y obvia de mejorar esto, ¿por qué no hacerlo? Commons lang HashCodeBuilder también sugiere valores curiosamente pequeños.
( Aclaración : esto no es un duplicado de ¿Por qué el hashCode () de Java usa 31 como un multiplicador? Ya que mi pregunta no se refiere al historial de los 31 en el JDK, sino a cuál sería un mejor valor en el nuevo código usando la misma plantilla básica. Ninguna de las respuestas intenta responder eso).
En realidad, si tomas un primo tan grande que se acerca a INT_MAX , tienes el mismo problema debido a la aritmética de módulo. Si esperas hash principalmente cadenas de longitud 2, quizás un mejor cerca de la raíz cuadrada de INT_MAX sería mejor, si las cadenas que hash son más largas no importa tanto y las colisiones son inevitables de todos modos ...
Las colisiones pueden no ser un gran problema ... El objetivo principal del hash es evitar el uso de iguales para las comparaciones 1: 1. Si tiene una implementación donde equals es "en general" extremadamente barato para los objetos que tienen hash colisionados, entonces esto no es un problema (en absoluto).
Al final, cuál es la mejor forma de hash depende de lo que comparas. En el caso de un int pair (como en su ejemplo), el uso de operadores bit a bit básicos podría ser suficiente (como usar & o ^).
Necesitas definir tu rango para i y j. Podría usar un número primo para ambos.
public int hashCode() {
http://primes.utm.edu/curios/ ;)
return 97654321 * i ^ 12356789 * j;
}
Recomiendo usar 92821 . Este es el por qué.
Para dar una respuesta significativa a esto, debes saber algo sobre los posibles valores de i y j . Lo único que se me ocurre en general es que, en muchos casos, los valores pequeños serán más comunes que los valores grandes. (Las probabilidades de que 15 aparezcan como un valor en su programa son mucho mejores que, digamos, 438281923). Por lo tanto, parece una buena idea hacer la menor colisión de hashcode lo más grande posible eligiendo un primo apropiado. Para 31 esto es bastante malo, ya para i=-1 y j=31 tienes el mismo valor hash que para i=0 y j=0 .
Dado que esto es interesante, he escrito un pequeño programa que buscó en todo el rango int para obtener el mejor primado en este sentido. Es decir, para cada primo busqué el valor mínimo de Math.abs(i) + Math.abs(j) sobre todos los valores de i,j que tienen el mismo código hash como 0,0 , y luego tomé el primo donde esto el valor mínimo es tan grande como sea posible.
Drumroll : el mejor primo en este sentido es 486187739 (siendo la colisión más pequeña i=-25486, j=67194 ). Casi tan bueno y más fácil de recordar es el 92821 con la menor colisión siendo i=-46272 and j=46016 .
Si le da otro significado a "pequeño" y quiere ser el mínimo de Math.sqrt(i*i+j*j) para la colisión lo más grande posible, los resultados son un poco diferentes: lo mejor sería 1322837333 con i=-6815 and j=70091 , pero mi 92821 favorito (la colisión más pequeña -46272,46016 ) nuevamente es casi tan buena como el mejor valor.
Reconozco que es bastante discutible si estos cálculos tienen mucho sentido en la práctica. Pero creo que tomar 92821 como primer tiene mucho más sentido que 31, a menos que tengas buenas razones para no hacerlo.
Solo quiero señalar que hashcode no tiene nada que ver con el primer. En la implementación de JDK
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
Descubrí que si reemplazas 31 con 27 , el resultado es muy similar.