Explicación del método HashMap # hash (int)

Question

¿Puede alguien explicarme el método estático HashMap # hash (int)?

¿Cuál es la justificación detrás de esto para generar hashes uniformemente distribuidos?

/** 
* Applies a supplemental hash function to a given hashCode, which 
* defends against poor quality hash functions. This is critical 
* because HashMap uses power-of-two length hash tables, that 
* otherwise encounter collisions for hashCodes that do not differ 
* in lower bits. Note: Null keys always map to hash 0, thus index 0. 
*/ 
static int hash(int h) { 
    // This function ensures that hashCodes that differ only by 
    // constant multiples at each bit position have a bounded 
    // number of collisions (approximately 8 at default load factor). 
    h ^= (h >>> 20)^(h >>> 12); 
    return h^(h >>> 7)^(h >>> 4); 
} 

Un ejemplo lo haría más fácil de digerir.

aclaración Conozco los operadores, las tablas de verdad y las operaciones bit a bit. Simplemente no puedo descifrar realmente la implementación ni el comentario en realidad. O incluso el razonamiento detrás de esto.

Answer 1

>>> es el desplazamiento lógico a la derecha (sin extensión de signo) (JLS 15.19 Shift Operators), y ^ es la operación O exclusiva (JLS 15.22.1 Integer Bitwise Operators).

En cuanto a por qué se hace esto, la documentación ofrece una pista: HashMap usa tablas de potencias de dos, y las claves hash enmascarando los bits más altos y tomando solo los bits más bajos de su código hash.

// HashMap.java -- edited for conciseness 
static int indexFor(int h, int length) { 
    return h & (length-1); 
} 

public V put(K key, V value) { 
    int hash = hash(key.hashCode()); 
    int index = indexFor(hash, table.length); 
    // ... 
} 

Así hash() intentos de llevar relevancia a los bits más altas, que de otra forma serían enmascarados distancia (indexFor descarta básicamente los bits más altos de h y toma sólo los más bajos k bits de donde length == (1 << k)).

Contraste esto con el modo Hashtable (que NO debe tener una tabla de potencia de dos longitudes) utiliza el código hash de una clave.

// Hashtable.java -- edited for conciseness 
public synchronized V get(Object key) { 
    int hash = key.hashCode(); 
    int index = (hash & 0x7FFFFFFF) % table.length; 
    // ... 
} 

Al hacer la operación más costosa % (en lugar de una simple enmascaramiento de bits), el rendimiento de Hashtable es menos sensible a hash de códigos con mala distribución de los bits inferiores (especialmente si table.length es un número primo).

Answer 2

no sé cómo todas las obras cambiantes, pero se presenta la motivación en los comentarios:

La forma en que se implementó el HashMap se basa en la función hashCode siendo lo suficientemente bien implementado. En particular, los bits más bajos del valor hash deben distribuirse uniformemente. Si tiene muchas colisiones en los bits inferiores, el HashMap no funcionará bien.

Dado que la implementación de hashCode está fuera del control de HashMap (cada objeto puede implementar el suyo), proporcionan una función hash adicional que desplaza el hashCode del objeto un poco para garantizar que los bits inferiores se distribuyan de forma más aleatoria. De nuevo, no tengo idea de cómo funciona esto exactamente (o cuán efectivo es), pero supongo que depende de que al menos los bits más altos se distribuyan por igual (parece engranar los bits más altos en los bits más bajos).

Entonces, lo que esto hace es intentar minimizar las colisiones (y así mejorar el rendimiento) en presencia de métodos hashCode mal implementados.