Qual é o significado do fator de carga no HashMap?

232

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?

Priyank Doshi
fonte

Respostas:

266

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).

NPE
fonte
14
Outras respostas sugerem especificar capacity = N/0.75para evitar repetições, mas meu pensamento inicial foi definido load factor = 1. Haveria desvantagens nessa abordagem? Por que o fator de carga afetaria get()e put()os custos operacionais?
Supermitch #
19
Um fator de carga = 1 mapa de hash com número de entradas = capacidade estatisticamente terá uma quantidade significativa de colisões (= quando várias chaves estiverem produzindo o mesmo hash). Quando ocorre uma colisão, o tempo de pesquisa aumenta, pois em um depósito haverá> 1 entradas correspondentes, para as quais a chave deve ser verificada individualmente quanto à igualdade. Algumas matemáticas detalhadas: preshing.com/20110504/hash-collision-probabilities
atimb
8
Não estou seguindo você @atimb; A propriedade loadset é usada apenas para determinar quando aumentar o tamanho do armazenamento, certo? - Como ter um conjunto de carga de um aumentaria a probabilidade de colisões de hash? - O algoritmo de hash não tem conhecimento de quantos itens estão no mapa ou com que frequência adquire novos "buckets" de armazenamento, etc. Para qualquer conjunto de objetos do mesmo tamanho, independentemente de como eles são armazenados, você deve ter o mesma probabilidade de valores de hash repetidas ...
BrainSlugs83
19
A probabilidade de colisão de hash é menor, se o tamanho do mapa for maior. Por exemplo, elementos com códigos de hash 4, 8, 16 e 32 serão colocados no mesmo bloco, se o tamanho do mapa for 4, mas cada item terá um próprio bloco, se o tamanho do mapa for maior que 32. O mapa com tamanho inicial 4 e fator de carga 1.0 (4 caçambas, mas todos os 4 elementos em uma única caçamba) será neste exemplo, em média, duas vezes mais lento que outro com o fator de carga 0,75 (8 caçambas, duas caçambas cheias - com o elemento "4" e com os elementos "8", "16", "32").
30thh
1
O custo da @Adelin Lookup é aumentado por fatores de carga mais altos, porque haverá mais colisões por valores mais altos, e a maneira como o Java lida com colisões é colocando os itens com o mesmo código de hash no mesmo bucket usando uma estrutura de dados. A partir do Java 8, essa estrutura de dados é uma árvore de pesquisa binária. Isso torna a pior complexidade de tempo de pesquisa O (lg (n)) com a pior ocorrência possível se todos os elementos adicionados tiverem o mesmo código de hash.
Gigi Bayte 2
141

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.

user2791282
fonte
3
Embora sua resposta seja clara, você pode dizer se, após armazenar 12 pares de valores-chave, a capacidade se torna 32 ou é que, quando a 13ª entrada é adicionada, nesse momento a capacidade muda e a entrada é inserida.
userab
isso significa que o número de buckets é aumentado em 2?
LoveMeow 28/09
39

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...
Olá Mundo
fonte
4
Nerds de matemática FTW! Provavelmente o .75foi arredondado para a fração mais fácil de entender log(2)e parece menos com um número mágico. Eu adoraria ver uma atualização do valor padrão do JDK, com o referido comentário acima de sua implementação: D
Decodificado
2
Eu realmente quero como esta resposta, mas eu sou um desenvolvedor de JavaEE, o que significa matemática nunca foi realmente o meu forte, então eu entendo muito pouco do que você escreveu lol
searchengine27
28

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.

Sujal Mandal
fonte
2
Você pode adicionar um pouco sobre como o hashCode é reduzido a um número com o intervalo de 1- {count bucket} e, portanto, não é o número de buckets per se, mas o resultado final do algoritmo de hash abrange um maior alcance. O HashCode não é o algoritmo completo de hash, é pequeno o suficiente para ser facilmente processado novamente. Portanto, não há conceito de "baldes livres", mas "número mínimo de baldes livres", pois você pode armazenar todos os seus elementos no mesmo balde. Em vez disso, é o espaço-chave do seu código de hash, que é igual à capacidade * (1 / load_factor). 40 elementos, fator de carga de 0,25 = 160 baldes.
user1122069
Eu acho que o tempo de pesquisa para um objeto do LinkedListé referido como Amortized Constant Execution Timee denotado com um +asO(1)+
Raf
19

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.

Óscar López
fonte
A documentação também diz; "Como regra geral, o fator de carga padrão (0,75) oferece uma boa compensação entre os custos de tempo e espaço.". Portanto, para quem não tem certeza, o padrão é uma boa regra de ouro.
Ferekdoley 6/07
4

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 insira a descrição da imagem aqui imagem é tirada daqui:

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

provisota
fonte
2

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

Ganesh Chowdhary Sadanala
fonte
1

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.

Brett Greenfield
fonte