HashMap Interenal Working

HashMap é uma estrutura de dados que armazena os dados em pares (chave, valor), semelhante ao Dicionário em python, se você estiver nessa!

Para entender o funcionamento interno do Hashmap, vamos nos familiarizar com os seguintes termos:

HASHING:
Hashing é o processo de converter uma determinada chave em outro valor baseado em uma fórmula usando uma função. Uma função hash é usada para gerar o novo valor de acordo com um algoritmo matemático. O resultado de uma função hash é conhecido como um valor hash ou simplesmente, um hash. Ela é usada para indexar e recuperar itens e para
algoritmos de criptografia.

Uma função hash verdadeira deve seguir esta regra –

“Função hash deve retornar o mesmo código hash toda vez que a função for aplicada em objetos iguais ou iguais. Em outras palavras, dois objetos iguais devem produzir o mesmo código hash consistentemente”

Todos os objetos em Java herdam uma implementação padrão da função hashCode() definida na classe Object.

COLLISIONS :
Calcance em mente que duas chaves podem gerar o mesmo hash que pode levar ao mesmo endereço. Este fenômeno é conhecido como colisão.

Funções do Mapa de hash

1. Public V get(Object key) : i.e. para obter um valor do mapa com base na chave.
2. Public V put(K key, V value) : ou para inserir uma chave , par de valores no mapa.

Nota: Geralmente é necessário sobrepor o método hashCode() sempre que o método igual() for sobreposto, de forma a manter o contrato geral para o método hashCode(), que diz que objetos iguais devem ter códigos hash iguais.

HashMap em JAVA

Modos para instanciar um HashMap em java:
1. Constrói um HashMap vazio com a inicial especificada
capacidade e fator de carga.

HashMap público(int inicialCapacidade, float loadFactor)

2. Constrói um HashMap vazio com a inicial especificada
capacidade e o fator de carga padrão (0,75).

public HashMap(int initialCapacity)

3. Constrói um HashMap vazio com a capacidade inicial padrão (16) e o fator de carga padrão (0.75).

public HashMap()

Load Factor and Initial Capacity.

Uma instância do HashMap tem dois parâmetros que afectam o seu desempenho:
1. Capacidade inicial
2. Fator de carga.

Capacidade inicial :
A capacidade é o número de baldes na tabela hash, e a capacidade inicial é simplesmente a capacidade no momento em que a tabela hash é criada.

Fator de Carga:
O fator de carga é uma medida de quão cheia é permitida a tabela de hash antes que a sua capacidade seja automaticamente aumentada. Quando o número de entradas na tabela de hash excede o produto do fator de carga e a capacidade atual, a tabela de hash é refazida (ou seja, estruturas de dados internas são reconstruídas) de modo que a tabela de hash tenha aproximadamente o dobro do número de baldes.

NOTE:

Como regra geral, o fator de carga padrão (.75) oferece um bom tradeoff 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 classe HashMap, incluindo get and put.

O número esperado de entradas no mapa e seu fator de carga deve ser levado em conta ao definir sua capacidade inicial, de modo a minimizar o número de operações de refazer. Se a capacidade inicial for maior que o número máximo de entradas dividido pelo fator de carga, nenhuma operação de refash ocorrerá.

HashMap em Java 8

A HashMap(de java 8) armazena dados em múltiplas listas de entradas ou múltiplas Árvores Pretas Vermelhas ou mistura de ambas, dependendo do limite, também chamadas de baldes ou silos.

Todas as listas/árvores são registradas em um array de Entradas (Entry<K,V> tabela) e a capacidade padrão deste array interno é 16.

Cada registo ou um par de chaves e um valor num HashMap é chamado como Entry<Key,Value>.

Entry

HashMaps usam uma classe interna para armazenar dados: o Entry<K,V>.
Esta entrada é um par simples de valores chave com dois valores extra que são os seguintes:

1. Uma referência a outra Entrada para que um HashMap possa armazenar entradas como listas ligadas individualmente, ou como Árvore com nós esquerdo e direito para fornecer uma melhor pesquisa.

2. Um valor hash que representa o valor hash da chave. Este valor de hash é armazenado para evitar o cálculo do hash toda vez que o HashMap precisar dele.

Entrada em java 8 pode ser de 2 tipos LinkedList Node ou RedBlack Tree Node.

* tamanho deste como discutido acima é definido ou durante a instanciação ou como padrão 16. Com base no fator de carga, ele aumenta para o dobro do tamanho anterior de forma a acomodar mais entradas.

Nó transparente<K,V>tabela; //contém todas as entradas.

Na tabela, cada índice é um Nó de uma LinkedList ou de uma RedBlackTree.
A Hierarquia de Entradas é assim:

Mapa.Entrada<K,V> → implementos → Nó<K,V> → estende → TreeNode<K,V>

Nó da Lista Vinculada:

Classe estática Nó<K,V>Mapa de implementos.Entrada<K,V> {
final int hash;
final K key;
V value;
Nó<K,V> next; // para manter uma LinkedList.
Nó(int hash, chave K, valor V, Nó<K,V>próximo) {
this.hash = hash;
this.key = key;
this.value = value;
this.value = value;
this.next = next;
}

TreeNode:

HashMap, em java 8 , usa RedBlackTree após certo limite conhecido como TREEIFY_THRESHOLD(valor padrão 8), já que dá uma complexidade de tempo de O(log n), em comparação ao LinkedList que dá a busca em O(n).

static final class TreeNode<K,V> estende o LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // links de árvores pretas-vermelhas
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // necessário para destravar em seguida ao apagar
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}

Funções do HashMap de trabalho

1. Ele verifica se a chave é nula ou não . Note que só pode haver uma chave nula no HashMap.Se a chave for nula , então as chaves Nulas sempre mapeiam para hash 0, assim o índice 0 da tabela.
2. Se chave não for nula então, o método chama o método hashCode() no objeto chave(Overriden pelo usuário na respectiva classe Key) e aplica o valor retornado do hashValue à sua própria função hash estática para encontrar uma localização de bucket(matriz de suporte) onde chaves e valores são armazenados na forma de uma classe aninhada chamada Entry.
A localização de bucket é um índice da tabela Entry nomeadamente.

NOTE: estamos calculando o valor do hash novamente usando hash(hashValue) como defende contra a função hash de má qualidade.

3. O valor final do hash é usado para encontrar a localização do balde no qual o objeto Entry é armazenado.
A complexidade de get() e put() é O(1) , assumindo que a função hash dispersa os elementos corretamente entre os baldes.

Note: Como sabemos agora que em caso de colisão de hash os objetos de entrada são armazenados como um nó em uma lista ligada e o método equals() é usado para comparar chaves. Essa comparação para encontrar a chave correta em uma lista vinculada é uma operação linear, então no pior caso a complexidade se torna O(n).
Para resolver esse problema, elementos de hash Java 8 usam árvores balanceadas em vez de listas vinculadas depois que um certo limite é atingido. O que significa que o HashMap começa com o armazenamento de objetos de entrada na lista ligada mas depois que o número de itens em um hash se torna maior que um certo limite, o hash irá mudar de usar uma lista ligada para uma árvore balanceada, o que irá melhorar o desempenho do pior caso de O(n) para O(log n).

E se quando duas chaves diferentes tiverem o mesmo código de hash ?

4. Em um índice podemos ter múltiplos valores já que podemos ter colisões no hash. Para descobrir qual deles precisamos, o HashMap leva a ajuda de equals().

Solução, método equals() vem para resgatar. Como bucket é um e temos dois objetos com o mesmo código hash .

Então depois de pegar o índice da chave, ele pega o primeiro nó presente nesse índice. O primeiro nó é então comparado com a chave usando equals(), Se este for o nó desejado, ele retorna o valor diretamente daqui.
Else, ele descobre a instância do Nó, para descobrir se os dados que contém os dados armazenados neste índice estão no formato de lista ligada ou de árvore RedBlack.

Após descobrirmos que, atravessamos a LinkedList ou Tree , comparando chaves em cada entrada usando keys.equals() até que ele retorne verdadeiro. Então o valor do objeto de entrada correspondente é retornado .

public V get(Object key) {
Node<K,V> e;
retorno (e = getNode(hash(key), key)) == null ? null : e.valor;
}

nó final<K,V> getNode(int hash, Object key) {
Nó<K,V> tab; //representa o Array of Entry
Nó<K,V> first, e;
int n; K k;

/* Verificando se a tabela tem entradas .*/
/* Também, encontrando o índice com base no hash computado nos passos anteriores, onde a entrada é armazenada como Lista ou Nó de Árvore.*/

if ((tab = tabela) != null && (n = tab.comprimento) > 0 &&(first = tab) != null) {
/*Incorrendo o Primeiro nó no índice obtido com base no hash.*/
if (first.hash == hash &&> /* verificar sempre o primeiro nó*/
((k = first.key) == key||| (key != null && key.equals(k))))
retorno primeiro;

/*Se o primeiro nó desse índice não for o valor que estamos pesquisando, então ele vai para o atravessamento.*/
if ((e = primeiro.seguinte) != nulo) {
if (primeira instância do TreeNode)
/*Vindo da Árvore Vermelha Preta se o Nó iniciando no índice se do TreeNode .*/

retorno ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {

/*Vindo da LinkedList se o nó inicial for do tipo Nó e não de Árvore.*/

if (e.hash == hash &&((k = e.key) == key ||| (key != null && key.equals(k))))
retorno e;
}
while ((e = e.next) != null);
}}
retorno null;
}

PUT:

1. Ele verifica se a chave é nula ou não .If key is null , então chaves nulas sempre mapeiam para hash 0, assim indexando 0 da tabela.
2. Se chave não é nula, método chama método hashCode() no objeto chave(Overriden pelo usuário na respectiva classe Key) e aplica hashValue retornado à sua própria função hash estática para encontrar uma localização de bucket(matriz de suporte) onde chaves e valores devem ser armazenados na forma de uma classe aninhada chamada Entry.A localização da caçamba é um índice do Entry, ou seja, a tabela.
3. O valor final do hash é usado para encontrar a localização da caçamba na qual o objeto Entry deve ser armazenado. Em seguida, as Chaves são percorridas da mesma forma descrita no get(), para verificar se a chave já existe, caso exista o valor é substituído pelo novo valor.
Else, o tamanho da lista é verificado,
Se exceder a TREEIFY_THRESHOLD(default 8), os nós são reestruturados em RedBlackTree e a nova chave é armazenada com o valor nela.
Se o limite não for excedido, a nova Entrada é criada com o respectivo valor da chave, e é armazenada.

public V put(K key, V value) {
retorno putVal(hash(key), key, value, false, true);}

final V putVal(int hash, chave K, valor V, boolean onlyIfAbsent, boolean evict) {
Node<K,V> tab;
Node<K,V> p;
int n, i;
if ((tab = tabela) == null ||| (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab) == null)
tab = newNode(hash, key, value, null);
else {
/*SAME traversing as in get()*/
Node<K,V> e; K k;
if (p.hash == hash &&((k = p.key) == key ||| (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ; ++binCount) {
if ((e = p.next) === null) {
p.next = newNode(hash, key, value, null);
/*Para verificar se o TREEIFY_THRESHOLD é executado ou não.*/

if (binCount >= TREEIFY_THRESHOLD – 1) /* -1 para 1st*/
treeifyBin(tab, hash);
break;}

if (e.hash == hash &&((k = e.key) == key ||| (key != null && key.equals(k))))
break;
p = e;
}}

if (e != null) { /* mapeamento existente para chave*/
V oldValue = e.value;
if (!onlyIfAbsent ||| oldValue == null)
e.value = value;
fterNodeAccess(e);
return oldValue;
}}

++modCount;

if (++tamanho > limiar)
resize();
fterNodeInsertion(evict);
return null;}