A maioria dos desenvolvedores de Java usa mapa, especialmente o hashmap. O Hashmap é uma maneira simples, mas poderosa de armazenar e obter dados. Mas quantos desenvolvedores sabem como o hashmap funciona internamente? Alguns dias atrás, li muitos código -fonte de java.util.hashmap (incluindo Java 7 e Java 8) para obter uma compreensão profunda dessa estrutura básica de dados. Nesta postagem, explicarei a implementação do java.util.hashmap, descreverei os novos recursos adicionados na implementação Java 8 e discutirá o desempenho, a memória e alguns problemas conhecidos ao usar o hashmap.
Armazenamento interno
A classe Java Hashmap implementa a interface mapa <k, v>. Os principais métodos nesta interface incluem:
V put (key k, v valor) v get (chave do objeto) v remocer (chave de objeto) boolean containsKey (chave do objeto)
O Hashmap usa uma entrada de classe interna <k, v> para armazenar dados. Esta classe interna é um par simples de valor-chave com dois dados adicionais:
Uma referência a outra entrada, para que o Hashmap possa armazenar objetos como listas de links.
Um valor de hash usado para representar a chave. Armazenar esse valor pode impedir que o hashmap regenera o valor do hash correspondente à chave toda vez que for necessário.
Aqui está uma parte do código para entrada <k, v> sob Java 7:
Classe estática entrada <k, v> implementa mapa.entry <k, v> {final k key; v valor; entrada <k, v> a seguir; int hash;…}O Hashmap armazena dados em várias listas unidirecionais (às vezes chamadas de orbins de baldes ou contêineres). Todas as listas são registradas em uma matriz de entrada (entrada de entrada <k, v> []) e o comprimento padrão dessa matriz interna é 16.
A figura a seguir descreve o armazenamento interno de uma instância de hashmap, que contém uma matriz de objetos anuláveis. Cada objeto está conectado a outro objeto, formando uma lista vinculada.
Todas as teclas com o mesmo valor de hash serão colocadas na mesma lista vinculada (balde). As chaves com hashes diferentes podem acabar no mesmo balde.
Quando as chamadas do usuário são colocadas (Key K, Value V) ou GET (tecla Object), o programa calcula o índice do balde em que o objeto deve estar. O programa irá itera sobre a lista correspondente para encontrar o objeto de entrada com a mesma chave (usando o método iguals () da chave).
No caso de chamada get (), o programa retornará o objeto de entrada correspondente ao valor (se o objeto de entrada existir).
Para que a chamada para colocar (Key K, Valor V), se o objeto de entrada já existir, o programa substituirá o valor por um novo valor, caso contrário, o programa criará uma nova entrada (chave e valor no parâmetro) no cabeçalho da lista vinculada de mão única.
O índice do balde (lista vinculada) é gerado através de 3 etapas do mapa:
Primeiro, obtenha o código de hash da chave.
O programa repete o código de hash para bloquear funções ruins de hash para chaves, porque isso tem o potencial de colocar todos os dados no mesmo índice (balde) da matriz interna.
O programa pega o código de hash duplicado e usa uma máscara de bits do comprimento da matriz (mínimo 1) para ele. Esta operação garante que o índice não seja maior que o tamanho da matriz. Você pode pensar nisso como uma função de módulo otimizada calculada.
Aqui está o código -fonte para gerar o índice:
// the "rehash" function in JAVA 7 that takes the hashcode of the keystatic int hash(int h) {h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);}// the "rehash" function in JAVA 8 that directly takes the keystatic final int hash(Object key) {int h;return (key == null) ? 0: (h = key.hashcode ()) ^ (h >>> 16);} // A função que retorna o índice do Índice Int Hashstatic Int rehathed (int h, int length) {return h & (comprimento-1);}Para trabalhar com mais eficiência, o tamanho da matriz interna deve ser um poder de 2. Vamos ver o porquê:
Supondo que o comprimento da matriz seja 17, o valor da máscara é 16 (comprimento da matriz-1). A representação binária de 16 é 0… 010000, de modo que, para qualquer valor H, o resultado de "H & 16" é 16 ou 0. Isso significa que as matrizes do comprimento 17 só podem ser aplicadas a dois baldes: um é 0 e o outro é 16, o que não é muito eficiente. Mas se você definir o comprimento da matriz como uma potência de 2, por exemplo 16, a indexação bit funciona para "H & 15". A representação binária de 15 é 0… 001111 e a saída de valor pela fórmula do índice pode variar de 0 a 15, para que uma matriz de comprimento 16 possa ser totalmente usada. Por exemplo:
Se h = 952, sua representação binária é 0..01110111000, e o índice correspondente é 0… 01000 = 8
Se h = 1576, sua representação binária é 0..011000101000, e o índice correspondente é 0… 01000 = 8
Se h = 12356146, sua representação binária é 0..0101111001000101010010, o índice correspondente é 0… 00010 = 2
Se h = 59843, sua representação binária é 0..01110100111000011, seu índice correspondente é 0… 00011 = 3
Esse mecanismo é transparente para o desenvolvedor: se ele selecionar um hashmap de comprimento 37, o mapa selecionará automaticamente o próximo valor de potência maior que 37 (64) como o comprimento da matriz interna.
Redimensionar automaticamente
Após obter o índice, os métodos get (), put () ou remover () acessarão a lista vinculada correspondente para ver se o objeto de entrada para a chave especificada já existe. Sem modificação, esse mecanismo pode causar problemas de desempenho, pois esse método requer iteração de toda a lista para verificar se o objeto de entrada existe. Suponha que a duração da matriz interna assuma o valor padrão de 16 e você precisa armazenar 2.000.000 de registros. Na melhor das hipóteses, haverá 125.000 objetos de entrada por lista vinculada (2.000.000/16). Os métodos get (), remover () e put () requerem 125.000 iterações cada vez que forem executadas. Para evitar isso, o hashmap pode aumentar o comprimento da matriz interna, garantindo assim que apenas alguns objetos de entrada sejam retidos na lista vinculada.
Ao criar um hashmap, você pode especificar um comprimento inicial e um fator de carga através do seguinte construtor:
</pre> HashMap público (int InitialCapacity, Float LoadFactor) <Pre>
Se você não especificar parâmetros, o valor padrão da capacidade inicial é 16 e o valor padrão do fator de carga é 0,75. InitialCapacidade representa o comprimento da lista vinculada da matriz interna.
Quando você usa o método put (...) para adicionar um novo par de valor-chave ao mapa, o método verifica se o comprimento da matriz interna precisa ser aumentado. Para conseguir isso, o mapa armazena 2 dados:
Tamanho do mapa: representa o número de registros no hashmap. Atualizamos o valor quando o inserimos ou o excluímos no hashmap.
Limite: é igual ao comprimento da matriz interna*LoadFactor, e esse limite também será atualizado ao mesmo tempo em que a duração da matriz interna for ajustada.
Antes de adicionar um novo objeto de entrada, o método put (…) verifica se o tamanho do mapa atual é maior que o limite. Se for maior que o limite, cria uma nova matriz com o dobro do comprimento da matriz interna atual. Como o tamanho da nova matriz mudou, a função de índice (ou seja, o resultado da operação de bits que retorna o "valor de hash da chave & (comprimento da matriz -1)") também muda. O redimensionamento da matriz cria dois novos baldes (listas vinculadas) e transfere todos os objetos de entrada existentes para o balde. O objetivo de ajustar o tamanho da matriz é reduzir o tamanho da lista vinculada, reduzindo assim o tempo de execução dos métodos put (), remover () e get (). Para todos os objetos de entrada correspondentes a chaves com o mesmo valor de hash, eles são alocados para o mesmo balde após o redimensionamento. No entanto, se os valores de hash dos dois objetos de entrada forem diferentes, mas eles estavam no mesmo balde antes e, após o ajuste, não há garantia de que eles ainda estão no mesmo balde.
Esta imagem descreve a situação do pré-ajuste e após o ajuste, matrizes internas. Antes de ajustar o comprimento da matriz, para obter o objeto de entrada e, o mapa precisa iterar sobre uma lista vinculada contendo 5 elementos. Após o ajuste do comprimento da matriz, o mesmo método get () precisa apenas atravessar uma lista vinculada contendo 2 elementos; portanto, a velocidade de execução do método get () após o ajuste do comprimento da matriz é aumentada 2 vezes.
Segurança do thread
Se você já está muito familiarizado com o Hashmap, definitivamente sabe que não é seguro, mas por quê? Por exemplo, suponha que você tenha um tópico de escritor que apenas insira dados existentes no mapa, um tópico do leitor que lerá dados do mapa, então por que não funciona?
Como no mecanismo de redimensionamento automático, se o encadeamento tentar adicionar ou obter um objeto, o mapa poderá usar o valor antigo do índice, para que o novo balde onde o objeto de entrada esteja localizado não seja encontrado.
Na pior das hipóteses, quando 2 threads inserem dados ao mesmo tempo, 2 chamadas () são iniciadas ao mesmo tempo e a matriz redimensionará automaticamente. Como dois threads modificam a lista vinculada ao mesmo tempo, é possível que o mapa saia no loop interno de uma lista vinculada. Se você tentar obter dados de uma lista com um loop interno, o método get () nunca terminará.
A hashtable fornece uma implementação segura para roscas que impede que o acima aconteça. No entanto, como todas as operações síncronas do CRUD são muito lentas. Por exemplo, se as chamadas do thread 1 Get (Key1), o Thread 2 Chamadas Get (Key2) e o Thread 2 Chamadas Get (Key3) e, em um horário especificado, apenas um thread pode obter seu valor, mas todos os três threads podem acessar esses dados ao mesmo tempo.
Desde o Java 5, temos uma implementação melhor e segura por threads: Concurrenthashmap. Para o ConcurrentMap, apenas os baldes são sincronizados, de modo que, se vários threads não usarem o mesmo balde ou redimensionam a matriz interna, eles podem chamar os métodos get (), remover () ou put () ao mesmo tempo. Em um aplicativo multithread, essa abordagem é uma escolha melhor.
Invariância de títulos
Por que é uma boa implementação usar strings e números inteiros como chaves para hashmap? Principalmente porque eles são imutáveis! Se você optar por criar uma classe como uma chave, mas não poderá garantir que a classe seja imutável, poderá perder dados dentro do hashmap.
Vejamos os seguintes casos de uso:
Você tem uma chave cujo valor interno é "1".
Se você inserir um objeto em um hashmap, sua chave é "1".
O hashmap gera valores de hash a partir do código de hash da chave (ou seja, "1").
MAP armazena esse valor de hash no registro recém -criado.
Você altera o valor interno da chave e a altera para "2".
O valor de hash da chave alterou, mas o hashmap não sabe disso (porque o valor antigo do hash é armazenado).
Você tenta obter o objeto correspondente pela tecla modificada.
O mapa calcula o valor de hash da nova chave (ou seja, "2") para encontrar a lista vinculada (balde) em que o objeto de entrada está localizado.
Caso 1: Como você modificou a chave, o mapa tentará procurar o objeto de entrada no balde errado, mas não é encontrado.
Caso 2: Você tem sorte de que o balde gerado pela chave modificada e o balde gerado pela chave antiga sejam iguais. O mapa então atravessará a lista vinculada e um objeto de entrada com a mesma chave foi encontrado. Mas, para encontrar a chave, o mapa comparará primeiro o valor de hash da chave, chamando o método iguals (). Como a chave modificada gerará diferentes valores de hash (os valores antigos de hash são armazenados no registro), o mapa não tem como encontrar o objeto de entrada correspondente na lista vinculada.
Aqui está um exemplo Java em que inserimos dois pares de valor-chave no mapa e, em seguida, modifi a primeira chave e tento obter os dois objetos. Você descobrirá que apenas o segundo objeto retornou do mapa, o primeiro objeto foi "perdido" no hashmap:
public class MutableKeyTest {public static void main (string [] args) {class MyKey {Integer i; public void Seti (Integer i) {this.i = i;} public MyKey (Integer i) {this.i = i;}@substerpublic int hashcode () {Return i;} {Return i.Equals ((((myKey) obj) .i);} elsereturn false;}} mapa <myKey, string> mymap = new hashmap <> (); myKey key1 = new myKey (1); 1); myKey key2 = new myKey (2); myMap.put.put (key1 "" 1); 1); key1Key1.seti (3); String test1 = mymap.get (key1); string test2 = mymap.get (key2); system.out.println ("test1 =" + test1 + "test2 =" + test2);}}A saída do código acima é "test1 = null test2 = teste 2". Como esperamos, o MAP não tem a capacidade de obter a string 1 correspondente à chave modificada 1.
Melhorias no Java 8
No Java 8, a implementação interna no Hashmap foi muito modificada. De fato, o Java 7 usa 1000 linhas de código para implementá -lo, enquanto o Java 8 usa 2000 linhas de código. A maior parte do que descrevi anteriormente ainda está correta no Java 8, exceto usando listas vinculadas para salvar objetos de entrada. No Java 8, ainda usamos matrizes, mas será salva no nó, que contém as mesmas informações que o objeto de entrada anterior e também usa uma lista vinculada:
Aqui está parte do código que implementa o nó em Java 8:
Classe estática nó <k, v> implementa mapa.entry <k, v> {final int hash; final k key; v valor; nó <k, v> a seguir;Então, qual é a grande diferença em comparação com o Java 7? Bem, o nó pode ser estendido ao Treenode. Treenode é uma estrutura de dados de uma árvore vermelha e preta que pode armazenar mais informações, para que possamos adicionar, excluir ou obter um elemento sob a complexidade de O (log (n)). O exemplo a seguir descreve todas as informações salvas pelo Treenode:
Classe final estática Treenode <k, v> estende LinkedHashmap.entry <k, v> {final int hash; // herdado do nó <k, v> Key K final; // herdado do nó <k, v> v valor; // herdado do nó <k, v> nó <k, v> próximo; // herdado do nó <k, v> entrada <k, v> antes, depois; // herdado de linkedhashmap.entry <k, v> parent; treenode <k, v> esquerda; treenode <k, v> direita; treenode <k, v> prev; boolean vermelho;Árvores vermelhas e negras são árvores de busca binária auto-equilibrada. Seu mecanismo interno garante que seu comprimento seja sempre log (n), se adicionamos ou excluímos nós. O benefício mais importante de usar esse tipo de árvore é que muitos dados na tabela interna têm o mesmo índice (balde). No momento, a complexidade da pesquisa na árvore é O (log (n)) e, para a lista vinculada, a complexidade é O (n) para executar a mesma operação.
Como você pode ver, armazenamos mais dados na árvore do que as listas vinculadas. De acordo com o princípio da herança, a tabela interna pode conter o nó (lista vinculada) ou treenode (árvore vermelha e preta). O Oracle decide usar essas duas estruturas de dados de acordo com as seguintes regras:
- Para o índice especificado (balde) na tabela interna, se o número de nós for superior a 8, a lista vinculada será convertida em uma árvore vermelha e preta.
- Para o índice especificado (balde) na tabela interna, se o número de nós for menor que 6, a árvore vermelha e preta será convertida em uma lista vinculada.
Esta imagem descreve uma matriz interna em um hashmap java 8, que contém as listas de árvores (balde 0) e vinculadas (balde 1, 2 e 3). O balde 0 é uma estrutura de árvore porque contém mais de 8 nós.
Sobrecarga de memória
Java 7
O uso do hashmap consome alguma memória. No Java 7, o hashmap encapsula os pares de valor-chave em objetos de entrada, um objeto de entrada contém as seguintes informações:
Referência ao próximo registro Um valor de hash pré-calculado (número inteiro)
Uma referência a uma chave e uma referência a um valor
Além disso, o hashmap no Java 7 usa uma matriz interna de objetos de entrada. Suponha que um hashmap java 7 contenha n elementos e sua matriz interna tem capacidade, então o consumo adicional de memória é sobre:
sizeof (número inteiro)* n + sizeof (referência)* (3* n + c)
em:
O tamanho de um número inteiro é de 4 bytes
O tamanho da referência depende da JVM, sistema operacional e processador, mas geralmente é de 4 bytes.
Isso significa que a sobrecarga total da memória é geralmente bytes de capacidade de 16 * n + 4 *.
NOTA: Depois que o mapa é redimensionado automaticamente, o valor da capacidade é a próxima menor potência de 2 maior que N.
Nota: A partir do Java 7, o Hashmap adota um mecanismo de carregamento preguiçoso. Isso significa que, mesmo se você especificar o tamanho do hashmap, a matriz interna usada (consumindo bytes de 4*capacidade) que não é alocada na memória antes de usarmos o método put ().
Java 8
Nas implementações Java 8, o uso da memória de computação se torna mais complicado porque o nó pode armazenar os mesmos dados que a entrada ou adicionar 6 referências e uma propriedade booleana (especificando se é um Treenode).
Se todos os nós forem apenas nós, a memória consumida pelo hashmap java 8 é a mesma que a consumida pelo Java 7 Hashmap.
Se todos os nós forem treenode, a memória consumida pelo hashmap java 8 se tornará:
N * sizeof (número inteiro) + n * sizeof (booleano) + sizeof (referência) * (capacidade 9 * n +)
Na maioria das JVMs padrão, o resultado da fórmula acima é de 44 * n + 4 * de bytes de capacidade.
Questões de desempenho
HashMap assimétrico vs Hashmap equilibrado
Na melhor das hipóteses, os métodos GET () e PUT () têm apenas a (1) complexidade. No entanto, se você não se importa com a função de hash da chave, seus métodos put () e get () podem ser executados muito lentamente. A execução eficiente dos métodos put () e get () depende dos dados que estão sendo alocados para diferentes índices da matriz interna (balde). Se a função de hash da chave não for projetada corretamente, você obterá uma partição assimétrica (independentemente do tamanho dos dados internos). Todos os métodos put () e get () usarão a maior lista vinculada, que demorará a executar, pois requer iterar todos os registros na lista vinculada. Na pior das hipóteses (se a maioria dos dados estiver no mesmo balde), sua complexidade de tempo se torna O (n).
Aqui está um exemplo visual. O primeiro gráfico descreve um hashmap assimétrico e o segundo gráfico descreve um hashmap equalizado.
Skewedhashmap
Neste hashmap assimétrico, levará tempo para executar os métodos get () e put () no balde 0. Obter o registro K leva 6 iterações.
Neste hashmap equilibrado, são necessárias apenas 3 iterações para obter o registro K. Esses dois hashmaps armazenam a mesma quantidade de dados e as matrizes internas são do mesmo tamanho. A única diferença é a função de hash da chave, que é usada para distribuir registros para diferentes baldes.
Aqui está um exemplo extremo escrito em Java, no qual uso uma função de hash para colocar todos os dados na mesma lista vinculada (balde) e, em seguida, adicionei 2.000.000 de dados.
public class Test {public static void main (string [] args) {class MyKey {Integer i; public MyKey (Integer i) {this.i = i;}@substituirpublic int hashcode () {return 1;}@substituir obublic boolean (my my my) {}}}}} Hashmap <> (2_500_000,1); para (int i = 0; i <2_000_000; i ++) {mymap.put (new MyKey (i), "test"+i);} date end = new date ();Minha configuração de máquina é o núcleo i5-2500k @ 3.6g e leva mais de 45 minutos para ser executado sob o Java 8U40 (parei o processo após 45 minutos). Se eu executar o mesmo código, mas uso a função de hash como esta:
@OverridePublic int hashCode () {int key = 2097152-1; chave de retorno+2097152*i;}Leva 46 segundos para executá -lo, o que é muito melhor do que antes! A nova função de hash é mais razoável que a função antiga de hash ao processar partições de hash; portanto, chamar o método put () é mais rápido. Se você executar o mesmo código agora, mas use a função de hash abaixo, ele fornece uma partição de hash melhor:
@OverridePublic int hashCode () {return i;}Agora leva apenas 2 segundos!
Espero que você possa perceber o quão importantes são as funções de hash. Se você executar o mesmo teste no Java 7, o primeiro e o segundo serão piores (porque o método put () no Java 7 tem complexidade O (n), enquanto a complexidade no Java 8 possui O (log (n)).
Ao usar o hashmap, você precisa encontrar uma função de hash para as teclas que podem espalhar as teclas para o balde mais provável. Para fazer isso, você precisa evitar conflitos de hash. Um objeto de string é uma chave muito boa porque possui uma boa função de hash. O número inteiro também é bom porque seu hash é seu próprio valor.
Redimensionando o alto
Se você precisar armazenar uma grande quantidade de dados, especifique uma capacidade inicial ao criar um hashmap, que deve estar próximo do tamanho desejado.
Se você não fizer isso, o mapa usará o tamanho padrão, ou seja, 16, e o valor da carga de fatores é 0,75. As primeiras 11 chamadas para colocar () o método serão muito rápidas, mas a 12ª (16*0,75) a chamada criará uma nova matriz interna com o comprimento 32 (e a lista/árvore vinculada correspondente), e a 13ª a 22ª chamada para colocar () a seleção será muito rápida. Em seguida, a operação de redimensionamento interna será acionada quando o método put () for chamado 48º, 96º, 192º…. Se a quantidade de dados não for grande, a operação de reconstruir a matriz interna será muito rápida, mas quando a quantidade de dados for grande, o tempo gasto poderá variar de segundos a minutos. Ao especificar o tamanho desejado do mapa durante a inicialização, você pode evitar o consumo causado pelas operações redimensionadas.
Mas há também uma desvantagem aqui: se você definir a matriz como muito grande, por exemplo 2^28, mas você apenas usa 2^26 baldes na matriz, então desperdiçará muita memória (cerca de 2^30 bytes neste exemplo).
para concluir
Para casos de uso simples, você não precisa saber como funciona o hashmap, porque você não verá a diferença entre O (1), O (n) e O (log (n)). Mas é sempre benéfico entender o mecanismo por trás dessa estrutura de dados frequentemente usada. Além disso, esta é uma pergunta típica de entrevista para as posições do desenvolvedor de Java.
Para grandes volumes de dados, torna -se muito importante entender como o hashmap funciona e entender a importância de uma função de hash para as chaves.
Espero que este artigo possa ajudá -lo a ter um profundo entendimento da implementação do Hashmap.