Prefácio: Há muitas coisas novas adicionadas após o Java 8. Encontrei algumas informações relevantes online. Depois que o Hashmap foi abusado, decidi resolver o conhecimento relevante para mim. Este artigo para referência na imagem e algum conteúdo: http://www.vevb.com/article/80446.htm
A estrutura de armazenamento do hashmap é mostrada na figura: se houver mais de 8 nós em um balde, a estrutura de armazenamento é uma árvore vermelha e preta e menos de 8 é uma lista vinculada de mão única.
1: Algumas propriedades do hashmap
Classe pública hashmap <k, v> estende abstrataMap <k, v> implementa mapa <k, v>, clonável, serializável {private estático final serialversionuid = 362498820763181265L; // a capacidade inicial é 16static Int default_initial_capacity = 1 <<1///capacity // a capacidade inicial 4; 30; // O fator de preenchimento padrão (as versões anteriores também foram chamadas de fator de carga) estático FLOAT FILOATFAULT_LOAD_FACTOR = 0,75F; // Este é um limite. Quando o número de listas vinculadas no balde for maior que esse valor, ele será convertido em uma árvore vermelha e preta. O código do método put usa o estático Int Treeify_threshold = 8; // também é o limite. Quando o número de listas vinculadas no balde é menor que esse valor, a árvore é convertida em uma lista vinculada final estático int unSeleify_threshold = 6; // é dito no comentar o código -fonte que é: a capacidade mínima dos pregos de 4 x Treeify_Threshold = 32. Em seguida, para evitar (o resumo e a árvore dos pregos). dos elementos é armazenado, sempre um múltiplo de 2 nó transitório <k, v> [] tabela; conjunto transitório <pap.entry <k, v >> conjunto de entrada; // o número de elementos armazenados, observe que isso não é igual ao comprimento da matriz. Tamanho Int transitório; // O contador para cada expansão e mudança da estrutura do mapa é transitório Int ModCount; // O valor crítico é expandido quando o tamanho real (fator de preenchimento de capacidade * de capacidade) excede o valor crítico, a capacidade é expandida do limite int; // o fator de enchimento final do float cargas do float;2: Método de construção de hashmap
// Constructor for specifying initial capacity and fill factor public HashMap(int initialCapacity, float loadFactor) {// The specified initial capacity is non-negative if (initialCapacity < 0)throw new IllegalArgumentException(Illegal initial capacity: +initialCapacity);// If the specified initial capacity is greater than the maximum capacity, set it to the maximum capacity if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = Maximum_capacity; // A relação de preenchimento é positiva se (LoadFactor <= 0 || float.isnan (loadfactor)) lançar uma nova ilegalArgumentException (fator de carga ilegal: +carga de carga); this.loadFactor = LoadFactor; // Após especificar a capacidade, o método Tablese para o método calcula o valor crítico. Se o valor for excedido ao colocar os dados, ele será expandido. O valor é definitivamente um múltiplo de 2.// A capacidade inicial especificada não foi salva e é usada apenas para gerar um valor crítico this.Threshold = TableSizeFor (InitialCapacity);} // Este método garante que sempre retorne um valor maior que o CAP e um múltiplo de 2. Por exemplo, a transmissão de 999 »Retornos 1024STATTATATATTIC INT e um múltiplo para 2. | = n >>> 1; n | = n >>> 2; n | = n >>> 4; n | = n >>> 8; n | = n >>> 16; // Retorno aninhado dos operadores trigonométricos (n <0)? 1: (n> = maximum_capacity)? Maximum_Capacity: n + 1;} // Construtor 2Public HashMap (int InitialCapacity) {this (InitialCapacity, Default_load_Factor);} // construtor 3public hashmap () {this.loadFactor = default_load_actor; // todos os outros campos padrão}3: determine a posição do elemento na matriz ao obter e colocar
estático final int hash (chave do objeto) {int h; return (key == null)? 0: (h = key.hashcode ()) ^ (h >>> 16);}Para determinar a localização
A primeira etapa: a primeira coisa é calcular o código de hash da chave, que é um número do tipo int. Os seguintes comentários do código -fonte H >>> 16 dizem: Para evitar colisões de hash, a alta posição está espalhada para a posição baixa, que é feita após levar em consideração vários fatores, como velocidade e desempenho.
Etapa 2: H é o código de hash, o comprimento é o comprimento da matriz [] [] acima, faça a mesma operação H & (comprimento-1). Como o comprimento é um múltiplo de 2 -1, seu código binário é 1 e o resultado de 1 com outros números nele pode ser 0 ou 1, de modo a garantir a uniformidade após a operação. Ou seja, o método de hash garante a uniformidade dos resultados, que é muito importante e afetará bastante a colocação e o desempenho do hashmap. Veja a imagem a seguir para comparação:
A Figura 3.1 são resultados de hash assimétricos
Figura 3.2 é o resultado do hash equilibrado
Não há muitos dados nesses dois gráficos. Se a lista vinculada for superior a 8, ela será convertida em uma árvore vermelha e preta. Seria mais óbvio naquele momento. O JDK8 sempre foi uma lista vinculada antes. A complexidade da consulta da lista vinculada é O (n) e a complexidade das árvores vermelhas e negras devido às suas próprias características é O (log (n)). Se os resultados do hash forem desiguais, isso afetará bastante a complexidade da operação. Existe um <a href = "http://blog.chinaunix.net/uid-26575352-id-3061918.html"> blog de conhecimento básico em árvore vermelha e preta </a> Há outro exemplo online para verificar: um objeto personalizado é usado para fazer as teclas que se ajustam.
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;}@Overridepublic int hashCode() {// If 1// return 1return i;}// object is stored as a key map, the equals method deve ser implementado @OverridePublic boolean é igual (object obj) {if (obj instância de myKey) {return i.Equals (((((myKey) obj) .i);} else {return false;}}} // A configuração da minha máquina não é alta. map = new Hashmap <> (25000,1); data BEGIN = new Date (); para (int i = 0; i <20000; i ++) {map.put (new MyKey (i), "teste" + i);} date end = new date (); system.out.println ("hora) (ms)" + (end.get;4: Get Method
public v get (chave do objeto) {node <k, v> e; retornar (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 k; // hash & (comprimento -1) Obtenha a posição raiz da árvore vermelha e preta ou o cabeçalho da lista vinculada se ((tab = tabela)! = Null && (n = tab.length)> 0 && (primeiro = TAB [(n - 1) e hash])! key.equals (k)))) retornar primeiro; if ((e = primeiro.next)! = null) {// Se for uma árvore, a complexidade de atravessar a árvore vermelha e preta é O (log (n)) para obter o valor do nó se (primeira instância do TreeNode) (Treenode <k, v>). == hash && ((k = e.key) == key || (key! = null && key.equals (k))) retorna e;} while ((e = e.next)! = null);}} retornar nulo;}5: Coloque o método, quando colocado, localize o balde de acordo com H & (comprimento 1) e depois veja se é uma árvore vermelha e preta ou uma lista vinculada e PutVal
public V put (K -Key, V Value) {return putval (hash (key), chave, valor, false, verdadeiro);} final v putval (int hash, k key, v valor, boolean somentefabsent, despet booleano) {node <k, v> [] guia; Nó <k, v> p; int n, i; // Se a guia estiver vazia ou o comprimento for 0, a memória alocada redimensiona () if ((tab = tabela) == null || (n = tab.length) == 0) n = (tab = redize ()). length; // (n - 1) e hash encontra a posição de put. Se estiver vazio, putif diretamente ((p = tab [i = (n - 1) e hash]) == null) guia [i] = newNode (hash, chave, valor, nulo); else {node <k, v> e; K k; // O valor de hash do primeiro nó é o mesmo, e o valor -chave é o mesmo que a chave de inserção se (p.hash == hash && ((k = P.Key) == key || (key! = Null && key.equals (k))) e = p; se (P, P instanceofed) // o método de put de um método de put de um preto e preto e preto. Depois de Putval, você deve atravessar a árvore inteira. Quando necessário, modifique o valor para garantir as características da árvore vermelha e preta E = ((Treenode <k, v>) p) .putTreeVal (this, tab, hash, chave, valor); else {// Lista vinculada para (int bincount = 0;; ++ bincount) {if ((e = p.next) == null) {/; da tabela, crie um novo nó p.Next = newNode (hash, chave, valor, nulo); // após adicionar um novo nó, se o número de nós atingir o limiar, converta a lista vinculada em uma árvore vermelha e preta (BINCOUNT> = Treeify_threshold - 1) // -1 para 1stTreeifyBin (tabinbin, hash) hash && ((k = e.key) == key || (key! = null && key.equals (k)))) quebra; p = e;}} // Atualizar o valor do nó com o mesmo valor de hash e o valor da chave se (e! valor; tardes.6: Método de redimensionamento
Nó final <k, v> [] redize () {node <k, v> [] oldtab = tabela; int anticcap = (OldTab == null)? 0: OldTab.Length; int Oldthr = limiar; int newCap, newthr = 0; if (antigo> 0) {if (Oldcap> = maximum_capacity) {limhold = integer.max_value; retorna antigo;} // Esta sentença é mais importante, pode ser visto que cada exansão é 2 vezes menor && OldCap> = default_initial_capacity) newthr = Oldthr << 1; // limiar duplo} else if (Oldthr> 0) // A capacidade inicial foi colocada no limite inicial do limite de ThresholdNewCap = antigo; else {// zero limite inicial significa usando padrão (default_facult_initial_capacity; (float) newcap * loadFactor; newthr = (newcap <maximum_capacity && ft <(float) maximum_capacity? (int) ft: Integer.max_value);} Threshold = newthr; @suppresswarnings ("Rawtypes" (Nó <k, v> []) novo nó [newCap]; tabela = newtab; if (Oldtab! = Null) {for (int j = 0; j <antigo; ++ j) {node <k, v> e; if ((e = antigo [j]! 1)] = e; else if (e instância de treenode) ((Treenode <k, v>) e) .split (this, newtab, j, antigo); else {// preservar o ordernode <k, v> lohead = null; null; OldCap) == 0) {if (lotail == null) lohead = e; elseloTail.Next = e; lotail = e;} else {if (hitil == null) hiHead = e; elsehitail.next = e; hitil = e;}} while (} while (} ()! lohead;} if (hitil! = null) {hitil.Next = null; newtab [j + OldCap] = hiHead;}}}}} retornar newtab;}O exposto acima é o conhecimento relevante sobre a análise de princípios de implementação do hashmap java8 introduzido pelo editor. Espero que seja útil para você!