Estoy viendo la implementación de HashMap en Java y estoy atascado en un punto.
¿Cómo se calcula la función indexFor?Implementación de HashMap en Java. ¿Cómo funciona el cálculo del índice del cubo?
static int indexFor(int h, int length) {
return h & (length-1);
}
Gracias
No es calcular el hash de , es calcular el cubo de .
La expresión h & (length-1) hace un bit a bit AND en h usando length-1, que es como una máscara de bits, para volver sólo los bits de orden bajo de h, con lo que para una variante súper rápido de h % length.
Está calculando el depósito del mapa hash donde se almacenará la entrada (par clave-valor). La identificación del cubo es hashvalue/buckets length.
Un mapa hash consiste en cubos; los objetos se colocarán en estos depósitos en función de la id del depósito.
Cualquier cantidad de objetos puede caer en el mismo contenedor en función de su valor hash code/buckets length. Esto se llama 'colisión'.
Si muchos objetos caen en el mismo cubo, mientras se busca su método equals() se llamará para desambiguar.
El número de colisiones es indirectamente proporcional a la longitud del cucharón.
El hash se calcula por el método hashCode() del objeto que intenta almacenar.
Lo que ves aquí es calcular el "cubo" para almacenar el objeto basado en el hash h. Idealmente, para evadir las colisiones, tendría la misma cantidad de cubetas que el valor máximo alcanzable de h, pero eso podría requerir demasiada memoria. Por lo tanto, generalmente tiene un número menor de cubos con peligro de colisión.
Si h es, digamos, 1000, pero solo tiene 512 cubos en su matriz subyacente, necesita saber dónde colocar el objeto. Generalmente, una operación mod en h sería suficiente, pero eso es demasiado lento. Dada la propiedad interna de HashMap que la matriz subyacente siempre ha serie de cubos iguales a 2^n, los ingenieros del Sol podrían utilizar la idea de h & (length-1), hace un bitwise AND con un número que consiste en todos los 1 's, prácticamente leer sólo el n los bits más bajos del hash (que es lo mismo que hacer h mod 2^n, solo mucho más rápido).
Ejemplo:
hash h: 11 1110 1000 -- (1000 in decimal)
length l: 10 0000 0000 -- (512 in decimal)
(l-1): 01 1111 1111 -- (511 in decimal - it will always be all ONEs)
h AND (l-1): 01 1110 1000 -- (488 in decimal which is a result of 1000 mod 512)
¿Tiene sentido ahora, o debo elaborar más sobre las partes internas? ? –
_ Muy bien explicado. Estoy impresionado. –
lo tengo .... gracias – gnreddy
¿Puede usted explicar este cálculo aquí? – gnreddy
¿Esto supone que 'length' es una potencia de 2? – LarsH
@LarsH Bueno, sería mucho mejor si fuera una potencia de 2, entonces obtendría un corte limpio de los bits de orden superior. Como sucede, la implementación de HashMap comienza con el tamaño 16 y, de hecho, se multiplica por dos al redimensionar.Todavía funcionaría si no fuera una potencia de dos, pero querría tantos bits "on" como sea posible para 'length -1' para equilibrar la dispersión entre cubos – Bohemian