Como funciona o HashMap em Java

A maioria de vocês concordará que HashMap, hoje, é o tópico preferido para discussão durante as entrevistas. Às vezes, tive discussões semelhantes com meus colegas e isso realmente ajudou. Agora terei essa discussão com você. Presumo que se você estiver interessado nos detalhes internos e no funcionamento do HashMap, então já está familiarizado com os fundamentos do HashMap , então pularei essa parte. Mas se você é novo nisso, sugiro que acesse o site Java Docs . Antes de prosseguirmos, recomendo fortemente que você leia meu artigo anterior: Trabalhando com hashCode e o método equals em Java. Conteúdo deste artigo:

1. A única resposta possível.
2. O que é hash.
3. Um pouco sobre a aula Entry.
4. O que faz o put().
5. Como funciona o método get().
6. Notas

A única resposta possível

Se alguém me pedir para explicar " Como funciona o HashMap?" ", responderei simplesmente: " De acordo com os princípios do Hashing ." Não poderia ser mais simples. Para entender isso e obter uma resposta extensa, você precisa ter certeza de que conhece os fundamentos do Hashing. Certo?

O que é hash

Hashing em sua forma mais simples é uma forma de converter qualquer variável/objeto em um código único após aplicar qualquer fórmula/algoritmo às suas propriedades. Uma função hash verdadeira deve seguir a seguinte regra: Uma função hash deve retornar o mesmo código hash sempre que for aplicada a objetos iguais ou iguais. Em outras palavras, dois objetos idênticos devem retornar os mesmos códigos hash por sua vez. Você pode ler mais sobre isso aqui: Trabalhando com hashCode e método equals em Java

Um pouco sobre a aula Entry

Por definição, um mapa é “um objeto que armazena valores e chaves em pares”. Muito simples, certo? Então, deve haver algum tipo de mecanismo no HashMap que armazene pares de Valores e Chaves? Resposta - Sim. HashMaptem uma classe interna Entryparecida com esta:

static class Entry implements Map.Entry
{
        final K key;
        V value;
        Entry next;
        final int hash;
        ...//остальной code тут…
}

Naturalmente, a classe Entrypossui uma chave e um valor armazenados como atributos. A chave está marcada como finale também vemos dois campos adicionais: nexte hash. Tentaremos entender a finalidade desses campos à medida que o artigo avança.

O que o método Java put() faz?

Antes de mergulharmos na implementação do método put(), é muito importante entender que as instâncias de uma classe Entrysão armazenadas em um array. A classe HashMap define esta variável como:

/**
* Размер таблицы, изменяется при необходимости. Длина всегда должна быть
* кратна двум!
*/
    transient Entry[] table;

Agora dê uma olhada no código de implementação do método put():

/**
* Связывает определенное meaning с определенным ключом в этой карте(map).
* Если карта перед этим содержала meaning для данного ключа, это meaning
* заменится на новое.
*
* @param key
*            ключ с которым указанное meaning должно быть связано.
* @param value
*            meaning которое должно быть связано с ключом.
* @return вернет предыдущее meaning связанное с key, or null
*         если не было значений связанных с key. (Вернет null
*         так же, если перед этим key был связан со meaningм null)
*/
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<k , V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}

modCount++;
addEntry(hash, key, value, i);
return null;
}

Vamos descobrir passo a passo:

• Em primeiro lugar, verificamos se a chave existe. Se a chave não existir ( null), o valor será colocado na tabela na posição zero porque o código hash do valor é null, это – всегда 0.


• Na próxima etapa, o valor hash é calculado usando o código hash da chave obtida pela chamada do método hashCode(). Este valor hash é usado para calcular a posição no array onde o objeto será colocado Entry. Os projetistas do JDK presumiram que uma função mal escrita hashCode()poderia retornar um valor de hash muito alto ou muito baixo. Para resolver esse problema, eles introduziram outra hash()função e passaram o valor hash de um objeto para ela para fazer com que o valor hash correspondesse ao tamanho do array.


• Agora a função é chamada indexFor(hash, table.length)para calcular a posição exata onde o objeto será colocado Entry.


• É aqui que começa a parte principal. Agora, com base no que sabemos que - dois objetos desiguais podem ter códigos hash iguais, fazemos a pergunta: Dois objetos diferentes serão colocados na mesma posição no array [bucket] LinkedList? Se você se lembra, a classe Entrypossui um atributo " next". Este atributo sempre aponta para o próximo objeto da cadeia. Este é exatamente o comportamento LinkedList.

Portanto, os objetos Entrysão armazenados no formato LinkedList. Quando um objeto Entrydeve ser colocado em um local específico, o HashMap verifica se já existe uma entrada nesse local. Se não houver entrada, o objeto será colocado nesta posição. Se, entretanto, já existir um objeto nesta posição, o próximo atributo será verificado. Se ele retornar nulle o objeto atual Entryse tornar o próximo link no arquivo LinkedList. Se a próxima variável não for null, o procedimento é repetido para a próxima até encontrar null. E se colocarmos outro objeto com valor diferente, mas com a mesma chave de antes? Logicamente, isso deve resultar na substituição do valor antigo. Como isso acontece? Em geral, após determinar a posição de um objeto Entry, ao percorrer LinkedListaté a posição calculada, HashMapele chama o método de comparação chave para cada objeto Entry. Todos esses Entryobjetos LinkedListpodem ter códigos hash semelhantes, mas o método equals()verificará a verdadeira semelhança. Isso substituirá apenas o valor dentro do arquivo Entry. Assim, o HashMap garante a exclusividade de todas as chaves.

Como funciona o método Java get()?

Agora temos uma ideia de como os pares de valores-chave são armazenados em arquivos HashMap. A próxima grande questão é: O que acontece quando um objeto é passado de um HashMap para um método get()? Como é determinado o valor de um objeto? Já deveríamos saber a resposta, pois a forma como a unicidade de uma chave é determinada no método put()tem a mesma lógica que o método aplica get(). Depois de HashMapdeterminar a chave do objeto passado como argumento, ele simplesmente retorna o valor do arquivo Entry. Se nenhuma correspondência for encontrada, o método get()retornará null. Vamos dar uma olhada no código:

public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<k,V>e=table[indexFor(hash,table.length)];e!=null;e=e.next){
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}

O código acima é semelhante ao método put()até agora if (e.hash == hash && ((k = e.key) == key || key.equals(k))), depois disso ele simplesmente retorna o valor do objeto.

Notas

• A estrutura de dados a ser armazenada em um objeto Entryé um array com um nome tablee um tipo Entry.
• Cada posição individual na matriz é chamada de bucket porque pode conter o primeiro elemento LinkedListdos objetos Entry.
• hashCode()A chave é necessária para calcular a posição do objeto Entry.
• equals()A chave é usada para verificar a exclusividade da chave no mapa ( map).
• hashCode()e equals()Valores não são usados ​​em métodos get()e set()em HashMap.
• O código hash para chaves com valor nullé sempre 0. E tal objeto Entrysempre será armazenado na posição zero do array.

Espero ter transmitido meus pensamentos corretamente neste artigo. Se você encontrar erros ou tiver dúvidas, deixe-os nos comentários. Feliz aprendizado!