java - value - Em um hashmap, a adição de um novo elemento à lista vinculada interna de um bucket está sempre no final. Por quê?



percorrer hashmap java (1)

Porque você não pode simplesmente adicionar o elemento quando o código hash é o mesmo. Quando o código de hash é o mesmo, ele deve verificar equals na chave em cada nó da lista vinculada. Portanto, ele precisa percorrer toda a lista vinculada para verificar se já existe alguma chave igual.

Em um mapa de hash, quando temos os mesmos códigos de hash, inserimos objetos como uma lista vinculada que posteriormente são convertidos em TreeNode. Cada novo objeto com o mesmo código de hash é adicionado ao último da lista vinculada anexada. Portanto, minha pergunta aqui é por que não adicionamos o novo elemento como primeiro elemento da lista vinculada interna anexada ao bucket? Por que atravessamos até o último elemento e adicionamos o novo elemento.

Tempo gasto pela lista vinculada para:

Inserir novo elemento no início = O (1)

Inserir novo elemento no final = O (n)

Uma resposta provável pode ser, já que o hashmap não é seguro para threads, a leitura e gravação simultânea de elementos, da posição única, pode levar a anomalias. Por exemplo, existem duas transações:

T1 - adição de novo objeto ao mapa com um código hash já presente no mapa hash.

T2 - leitura de novo objeto no mapa, novamente com um código hash já presente no mapa hash.

Quando essas duas transações ocorrem simultaneamente, e começamos a adicionar os novos elementos à partida, em vez do último lugar, pode haver uma pequena probabilidade de que a operação de leitura seja afetada, devido às alterações feitas na primeira posição.

Se alguém puder ter uma idéia melhor sobre isso, comente.





hashmap