Qual é o significado do fator de carga no HashMap?

HashMap tem duas propriedades importantes: size e load factor . Eu passei pela documentação do Java e ele diz que 0.75f é o fator de carga inicial. Mas não consigo encontrar o uso real disso.

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 casos diferentes?

A documentação explica isso 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 depósitos 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 como a tabela hash é permitida antes que sua capacidade seja aumentada automaticamente. Quando o número de inputs na tabela de hash excede o produto do fator de carga e a capacidade atual, a tabela de hash é reexposta (isto é, as estruturas de dados internas são recriadas) 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 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 class HashMap, incluindo get e put). O número esperado de inputs no mapa e seu fator de carga devem ser levados em conta ao definir sua capacidade inicial, de modo a minimizar o número de operações de repetição. Se a capacidade inicial for maior que o número máximo de inputs dividido pelo fator de carga, nenhuma operação de reesca ocorrerá.

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

A capacidade inicial padrão do HashMap é 16 e o ​​fator de carga é 0.75f ​​(isto é, 75% do tamanho atual do mapa). O fator de carga representa em que nível a capacidade do HashMap deve ser duplicada.

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

Na verdade, a partir dos 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 trará um melhor desempenho. Eu acho que 0,75 provavelmente foi tirado de um chapéu.

Prova:

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

Vamos representar o tamanho e o número de chaves adicionadas. Usando o teorema binomial, 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 

Quando s atinge o infinito e se o número de chaves adicionadas é tal que P (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?

O fator de carga é por padrão 0.75 da capacidade inicial (16), portanto, 25% dos buckets serão liberados antes que haja um aumento na capacidade e isso faz com que muitos novos buckets com novos hashcodes apontem para eles existirem logo após o aumento no número de baldes.

Agora, por que você deve manter muitos baldes grátis 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 object x ao seu hashmap cujo hashCode é 888 & em seu hashmap o bucket que representa o hashcode é gratuito, então o object x é adicionado ao bucket, mas agora diz se você está adicionando outro object y cujo hashCode é também 888 então seu object y será adicionado com certeza MAS no final do intervalo ( porque os buckets são nada mais que a implementação de linkedList armazenando key, value & next ) agora isso tem um impacto no desempenho! Como seu object y não está mais presente na cabeça do bucket, se você executar uma pesquisa, o tempo gasto não será O (1), desta vez, depende de quantos itens existem no mesmo bucket. 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 carga?

Fator de carga menor = mais baldes livres = menos chances de colisão = alto desempenho = alta exigência de espaço.

Me corrija se eu estiver errado em algum lugar.

Da documentação :

O fator de carga é uma medida de como a tabela hash é permitida antes que sua capacidade seja automaticamente aumentada

Isso realmente depende de suas necessidades específicas, não há “regra geral” para especificar um fator de carga inicial.

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.