Hashmap também é uma coleção que usamos muito. É uma implementação da interface do mapa com base nas tabelas de hash e existe na forma de um valor-chave. No hashmap, o valor-chave é sempre processado como um todo. O sistema calculará o local de armazenamento do valor-chave com base no algoritmo de hash. Sempre podemos armazenar e recuperar rapidamente o valor através da chave. Vamos analisar o acesso ao hashmap.
1. Definição
Hashmap implementa a interface do mapa e herda o abstrataMap. A interface do mapa define as regras para mapeamento de chaves para valores, e a classe AbstractMap fornece a implementação da backbone da interface do mapa para minimizar o trabalho necessário para implementar essa interface. De fato, a classe AbstractMap implementou o mapa. Eu acho que deve ser mais claro marcar o mapa LZ aqui!
Classe pública Hashmap <k, v> estende abstractmap <k, v> implementa mapa <k, v>, clonável, serializável
2. Função do construtor
Hashmap fornece três construtores:
Hashmap (): Construa um hash de hash vazio com a capacidade inicial padrão (16) e o fator de carregamento padrão (0,75).
HashMap (int InitialCapacity): Construa um hashmap vazio com capacidade inicial especificada e fator de carregamento padrão (0,75).
HashMap (int InitialCapacity, Float LoadFactor): Construa um hashmap vazio com capacidade inicial especificada e fator de carga.
Dois parâmetros são mencionados aqui: capacidade inicial, fator de carregamento. Esses dois parâmetros são parâmetros importantes que afetam o desempenho do hashmap. A capacidade representa o número de baldes na tabela de hash. A capacidade inicial é a capacidade ao criar uma tabela de hash. O fator de carregamento é uma escala que a tabela de hash pode atingir antes que sua capacidade aumente automaticamente. Ele mede o grau de uso de um espaço na tabela de hash. Quanto maior o fator de carga indica quanto maior o grau de carga da tabela de hash e vice -versa. Para tabelas de hash usando o método da lista vinculada, o tempo médio para encontrar um elemento é o (1+a). Portanto, se o fator de carga for maior, o espaço será mais totalmente utilizado, mas a conseqüência é uma diminuição na eficiência da pesquisa; Se o fator de carga for muito pequeno, os dados da tabela de hash serão muito escassos, causando resíduos graves no espaço. O fator de carga padrão do sistema é de 0,75 e geralmente não precisamos modificá -lo.
Hashmap é uma estrutura de dados que suporta acesso rápido. Para entender seu desempenho, você deve entender sua estrutura de dados.
Iii. Estrutura de dados
Sabemos que as duas estruturas mais usadas em Java são matrizes e ponteiros simulados (referências). Quase todas as estruturas de dados podem ser implementadas em combinação com esses dois, e o mesmo se aplica ao hashmap. De fato, o Hashmap é um "hash da lista vinculada", como segue sua estrutura de dados:
A partir da figura acima, podemos ver se a implementação subjacente do hashmap é ou uma matriz, mas cada item da matriz é uma corrente. A capacidade inicial do parâmetro representa o comprimento da matriz. A seguir, o código -fonte do construtor de hashmap:
public hashmap (int inicialCapacity, float LoadFactor) {// A capacidade inicial não pode ser <0 se (InitialCapacity <0) lançar nova ilegalArgumentException ("Capacidade inicial ilegal:" + InitialCapacidade); // A capacidade inicial não pode> valor máximo de capacidade, a capacidade máxima do hashmap é 2^30 se (InitialCapacity> MAXIMUM_CAPACIDADE) InitialCapacity = MAXIMUM_CAPACIDADE; // O fator de carga não pode ser <0 se (LoadFactor <= 0 || float.isnan (LoadFactor)) lança nova ilegalArgumentException ("Fator de carga ilegal:" + LoadFactor); // Calcule o valor N-power dos menores 2 maior que a capacidade inicial. capacidade int = 1; while (Capacidade <InitialCapacity) Capacidade << = 1; this.loadFactor = loadFactor; // Defina o limite de capacidade do hashmap. Quando a capacidade do hashmap atingir esse limite, a operação de expansão da capacidade será executada limite = (int) (capacidade * LoadFactor); // inicialize a tabela de matriz de tabela = nova entrada [capacidade]; init (); } Como pode ser visto no código -fonte, uma matriz de tabela será inicializada toda vez que um novo hashmap for criado. O elemento da matriz de tabela é um nó de entrada.
Classe estática Entrada <k, v> implementa mapa.entry <k, v> {final k key; Valor V; Entrada <k, v> próximo; Final int hash; /*** Cria uma nova entrada. */ Entrada (int h, k k, v v, entrada <k, v> n) {value = v; próximo = n; chave = k; hash = h; } .....}Entre eles, a entrada está a classe interna do hashmap, que contém a chave da chave, o valor do valor, o próximo nó próximo e o valor do hash. Isso é muito importante. É precisamente porque a entrada forma os itens da matriz de tabela como uma lista vinculada.
O acima analisa brevemente a estrutura de dados do hashmap e abaixo explorará como o hashmap implementa acesso rápido.
4. Implementação de armazenamento: Put (Key, Vlaue)
Primeiro, vejamos o código -fonte
public V put (K -Key, V Valor) {// Quando a chave é nula, ligue para o método PutformullKey para salvar a primeira posição de NULL e TABLE. É por isso que o hashmap permite nulo se (key == null) retorna putfornullkey (valor); // Calcule o valor de hash do key int hash = hash (key.hashcode ()); ----- (1) // Calcule a posição do valor do hash da chave na matriz de tabela int i = indexfor (hash, tabela.length); ----- (2) // iterar de i e encontre o local onde a chave é salva (entrada <k, v> e = tabela [i]; e! = Null; e = e.next) {objeto k; // julga se existe o mesmo valor de hash na cadeia (a chave é a mesma) // Se o mesmo existir, substitua diretamente o valor e retorne o valor antigo se (e.hash == hash && ((k = e.key) == key || key.equals (k))) {v OldValue = E.Value; // Valor antigo = novo valor E.Value = Value; E.RecordAccess (isto); retornar OldValue; // retorna o valor antigo}} // aumenta o número de modificações por 1 modCount ++; // Adicione a tecla e o valor à posição i Addentry (hash, chave, valor, i); retornar nulo; }Através do código -fonte, podemos ver claramente que o processo de dados de salvamento de hashmap é: primeiro determine se a chave é nula. Se for nulo, chame diretamente o método PutformullKey. Se não estiver vazio, primeiro calcule o valor de hash da chave e, em seguida, procure a posição do índice na matriz de tabela de acordo com o valor do hash. Se houver um elemento nesta posição, compare se a mesma chave existe. Se existir, substitua o valor da chave original; caso contrário, salve o elemento na cabeça da corrente (o primeiro elemento salvo é colocado no final da corrente). Se a tabela não tiver elementos lá, ela será salva diretamente. Esse processo parece simples, mas na verdade tem informações profundas. Existem vários pontos da seguinte maneira:
1. Vamos olhar primeiro para a iteração. O motivo da iteração aqui é impedir a existência do mesmo valor de chave. Se dois valores de hash (chaves) forem os mesmos, o método de processamento do hashmap é substituir o valor antigo pelo novo valor. A chave não é processada aqui, o que explica que não existem duas chaves idênticas no hashmap.
2. Na vista (1) e (2). Esta é a essência do hashmap. Primeiro de tudo, existe o método hash, que é um cálculo matemático puro, que é calcular o valor de hash de h.
estático int hash (int h) {h ^ = (h >>> 20) ^ (h >>> 12); retornar h ^ (h >>> 7) ^ (h >>> 4); }Sabemos que, para tabelas de hashmap, a distribuição de dados precisa ser uniforme (é melhor ter apenas um elemento para cada item, para que possa ser encontrado diretamente). Não pode ser muito apertado ou muito solto. Muito apertado levará à velocidade de consulta lenta, e muito solta desperdiçar espaço. Depois de calcular o valor do hash, como podemos garantir que os elementos da tabela sejam distribuídos igualmente? Pensaremos na aquisição de moldes, mas como a aquisição de moldes consome muito, o hashmap lida com isso assim: chame o método do índice.
estático int indexfor (int h, int length) {return h & (comprimento-1); }O comprimento da matriz subjacente do hashmap está sempre na potência n de 2 e existe no construtor: capacidade << = 1; Isso sempre pode garantir que o comprimento da matriz subjacente do hashmap esteja na potência n de 2. Quando o comprimento é para n potência de 2, h & (comprimento - 1) é equivalente a tomar o módulo de comprimento, e a velocidade é muito mais rápida do que tomar o módulo diretamente. Esta é uma otimização do hashmap em termos de velocidade. Quanto ao motivo pelo qual é 2 para o enésimo poder, a explicação a seguir é.
Vamos voltar ao método índice, que possui apenas uma afirmação: H & (comprimento - 1). Além da operação do módulo acima, esta frase também tem uma responsabilidade muito importante: distribua uniformemente os dados da tabela e faça uso total do espaço.
Aqui assumimos que o comprimento é 16 (2^n) e 15, e H é 5, 6 e 7.
Quando n = 15, os resultados de 6 e 7 são os mesmos, o que significa que seus locais armazenados na tabela são os mesmos, ou seja, ocorre uma colisão e 6 e 7 formarão uma lista vinculada em um local, o que levará a uma diminuição na velocidade da consulta. É verdade que apenas três números são analisados aqui, mas não muitos, então vamos ver 0-15.
No gráfico acima, vemos um total de 8 colisões e, ao mesmo tempo, descobrimos que o espaço desperdiçado é muito grande, sem registros em 1, 3, 5, 7, 9, 11, 13 e 15 locais, ou seja, nenhum dado é armazenado. Isso ocorre porque, quando eles executam e funcionam com 14, o último bit do resultado que eles obtêm sempre será 0, ou seja, é impossível armazenar dados nos locais de 0001, 0011, 0101, 0111, 1001, 1011, 1101, 1111 e 1111. O espaço é reduzido e a chance de colisão aumentará ainda mais, o que levará a lentidão. Quando o comprimento = 16, comprimento 1 = 15 é 1111. Então, ao executar a operação e operação de baixo bit, o valor é sempre o mesmo que o valor de hash original e, ao executar a operação de alto bit, seu valor é igual ao seu valor de baixo bit. Portanto, quando o comprimento = 2^n, a probabilidade de colisão entre diferentes valores de hash é relativamente pequena, o que tornará os dados distribuídos uniformemente na matriz de tabela e a velocidade da consulta é mais rápida.
Aqui, revisamos o processo de put: quando queremos adicionar um par de valores-chave a um hashmap, o sistema calcula primeiro o valor de hash da chave e depois confirmará o local armazenado na tabela com base no valor do hash. Se não houver elemento nesta posição, insira -o diretamente. Caso contrário, iterar sobre a lista de elementos nesse ponto e compare o valor de hash de sua chave de acordo. Se os dois valores de hash forem iguais e os valores -chave forem iguais (e.hash == hash && ((k = e.key) == key || key.equals (k))), o valor do nó original será substituído com o valor da nova entrada. Se os dois valores de hash forem iguais, mas os valores -chave não forem iguais, insira o nó no cabeçalho da lista vinculada. Para o processo de implementação específico, consulte o método Addentry, como segue:
Void Addentry (int hash, K Key, V Valor, int BucketIndex) {// Obtenha a entrada de entrada <k, v> e = tabela [bucketIndex]; // Coloque a entrada recém -criada no índice bucketIndex e deixe o novo ponto de entrada para a tabela de entrada original [bucketIndex] = nova entrada <k, v> (hash, chave, valor, e); // Se o número de elementos no hashmap exceder o limite, a capacidade será duas vezes maior se (tamanho ++> = limiar) redimensionar (2 * tabela.length); }Há dois pontos a serem observados neste método:
Uma é a geração de correntes. Este é um design muito elegante. O sistema sempre adiciona um novo objeto de entrada ao bucketIndex. Se houver um objeto no BucketIndex, o objeto de entrada recém -adicionado apontará para o objeto de entrada original, formando uma cadeia de entrada. No entanto, se não houver um objeto de entrada no bucketIndex, ou seja, e == null, o objeto de entrada recém -adicionado aponta para NULL e não haverá cadeia de entrada gerada.
2. Expansão de capacidade.
À medida que o número de elementos no hashmap aumenta, a probabilidade de colisão se torna cada vez maior e o comprimento da lista de links gerados se tornará mais longo e mais longo. Isso afetará inevitavelmente a velocidade do hashmap. Para garantir a eficiência do hashmap, o sistema deve expandir a capacidade em um determinado ponto crítico. Esse ponto crítico é quando o número de elementos no hashmap é igual ao fator de carga do comprimento da matriz*. Mas a escala é um processo muito demorado, pois requer recalcular a localização desses dados na nova matriz de tabela e copiá-los. Portanto, se previmos o número de elementos no hashmap, o número de elementos predefinidos pode melhorar efetivamente o desempenho do hashmap.
5. Implementação de leitura: Get (chave)
Comparado com o armazenamento do hashmap, a retirada é relativamente simples. Encontre a entrada no índice na matriz de tabela através do valor de hash da chave e retorne o valor correspondente à chave.
public v get (chave do objeto) {// Se nulo, ligue para o método getFornullKey para retornar o valor correspondente se (key == null) retornar getFornullKey (); // Calcule seu código de hash com base no valor de hashcode do key int hash = hash (key.hashcode ()); // retire o valor no índice especificado na matriz de tabela para (entrada <k, v> e = tabela [indexfor (hash, tabela.length)]; e! = Null; e = e.next) {objeto k; // Se a tecla pesquisada for a mesma que a tecla pesquisada, retorne o valor correspondente se (e.hash == hash && ((k = e.key) == key || key.equals (k)) retorna e.value; } retornar nulo; } Aqui, o valor que pode ser recuperado rapidamente com base na chave não é apenas inseparável da estrutura de dados do HashMap, mas também tem muito a ver com a entrada. Como mencionado anteriormente, o HashMap não armazena a chave e o valor separadamente no procedimento armazenado, mas é processado como um valor de chave inteiro, que é o objeto de entrada. Ao mesmo tempo, o valor é equivalente ao anexo da chave. Durante o processo de armazenamento, o sistema determina o local de armazenamento da entrada na matriz de tabela com base no código de hash da chave e, no processo de busca, o objeto de entrada correspondente também é retirado de acordo com o código de hash da chave.
Link original: http://www.cnblogs.com/chenssy/p/3521565.html
O exposto acima é todo o conteúdo deste artigo. Espero que seja útil para o aprendizado de todos e espero que todos apoiem mais o wulin.com.