Visão geral do hashmap
Hashmap é uma implementação assíncrona da interface do mapa com base na tabela de hash. Esta implementação fornece todas as operações de mapeamento opcional e permite o uso de valores nulos e teclas nulas. Esta classe não garante a ordem dos mapeamentos, especialmente não garante que o pedido durará.
Estrutura de dados do Hashmap
Na linguagem de programação Java, existem duas estruturas básicas, uma é uma matriz e a outra é um ponteiro simulado (referência). Todas as estruturas de dados podem ser construídas usando essas duas estruturas básicas, e o hashmap não é exceção. Hashmap é na verdade uma estrutura de dados de "lista vinculada", ou seja, a estrutura das matrizes e listas vinculadas, mas no JDK1.8
A implementação da árvore vermelha e preta é adicionada. Quando o comprimento da lista vinculado é maior que 8, ela é convertida na estrutura da árvore vermelha e preta.
Como pode ser visto na figura acima, o hashmap usa o método de endereço da corrente em Java. O método de endereço do link, simplesmente colocado, é uma combinação de matrizes e listas vinculadas. Existe uma estrutura de lista vinculada em cada elemento da matriz. Quando os dados são hash, o subscrito da matriz é obtido e os dados são colocados na lista vinculada dos elementos do subscrito correspondentes.
*/ Classe estática Nó <k, v> implementa map.entry <k, v> {final int hash; // usado para localizar a posição da chave final do índice de matriz; Valor V; Nó <k, v> próximo; // NODE NO NOTE NO NODE LIGADO (INT HASH, K KEY, V VALOR, NODE <K, V> AIXTEMENTE) {this.hash = hash; this.Key = key; this.value = value; this.Next = Next; }O nó é uma classe interna de hashmap, que implementa a interface mapa.entry, que é essencialmente um mapa (par de valores-chave).
Às vezes, duas teclas são posicionadas na mesma posição, indicando que ocorreu uma colisão de hash. Obviamente, quanto mais uniformes os resultados do cálculo do algoritmo hash, menor a probabilidade de colisão de hash e maior a eficiência de acesso do mapa.
Existe um campo muito importante na classe HashMap, que é a tabela de nó [], ou seja, a matriz de balde de hash. É obviamente uma variedade de nós.
Se a matriz de balde de hash for grande, até o algoritmo de hash pobre será mais disperso. Se a matriz de matriz de balde de hash for pequena, mesmo um bom algoritmo de hash terá mais colisões, por isso é necessário pesar o custo e o custo do espaço. De fato, é para determinar o tamanho da matriz de balde de hash com base na situação real e, nessa base, o algoritmo de hash projetado reduzirá as colisões de hash. Então, como podemos controlar mapas para tornar a probabilidade de colisões de hash pequenas e matrizes de balde de hash (tabelas de nó []) ocupam menos espaço? A resposta é um bom algoritmo de hash e mecanismo de expansão de capacidade.
Antes de entender o processo de hash e expansão, precisamos entender vários campos de hashmap. A partir do código -fonte do construtor padrão do Hashmap, pode -se observar que o construtor inicializa os seguintes campos, o código -fonte é o seguinte:
limiar int; // O valor-chave que pode ser acomodado é o melhor fator de carga float; // fator de carga int modCount; Int tamanho;
Primeiro, o comprimento da inicialização da tabela de nó [] (o valor padrão é 16), o fator de carga é o fator de carga (o valor padrão é 0,75) e o limite é o número de nó (pares de valor-chave) da quantidade máxima de dados que o hashmap pode acomodar. limiar = comprimento * fator de carga. Ou seja, depois que a matriz definir seu comprimento, quanto maior o fator de carga, mais pares de valor-chave ela pode acomodar.
Com base na fórmula de definição do fator de carga, pode -se ver que o limite é o número máximo de elementos permitidos de acordo com esse fator de carga e comprimento (comprimento da matriz). Se esse número exceder isso, redimensione (capacidade de ampliar). A capacidade expandida do hashmap é o dobro da capacidade anterior. O fator de carga padrão 0,75 é uma escolha equilibrada para eficiência de espaço e tempo. Recomenda -se que você não o modifique, a menos que, no caso de tempo e espaço especiais, se houver muito espaço de memória e requisitos de eficiência de tempo, o valor do fator de carga do fator de carga pode ser reduzido; Pelo contrário, se o espaço de memória estiver apertado e os requisitos de eficiência do tempo não forem altos, o valor do fator de carga do fator de carga pode ser aumentado, o que pode ser maior que 1.
O campo de tamanho é realmente fácil de entender, é o número de pares de valor-chave que realmente existem no hashmap. Observe a diferença entre o comprimento da tabela e o número de limites que acomodam os pares máximos de valor da chave. O campo ModCount é usado principalmente para registrar o número de alterações na estrutura interna do hashmap e é usado principalmente para a rápida falha da iteração. Para enfatizar, as alterações na estrutura interna se referem a alterações na estrutura, como colocar novos pares de valor-chave, mas o valor correspondente a uma chave é substituído e não pertence a alterações estruturais.
No hashmap, o comprimento da tabela de matriz de hash deve estar na potência N de 2 (deve ser um número composto). Este é um design não convencional. O design convencional é projetar o tamanho do balde como um número primo. Relativamente falando, a probabilidade de conflito causada por números primos é menor que a dos números compostos. Para provas específicas, consulte //www.vevb.com/article/100911.htm. A hashtable inicializa o tamanho do balde para 11, que é a aplicação do tamanho do balde projetado como números primos (a hashtable não pode ser garantida como números primos após a expansão). O Hashmap adota esse design não convencional, principalmente para otimizar quando Modulo e expansão. Ao mesmo tempo, para reduzir os conflitos, o Hashmap também adiciona o processo de participação de alto bit na computação ao localizar a posição do índice de balde de hash.
Há um problema aqui. Mesmo que o fator de carga e o algoritmo de hash sejam projetados razoavelmente, haverá inevitavelmente uma situação em que o zíper é muito longo. Uma vez que o zíper for muito longo, isso afetará seriamente o desempenho do hashmap. Portanto, na versão JDK1.8, a estrutura de dados foi otimizada e a árvore vermelha e preta foi introduzida. Quando o comprimento da lista vinculado é muito longo (o padrão é superior a 8), a lista vinculada é convertida em uma árvore vermelha e preta. As características de adição rápida e vermelha e preta, deleções, modificações e pesquisas serão usadas para melhorar o desempenho do hashmap. A inserção, exclusão e pesquisa de árvores vermelhas e pretas serão usadas para inserir, excluir e pesquisar algoritmos como Red e Black Tree.
Determine a posição do índice da matriz de balde de hash
Implementação de código:
// Método 1: estático final int hash (chave do objeto) {//jdk1.8 & jdk1.7 int h; // h = key.hashcode () Obtém o valor do hashcode para a primeira etapa // h ^ (h >>> 16) Participa na operação do segundo passo retorno (key == null)? 0: (h = key.hashcode ()) ^ (h >>> 16);} // Método 2: estático int indexfor (int h, int length) {//jdk1.7 código-fonte, jdk1.8 não possui esse método, mas o princípio da implementação é o mesmo retorno H & (comprimento-1); // O terceiro passo leva a operação do módulo}O algoritmo de hash aqui é essencialmente três etapas: tomando o valor de hashcode da operação de chave, de alto bit e operação de módulo.
Para qualquer objeto, desde que seu valor de retorno hashcode () seja o mesmo, o código de hash calculado pelo método de chamada do programa é sempre o mesmo. A primeira coisa que pensamos é modular o valor do hash para o comprimento da matriz, para que a distribuição de elementos seja relativamente uniforme. No entanto, o consumo de operações de módulo é relativamente grande. Isso é feito no hashmap: ligue para o método dois para calcular qual índice o objeto deve ser armazenado na matriz de tabela.
Este método é muito inteligente. Ele obtém os bits salvos do objeto através de h & (tabela.length -1) e o comprimento da matriz subjacente do hashmap é sempre para o N -Power de 2, que é a otimização do hashmap em termos de velocidade. Quando o comprimento é sempre para a potência N de 2, a operação de H & (Length-1) é equivalente ao comprimento do módulo, ou seja, H %de comprimento, mas e tem maior eficiência que %.
Na implementação do JDK1.8, o algoritmo para operações de alto bit é otimizado e a implementação XOR de 16 bits de XOR de 16 bits de HashCode (): (H = K.HashCode ()) ^ (H >>> 16), que é considerado principalmente a partir da velocidade, eficiência e qualidade. Isso pode garantir que, quando o comprimento da tabela de matrizes for relativamente pequeno, também pode garantir que os bits estejam envolvidos nos cálculos de hash, levando em consideração a alta baixa e não haverá uma sobrecarga excessiva.
Aqui está um exemplo: n é o comprimento da tabela.
Implementação do método put hashmap
A idéia geral da função de put é:
O código específico é implementado da seguinte maneira:
public V put (K -Key, V valor) {return putval (hash (chave), chave, valor, false, verdadeiro); } / ***Método para gerar hash* / estático final int hash (chave do objeto) {int h; return (key == null)? 0: (h = key.hashcode ()) ^ (h >>> 16); } final v putval (int hash, k key, v valor, boolean somentefabsent, despet booleano) {node <k, v> [] guia; Nó <k, v> p; int n, i; // julgue se a tabela está vazia, if ((tab = tabela) == null || (n = tab.length) == 0) n = (tab = redize ()). Length; // Crie uma nova matriz de tabela e obtenha o comprimento da matriz // calcule o valor do hash para o índice de matriz inserido I de acordo com a chave da chave. Se tabela [i] == NULL, crie diretamente um novo nó e adicione if ((p = tab [i = (n - 1) e hash]) == null) guia [i] = newNode (hash, chave, valor, nulo); else {// se o nó correspondente tiver nó <k, v> e; K K; // julga se o primeiro elemento da tabela [i] é o mesmo que a chave, se o mesmo, substitua diretamente o valor if (p.hash == hash && ((k = p.Key) == key || (key! = Null && key.equals (k))) e = p; // julga se a Tabela [i] é um Treenode, ou seja, se a Tabela [I] é uma árvore preta-preta. Se for uma árvore em preto vermelho, insira diretamente o par de valores-chave na árvore else if (p instanceof Treenode) e = ((Treenode <k, v>) p) .putTreeval (this, guia, hash, chave, valor); // Esta cadeia é uma lista vinculada mais {// transmita através da tabela [i] para determinar se o comprimento da lista vinculado é maior que o Treeify_threshold (o valor padrão é 8). Se for maior que 8, converta a lista vinculada em uma árvore vermelha-preta e execute a operação de inserção na árvore vermelha-preta. Caso contrário, a operação de inserção da lista vinculada é executada; Se for constatado que a chave já possui um valor de substituição direta durante o processo de travessia; for (int bincount = 0;; ++ bincount) {if ((e = p.next) == null) {p.next = newNode (hash, chave, valor, nulo); if (Bincount> = Treeify_threshold - 1) // -1 para 1st TreeifyBin (guia, hash); quebrar; } if (e.hash == hash && ((k = e.key) == key || (key! = null && key.equals (k)))) break; p = e; }} // Escreva if (e! = Null) {// mapeamento existente para chave v anticvalue = e.value; if (! SOMEFABSENT || OldValue == NULL) E.Value = Value; tardia (e); retornar OldValue; }} ++ modCount; // Depois que a inserção for bem -sucedida, determine se o número real de pares de valor -chave excede o limite máximo de capacidade. Se exceder a capacidade, expanda se (++ tamanho> limite) redimensione (); tardianserção (despejo); retornar nulo; }HashMap Get Method Implementation
A idéia é a seguinte:
1. O primeiro nó no balde, bate diretamente;
2. Se houver um conflito, use a chave. Equals (k) para encontrar a entrada correspondente
Se for uma árvore, procure na árvore através da chave.Equals (k), O (logn);
Se for uma lista vinculada, pesquise no key.equals (k) na lista vinculada, o (n).
public v get (chave do objeto) {node <k, v> e; return (e = getNode (hash (chave), chave)) == null? nulo: E.Value; } nó final <k, v> getNode (int hash, chave do objeto) {node <k, v> [] guia; Nó <k, v> primeiro, e; int n; K K; if ((tab = tabela)! = null && (n = tab.length)> 0 && (primeiro = tab [(n - 1) & hash])! = null) {// pressione diretamente se (primeiro.hash == hash && // e toda vez que é verificado o primeiro nó (k = primeiro.key) == key || (key! // perdeu se ((e = primeiro.next)! = Null) {// get if (primeira instância de treenode) return ((treenode <k, v>) primeiro) .getTreenode (hash, chave); // get Do {if (e.hash == hash && ((k = e.key) == key || (key! = Null && key.equals (k))) retornar e; } while ((e = e.next)! = nulo); }} retornar nulo; }Mecanismo de expansão da capacidade
Redimensionar significa recalcular a capacidade e adicionar constantemente elementos ao objeto HashMap. Quando a matriz dentro do objeto Hashmap não pode carregar mais elementos, o objeto precisa expandir o comprimento da matriz para que mais elementos possam ser carregados. Obviamente, as matrizes em Java não podem ser expandidas automaticamente. O método é usar uma nova matriz em vez de matrizes existentes com pequena capacidade, assim como usamos um pequeno balde para encher água. Se quisermos encher mais água, precisamos substituí -lo por um balde grande.
Analisamos o código -fonte de redimensionamento. Dado que o JDK1.8 integra árvores vermelhas e negras, é mais complicado. Para facilitar a compreensão, ainda usamos o código JDK1.7, o que é mais fácil de entender. Há pouca diferença em essência. Vamos falar sobre as diferenças específicas mais tarde.
Void redimensiona (int newCapacity) {// pausa nova entrada de capacidade [] OldTable = tabela; // Referenciar a matriz de entrada antes da expansão int antiga Capacidade = OldTable.Length; if (OldCapacity == MAXIMUM_CAPACIDADE) {// Se o tamanho da matriz antes da expansão atingir o limite máximo (2^30) = inteiro.max_value; // modifica o limite para o valor máximo de int (2^31-1), para que a capacidade não seja expandida no retorno futuro; } Entrada [] newTable = nova entrada [newCapacity]; // inicialize uma nova transferência de matriz de entrada (newTable); //! ! Transferir dados para a nova tabela de matriz de entrada = newTable; // atributo da tabela do hashmap refere -se ao novo limite de matriz de entrada = (int) (newCapacity * loadFactor); // modifique o limite}Aqui, usamos uma matriz com maior capacidade, em vez de uma matriz existente com menor capacidade. O método transfer () copia os elementos da matriz de entrada original para a nova matriz de entrada.
transferência void (entrada [] newTable) {Entry [] src = tabela; // src refere -se à antiga matriz de entrada int newCapacity = newtable.length; for (int j = 0; j <src.length; j ++) {// Tranquilidade através da entrada antiga de entrada de entrada <k, v> e = src [j]; // Obtenha cada elemento da matriz de entrada antiga if (e! = Null) {src [j] = null; // liberar a referência do objeto da matriz de entrada antiga (após o loop for, a matriz de entrada antiga não se refere mais a nenhum objeto) fazer {entrada <k, v> a seguir = e.next; int i = indexfor (e.hash, newcapacity); //! ! Recalcule a posição de cada elemento na matriz e.next = newTable [i]; // tag [1] newTable [i] = e; // coloque o elemento na matriz e = a seguir; // Acesse o elemento na próxima cadeia de entrada} while (e! = Null); }}}A referência ao NewTable [i] é atribuída ao E.Next, o que significa que o método de inserção do cabeçalho de uma única lista vinculada é usada. Novos elementos na mesma posição sempre serão colocados na cabeça da lista vinculada; Dessa forma, os elementos colocados em um índice serão colocados no final da cadeia de entrada (se ocorrer um conflito de hash). Isso é diferente do JDK1.8, que é explicado em detalhes abaixo. Os elementos da mesma cadeia de entrada na matriz antiga podem ser colocados em posições diferentes na nova matriz após a recalculação da posição do índice.
Aqui está um exemplo para ilustrar o processo de expansão da capacidade. Suponha que nosso algoritmo de hash simplesmente use o Mod Key para obter o tamanho da tabela (ou seja, o comprimento da matriz). O tamanho da tabela de matriz de balde de hash = 2, portanto, a chave = 3, 7, 5 e a ordem de venda é 5, 7 e 3. Após o mod 2, o conflito está na tabela [1]. Aqui, supõe-se que o fator de carga do fator de carga = 1, ou seja, quando o tamanho real do par de valores-chave é maior que o tamanho real da tabela, ela é expandida. As próximas três etapas são o processo de redimensionamento da matriz de balde de hash para 4 e depois reformulando todos os nós.
Vamos explicar quais otimizações foram feitas no JDK1.8. Após a observação, podemos descobrir que estamos usando uma potência de duas expansão (referindo -se ao comprimento de duas vezes o original), de modo que a posição do elemento está na posição original ou move a posição do poder dos dois novamente na posição original. Olhando para a figura abaixo, você pode entender o significado desta frase. n é o comprimento da tabela. A Figura (a) representa um exemplo da posição do índice das duas teclas que determinam a posição do índice do KEY1 e KEY2 antes da expansão. A Figura (b) representa um exemplo da posição do índice do KEY1 e KEY2 após a expansão. Onde o hash1 é o resultado de operação de hash e alto bit correspondente a Key1.
Depois que o elemento recalcula o hash, pois N se torna 2 vezes, a faixa de máscara de N-1 é de 1 bit (vermelha) no ponto alto, de modo que o novo índice mudará assim:
Portanto, quando expandimos o hashmap, não precisamos recalcular o hash como a implementação do JDK1.7. Só precisamos ver se o bit adicionado ao valor do hash original é 1 ou 0. Se for 0, o índice não foi alterado. Se for 1, o índice se tornará "índice original + antigo". Você pode ver a figura a seguir como o diagrama redimensionado com 16 expansão para 32:
Esse design é realmente muito inteligente, o que não apenas economiza tempo para recalcular o valor do hash, mas também, uma vez que o recém -adicionado 1 bit é 0 ou 1, pode ser considerado aleatório, portanto o processo de redimensionamento distribui uniformemente os nós conflitantes anteriores para o novo balde. Este é o novo ponto de otimização adicionado pelo JDK1.8. Há um pouco de atenção à diferença. Quando o Rehash in JDK1.7, quando listas vinculadas antigas migram novas listas vinculadas, se a posição do índice da matriz da nova tabela for a mesma, os elementos da lista vinculada serão invertidos, mas, como pode ser visto na figura acima, o JDK1.8 não será invertido. Os alunos interessados podem estudar o código -fonte redimensionado do JDK1.8, o que é muito bom, como segue:
Nó final <k, v> [] redize () {node <k, v> [] oldTab = tabela; int OldCap = (OldTab == NULL)? 0: Oldtab.Length; int Oldthr = limiar; int newCap, newthr = 0; se (antigo> 0) {// Se o valor máximo exceder, ele não será mais expandido, então eu tenho que colidir com você se (antigo> = maximum_capacity) {threshold = Integer.max_value; retornar Oldtab; } // Se o valor máximo não for excedido, ele será expandido para 2 vezes o original if ((newCap = antiga << 1) <maximum_capacity && Oldcap> = default_initial_capacity) newthr = Oldthr << 1; // limiar duplo} else if (Oldthr> 0) // A capacidade inicial foi colocada em limiar newcap = antigo; else {// limiar inicial zero significa usando os padrões newcap = default_initial_capacity; newthr = (int) (default_load_factor * default_initial_capacity); } // Calcule o novo limite superior de redimensionamento se (newthr == 0) {float ft = (float) newcap * loadFactor; newthr = (newcap <maximum_capacity && ft <(float) maximum_capacity? (int) ft: Integer.max_value); } limite = newthr; @Suppresswarnings ({"RawTypes", "desmarcado"}) nó <k, v> [] newtab = (nó <k, v> []) new Node [newcap]; tabela = newtab; if (OldTab! = null) {// mova cada balde para os novos baldes para (int j = 0; j <antigo; ++ j) {node <k, v> e; if ((e = OldTab [j])! = null) {OldTab [j] = null; if (e.next == null) newtab [e.hash & (newCap - 1)] = e; caso contrário, if (e instanceof Treenode) ((Treenode <k, v>) e) .split (this, newtab, j, antigo); else {// preservar o nó da ordem <k, v> lohead = null, lotail = null; Nó <k, v> hihead = null, hitil = null; Nó <k, v> próximo; do {next = e.next; // ÍNDICE ORIGINAL IF ((E.Hash & OldCap) == 0) {if (lotail == null) lohead = e; else lotail.Next = e; lotail = e; } // ÍNDICE ORIGINAL + antigo else {if (hitil == null) hihead = e; else hitil.next = e; hitil = e; }} while ((e = a seguir)! = nulo); // Coloque o índice original no balde if (lotail! = Null) {lotail.next = null; newtab [j] = lohead; } // Coloque o índice original + antigo no balde if (hitil! = Null) {hitil.next = null; newtab [J + OldCap] = HiHead; }}}}} retornar newtab;}Resumir
Agora podemos responder a várias perguntas no começo para aprofundar nossa compreensão do hashmap:
1. Quando o hashmap será usado? Quais são as suas características?
É baseado na implementação da interface do mapa. Ao armazenar pares de valor-chave, ele pode receber valores de chave nula, que são assíncronos. Entrada de lojas de hashmap (hash, chave, valor, a seguir) objetos.
2. Você sabe como funciona o hashmap?
Através do método hash, os objetos são armazenados e obtidos por meio de put e obtém. Ao armazenar um objeto, quando passamos k/v para o método put, ele chama HashCode para calcular o hash para obter o local do balde e armazená -lo ainda mais. O hashmap ajustará automaticamente a capacidade de acordo com a ocupação atual do balde (se exceder o CarcoTr, o redimensionamento será o dobro do original). Ao obter o objeto, passamos k para obter, que chama o HashCode para calcular o hash para obter a posição do balde e mais chama o método iguals () para determinar o par de valores-chave. Se ocorrer uma colisão, o HashMap organiza os elementos que geram conflitos de colisão através da lista vinculada. No Java 8, se os elementos que colidem em um balde excederem um certo limite (o padrão é 8), uma árvore vermelha e preta é usada para substituir a lista vinculada para aumentar a velocidade.
3. Você conhece os princípios de Get and Put? Quais são as funções de igual () e hashcode ()?
Ao haver o hashcode () da chave e calcular o subscrito (N-1 & hash), a posição dos baldes é obtida. Se ocorrer uma colisão, use o método key.equals () para procurar o nó correspondente na lista ou árvore vinculada
4. Você conhece a implementação do hash? Por que eu preciso fazer isso?
Na implementação do Java 1.8, é implementada através do alto X-OR de 16 bits de 16 bits de hashcode (): (h = k.hashcode ()) ^ (h >>> 16), que é considerado principalmente a partir da velocidade, eficiência e qualidade. Isso pode garantir que, quando o N do balde for relativamente pequeno, também pode garantir que os bits altos e baixos estejam envolvidos no cálculo do hash e não haverá uma sobrecarga excessiva.
5. E se o tamanho do hashmap exceder a capacidade definida pelo fator de carga?
Se o fator de carga for excedido (padrão 0,75), um hashmap com o dobro do comprimento original será redimensionado e o método hash será chamado novamente.
A folha de dicas sobre coleções Java é descrita da seguinte forma:
A matriz de bucket de hash implementada com a matriz de entrada [] e o valor de hash da chave pode ser usado para obter o subscrito da matriz.
Ao inserir um elemento, se duas teclas se enquadram no mesmo balde (por exemplo, depois que os valores de hash 1 e 17 forem o módulo 16, ambos pertencem ao primeiro bucket de hash), a entrada usa uma propriedade seguinte para implementar a entrada múltipla em uma lista vinculada unidirecional e a entrada que entra nos pontos do balde ao lado da entrada do balde.
Ao procurar uma chave com um valor de hash de 17, primeiro localize o primeiro bucket de hash e depois itera todos os elementos no balde com uma lista vinculada e compare seus principais valores um por um.
Quando o número de entrada atingir 75% dos baldes (muitos artigos dizem que o número de baldes utilizados atinge 75%, mas de acordo com o código, a matriz do balde será expandida exponencialmente e toda a entrada original será reatribuída, por isso é melhor ter um valor estimado aqui.
A operação de bit (hash & (ArrayLength-1)) será mais rápida, portanto, o tamanho da matriz é sempre para a potência N de 2. Se você fornecer um valor inicial como 17, será convertido em 32. O valor inicial padrão quando o elemento for colocado primeiro é 16.
Iterator () atravessa a matriz de balde de hash, que parece uma ordem fora de ordem.
6. O que acontece quando o código de hash de dois objetos é o mesmo?
Como o código de hash é o mesmo, a posição do balde é a mesma e uma 'colisão' acontecerá. Como o Hashmap usa uma lista vinculada para armazenar objetos, esta entrada (o objeto Map.Entry contendo pares de valor-chave) é armazenado na lista vinculada.
7. Se o código de hash de duas teclas for o mesmo, como você obtém o objeto Valor?
Depois de encontrar a localização do balde, o método Keys.Equals () será chamado para encontrar o nó correto na lista vinculada e, finalmente, encontrar o objeto Valor a ser encontrado. Portanto, ao projetar o tipo de chave de hashmap, se um objeto imutável for declarado como final e os métodos Equals () e HashCode () apropriados forem utilizados, a ocorrência de colisões será reduzida e a eficiência será aprimorada. A imutabilidade pode cache hashcodes para diferentes teclas, o que aumentará a velocidade de obter o objeto inteiro. Usar classes de wrapper como String e Interger como Keys é uma escolha muito boa.
8. E se o tamanho do hashmap exceder a capacidade definida pelo fator de carga?
O tamanho padrão do fator de carga é 0,75. Ou seja, quando um mapa enche 75% de baldes, como outras aulas de coleção (como a Arraylist etc.), uma matriz de balde que é o dobro do tamanho do hashmap original será criada para redimensionar o mapa e colocar o objeto original na nova matriz de balde. Esse processo é chamado de re -remancrar porque chama o método hash para encontrar o novo local do balde
9. Você entende o que há de errado em redimensionar o hashmap?
Ao redimensionar o hashmap, há de fato uma concorrência condicional, porque se os dois threads descobrirem que o hashmap precisará ser redimensionado, eles tentarão redimensionar ao mesmo tempo. Durante o processo de redimensionamento, a ordem dos elementos armazenados na lista vinculada será revertida, porque, ao se mudar para a nova posição do balde, o hashmap não coloca os elementos no final da lista vinculada, mas na cabeça, que é evitar percorrer a cauda. Se ocorrer uma competição condicional, há um ciclo vicioso. Portanto, em um ambiente simultâneo, usamos o CurrentHashmap para substituir o hashmap
10. Por que as classes de invólucro são como string e interger adequadas como chaves?
Porque a string é imutável e final, e os métodos iguais () e hashcode () foram reescritos. Outras classes de wrapper também têm esse recurso. A imutabilidade é necessária porque, para calcular o hashcode (), você deve impedir que o valor da chave mude. Se o valor -chave retornar um código de hash diferente ao colocar e obter, você não poderá encontrar o objeto que deseja do hashmap. A imutabilidade tem outras vantagens, como a segurança dos threads. Se você pode garantir que o HashCode permaneça inalterado apenas declarando um campo como final, faça -o. Como os métodos iguais () e hashcode () são usados ao obter objetos, é muito importante reescrever esses dois métodos corretamente. Se dois objetos desiguais retornarem diferentes códigos de hash, a chance de colisão será menor, o que melhorará o desempenho do hashmap
Obrigado pela leitura, espero que isso possa ajudá -lo. Obrigado pelo seu apoio a este site!