Qual é o significado do factor de carga no HashMap?

A capacidade inicial por defeito das tomadas de HashMap é de 16 e o factor de carga é de 0,75 f (isto é, 75% do tamanho actual do mapa). O Fator de carga representa a que nível a capacidade HashMap deve ser duplicada.

Por exemplo produto da capacidade e do factor de carga como 16 * 0.75 = 12. Isto representa que depois de armazenar o 12º par de valores-chave no HashMap, a sua capacidade torna-se 32.

Na verdade, pelos meus cálculos, o factor de carga "perfeito" está mais perto do log 2 (~ 0.7). Embora qualquer fator de carga menor do que isso irá produzir um melhor desempenho. Acho que sim .O 75 deve ter sido tirado de um chapéu.

Prova:

Pode evitar-se a Acorrentação e prever-se ramificações, prevendo-se se uma o balde está vazio ou não. Um balde está provavelmente vazio se a probabilidade dele estar vazio excede .5.

Vamos representar o tamanho e n o número de chaves adicionadas. Mear Binomio teorema, a probabilidade de um balde estar vazio é:

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

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

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

As s chegam ao infinito e se o número de teclas adicionadas for tal que P(0) = .5, então n/s aproxima-se log(2) rapidamente:

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

O que é o factor de carga ?

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

Porquê o factor de carga ?

Fator de Carga é, por padrão, 0.75 da capacidade inicial (16), portanto, 25% dos baldes serão livres antes que haja um aumento na capacidade e isso faz com que muitos novos baldes com novo hashcodes apontando para eles existem apenas após o aumento no número de baldes.

Agora Por que deveria você mantém muitos baldes livres & Qual é o impacto de manter baldes livres na performance ?

Se você definir o factor de carregamento para dizer 1.0, então algo muito interessante pode acontecer.

Diga que está a adicionar um objecto x ao seu hashmap cujo código de hashmap é 888 & no seu hashmap o balde que representa o código de hashcode é livre, por isso o objecto x é adicionado ao balde, mas agora diga novamente se está a adicionar outro objecto y cujo código de hashCode também é 888, então o seu objecto y irá seja adicionado com certeza, mas no final do balde (porque os baldes não são nada mais do que a chave de armazenamento de implementação linkedList,value & next) Agora isso tem um impacto de desempenho ! Uma vez que o seuobjecto y já não está presente na cabeça do balde se efectuar uma pesquisa o tempo necessário não vai serO(1) desta vez depende de quantos itens existem no mesmo balde. Isto é chamado de colisão de hash pela maneira & isto mesmo acontece quando o seu factor de carregamento é menor que 1.

Correlação entre desempenho , colisão de hash e Factor de carga ?

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

corrija-me se estiver errado em algum lugar.

Da documentação :

O factor de carga é uma medida de até que ponto a tabela de hash é permitida antes que a sua capacidade seja automaticamente aumentada

Realmente depende de suas necessidades particulares, não há "regra de ouro" para especificar um fator de carga inicial.

Para HashMap DEFAULT_ INITIAL_CAPACE = 16 e DEFAULT_ LOAD_FACTOR = 0, 75 f significa que o número máximo de todos os itens no HashMap = 16 * 0.75 = 12. Quando o décimo terceiro elemento será adicionado capacidade (tamanho da matriz) do HashMap será dobrado! 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

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

Se os baldes ficarem muito cheios, então temos de olhar para dentro.

Uma lista muito longa.

E isso está a acabar com o ponto. Eis um exemplo em que tenho quatro baldes. Tenho elefante e texugo no meu HashSet até agora. Esta é uma situação muito boa, certo?

Cada elemento tem zero ou um elemento.

Agora colocamos mais dois elementos em nosso HashSet.

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

Isto também não é assim tão mau.

Cada bucket só tem um elemento . Se eu quiser saber, isto contém panda?

Posso ver rapidamente o balde número 1 e não é

Ali e ali. Sei que não está na nossa colecção. Se quero saber se contém gato, olho para o bucket.

Número 3,

Eu encontro o gato, e muito rapidamente sei se está no nosso ... Colecção. E se eu adicionar coala, não é assim tão mau.

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

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

Um elemento,

Preciso de ver dois. Mas pelo menos Não tenho de olhar para o elefante, texugo e ... Gato. Se estou de novo à procura do panda, só pode estar no balde.

Número 1 e

Não tenho de olhar para nada além de lontra e ... Coala. Mas agora ponho jacaré no balde número 1 e tu podes. Vê onde isto vai dar. Que se o balde número 1 continuar a crescer e maior e Maior, depois tenho de ver tudo.

Esses elementos para encontrar

Algo que devia estar no balde número 1.

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

Se eu começar a adicionar cordas a outros baldes,

Certo, o problema fica cada vez maior em cada um. Um balde. Como é que impedimos que os baldes fiquem demasiado cheios?

A solução aqui é que

          "the HashSet can automatically

        resize the number of buckets."

Há a HashSet que percebe que os baldes são getting Muito cheio. Está a perder a vantagem de tudo isto.

Elementos.

E vai criar mais baldes (geralmente duas vezes mais do que antes)e ... Então coloque os elementos no balde correto. Então aqui está a nossa implementação básica com HashSet separada. Chaining. Agora vou criar um "HashSet de auto-dimensionamento". Este HashSet vai perceber que os baldes são ...

Estou a ficar demasiado cheio e

Precisa de mais baldes. O LoadFactor é outro campo da classe HashSet.

O LoadFactor representa o número médio de elementos por

Balde,

Acima do qual queremos redimensionar. O LoadFactor é um equilíbrio entre o espaço e o tempo. Se os baldes ficarem muito cheios, vamos redimensionar. Isso leva tempo, claro, mas ... Pode poupar-nos tempo se os baldes forem ... Um pouco mais vazio. Vejamos um exemplo. Aqui está uma HashSet, adicionamos quatro elementos até agora. Elefante, cão, gato e peixe.

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

Neste momento, decidi que o loadFactor, o ...

Limiar,

O número médio de elementos por balde que estou bem. Com, é 0,75. O número de baldes é de baldes.comprimento, que é 6, e Neste ponto, a nossa HashSet tem quatro elementos, por isso a

O tamanho actual é 4.

Vamos redimensionar o HashSet, ou seja, vamos adicionar mais baldes.

Quando o número médio de elementos por balde exceder

O loadFactor.

É quando o tamanho actual é dividido por baldes.o comprimento é

Maior que o loadFactor.

Neste ponto, o número médio de elementos por balde

É 4 dividido por 6.

4 Elementos, 6 baldes, é 0,67. Isso é menos do que o limiar que eu fixei de 0,75. Está bem. Não precisamos de redimensionar. Mas agora digamos que adicionamos marmota.

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

O Woodchuck acabaria no balde número 3. Neste momento, o tamanho actual é 5. E agora o número médio de elementos por balde

É o tamanho actual dividido por baldes.comprimento.

São 5 elementos divididos por 6 baldes e 0,83.

E isto excede o loadFactor que era 0,75.

Para resolver este problema, em ordem para fazer o

Baldes, talvez um pouco.

Mais vazio para que as operações gostem de determinar se um

Bucket contém

Um elemento será um pouco menos complexo, eu quero redimensionar {[[8]} A Minha HashSet.

Redimensionar a HashSet dá dois passos.

Primeiro vou duplicar o número de baldes, tinha 6 baldes, Agora vou ter 12 baldes. Note aqui que o loadFactor que programei para 0,75 permanece o mesmo.

Mas o número de baldes trocados é de 12,

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

5 dividido por 12 é cerca de 0,42, isso está bem abaixo do nosso

LoadFactor,

Então, agora estamos bem. Mas ainda não acabámos porque alguns destes elementos estão em O balde errado agora. Por exemplo, elefante.

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

Caracteres em elefante

Tinha 8 anos. Temos 6 baldes., 8 menos 6 são 2. Foi por isso que acabou no número 2. Mas agora que temos 12 baldes, 8 mod 12 é 8, por isso ... O elefante já não pertence ao balde número 2. O elefante pertence ao balde número 8. E o woodchuck? Foi o Woodchuck que começou este problema. O Woodchuck acabou no balde número 3.

Porque 9 mod 6 é 3.

Mas agora fazemos 9 mod 12. 9 mod 12 é 9, woodchuck vai para balde número 9. E vês a vantagem de tudo isto.

Agora o balde número 3 só tem dois elementos enquanto antes tinha três.

Então aqui está o nosso código. Onde tínhamos a nossa HashSet com acorrentamento separado que ... Não fiz nenhum redimensionamento. Agora, aqui está uma nova implementação onde usamos redimensionamento.

A maior parte deste código é o mesmo,

Ainda vamos determinar se contém o ...

Já tem valor.

Se for se não, então vamos descobrir qual é o balde.

Deve entrar e

Depois adiciona - o a esse balde, adiciona-o à lista de links.

Mas agora aumentamos o campo actual.

CurrentSize era o campo que mantinha o registo do número

De elementos na nossa HashSet.

Vamos incrementá-lo e depois vamos olhar.

Na carga média,

O número médio de elementos por balde.

Vamos fazer essa divisão. aqui em baixo. Temos de fazer um pouco de casting para ter a certeza. Que recebamos um duplo. E depois compararemos essa carga média com o campo.

Que eu defini como

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

O loadFactor.

Se a carga média for superior ao loadFactor,

Isso significa que há demasiados elementos por balde.

Média, e preciso de reinserir.

Então aqui está o nosso aplicação do método de resseguro Todos os elementos. Primeiro, vou criar uma variável local chamada oldBuckets. Que se refere aos baldes na sua forma actual. Antes de começar a redimensionar tudo. Note que ainda não estou a criar uma nova lista de listas ligadas. Estou a mudar o nome dos baldes para velhotes. Lembrem - se que os baldes eram um campo da nossa turma, eu vou ...

Para agora criar um novo array

De listas ligadas, mas isto terá o dobro de Elementos

Como da primeira vez. Agora preciso de fazer a reinserção. Vou passar por todos os baldes velhos. Cada elemento do oldBuckets é uma lista de cadeias de caracteres ([8]} Isso é um balde. Vou passar por aquele balde e meter cada elemento naquele ... Balde. E agora vou reinseri-lo nos novatos. Eu vou conseguir. hashCode. Vou descobrir qual é o índice. E agora tenho o novo balde, a nova lista de links de

Cordas e

Vou adicioná-lo àquele balde novo. Então, recapitulando, HashSets como vimos são matrizes de Linked {[[8]} Listas ou baldes.

Uma HashSet de auto-dimensionamento pode realizar-se usando alguma razão ou