Estrutura de armazenamento
Primeiro, o hashmap é armazenado com base em uma tabela de hash. Há uma matriz dentro dela. Quando um elemento deve ser armazenado, calcule primeiro o valor de hash de sua chave e encontre o subscrito correspondente do elemento na matriz com base no valor do hash. Se não houver elemento nesta posição, coloque o elemento atual diretamente. Se houver um elemento (lembrado como aqui), vincule o elemento atual à frente do elemento A e, em seguida, coloque o elemento atual na matriz. Então, no Hashmap, a matriz realmente salva o primeiro nó da lista vinculada. Abaixo está uma foto da Encyclopedia Baidu:
Como mostrado na figura acima, cada elemento é um objeto de entrada, onde a chave e o valor do elemento são salvos, e há um ponteiro que pode ser usado para apontar para o próximo objeto. Todas as teclas com o mesmo valor de hash (ou seja, conflitos) unidas usando uma lista vinculada, que é o método zíper.
Variáveis internas
// Capacidade inicial padrão estática final int default_initial_capacity = 16; // Capacidade máxima estática final int fator de carga do fator de carga de flutuação final da matriz de hash;
Nas variáveis acima, a capacidade refere -se à duração da tabela de hash, ou seja, o tamanho da tabela e o padrão é 16. O fator de carga do fator de carga é o "grau completo" da tabela de hash, e a documentação do JDK diz o seguinte:
O fator de carga é uma medida de quão cheia a tabela de hash pode obter antes que sua capacidade seja aumentada automaticamente. 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 é reformulada (ou seja, as estruturas de dados internas são reconstruídas) para que a tabela de hash tenha aproximadamente o dobro do número de baldes.
O significado geral é: o fator de carregamento é a medida de quão cheia a tabela de hash pode ser instalada antes da expansão. Quando o número de "pares de valor-chave" na tabela de hash excede o produto da capacidade atual e do fator de carregamento, a tabela de hash hash (ou seja, a estrutura de dados interna é reconstruída) e a capacidade da tabela de hash se torna cerca de duas vezes o original.
Como pode ser visto na definição da variável acima, o fator de carregamento padrão default_load_factor é 0,75. Quanto maior esse valor, maior a taxa de utilização do espaço, mas a velocidade da consulta (incluindo get e put) desacelerará. Depois de entender o fator de carregamento, o limite também pode entendê -lo. Na verdade, é igual ao fator de carregamento da capacidade*.
Construtor
public hashmap (int inicialCapacity, float loadFactor) {if (InitialCapacidade <0) Lança nova ilegalArgumentException ("Capacidade inicial ilegal:" + InitialCapacidade); if (InitialCapacity> MAXIMUM_CAPACIDADE) InitialCapacidade = Maximum_Capacity; if (LoadFactor <= 0 || float.isnan (loadFactor)) lança nova ilegalArgumentException ("fator de carga ilegal:" + LoadFactor); // Encontre uma potência de 2> = inicialCaPacity int Capacidade = 1; enquanto (capacidade <inicialCaPacity) // calcula a menor potência de 2 que é maior que a capacidade especificada << = 1; this.loadFactor = loadFactor; limite = (int) math.min (capacidade * loadFactor, maximum_capacity + 1); tabela = nova entrada [capacidade]; // aloca espaço para a tabela de hash usealthingshash = Sun.misc.vm.isBooted () && (capacidade> = holder.alternative_hashing_threshold); init ();}Existem vários construtores, e eles acabarão ligando para o acima. Ele aceita dois parâmetros, um é a capacidade inicial e o outro é o fator de carregamento. No início, primeiro determinamos se a combinação de valor é legal e, se houver algum problema, uma exceção será lançada. O importante é o cálculo da capacidade abaixo, sua lógica é calcular a menor potência de 2 maior que a capacidade inicial. De fato, o objetivo é tornar a capacidade mais ou igual à capacidade inicial especificada, mas esse valor deve ser um múltiplo exponencial de 2, que é uma questão -chave. O motivo disso é mapear principalmente os valores de hash. Vamos primeiro olhar para o método hash no hashmap:
final int hash (objeto k) {int h = 0; if (usealthinging) {if (k instanceof string) {return sun.misc.hashing.stringhash32 ((string) k); } h = hashseed; } h ^= k.hashcode (); // Esta função garante que os códigos de hash que diferentes apenas por // múltiplos constantes em cada posição de bit tenham um número limitado de colisões (aproximadamente 8 no fator de carga padrão). h ^ = (h >>> 20) ^ (h >>> 12); retornar h ^ (h >>> 7) ^ (h >>> 4);} estático int indexfor (int h, int length) {return h & (comprimento-1);}O método hash () recalcula o valor de hash da chave e usa operações de bits relativamente complexas. Não conheço a lógica específica. De qualquer forma, é definitivamente um método melhor, que pode reduzir conflitos ou algo assim.
O indexfor () abaixo está o subscrito do elemento na tabela de hash com base no valor do hash. Geralmente, em uma tabela de hash, você usa valores de hash para modular o comprimento da tabela. Quando o comprimento (ou seja, capacidade) é uma potência de 2, H & (comprimento-1) é o mesmo efeito. Além disso, o poder de 2 deve ser um número par e, depois de subtrair 1, é um número ímpar, e o último bit do binário deve ser 1. Então o último bit de h & (comprimento-1) pode ser 1 ou 0, o que pode ser hash de uniformenamento. Se o comprimento for um número ímpar, o comprimento-1 é um número par e o último bit é 0. Nesse momento, o último bit de H & (comprimento-1) pode ser apenas 0 e todos os subscritos resultantes são uniformes, então metade do espaço é desperdiçado. Portanto, a capacidade no hashmap deve ser uma potência de 2. Você pode ver que o padrão padrão_initial_capacity = 16 e o maximum_capacity = 1 << 30 são assim.
Objeto de entrada
Os pares de valor-chave no hashmap são encapsulados em objetos de entrada, que é uma classe interna no hashmap. Vamos dar uma olhada em sua implementação:
Classe estática Entrada <k, v> implementa mapa.entry <k, v> {final k key; Valor V; Entrada <k, v> próximo; int hash; Entrada (int h, k k, v v, entrada <k, v> n) {value = v; próximo = n; chave = k; hash = h; } public final k getKey () {return key; } public final v getValue () {retornar valor; } public final V SetValue (v newValue) {v OldValue = value; valor = newValue; retornar OldValue; } public final boolean é igual (objeto o) {if (! (o instanceof map.entry)) retornar false; Map.entry e = (map.entry) o; Objeto k1 = getKey (); Objeto k2 = e.getKey (); if (k1 == k2 || (k1! = null && k1.equals (k2))) {objeto v1 = getValue (); Objeto v2 = e.getValue (); if (v1 == v2 || (v1! = null && v1.equals (v2))) retorne true; } retornar false; } public final int hashCode () {return (key == null? 0: key.hashcode ()) ^ (value == null? 0: value.hashcode ()); } public final string tostring () {return getKey () + "=" + getValue (); } void recordaccess (hashmap <k, v> m) {}}A implementação desta classe é simples e fácil de entender. Métodos como getKey (), getValue () são fornecidos para chamada. Para determinar a igualdade, é necessário que a chave e o valor sejam iguais.
Coloque operação
Coloque primeiro antes de obtê -lo, então veja o método put () primeiro:
public V put (K -Key, V valor) {if (key == null) retorna putformullKey (valor); int hash = hash (chave); int i = indexfor (hash, tabela.length); para (entrada <k, v> e = tabela [i]; e! = null; e = e.next) {objeto k; if (e.hash == hash && ((k = e.Key) == key || key.equals (k))) {v OldValue = e.value; E.Value = Value; E.RecordAccess (isto); retornar OldValue; }} modCount ++; addentry (hash, chave, valor, i); retornar nulo;}Neste método, primeiro determine se a chave é nula. Se sim, ligue para o método putformullkey (), o que significa que o hashmap permite que a chave seja nula (de fato, o valor pode ser). Se não for nulo, calcule o valor do hash e obtenha o subscrito na tabela. Em seguida, vá para a lista vinculada correspondente para consultar se a mesma chave já existe. Se já existir, o valor será atualizado diretamente. Caso contrário, ligue para o método addEntry () para inserção.
Dê uma olhada no método putformullkey ():
Private v PutforNullKey (Value V) {for (Entrada <k, v> e = tabela [0]; e! = null; e = e.next) {if (e.key == null) {v OldValue = E.Value; E.Value = Value; E.RecordAccess (isto); retornar OldValue; }} modCount ++; addentry (0, nulo, valor, 0); retornar nulo;}Pode -se observar que, quando a chave for nula, o valor será atualizado se existir, caso contrário, addentry () será chamado para inserir.
A seguir, é apresentada a implementação do método addEntry ():
Void Addentry (int hash, K Key, V Valor, int BucketIndex) {if ((size> = limiar) && (null! = tabela [bucketIndex])) {redimensionamento (2 * tabela.length); hash = (null! = chave)? hash (chave): 0; bucketIndex = indexfor (hash, tabela.length); } createEntry (hash, chave, valor, bucketIndex);} void createEntry (int hash, k key, v value, int bucketIndex) {entrada <k, v> e = tabela [bucketIndex]; tabela [bucketIndex] = nova entrada <> (hash, chave, valor, e); tamanho ++;}Primeiro, determine se deve expandir a capacidade (a capacidade de expansão recalculará o valor do subscrito e copiará o elemento), calcule o subscrito da matriz e, finalmente, insira o elemento usando o método de inserção do cabeçalho no CreateEntry ().
Obtenha operação
public v get (chave do objeto) {if (key == null) return getFornullKey (); Entrada <k, v> entrada = getentry (chave); retornar nulo == entrada? null: Entry.getValue ();} private v getFornullKey () {for (Entrada <k, v> e = tabela [0]; e! = null; e = e.next) {if (e.key == null) retornar e.value; } retornar null;} entrada final <k, v> getentry (chave do objeto) {int hash = (key == null)? 0: Hash (chave); for (entrada <k, v> e = tabela [indexfor (hash, tabela.length)]; e! = null; e = e.next) {objeto k; if (e.hash == hash && ((k = e.key) == key || (key! = null && key.equals (k)))) retornar e; } retornar nulo;}Isso é mais simples que o put (). Você também precisa determinar se a chave é nula e, em seguida, a consulta Traversal da lista vinculada.
Otimização de desempenho
O Hashmap é uma estrutura de dados eficiente e universal que pode ser vista em todos os lugares de todos os programas Java. Vamos apresentar algum conhecimento básico primeiro. Como você também deve saber, o hashmap usa os métodos HashCode () e Equals () da chave para dividir os valores em diferentes baldes. O número de baldes é geralmente um pouco maior que o número de registros no mapa, para que cada balde inclua menos valores (de preferência um). Ao pesquisar nas teclas, podemos localizar rapidamente um balde (usando hashcode () para modular o número de baldes) e o objeto que estamos procurando em tempo constante.
Você já deveria saber todas essas coisas. Você também pode saber que as colisões de hash podem ter um impacto catastrófico no desempenho do hashmap. Se vários valores hashcode () cairem no mesmo balde, esses valores serão armazenados em uma lista vinculada. Na pior das hipóteses, todas as teclas são mapeadas para o mesmo balde; portanto, o hashmap degenera em uma lista vinculada - o tempo de pesquisa é de O (1) a O (n). Vamos primeiro testar o desempenho do Hashmap em Java 7 e Java 8 em circunstâncias normais. Para controlar o comportamento do método hashcode (), definimos uma classe chave da seguinte maneira:
classe Chave implementa comparável <Key> {private final int Value; key (int value) {this.value = value;}@SubsteridePublic int compareto (chave o) {return integer.comPare (this.value, o.value);}@substituição de substituição boolean = o object o) {if (this ==) o.getclass ()) retornar false; key key = (key) o; valor de retorno == key.value;}@substituirpublic int hashcode () {return value;}}A implementação da classe chave é bastante padrão: reescreve o método Equals () e fornece um método HashCode () bastante decente. Para evitar o GC excessivo, cache o objeto de chave imutável em vez de começar a criá -lo novamente toda vez:
Classe Chave implementa comparável <Key> {classe pública Chaves {public static final int max_key = 10_000_000; Keys_cache [valor];}Agora podemos começar a testar. Nosso benchmark usa valores -chave contínuos para criar hashmaps de tamanhos diferentes (multiplicador para 10, de 1 a 1 milhão). No teste, também usaremos as chaves para pesquisar e medir o tempo necessário para hashmaps de tamanhos diferentes:
importar com.google.caliper.param; importar com.google.caliper.runner; importar com.google.caliper.simplebenchmark; classe pública mapbenchmark estende simplesBenchmark {private hashmap <key, inteiro> map; @paramprivate int mapsize; @OverrideProttected assassinando (INTEGER> Hashmap <> (mapsize); para (int i = 0; i <mapsize; ++ i) {map.put (keys.of (i), i);}} public void timemapget (int reps) {para (int i = 0; i <reps; i ++) {}}} {»» {»}Curiosamente, neste simples hashmap.get (), o Java 8 é 20% mais rápido que o Java 7. O desempenho geral também é muito bom: embora existam um milhão de registros no Hashmap, uma única consulta levou apenas menos de 10 nanossegundos, que são cerca de 20 ciclos de CPU na minha máquina. Muito chocante! Mas não é isso que queremos medir.
Suponha que haja uma chave ruim, ela sempre retorna o mesmo valor. Este é o pior cenário, e você não deve usar o hashmap:
classe Chain implementa comparável <Key> {//...@overridepublic int hashcode () {return 0;}}Os resultados do Java 7 são esperados. À medida que o tamanho do hashmap aumenta, a sobrecarga do método get () está ficando cada vez maior. Como todos os registros estão na lista vinculada ultra-longa no mesmo balde, pesquisar em uma média de um registro requer travessia metade da lista. Portanto, pode ser visto a partir da figura que sua complexidade do tempo é O (n).
No entanto, o Java 8 tem um desempenho muito melhor! É uma curva de log, portanto, seu desempenho é melhor de magnitude. Apesar do pior cenário de colisões graves de hash, esse mesmo referência tem uma complexidade de tempo no JDK8 de O (LOGN). Se você olhar apenas para a curva do JDK 8, ficará mais claro. Esta é uma distribuição linear logarítmica:
Por que existe uma melhoria de desempenho tão ótima, embora o grande símbolo O seja usado aqui (o Big O descreve o limite superior assintótico)? De fato, essa otimização foi mencionada no JEP-180. Se o registro em um balde for muito grande (atualmente Treeify_threshold = 8), o hashmap o substituirá dinamicamente por uma implementação especial do TreeMap. Isso resultará em melhores resultados, O (logn), não é ruim O (n). Como funciona? Os registros correspondentes à chave que têm conflitos na frente são simplesmente anexados a uma lista vinculada, e esses registros só podem ser encontrados através do Traversal. No entanto, depois de exceder esse limiar, o hashmap começa a atualizar a lista para uma árvore binária, usando o valor do hash como a variável de ramificação da árvore. Se os dois valores de hash não forem iguais, mas apontando para o mesmo balde, o maior será inserido na subárvore direita. Se os valores de hash forem iguais, o HashMap espera que o valor da chave seja melhor implementado pela interface comparável para que ela possa ser inserida em ordem. Isso não é necessário para a chave do Hashmap, mas é claro que é o melhor se implementado. Se essa interface não for implementada, você não deve esperar melhorias de desempenho no caso de colisões graves de hash.
Qual é o uso dessa melhoria de desempenho? Por exemplo, um programa malicioso, se souber que estamos usando um algoritmo de hash, ele pode enviar um grande número de solicitações, resultando em colisões sérias de hash. Em seguida, acessar constantemente essas chaves pode afetar significativamente o desempenho do servidor, o que leva a um ataque de negação de serviço (DOS). O salto de O (n) para O (logn) no JDK 8 pode efetivamente impedir ataques semelhantes, além de aumentar um pouco a previsibilidade do desempenho do hashmap. Espero que essa melhoria eventualmente convença seu chefe a concordar em atualizar para o JDK 8.
O ambiente usado para o teste é: Intel Core i7-3635qm @ 2,4 GHz, memória de 8 GB, disco rígido SSD, usando parâmetros JVM padrão, executando em um sistema Windows 8.1 de 64 bits.
Resumir
A implementação básica do HashMap é a analisada acima e, finalmente, o resumo é feito: