Rehashing no Hashmap [fechado]
A capacidade inicial e fator de carga dois parâmetros que afetam oHashMap
desempenho. O fator de carga padrão (.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.
Quando um item é adicionado aoHashMap
, ele é atribuído a um intervalo com base em um valor derivado dehashCode
e o tamanho do balde doHashMap
. Para identificar o intervalo para qualquer, use o mapa Hashkey.hashCode()
e execute alguma operação:
Bucket (index) = HashMap.indexFor(HashMap.hash(key.hashCode()),
entryArray.length)
Quando o número de entradas no mapa hash excede o produto do fator de carga e a capacidade atual, o mapa hash é reexecutado (estruturas de dados internas são reconstruídas), de modo que o mapa hash tenha aproximadamente o dobro do número de depósitos.
Quando você repassa e move tudo para um novo local (bucket, etc.), os elementos mais antigos também são reexecutados novamente e armazenados no novo bucket de acordo com seus novos códigos de hash. O espaço antigo que foi alocado para armazenar os elementos é coletado como lixo.
Se duas linhas ao mesmo tempo descobrissem que agoraHashMap
precisa redimensionar e ambos tentam redimensionar pode causar condição de corrida emHashMap
.
No processo de redimensionamento deHashMap
, o elemento no bucket que é armazenado na lista vinculada é revertido em ordem durante a migração para o novo bucket porque javaHashMap
não acrescenta o novo elemento na cauda, em vez disso, acrescenta um novo elemento na cabeça para evitar a passagem da cauda. Se a condição de corrida acontecer, você terminará com um loop infinito.
Eu tenho as seguintes perguntas:
Por que a lista vinculada de cada depósito é revertida em ordem durante a migração para o novo intervalo?Como condição de corrida pode levar a loop infinito?Como o aumento do número de depósitos pode diminuir o tempo de espera da pesquisa?Elementos que estão no mesmo balde ainda estarão juntos no mesmo balde após rehashing?