¿Por qué un HashMap repite el código hash proporcionado por el objeto clave?

Question

Estoy leyendo el código de la clase HashMap que proporciona la API Java 1.6 y es incapaz de comprender plenamente la necesidad de la operación siguiente (que se encuentran en el cuerpo de PUT y GET métodos):

int hash = hash(key.hashCode()); 

donde el método hash() tiene el siguiente cuerpo:

private static int hash(int h) { 
     h ^= (h >>> 20)^(h >>> 12); 
    return h^(h >>> 7)^(h >>> 4); 
} 

Esto vuelve a calcular el hash de manera efectiva mediante la ejecución de operaciones de bits en el código hash suministrado. Soy incapaz de comprender la necesidad de hacerlo a pesar de que la API establece de la siguiente manera:

Esto es crítico porque HashMap utiliza tablas de hash longitud de energía-de-dos, que de otra manera se encuentran con colisiones para que hashcodes no difiera en bits inferiores.

Entiendo que los pares de valores clave se almacenan en una matriz de estructuras de datos, y que la ubicación del índice de un elemento en esta matriz está determinada por su hash. Lo que no entiendo es cómo agregaría esta función ningún valor a la distribución hash.

Answer 1

Como escribió Helper, está ahí solo en caso de que la función hash existente para los objetos clave sea defectuosa y no haga un trabajo lo suficientemente bueno para mezclar los bits más bajos. Según the source citado por pgras,

/** 
    * Returns index for hash code h. 
    */ 
static int indexFor(int h, int length) { 
    return h & (length-1); 
} 

El hash está siendo ANDed en con una longitud de potencias de dos (por lo tanto, length-1 se garantiza que sea una secuencia de 1s). Debido a este AND, solo se utilizan los bits inferiores de h. El resto de h se ignora. Imagine que, por cualquier razón, el hash original solo devuelve números divisibles por 2. Si lo utilizó directamente, las posiciones impares del hashmap nunca se usarían, lo que llevaría a un aumento de x2 en el número de colisiones. En un caso verdaderamente patológico, una mala función hash puede hacer que un hashmap se comporte más como una lista que como un contenedor O (1).

Los ingenieros de Sun deben haber ejecutado pruebas que demuestren que demasiadas funciones de hash no son lo suficientemente aleatorias en sus bits más bajos, y que muchos hashmaps no son lo suficientemente grandes como para usar los bits más altos. En estas circunstancias, las operaciones de bits en HashMap's hash(int h) pueden proporcionar una mejora neta sobre la mayoría de los casos de uso esperados (debido a las menores tasas de colisión), aunque se requiere un cálculo adicional.

Answer 2

En algún lugar leí que esto se hace para asegurar una buena distribución incluso si su implementación de hashCode, bueno, err, es una mierda.

Answer 3

como usted sabe con el hashmap, la implementación subyacente es una tabla hash, específicamente una tabla hash de cubo cerrado. El factor de carga determina la cantidad apropiada de objetos en la colección/número total de cubos.

Digamos que sigue agregando más elementos. Cada vez que lo hace, y no es una actualización, ejecuta el método de código hash del objeto y utiliza el número de segmentos con el operador de módulo para decidir a qué segmento debe ir el objeto.

como n (el número de elementos en la colección)/m (el número de segmentos) aumenta, su rendimiento para lecturas y escrituras empeora.

Suponiendo que su algoritmo de código hash es sorprendente, el rendimiento sigue dependiendo de esta comparación n/m.

El reajuste se usa también para cambiar el número de cubetas, y aun así mantener el mismo factor de carga con el que se construyó la colección.

Recuerde, el beneficio principal de cualquier implementación de hash es el rendimiento O (1) ideal para lecturas y escrituras.

Answer 4

Como ya sabe, object.hashCode() puede ser anulado por los usuarios, por lo que una implementación realmente mala arrojaría bits de nivel inferior no aleatorios. Eso tendería a llenar algunos cubos y dejaría muchos cubos sin llenar.

Acabo de crear un mapa visual de lo que están tratando de hacer en hash. Parece que el método hash (int h) solo está creando un número aleatorio al hacer una manuplación de nivel de bits para que los números resultantes sean más aleatorios (y por lo tanto más compartidos) distribuidos.

Cada bit se reasigna a un poco diferente de la siguiente manera:

 h1 = h1^h13^h21^h9^h6  
     h2 = h2^h14^h22^h10^h7 
     h3 = h3^h15^h23^h11^h8 
     h4 = h4^h16^h24^h12^h9 
     h5 = h5^h17^h25^h13^h10 

. . . .

hasta h12.

Como puede ver, cada bit de h va a estar tan lejos de sí mismo. Por lo tanto, va a ser bastante aleatorio y no va a llenar un cubo en particular. Espero que esto ayude. Envíame un correo electrónico si necesitas visión completa.