examples - hashmap java example
¿Cuál es la importancia del factor de carga en HashMap? (7)
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 ella.
¿Puede alguien describir cuáles son los diferentes escenarios en los que necesitamos establecer el factor de carga y cuáles son algunos valores ideales de muestra para diferentes casos?
¿Qué es el factor de carga?
¿La cantidad de capacidad que se va a agotar para que HashMap aumente 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 los compartimientos estarán libres antes de que haya un aumento en la capacidad y esto hace que muchos nuevos compartimientos con nuevos códigos hash indiquen su existencia justo después del aumento en el número de cubos.
Ahora, ¿por qué debería mantener muchos cubos gratuitos y cuál es el impacto de mantener cubos gratuitos en el rendimiento?
Si configura el factor de carga para que diga 1.0, entonces puede suceder algo muy interesante.
Supongamos que está agregando un objeto x a su hashmap cuyo código de hash es 888 y en su hashmap el cubo que representa el hashcode es gratuito, por lo que el objeto x se agrega al bucket, pero ahora nuevamente diga si está agregando otro objeto y cuyo código hash es también 888, entonces su objeto y se agregará con seguridad, PERO al final del grupo ( porque los grupos no son más que la clave de almacenamiento de implementación de linkList, el valor y el siguiente ) ¡ahora esto tiene un impacto en el rendimiento! Dado que 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 cubo. Esto se denomina colisión hash por cierto y esto incluso ocurre cuando el factor de carga es menor que 1.
¿Correlación entre rendimiento, colisión de 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 me equivoco en alguna parte.
De la documentation :
El factor de carga es una medida de qué tan llena está permitida la tabla hash antes de que su capacidad se incremente automáticamente
Realmente depende de sus requisitos particulares, no hay una "regla de oro" para especificar un factor de carga inicial.
Elegirí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 el hardware
En realidad, según mis cálculos, el factor de carga "perfecto" está más cerca del log 2 (~ 0.7). Aunque cualquier factor de carga menor a 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 la rama prediciendo si un cubo está vacío o no. Un cubo probablemente esté vacío si la probabilidad de que esté vacío exceda de .5.
Represente s el tamaño y n el número de teclas 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 está probablemente vacío si hay menos de
log(2)/log(s/(s - 1)) keys
Cuando s alcanza el infinito y si el número de teclas agregadas es tal que P (0) = .5, n / s se aproxima al log (2) rápidamente:
lim (log(2)/log(s/(s - 1)))/s as s -> infinity = log(2) ~ 0.693...
La documentation 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 depósitos 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 qué tan llena está permitida la tabla hash antes de que su capacidad se incremente 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 lavar (es decir, se reconstruyen las estructuras de datos internas) 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 (reflejado en la mayoría de las operaciones de la clase HashMap, incluyendo obtener y poner). El número esperado de entradas en el mapa y su factor de carga deben tenerse en cuenta al configurar su capacidad inicial, a fin de minimizar el número de operaciones de reinicio. Si la capacidad inicial es mayor que la cantidad máxima de entradas dividida por el factor de carga, nunca se realizará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 HashMap es 16 y el factor de carga es 0.75f (es decir, 75% del tamaño actual del mapa). 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.
Si los cubos se llenan demasiado, entonces tenemos que mirar a través de
Una lista enlazada muy larga.
Y eso es como derrotar el punto.
Así que aquí hay un ejemplo donde tengo cuatro cubos.
Tengo elefante y tejón en mi HashSet hasta ahora.
Esta es una situación bastante buena, ¿verdad?
Cada elemento tiene cero o uno elementos.
Ahora ponemos dos elementos más en nuestro HashSet.
buckets elements
------- -------
0 elephant
1 otter
2 badger
3 cat
Esto tampoco es tan malo.
Cada cubo solo tiene un elemento. Así que si quiero saber, ¿esto contiene panda?
Puedo ver rápidamente el cubo número 1 y no es
alli y
Sabía que no está en nuestra colección.
Si quiero saber si contiene gato, miro al cubo.
numero 3,
Encuentro gato, sé muy rápidamente si está en nuestra
colección.
¿Qué pasa si agrego koala, bueno, eso no es tan malo.
buckets elements
------- -------
0 elephant
1 otter -> koala
2 badger
3 cat
Tal vez ahora en lugar de en el cubo número 1 solo mirando
un elemento,
Necesito mirar dos.
Pero al menos no tengo que mirar elefante, tejón y
gato.
Si vuelvo a buscar panda, solo puede ser en cubo.
numero 1 y
No tengo que mirar otra cosa que no sea nutria y
coala.
Pero ahora pongo cocodrilo en el cubo número 1 y puedes
Ver quizás a dónde va esto.
Eso si el cubo número 1 sigue creciendo y creciendo.
Más grande, entonces básicamente tengo que mirar a través de todos
esos elementos para encontrar
Algo que debería estar en el cubo número 1.
buckets elements
------- -------
0 elephant
1 otter -> koala ->alligator
2 badger
3 cat
Si empiezo a añadir cadenas a otros cubos,
bien, el problema se hace cada vez más grande en cada
solo cubo
¿Cómo evitamos que nuestros cubos se llenen demasiado?
La solución aquí es que
"the HashSet can automatically
resize the number of buckets."
Ahí está el HashSet se da cuenta de que los cubos están recibiendo
muy lleno.
Está perdiendo esta ventaja de esta búsqueda de todos
elementos.
Y solo creará más cubos (generalmente el doble que antes) y
a continuación, coloque los elementos en el cubo correcto.
Así que aquí está nuestra implementación básica de HashSet con separado
encadenamiento Ahora voy a crear un "HashSet auto-redimensionado".
Este HashSet se va a dar cuenta de que los cubos son
demasiado lleno y
Necesita más cubos.
loadFactor es otro campo en nuestra clase HashSet.
loadFactor representa el número promedio de elementos por
cangilón,
por encima del cual queremos redimensionar.
loadFactor es un equilibrio entre el espacio y el tiempo.
Si los cubos se llenan demasiado, cambiaremos de tamaño.
Eso lleva tiempo, por supuesto, pero
Nos puede ahorrar tiempo en el camino si los cubos son una
poco mas vacio
Veamos un ejemplo.
Aquí hay un HashSet, hemos agregado cuatro elementos hasta ahora.
Elefante, perro, gato y pez.
buckets elements
------- -------
0
1 elephant
2 cat ->dog
3 fish
4
5
En este punto, he decidido que el loadFactor, el
límite,
el promedio de elementos por cubo que estoy bien
con, es de 0,75.
El número de cubos es buckets.length, que es 6, y
En este punto, nuestro HashSet tiene cuatro elementos, por lo que el
el tamaño actual es 4.
Cambiaremos el tamaño de nuestro HashSet, es decir, agregaremos más cubos,
cuando el número medio de elementos por cubo excede
El factor de carga.
Eso es cuando el tamaño actual dividido por buckets.length es
mayor que loadFactor.
En este punto, el número promedio de elementos por cubo.
es 4 dividido por 6
4 elementos, 6 cubos, eso es 0.67.
Eso es menos que el umbral que establezco de 0,75, así que estamos
bueno.
No necesitamos cambiar el tamaño.
Pero ahora digamos que le agregamos la marmota.
buckets elements
------- -------
0
1 elephant
2 woodchuck-> cat ->dog
3 fish
4
5
La marmota terminaría en el cubo número 3.
En este punto, el tamaño actual es 5.
Y ahora el número medio de elementos por cubo.
es el tamaño actual dividido por buckets.length.
Eso es 5 elementos divididos por 6 cubos es 0.83.
Y esto supera el factor de carga que fue de 0.75.
Con el fin de abordar este problema, con el fin de hacer que el
cubos quizás un poco
más vacío para que las operaciones como determinar si una
cubo contiene
Un elemento será un poco menos complejo, quiero redimensionarlo.
mi HashSet.
Cambiar el tamaño del HashSet toma dos pasos.
Primero doblaré el número de cubos, tuve 6 cubos,
Ahora voy a tener 12 cubos.
Tenga en cuenta que el factor de carga que configuré en 0.75 permanece igual.
Pero el número de cubos cambiados es 12,
El número de elementos se mantuvo igual, es de 5.
5 dividido por 12 es alrededor de 0.42, eso está bien bajo nuestra
factor de carga,
así que estamos bien ahora.
Pero no hemos terminado porque algunos de estos elementos están en
el cubo equivocado ahora.
Por ejemplo, elefante.
El elefante estaba en el cubo número 2 porque el número de
personajes en elefante
tenía 8 años.
Tenemos 6 cubos, 8 menos 6 es 2.
Es por eso que terminó en el número 2.
Pero ahora que tenemos 12 cubos, 8 mod 12 es 8, entonces
El elefante ya no pertenece al cubo número 2.
El elefante pertenece al cubo número 8.
¿Qué pasa con la marmota?
Woodchuck fue el que comenzó todo este problema.
Woodchuck terminó en el cubo número 3.
Porque 9 mod 6 es 3.
Pero ahora hacemos 9 mod 12.
9 mod 12 es 9, la marmota va al cubo número 9.
Y ves la ventaja de todo esto.
Ahora el cubo número 3 solo tiene dos elementos, mientras que antes tenía 3.
Así que aquí está nuestro código,
donde tuvimos nuestro HashSet con encadenamiento separado que
no hizo ningún cambio de tamaño.
Ahora, aquí hay una nueva implementación donde usamos redimensionamiento.
La mayor parte de este código es el mismo,
todavía vamos a determinar si contiene el
valor ya
Si no lo hace, entonces vamos a averiguar qué cubo es
debe entrar y
luego agréguelo a ese grupo, agréguelo a esa lista enlazada.
Pero ahora incrementamos el campo currentSize.
currentSize fue el campo que hizo un seguimiento del número
de elementos en nuestro HashSet.
Vamos a incrementarlo y luego vamos a mirar
a la carga media,
El número medio de elementos por cubo.
Haremos esa división aquí abajo.
Tenemos que hacer un poco de casting aquí para asegurarnos
Que obtengamos un doble.
Y luego, compararemos esa carga promedio con el campo.
que he puesto como
0,75 cuando creé este HashSet, por ejemplo, que era
El factor de carga.
Si la carga promedio es mayor que el loadFactor,
eso significa que hay demasiados elementos por cubo en
Promedio, y necesito reinsertar.
Así que aquí está nuestra implementación del método para reinsertar.
Todos los elementos.
Primero, crearé una variable local llamada oldBuckets.
Que se refiere a los cubos como están actualmente.
Antes de empezar a cambiar el tamaño de todo.
Tenga en cuenta que todavía no estoy creando una nueva matriz de listas vinculadas.
Solo estoy cambiando el nombre de cubos como OldBuckets.
Ahora recuerden que los cubos eran un campo en nuestra clase, voy
para crear ahora una nueva matriz
de listas enlazadas pero esto tendrá el doble de elementos
Como lo hizo la primera vez.
Ahora necesito hacer la reinserción,
Voy a recorrer todos los cubos viejos.
Cada elemento en oldBuckets es una lista enlazada de cadenas
eso es un cubo
Voy a ir a través de ese cubo y obtener cada elemento en ese
cangilón.
Y ahora voy a reinsertarlo en los nuevos cubos.
Obtendré su código hash.
Voy a averiguar qué índice es.
Y ahora recibo el nuevo bucket, el nuevo LinkedList de
cuerdas y
Lo agregaré a ese nuevo cubo.
Así que para recapitular, los HashSets, como hemos visto, son matrices de Linked
Listas, o cubos.
Un autoajuste HashSet puede darse cuenta usando alguna proporción o