Geekly articles weekly

HashMap interno em Java

[nota do autor da tradução] A tradução foi feita para as próprias necessidades, mas se for útil para alguém, o mundo se tornará pelo menos um pouco, mas melhor! Artigo original - Trabalho interno do HashMap em Java


Neste artigo, veremos como os métodos get e put na coleção HashMap funcionam internamente. Quais operações são executadas. Como o hash acontece. Como o valor é recuperado pela chave. Como os pares de valores-chave são armazenados?


Como no artigo anterior , o HashMap contém uma matriz de Nó e o Nó pode representar uma classe que contém os seguintes objetos:


  1. int - hash
  2. K é a chave
  3. V é o valor
  4. Nó - próximo item

Agora vamos ver como tudo funciona. Primeiro, veremos o processo de hash.


Hashing


Hashing é o processo de conversão de um objeto em um formulário inteiro, realizado usando o método hashCode (). É muito importante implementar corretamente o método hashCode () para garantir o melhor desempenho da classe HashMap.


Aqui eu uso minha própria classe Key e, dessa forma, posso substituir o método hashCode () para demonstrar vários scripts. Minha classe Key:


//   Key    hashCode() //  equals() class Key { String key; Key(String key) { this.key = key; } @Override public int hashCode() { return (int)key.charAt(0); } @Override public boolean equals(Object obj) { return key.equals((String)obj); } }

Aqui, o método hashCode () substituído retorna o código ASCII do primeiro caractere da string. Portanto, se os primeiros caracteres da string forem os mesmos, os códigos de hash serão os mesmos. Não use lógica semelhante em seus programas.


Este código é apenas para fins de demonstração. Como o HashCode aceita uma chave nula, o código de hash nulo sempre será 0.


Método HashCode ()


O método hashCode () é usado para obter o código de hash do objeto. O método hashCode () da classe Object retorna uma referência de memória inteira (código de hash de identidade ). A assinatura do método public native hashCode() . Isso sugere que o método é implementado como nativo, porque em java não há método para obter uma referência ao objeto. É permitido definir sua própria implementação do método hashCode (). Na classe HashMap, o método hashCode () é usado para calcular o bucket e, portanto, calcular o índice.


Método Equals ()


O método equals é usado para testar dois objetos quanto à igualdade. O método é implementado na classe Object. Você pode substituí-lo em sua própria classe. Na classe HashMap, o método equals () é usado para verificar a igualdade das chaves. Caso as chaves sejam iguais, o método equals () retorna true, caso contrário false.


Cestas


Bucket é o único elemento da matriz HashMap. É usado para armazenar nós (nós). Dois ou mais nós podem ter o mesmo bucket. Nesse caso, uma estrutura de dados de lista vinculada é usada para vincular nós. As caçambas diferem em capacidade (propriedade de capacidade). A relação entre caçamba e capacidade é a seguinte:


 capacity = number of buckets * load factor

Um bucket pode ter mais de um nó, depende da implementação do método hashCode (). Quanto melhor o método hashCode () for implementado, melhor o seu bucket será usado.


Cálculo do índice HashMap


O código de hash da chave pode ser grande o suficiente para criar uma matriz. O código hash gerado pode estar no intervalo de um tipo inteiro e, se criarmos uma matriz desse tamanho, podemos obter facilmente uma outOfMemoryException. Portanto, geramos um índice para minimizar o tamanho da matriz. Essencialmente, a seguinte operação é executada para calcular o índice:


 index = hashCode(key) & (n-1).

onde n é igual ao número de bucket ou ao valor do comprimento da matriz. No nosso exemplo, considero n como o valor padrão de 16.


  • hashMap inicialmente vazio: aqui o tamanho do hashmap é 16:

 HashMap map = new HashMap();

HashMap:


  • inserir pares Chave - Valor: adicione um valor - chave de par ao final do HashMap

 map.put(new Key("vishal"), 20);

Passos:


  1. Calcule o valor da chave {"vishal"}. Será gerado como 118.


  2. Calcule o índice usando o método index , que será 6.


  3. Crie um objeto de nó.


     { int hash = 118 // {"vishal"}  ,  //   Key Key key = {"vishal"} Integer value = 20 Node next = null }

  4. Coloque o objeto na posição com o índice 6, se o espaço estiver livre.



O HashMap agora se parece com isso:



  • adicionando outro par de valores-chave: agora adicione outro par

 map.put(new Key("sachin"), 30);

Passos:


  1. Calcule o valor da chave {"sachin"}. Será gerado como 115.


  2. Calcule o índice usando o método index , que será 3.


  3. Crie um objeto de nó.


     { int hash = 115 Key key = {"sachin"} Integer value = 30 Node next = null }

  4. Coloque o objeto na posição com o índice 3, se o espaço estiver livre.



O HashMap agora se parece com isso:



  • em caso de colisão: agora adicione outro par

 map.put(new Key("vaibhav"), 40);

Passos:


  1. Calcule o valor da chave {"vaibhav"}. Será gerado como 118.


  2. Calcule o índice usando o método index , que será 6.


  3. Crie um objeto de nó.


     { int hash = 118 Key key = {"vaibhav"} Integer value = 20 Node next = null }

  4. Coloque o objeto na posição com o índice 6, se o espaço estiver livre.


  5. Nesse caso, já existe outro objeto na posição com o índice 6, esse caso é chamado de colisão.


  6. Nesse caso, verifique com os métodos hashCode () e equals () se as duas chaves são iguais.


  7. Se as chaves forem iguais, substitua o valor atual por um novo.


  8. Caso contrário, vincule os objetos novos e antigos usando a estrutura de dados "lista vinculada", especificando um link para o próximo objeto no atual e salve ambos no índice 6.



O HashMap agora se parece com isso:



[nota do autor da tradução] A imagem é retirada do artigo original e contém inicialmente um erro. A referência ao próximo objeto no objeto visual com índice 6 não é nula, contém um ponteiro para o objeto vaibhav.


  • obtemos o valor pela chave sachin:

 map.get(new Key("sachin"));

Passos:


  1. Calcule o código de hash do objeto {{sachin »}. Foi gerado como 115.


  2. Calcule o índice usando o método index , que será 3.


  3. Vá para o índice 3 e compare a chave do primeiro elemento com o valor existente. Se forem iguais, gire o valor, caso contrário, verifique o próximo elemento, se ele existir.


  4. No nosso caso, o elemento é encontrado e o valor de retorno é 30.



  • obtemos o valor pela chave vaibahv:

 map.get(new Key("vaibhav"));

Passos:


  1. Calcule o código de hash do objeto {"vaibhav"}. Foi gerado como 118.


  2. Calcule o índice usando o método index , que será 6.


  3. Vá para o índice 6 e compare a chave do primeiro elemento com o valor existente. Se forem iguais, gire o valor, caso contrário, verifique o próximo elemento, se ele existir.


  4. Nesse caso, ele não foi encontrado e o próximo objeto do nó não é nulo.


  5. Se o próximo objeto do nó for nulo, retorne nulo.


  6. Se o próximo objeto do nó não for nulo, vá para ele e repita as três primeiras etapas até que o elemento seja encontrado ou o próximo objeto do nó seja nulo.



 // Java    //   HashMap import java.util.HashMap; class Key { String key; Key(String key) { this.key = key; } @Override public int hashCode() { int hash = (int)key.charAt(0); System.out.println("hashCode for key: " + key + " = " + hash); return hash; } @Override public boolean equals(Object obj) { return key.equals(((Key)obj).key); } } // Driver class public class GFG { public static void main(String[] args) { HashMap map = new HashMap(); map.put(new Key("vishal"), 20); map.put(new Key("sachin"), 30); map.put(new Key("vaibhav"), 40); System.out.println(); System.out.println("Value for key sachin: " + map.get(new Key("sachin"))); System.out.println("Value for key vaibhav: " + map.get(new Key("vaibhav"))); } }

Conclusão:


 hashCode for key: vishal = 118 hashCode for key: sachin = 115 hashCode for key: vaibhav = 118 hashCode for key: sachin = 115 Value for key sachin: 30 hashCode for key: vaibhav = 118 Value for key vaibhav: 40

Mudanças no Java 8


Como já sabemos no caso de colisões, o objeto nó é armazenado na estrutura de dados da "lista vinculada" e o método equals () é usado para comparar chaves. Essas são comparações para encontrar a chave certa em uma lista vinculada - uma operação linear e, no pior caso, a complexidade é O (n) .


Para corrigir esse problema no Java 8, após atingir um determinado limite, árvores balanceadas são usadas em vez de listas vinculadas. Isso significa que o HashMap no início salva os objetos em uma lista vinculada, mas depois que o número de elementos no hash atinge um determinado limite, ocorre uma transição para árvores balanceadas. O que melhora o desempenho, na pior das hipóteses, de O (n) para O (log n).


Ponto importante


  1. A complexidade das operações get () e put () é quase constante até que o re-hash seja executado.
  2. Em caso de colisão, se os índices de dois ou mais objetos de nó forem iguais, os objetos de nó serão conectados usando uma lista vinculada, ou seja, o link para o segundo objeto do nó é armazenado no primeiro, para o terceiro no segundo, etc.
  3. Se a chave fornecida já existir no HashMap, o valor será substituído.
  4. O código de hash nulo é 0.
  5. Quando um objeto é obtido pela chave, as transições na lista vinculada ocorrem até que o objeto seja encontrado ou o link para o próximo objeto seja nulo.

Source: https://habr.com/ru/post/pt421179/

More articles:


All Articles