¿Cuál es la importancia del factor de carga en HashMap?

HashMap tiene dos propiedades importantes: size y load factor . 0.75f la documentación de Java y dice que 0.75f es el factor de carga inicial. Pero no puedo encontrar el uso real de eso.

¿Puede alguien describir cuáles son los diferentes escenarios donde necesitamos establecer el factor de carga y cuáles son algunos valores ideales de muestra para diferentes casos?

La documentación lo explica bastante bien:

Una instancia de HashMap tiene dos parámetros que afectan su rendimiento: capacidad inicial y factor de carga. La capacidad es el número de segmentos en la tabla hash, y la capacidad inicial es simplemente la capacidad en el momento en que se crea la tabla hash. El factor de carga es una medida de cuán completa está permitida la tabla hash antes de que su capacidad aumente automáticamente. Cuando el número de entradas en la tabla hash excede el producto del factor de carga y la capacidad actual, la tabla hash se vuelve a generar (es decir, se reconstruyen las estructuras internas de datos) para que la tabla hash tenga aproximadamente el doble de cubetas.

Como regla general, el factor de carga predeterminado (.75) ofrece una buena compensación entre los costos de tiempo y espacio. Los valores más altos disminuyen la sobrecarga de espacio, pero aumentan el costo de búsqueda (que se refleja en la mayoría de las operaciones de la clase HashMap, incluidos get y put). El número esperado de entradas en el mapa y su factor de carga se deben tener en cuenta al establecer su capacidad inicial, a fin de minimizar el número de operaciones de repetición. Si la capacidad inicial es mayor que la cantidad máxima de entradas dividida por el factor de carga, nunca se producirán operaciones de repetición.

Al igual que con todas las optimizaciones de rendimiento, es una buena idea evitar la optimización prematura de las cosas (es decir, sin datos concretos sobre dónde se encuentran los cuellos de botella).

La capacidad inicial predeterminada de las tomas de HashMap es 16 y el factor de carga es 0.75f ​​(es decir, el 75% del tamaño del mapa actual). El factor de carga representa a qué nivel se debe duplicar la capacidad de HashMap .

Por ejemplo, producto de capacidad y factor de carga como 16 * 0.75 = 12 . Esto representa que después de almacenar el 12 ° par clave-valor en el HashMap , su capacidad se convierte en 32.

En realidad, según mis cálculos, el factor de carga “perfecto” está más cerca de log 2 (~ 0.7). Aunque cualquier factor de carga menor que este dará un mejor rendimiento. Creo que .75 probablemente fue sacado de un sombrero.

Prueba:

Se puede evitar el encadenamiento y explotar la predicción de ramificación al predecir si un cubo está vacío o no. Un cubo probablemente esté vacío si la probabilidad de que esté vacío excede de .5.

Representemos el tamaño y n la cantidad de claves agregadas. Usando el teorema binomial, la probabilidad de que un cubo esté vacío es:

 P(0) = C(n, 0) * (1/s)^0 * (1 - 1/s)^(n - 0) 

Por lo tanto, un cubo probablemente esté vacío si hay menos de

 log(2)/log(s/(s - 1)) keys 

Como s llega al infinito y si el número de teclas añadidas es tal que P (0) = .5, entonces n / s se acerca al log (2) rápidamente:

 lim (log(2)/log(s/(s - 1)))/s as s -> infinity = log(2) ~ 0.693... 

¿Cuál es el factor de carga?

¿La cantidad de capacidad que se debe agotar para HashMap para boost su capacidad?

¿Por qué factor de carga?

El factor de carga es por defecto 0,75 de la capacidad inicial (16), por lo tanto, el 25% de las cubetas estarán libres antes de que haya un aumento en la capacidad y esto hace que muchos cubos nuevos con nuevos códigos de hash indiquen que existen justo después del aumento en el cantidad de cubos.

Ahora, ¿por qué debería mantener muchos contenedores gratuitos y cuál es el impacto de mantener cubos libres en el rendimiento?

Si establece el factor de carga para decir 1.0, entonces podría suceder algo muy interesante.

Digamos que está agregando un objeto x a su hashmap cuyo hashCode es 888 y en su hashmap el cubo que representa el hashcode es libre, entonces el objeto x se agrega al cubo, pero ahora diga si está agregando otro objeto y cuyo hashCode es también 888, entonces su objeto y se agregará con seguridad PERO al final del segmento ( porque los depósitos no son más que la implementación de la lista linkedList, el valor y el próximo ) ahora esto tiene un impacto en el rendimiento. Como su objeto y ya no está presente en la cabecera del cubo, si realiza una búsqueda, el tiempo empleado no será O (1) esta vez, depende de cuántos elementos haya en el mismo contenedor. Esto se llama colisión hash por cierto y esto incluso sucede cuando el factor de carga es menor a 1.

Correlación entre rendimiento, colisión hash y factor de carga?

Factor de carga más bajo = más cubos libres = menos posibilidades de colisión = alto rendimiento = alto requerimiento de espacio.

Corrígeme si estoy equivocado en alguna parte.

De la documentación :

El factor de carga es una medida de la capacidad de carga de la tabla hash antes de boost automáticamente su capacidad

Realmente depende de sus requisitos particulares, no existe una “regla práctica” para especificar un factor de carga inicial.

Escogería un tamaño de tabla de n * 1.5 o n + (n >> 1), esto daría un factor de carga de .66666 ~ sin división, que es lento en la mayoría de los sistemas, especialmente en sistemas portátiles donde no hay división en el hardware.