Refiriéndose a la documentación del hashCode de Object:
“Este método es compatible en beneficio de tablas hash como las proporcionadas por java.util.Hashtable”.
http://grepcode.com/file/reposit……
- Si clasifica todos los pesos de una red neuronal entrenada en orden ascendente, ¿cómo se vería la curva de los datos ordenados?
- En Codeforces Round # 308 (Div. 2), ¿cómo descubrieron todos la cantidad de dígitos de un número usando un algoritmo eficiente de toma de tiempo? ¿Alguien puede explicarlo?
- ¿Cuál es la relación entre las cadenas de Markov y los procesos de Poisson?
- ¿Qué es un algoritmo eficiente para encontrar un número mágico?
- ¿Cuál es la diferencia entre un código y un algoritmo?
Los diseñadores del lenguaje Java agregaron hashcode principalmente para colecciones basadas en hash como HashTable y HashMap. La cadena no es diferente.
Si observa HashMap, notará que se utiliza “bit a bit” para asignar objetos a los depósitos de HashMap; esencialmente, los bits de orden inferior determinan el índice del depósito.
/ *** Devuelve el índice para el código hash h. * /
static int indexFor (int h, int length) {
retorno h & (longitud-1);
}
De tus días de escuela, puedes recordar haber usado
myString.hashCode() % numOfBuckets
para asignar un objeto a un cubo.
En Java HashMap (a partir de 1.4, creo), Josh Bloch et al cambiaron esto a myString.hashCode() & (numOfBuckets -1)
Esto es mucho más barato en términos de CPU, ya que el módulo (división) es más costoso que bit-AND o bit-shifts.
Siempre que los bits de orden inferior de myString.hashCode () sean aleatorios, este algoritmo obtendrá una distribución uniforme de objeto a cubo.
Sin embargo, dado que cualquiera puede anular el código hash para un objeto, Josh et al deben proporcionar algunas garantías. Esto se logra mediante un método hash complementario (en la clase HashMap).
/ *** Aplica una función hash complementaria a un código hash dado, que * defiende contra las funciones hash de baja calidad. Esto es crítico * porque HashMap usa tablas hash de potencia de dos longitudes, que * de lo contrario encuentran colisiones para códigos hash que no difieren * en bits más bajos. Nota: las teclas nulas siempre se asignan al hash 0, por lo tanto, el índice 0. * /
hash int estático (int h) {
// Esta función asegura que los códigos hash que difieren solo por
// los múltiplos constantes en cada posición de bit tienen un límite
// número de colisiones (aproximadamente 8 con el factor de carga predeterminado).h ^ = (h >>> 20) ^ (h >>> 12); devuelve h ^ (h >>> 7) ^ (h >>> 4);
}
Para resumir, un objetivo clave del código hash de Java era admitir colecciones basadas en hash. Las colecciones basadas en hash como HashMap tratan algunos sesgos de bits y problemas relacionados con implementaciones de funciones hash pobres, por lo que una implementación mediocre de hashCode en String no es un gran problema.
