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

collections hashcode

Question

Estoy leyendo el código de la clase HashMap provisto por la API Java 1.6 y no puedo entender completamente la necesidad de la siguiente operación (que se encuentra en el cuerpo de los métodos put y get):

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 recalcula efectivamente el hash ejecutando operaciones de bit en el código hash proporcionado. No puedo entender la necesidad de hacerlo aunque la API lo indica de la siguiente manera:

Esto es crítico porque HashMap usa tablas hash de potencia de dos longitudes, que de otra manera encuentran colisiones para códigos hash que no difieren en bits más bajos.

Entiendo que los valores de valor 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 esta función agregaría algún valor a la distribución de hash.

Answer 1

Como Helper escribió, está ahí en caso de que la función hash existente para los objetos clave sea defectuosa y no haga un buen trabajo de mezclar los bits más bajos. Según la fuente citada por pgras,

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

El hash se está ANDando con una longitud de potencia de dos (por lo tanto, se garantiza que la length-1 es 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 el motivo que sea, el hash original solo devuelve números divisibles entre 2. Si lo usó directamente, las posiciones impares del hashmap nunca se usarían, lo que provocaría un aumento de x2 en el número de colisiones. En un caso verdaderamente patológico, una función hash mala puede hacer que un mapa hash se comporte más como una lista que como un contenedor O (1).

Los ingenieros de Sun deben realizar pruebas que muestren que demasiadas funciones 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 el hash(int h) de HashMap hash(int h) pueden proporcionar una mejora neta con respecto a la mayoría de los casos de uso esperados (debido a menores tasas de colisión), aunque se requiera un cálculo adicional.

Answer 2

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

Digamos que sigues añadiendo más elementos. Cada vez que lo haces, y no es una actualización, ejecuta el método de código de hash del objeto y utiliza el número de grupos con el operador de módulo para decidir en qué grupo debe ir el objeto.

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

Asumiendo que su algoritmo de hashcode es increíble, el rendimiento aún depende de esta comparación n / m.

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

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

Answer 3

Como saben, los usuarios pueden anular object.hashCode (), por lo que una implementación realmente mala generaría bits de nivel inferior no aleatorios. Eso tendería a amontonar algunos de los cubos y dejaría muchos cubos sin llenar.

Acabo de crear un mapa visual de lo que están tratando de hacer con hash. Parece que el método hash (int h) simplemente está creando un número aleatorio al hacer la administración a nivel de bits para que los números resultantes se distribuyan de forma más aleatoria (y, por lo tanto, en grupos de manera más uniforme) distribuidos.

Cada bit se vuelve a asignar a un bit 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 estará muy lejos de sí mismo. Por lo tanto, va a ser bastante aleatorio y no va a abarrotar ningún cubo en particular. Espero que esto ayude. Envíame un correo electrónico si necesitas visual completo.

Answer 4

En algún lugar, leo que esto se hace para garantizar una buena distribución, incluso si la implementación de hashCode, bueno, err, chupa.