/** * Returns index for Object x. */ private static int hash(Object x, int length) { int h = System.identityHashCode(x); // Multiply by -127, and left-shift to use least bit as part of hash return ((h << 1) - (h << 8)) & (length - 1); }De: jdk/IdentityHashMap.java en jdk8-b120 · openjdk/jdk · GitHub
En teoría, los valores hash devueltos por System.identityHashCode() ya están distribuidos uniformemente, entonces, ¿por qué hay una operación de cambio adicional en lugar de una operación AND directa con length - 1 ?
La implementación parece garantizar que el bit más bajo sea 0 para garantizar que el resultado del cálculo sea un número par, porque la implementación requiere que todas las claves estén en índices pares y que todos los valores estén en índices impares.
h << 8 parece mezclar los bits bajos y altos para manejar el escenario cuando System.identityHashCode() se implementa como una dirección de memoria o un valor incremental, no está claro por qué solo se desplazan 8 bits aquí en lugar de algo como HashMap.hash() también mueve 16 bits.
Los comentarios en el código dicen:
"Nota de implementación: esta es una tabla hash de sonda lineal simple, como se describe, por ejemplo, en los textos de Sedgewick y Knuth. La matriz alterna la retención de claves y valores".
De hecho, el método hash devuelve un valor que se utiliza como índice directo en la matriz. Por ejemplo:
public V get(Object key) { Object k = maskNull(key); Object[] tab = table; int len = tab.length; int i = hash(k, len); while (true) { Object item = tab[i]; if (item == k) return (V) tab[i + 1]; if (item == null) return null; i = nextKeyIndex(i, len); } } Eso significa que el hash debe devolver un valor par. El cálculo en hash garantiza que el índice sea uniforme sin descartar el bit inferior del valor System.identityHashCode(x) .
¿Por qué no tirar la parte inferior?
Bueno, la respuesta está en la forma en que se implementa System.identityHashCode . En realidad, hay varios algoritmos para generar el hash, y el algoritmo utilizado (en tiempo de ejecución) depende de una opción de línea de comandos de JVM oscura.
Algunos algoritmos están (teóricamente) distribuidos uniformemente en el rango de int . Para aquellos, descartar la parte inferior estaría bien.
Otros algoritmos no son así. Uno de los algoritmos utiliza un contador global simple. Otro usa la dirección de memoria del objeto con los 3 bits inferiores eliminados. Si se seleccionan estos algoritmos, descartar el LSB aumentaría la probabilidad de colisiones de hash en IdentityHashMap .
Consulte https://shipilev.net/jvm/anatomy-quarks/26-identity-hash-code/ para obtener más información sobre los algoritmos de IdentityHashcode y cómo se seleccionan. Tenga en cuenta que este aspecto del comportamiento de JVM no está especificado y es probable que sea específico de la versión.
Mi corazonada de lo que está pasando aquí es que está diseñado para abordar dos problemas.
Primero, el índice de ranura que produce esta función debe ser un número par. (La implementación almacena claves en los espacios de la tabla pares y valores en los espacios de la tabla impar). Esto significa que cualquier índice que se devuelva debe tener su último bit igual a cero.
En segundo lugar, los códigos hash de identidad utilizados se basan (potencialmente) en las direcciones de memoria, y los bits bajos de las direcciones de memoria son "más aleatorios" que los bits altos. Por ejemplo, si asignamos una lista de objetos y el asignador los coloca todos consecutivamente en la memoria, todas sus direcciones tendrán los mismos bits altos pero diferentes bits bajos. (O tal vez solo hay un contador global de objetos que se incrementa cuando se crea un objeto. En ese caso, los bits bajos de hash de objetos tendrán una dispersión más amplia que los bits altos).
Para asegurarnos de que las cosas estén distribuidas en la tabla, nos gustaría "mezclar" los bits bajos del código hash con los bits "altos" del código hash. El efecto de restar h << 8 es desplazar los bits bajos del código hash de identidad hacia arriba, voltearlos y volver a agregarlos al código hash, lo que provoca un montón de "ondas" a medida que se desarrolla la suma. Creo (?) Esta es una forma efectiva de inyectar bits bajos de mayor entropía en los bits altos, dando un hash más uniforme sobre la matriz de ranuras una vez que la mesa comienza a crecer más y más.