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

233

HashMaptiene dos propiedades importantes: sizey load factor. Revisé la documentación de Java y dice que 0.75fes el factor de carga inicial. Pero no puedo encontrar el uso real de la misma.

¿Alguien puede 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?

java hashmap load-factor Priyank Doshi
fuente

Respuestas:

267

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 cubos 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 llena se permite que llegue 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 aplicar (es decir, se reconstruyen las estructuras de datos internas) para que la tabla hash tenga aproximadamente el doble de la cantidad de depósitos.

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, incluidas get y put). El número esperado de entradas en el mapa y su factor de carga deben tenerse en cuenta al establecer su capacidad inicial, para minimizar el número de operaciones de repetición. Si la capacidad inicial es mayor que el número máximo de entradas dividido 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 optimizar las cosas prematuramente (es decir, sin datos precisos sobre dónde están los cuellos de botella).

NPE
fuente
14
Otras respuestas sugieren especificar capacity = N/0.75para evitar repetir, pero mi pensamiento inicial se acaba de establecer load factor = 1. ¿Habría inconvenientes en ese enfoque? ¿Por qué afectaría el factor de carga get()y los put()costos de operación?
Supermitch
19
Un factor de carga = 1 hashmap con número de entradas = capacidad estadísticamente tendrá una cantidad significativa de colisiones (= cuando varias claves están produciendo el mismo hash). Cuando se produce una colisión, el tiempo de búsqueda aumenta, ya que en un segmento habrá> 1 entradas coincidentes, para las cuales la clave debe verificarse individualmente para determinar la igualdad. Algunas matemáticas detalladas: preshing.com/20110504/hash-collision-probabilities
atimb
8
No te estoy siguiendo @atimb; La propiedad del conjunto de carga solo se usa para determinar cuándo aumentar el tamaño de almacenamiento, ¿verdad? - ¿De qué manera tener un conjunto de carga de uno aumenta la probabilidad de colisiones de hash? - El algoritmo de hash no tiene conocimiento de cuántos elementos hay en el mapa o con qué frecuencia adquiere nuevos "cubos" de almacenamiento, etc. Para cualquier conjunto de objetos del mismo tamaño, independientemente de cómo estén almacenados, debe tener el misma probabilidad de valores hash repetidos ...
BrainSlugs83
19
La probabilidad de la colisión de hash es menor si el tamaño del mapa es mayor. Por ejemplo, los elementos con los códigos hash 4, 8, 16 y 32 se colocarán en el mismo depósito, si el tamaño del mapa es 4, pero cada elemento obtendrá un depósito propio, si el tamaño del mapa es superior a 32. El mapa con tamaño inicial 4 y factor de carga 1.0 (4 cubetas, pero todos los 4 elementos en una sola cubeta) será en este ejemplo en promedio dos veces más lento que otro con el factor de carga 0.75 (8 cubetas, dos cubetas llenas - con elemento "4" y con elementos "8", "16", "32").
30 de
1
El costo de búsqueda de @Adelin aumenta para factores de carga más altos porque habrá más colisiones para valores más altos, y la forma en que Java maneja las colisiones es colocando los elementos con el mismo código hash en el mismo depósito utilizando una estructura de datos. A partir de Java 8, esta estructura de datos es un árbol de búsqueda binario. Esto hace que la búsqueda de la complejidad de tiempo del caso más desfavorable O (lg (n)) ocurra en el peor de los casos si todos los elementos agregados tienen el mismo código hash.
Gigi Bayte 2
141

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

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

usuario2791282
fuente
3
Aunque su respuesta es clara, ¿puede decir si justo después de almacenar 12 pares clave-valor la capacidad se convierte en 32 o es que cuando se agrega la 13a entrada, en ese momento la capacidad cambia y luego se inserta la entrada.
userab
¿eso significa que el número de cubos se incrementa en 2?
LoveMeow
39

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 inferior a este producirá un mejor rendimiento. Creo que .75 probablemente fue sacado de un sombrero.

Prueba:

Se puede evitar el encadenamiento y se puede explotar la predicción de rama al predecir 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.

Vamos a representar el tamaño yn el número 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

Cuando s alcanza el infinito y si el número de claves agregadas es tal que P (0) = .5, entonces n / s se acerca rápidamente a log (2):

lim (log(2)/log(s/(s - 1)))/s as s -> infinity = log(2) ~ 0.693...
Hola Mundo
fuente
44
Nerds matemáticos FTW! Probablemente .75se redondeó a la fracción más fácil de entender log(2), y parece menos un número mágico. Me encantaría ver una actualización del valor predeterminado de JDK, con dicho comentario sobre su implementación: D
Decodificado el
2
Realmente quiero que me guste esta respuesta, pero soy un desarrollador JavaEE, lo que significa que las matemáticas nunca fueron realmente mi punto fuerte, así que entiendo muy poco de lo que escribiste lol
searchengine27
28

¿Qué es el factor de carga?

¿La cantidad de capacidad que se debe 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 cubos estarán libres antes de que haya un aumento en la capacidad y esto hace que muchos nuevos cubos con nuevos códigos hash apunten a que existan justo después del aumento en el Número de cubos.

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

Si configura el factor de carga para que diga 1.0, puede suceder algo muy interesante.

Supongamos que está agregando un objeto x a su mapa hash cuyo código hash es 888 y en su mapa hash el depósito que representa el código hash es libre, por lo que el objeto x se agrega al depósito, pero ahora diga nuevamente 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 depósito ( porque los depósitos no son más que enlaces Implementación de lista de almacenamiento de clave, valor y siguiente ) ahora esto tiene un impacto en el rendimiento. Dado que su objeto y ya no está presente en la cabeza del cubo si realiza una búsqueda, el tiempo necesario no será O (1)esta vez depende de cuántos elementos hay en el mismo cubo. Por cierto, esto se llama colisión hash y esto incluso ocurre cuando su factor de carga es inferior a 1.

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

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

Corrígeme si estoy equivocado en alguna parte.

Sujal Mandal
fuente
2
Podría agregar un poco sobre cómo el código hash se reduce a un número con el rango de 1- {count bucket}, por lo que no es per se el número de buckets, sino que el resultado final del algoritmo hash cubre un Mayor rango. HashCode no es el algoritmo hash completo, es lo suficientemente pequeño como para volver a procesarse fácilmente. Por lo tanto, no existe el concepto de "depósitos libres", sino "número mínimo de depósitos libres", ya que podría almacenar todos sus elementos en el mismo depósito. Más bien, es el espacio clave de su código hash, que es igual a la capacidad * (1 / load_factor). 40 elementos, factor de carga 0.25 = 160 cucharones.
user1122069
Creo que el tiempo de búsqueda de un objeto del LinkedListque se conoce como Amortized Constant Execution Timey denota con un +tanO(1)+
Raf
19

De la documentación :

El factor de carga es una medida de cuán llena se permite que llegue la tabla hash antes de que se aumente automáticamente

Realmente depende de sus requisitos particulares, no existe una "regla general" para especificar un factor de carga inicial.

Óscar López
fuente
La documentación también dice; "Como regla general, el factor de carga predeterminado (.75) ofrece una buena compensación entre los costos de tiempo y espacio". Entonces, para cualquier persona que no esté segura, el valor predeterminado es una buena regla general.
ferekdoley
2

Si los cubos se llenan demasiado, entonces tenemos que mirar a través de

Una larga lista vinculada.

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 muy buena situación, ¿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. Entonces, 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 el cubo

numero 3,

Encuentro gato, sé muy rápidamente si está en nuestro

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 a las dos.

Pero al menos no tengo que mirar elefante, tejón y

gato.

Si nuevamente estoy buscando panda, solo puede estar en el cubo

número 1 y

No tengo que mirar nada más que nutria y

coala.

Pero ahora pongo cocodrilo en el cubo número 1 y puedes

mira quizás a dónde va esto.

Que 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 agregar 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 se están poniendo

muy lleno.

Está perdiendo esta ventaja de esta búsqueda completa de

elementos.

Y solo creará más cubos (generalmente el doble que antes) y

luego coloque los elementos en el cubo correcto.

Así que aquí está nuestra implementación básica de HashSet con separador

encadenamiento Ahora voy a crear un "HashSet auto-redimensionable".

Este HashSet se dará cuenta de que los cubos son

llenándose demasiado y

Necesita más cubos.

loadFactor es otro campo en nuestra clase HashSet.

loadFactor representa el número promedio de elementos por

Cubeta,

por encima del cual queremos cambiar el tamaño.

loadFactor es un equilibrio entre espacio y tiempo.

Si los cubos se llenan demasiado, cambiaremos el tamaño.

Eso lleva tiempo, por supuesto, pero

puede ahorrarnos tiempo en el futuro si los cubos son un

Un poco más vacío.

Veamos un ejemplo.

Aquí hay un HashSet, hasta ahora hemos agregado cuatro elementos.

Elefante, perro, gato y pez.

          buckets      elements
      -------      -------
        0          
        1          elephant
         2          cat ->dog
         3           fish
          4         
           5

En este punto, he decidido que loadFactor, el

límite,

el número promedio de elementos por cubo que estoy bien

con, es 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.

Redimensionaremos nuestro HashSet, es decir, agregaremos más cubos,

cuando el número promedio de elementos por cubo excede

el loadFactor.

Es entonces cuando el tamaño actual dividido por cubos. Longitud 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 establecí de 0,75, así que estamos

bueno.

No necesitamos cambiar el tamaño.

Pero ahora digamos que agregamos 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 promedio 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 excede el loadFactor que era 0.75.

Para abordar este problema, para hacer que el

cubos tal vez un poco

más vacío para que las operaciones como determinar si un

el cubo contiene

un elemento será un poco menos complejo, quiero cambiar el tamaño

mi HashSet.

Cambiar el tamaño del HashSet tiene dos pasos.

Primero doblaré el número de cubos, tuve 6 cubos,

ahora voy a tener 12 cubos.

Tenga en cuenta que el loadFactor 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 5.

5 dividido por 12 es alrededor de 0,42, eso está muy por debajo de nuestro

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.

Elefante estaba en el cubo número 2 porque el número de

personajes en elefante

fue 8.

Tenemos 6 cubos, 8 menos 6 es 2.

Por eso 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é hay de la marmota?

La marmota fue la que inició todo este problema.

La marmota 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 teníamos nuestro HashSet con encadenamiento separado que

no hizo ningún cambio de tamaño.

Ahora, aquí hay una nueva implementación donde usamos el cambio de tamaño.

La mayor parte de este código es el mismo,

todavía vamos a determinar si contiene el

valor ya.

Si no es así, entonces descubriremos qué cubeta

debería entrar y

luego agréguelo a ese cubo, agréguelo a esa LinkedList.

Pero ahora incrementamos el campo currentSize.

currentSize fue el campo que realizó un seguimiento del número

de elementos en nuestro HashSet.

Vamos a aumentarlo y luego vamos a mirar

a la carga promedio,

El número promedio de elementos por cubo.

Haremos esa división aquí abajo.

Tenemos que hacer un poco de casting aquí para asegurarnos

Que tenemos un doble.

Y luego, compararemos esa carga promedio con el campo

que he establecido como

0.75 cuando creé este HashSet, por ejemplo, que era

el loadFactor.

Si la carga promedio es mayor que el factor de carga,

eso significa que hay demasiados elementos por cubo en

promedio, y necesito reinsertarme.

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 tal como están actualmente

antes de comenzar 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 los cubos como oldBuckets.

Ahora recuerda 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 viejos cubos.

Cada elemento en oldBuckets es un LinkedList de cadenas

Eso es un balde.

Revisaré ese cubo y obtendré cada elemento en ese

Cubeta.

Y ahora lo voy a reinsertar en los nuevos Buckets.

Obtendré su hashCode.

Descubriré qué índice es.

Y ahora obtengo el nuevo cubo, la nueva LinkedList de

cuerdas y

Lo agregaré a ese nuevo cubo.

En resumen, los HashSets, como hemos visto, son matrices de Linked

Listas o cubos.

Un HashSet auto-redimensionable puede darse cuenta usando alguna relación o

Ganesh Chowdhary Sadanala
fuente
1

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 en El hardware.

Brett Greenfield
fuente