Qual é o significado do fator de carga no HashMap?

HashMaptem duas propriedades importantes: sizee load factor. Examinei a documentação do Java e diz que 0.75fé o fator de carga inicial. Mas não consigo encontrar o uso real dele.

Alguém pode descrever quais são os diferentes cenários em que precisamos definir o fator de carga e quais são alguns exemplos de valores ideais para diferentes casos?

A documentação explica muito bem:

Uma instância do HashMap possui dois parâmetros que afetam seu desempenho: capacidade inicial e fator de carga. A capacidade é o número de buckets na tabela de hash e a capacidade inicial é simplesmente a capacidade no momento em que a tabela de hash é criada. O fator de carga é uma medida de quão cheia é permitida a tabela de hash antes que sua capacidade seja aumentada automaticamente. Quando o número de entradas na tabela de hash excede o produto do fator de carga e a capacidade atual, a tabela de hash é refeita novamente (ou seja, as estruturas de dados internas são reconstruídas) para que a tabela de hash tenha aproximadamente o dobro do número de buckets.

Como regra geral, o fator de carga padrão (0,75) oferece uma boa compensação entre os custos de tempo e espaço. Valores mais altos diminuem a sobrecarga de espaço, mas aumentam o custo de pesquisa (refletido na maioria das operações da classe HashMap, incluindo get e put). O número esperado de entradas no mapa e seu fator de carga devem ser levados em consideração ao definir sua capacidade inicial, de modo a minimizar o número de operações de rehash. Se a capacidade inicial for maior que o número máximo de entradas divididas pelo fator de carga, nenhuma operação de repetição será realizada.

Como em todas as otimizações de desempenho, é uma boa idéia evitar otimizar as coisas prematuramente (ou seja, sem dados concretos sobre onde estão os gargalos).

A capacidade inicial padrão das HashMaptomadas é 16 e o ​​fator de carga é 0,75f (ou seja, 75% do tamanho atual do mapa). O fator de carga representa em que nível a HashMapcapacidade deve ser dobrada.

Por exemplo, produto de capacidade e fator de carga como 16 * 0.75 = 12. Isso representa que, após armazenar o 12º par de valores-chave no HashMap, sua capacidade se torna 32.

Na verdade, pelos meus cálculos, o fator de carga "perfeito" está mais próximo do log 2 (~ 0,7). Embora qualquer fator de carga menor que isso traga melhor desempenho. Eu acho que 0,75 provavelmente foi tirado do chapéu.

Prova:

O encadeamento pode ser evitado e a previsão de ramificação explorada, prevendo se um bucket está vazio ou não. Um balde provavelmente está vazio se a probabilidade de estar vazio exceder 0,5.

Vamos representar o tamanho en o número de chaves adicionadas. Usando o teorema do binômio, a probabilidade de um balde estar vazio é:

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

Portanto, um balde provavelmente está vazio se houver menos de

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

Quando s atinge o infinito e se o número de chaves adicionadas for tal que P (0) = 0,5, então n / s se aproxima do log (2) rapidamente:

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

O que é fator de carga?

A quantidade de capacidade que deve ser esgotada para o HashMap aumentar sua capacidade?

Por que fator de carga?

Por padrão, o fator de carga é 0,75 da capacidade inicial (16), portanto, 25% dos baldes estarão livres antes que haja um aumento na capacidade e isso faz com que muitos novos baldes com novos códigos de hash apontem para eles logo após o aumento no número de baldes.

Agora, por que você deve manter muitos baldes gratuitos e qual é o impacto de manter baldes livres no desempenho?

Se você definir o fator de carregamento para dizer 1,0, algo muito interessante poderá acontecer.

Digamos que você esteja adicionando um objeto x ao seu hashmap cujo hashCode seja 888 e, no seu hashmap, o bucket que representa o hashcode esteja livre, portanto o objeto x será adicionado ao bucket, mas agora diga novamente se você está adicionando outro objeto y cujo hashCode é também 888, seu objeto y será adicionado com certeza, MAS no final do bucket ( porque os buckets nada mais são do que chave de armazenamento de implementação vinculada, lista, valor e próximo ) agora isso tem um impacto no desempenho! Como seu objeto y não está mais presente na cabeça do balde, se você realizar uma pesquisa, o tempo necessário não será O (1)dessa vez, depende de quantos itens existem no mesmo balde. A propósito, isso é chamado de colisão de hash e isso acontece mesmo quando o fator de carregamento é menor que 1.

Correlação entre desempenho, colisão de hash e fator de carregamento?

Menor fator de carga = mais caçambas livres = menos chances de colisão = alto desempenho = alto requisito de espaço.

Corrija-me se eu estiver errado em algum lugar.

A partir da documentação :

O fator de carga é uma medida de quão cheia é permitida a tabela de hash antes que sua capacidade seja aumentada automaticamente

Realmente depende de seus requisitos específicos, não há uma "regra de ouro" para especificar um fator de carga inicial.

Para o HashMap DEFAULT_INITIAL_CAPACITY = 16 e DEFAULT_LOAD_FACTOR = 0,75f , significa que o número MAX de TODAS as entradas no HashMap = 16 * 0,75 = 12 . Quando o décimo terceiro elemento for adicionado, a capacidade (tamanho da matriz) do HashMap será dobrada! A ilustração perfeita respondeu a esta pergunta: a imagem é tirada daqui:

https://javabypatel.blogspot.com/2015/10/what-is-load-factor-and-rehashing-in-hashmap.html

Se os baldes ficarem muito cheios, temos que olhar através

uma lista vinculada muito longa.

E isso é meio que derrotar o ponto.

Então, aqui está um exemplo em que tenho quatro baldes.

Eu tenho elefante e texugo no meu HashSet até agora.

Esta é uma situação muito boa, certo?

Cada elemento possui zero ou um elemento.

Agora, colocamos mais dois elementos em nosso HashSet.

     buckets      elements
      -------      -------
        0          elephant
        1          otter
         2          badger
         3           cat

Isso também não é tão ruim.

Todo depósito possui apenas um elemento. Então, se eu quero saber, isso contém panda?

Eu posso olhar muito rapidamente para o balde número 1 e não é

lá e

Eu sabia que não está em nossa coleção.

Se eu quero saber se ele contém gato, eu olho no balde

número 3,

Encontro gato, sei muito rapidamente se está no nosso

coleção.

E se eu adicionar coala, bem, isso não é tão ruim.

             buckets      elements
      -------      -------
        0          elephant
        1          otter -> koala 
         2          badger
         3           cat

Talvez agora, em vez de no balde número 1, apenas olhando

um elemento

Eu preciso olhar para duas.

Mas pelo menos eu não tenho que olhar para elefante, texugo e

gato.

Se eu estiver novamente procurando por panda, ele só pode estar no balde

número 1 e

Eu não tenho que olhar para outra coisa senão lontra e

coala.

Mas agora eu coloquei jacaré no balde número 1 e você pode

veja talvez para onde isso está indo.

Que se o balde número 1 estiver ficando cada vez maior e maior

maior, então eu basicamente tenho que olhar através de todos

esses elementos para encontrar

algo que deve estar no balde número 1.

            buckets      elements
      -------      -------
        0          elephant
        1          otter -> koala ->alligator
         2          badger
         3           cat

Se eu começar a adicionar strings a outros buckets,

certo, o problema se torna cada vez maior a cada

balde único.

Como impedimos que nossos baldes fiquem cheios demais?

A solução aqui é que

          "the HashSet can automatically

        resize the number of buckets."

Há o HashSet percebe que os baldes estão recebendo

muito cheio.

Está perdendo essa vantagem dessa busca única por

elementos.

E apenas criará mais buckets (geralmente duas vezes mais do que antes) e

depois coloque os elementos no balde correto.

Então, aqui está nossa implementação básica do HashSet com

encadeamento. Agora vou criar um "HashSet com redimensionamento automático".

Este HashSet vai perceber que os baldes estão

ficando muito cheio e

precisa de mais baldes.

loadFactor é outro campo em nossa classe HashSet.

loadFactor representa o número médio de elementos por

balde,

acima do qual queremos redimensionar.

loadFactor é um equilíbrio entre espaço e tempo.

Se os baldes ficarem muito cheios, redimensionaremos.

Isso leva tempo, é claro, mas

pode economizar tempo na estrada se os baldes forem um

um pouco mais vazio.

Vamos ver um exemplo.

Aqui está um HashSet, adicionamos quatro elementos até agora.

Elefante, cachorro, gato e peixe.

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

Neste ponto, eu decidi que o loadFactor, o

limite,

o número médio de elementos por bloco que eu estou bem

com, é 0,75.

O número de buckets é buckets.length, que é 6 e

Nesse ponto, nosso HashSet possui quatro elementos, portanto, o

o tamanho atual é 4.

Redimensionaremos nosso HashSet, ou seja, adicionaremos mais buckets,

quando o número médio de elementos por bloco exceder

o loadFactor.

É quando o tamanho atual dividido por buckets.length é

maior que loadFactor.

Nesse ponto, o número médio de elementos por bucket

é 4 dividido por 6.

4 elementos, 6 baldes, ou seja, 0,67.

Isso é menor que o limite que eu defini de 0,75, então estamos

OK.

Não precisamos redimensionar.

Mas agora vamos dizer que adicionamos marmota.

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

A marmota acabaria no balde número 3.

Neste ponto, o currentSize é 5.

E agora o número médio de elementos por bucket

é o currentSize dividido por buckets.length.

São 5 elementos divididos por 6 depósitos: 0,83.

E isso excede o loadFactor que foi de 0,75.

Para resolver este problema, a fim de tornar o

baldes talvez um pouco

mais vazio, de modo que operações como determinar se um

balde contém

um elemento será um pouco menos complexo, eu quero redimensionar

meu HashSet.

O redimensionamento do HashSet leva duas etapas.

Primeiro vou dobrar o número de baldes, eu tinha 6 baldes,

agora eu vou ter 12 baldes.

Observe aqui que o loadFactor que defini como 0,75 permanece o mesmo.

Mas o número de buckets alterados é 12,

o número de elementos permaneceu o mesmo, é 5.

5 dividido por 12 é de cerca de 0,42, isso está bem sob nossa

loadFactor,

então estamos bem agora.

Mas não terminamos porque alguns desses elementos estão em

o balde errado agora.

Por exemplo, elefante.

Elefante estava no balde número 2 porque o número de

personagens em elefante

tinha 8 anos

Temos 6 baldes, 8 menos 6 é 2.

Por isso, acabou no número 2.

Mas agora que temos 12 baldes, 8 mod 12 é 8, então

o elefante não pertence mais ao balde número 2.

O elefante pertence ao balde número 8.

E a marmota?

Foi a marmota que iniciou todo esse problema.

A marmota acabou no balde número 3.

Porque 9 mod 6 é 3.

Mas agora fazemos 9 mod 12.

9 mod 12 é 9, a marmota vai para o balde número 9.

E você vê a vantagem de tudo isso.

Agora, o balde número 3 tem apenas dois elementos, enquanto antes tinha 3.

Então aqui está o nosso código,

onde tivemos nosso HashSet com encadeamento separado

não redimensionou.

Agora, aqui está uma nova implementação em que usamos o redimensionamento.

A maior parte desse código é a mesma,

ainda vamos determinar se ele contém o

valor já.

Se não, então vamos descobrir qual balde

deve entrar e

em seguida, adicione-o a esse bucket, adicione-o a esse LinkedList.

Mas agora incrementamos o campo currentSize.

currentSize era o campo que acompanhava o número

de elementos em nosso HashSet.

Vamos incrementá-lo e depois vamos olhar

na carga média,

o número médio de elementos por bloco.

Nós vamos fazer essa divisão aqui em baixo.

Temos que fazer um pouco de casting aqui para garantir

que temos um duplo.

E então, compararemos essa carga média com o campo

que eu coloquei como

0,75 quando criei este HashSet, por exemplo, que era

o loadFactor.

Se a carga média for maior que o loadFactor,

isso significa que há muitos elementos por balde no

média e preciso reinserir.

Então aqui está a nossa implementação do método para reinserir

todos os elementos

Primeiro, vou criar uma variável local chamada oldBuckets.

Que se refere aos baldes como estão atualmente

antes de começar a redimensionar tudo.

Nota: ainda não estou criando uma nova matriz de listas vinculadas.

Estou apenas renomeando baldes como oldBuckets.

Agora lembre-se de baldes era um campo em nossa classe, eu vou

agora criar uma nova matriz

de listas vinculadas, mas isso terá o dobro de elementos

como fez a primeira vez.

Agora eu preciso fazer a reinserção,

Vou percorrer todos os baldes antigos.

Cada elemento em oldBuckets é um LinkedList de strings

isso é um balde.

Vou passar por esse balde e obter cada elemento nesse

balde.

E agora vou reinseri-lo nos newBuckets.

Vou receber o seu hashCode.

Vou descobrir qual é o índice.

E agora eu recebo o novo balde, o novo LinkedList de

cordas e

Vou adicioná-lo a esse novo balde.

Então, para recapitular, o HashSets como vimos são matrizes de Linked

Listas ou baldes.

Um HashSet com redimensionamento automático pode ser realizado usando alguma taxa ou

Eu escolheria um tamanho de tabela de n * 1,5 ou n + (n >> 1), isso daria um fator de carga de .66666 ~ sem divisão, o que é lento na maioria dos sistemas, especialmente em sistemas portáteis onde não há divisão em o hardware.