Hashmap e Hashset são dois membros importantes da estrutura de coleção Java. O hashmap é uma classe de implementação comum para a interface do mapa, e o hashset é uma classe de implementação comum para a interface definida. Embora as especificações da interface implementadas pelo HashMap e Hashset sejam diferentes, seu mecanismo de armazenamento de hash subjacente é exatamente o mesmo e até o próprio hashset usa o hashmap para implementá -lo.
De fato, existem muitas semelhanças entre hashset e hashmap. Para o hashset, o sistema usa o algoritmo de hash para determinar o local de armazenamento dos elementos de coleta, para garantir que os elementos de coleta possam ser armazenados e recuperados rapidamente; Para o hashmap, o valor da chave do sistema é processado como um todo, e o sistema sempre calcula o local de armazenamento do valor-chave com base no algoritmo de hash, para que os pares de valor-chave do mapa possam ser armazenados e recuperados rapidamente.
Antes de introduzir o armazenamento de coleções, deve -se ressaltar que, embora uma coleção alega armazenar objetos Java, ele realmente não coloca objetos Java na coleção de conjuntos, mas mantém apenas referências a esses objetos na coleção de conjuntos. Ou seja, uma coleção Java é na verdade uma coleção de várias variáveis de referência que apontam para o objeto Java real.
1. Características básicas do hashmap
Depois de ler os comentários no código -fonte JDK Hashmap.class, você pode resumir muitos recursos de hashmap.
O hashmap permite que a chave e o valor sejam nulos, enquanto a hashtable não.
O hashmap é inseguro, enquanto a hashtable é segura por threads
A ordem dos elementos no hashmap nem sempre é a mesma, e a posição do mesmo elemento também pode mudar com o tempo (o caso de redimensionamento)
A complexidade do tempo de atravessar um hashmap é proporcional à sua capacidade e ao número de elementos existentes. Se você deseja garantir a eficiência da Traversal, a capacidade inicial não pode ser definida muito alta ou o fator de equilíbrio não pode ser definido muito baixo.
Semelhante à lista relacionada anterior, como o hashmap é inseguro, o Fail-Fast será gerado quando o iterador tentar alterar a estrutura do contêiner durante o processo de iteração. Um hashmap sincronizado pode ser obtido através de coleções.SynchronizedMap (Hashmap)
2. Análise da estrutura de dados da tabela de hash
Tabela de hash (tabela de hash, tabela de hash) é uma estrutura de dados que acessa diretamente os locais de armazenamento de memória com base em palavras -chave. Ou seja, a tabela de hash estabelece um mapeamento direto entre palavras -chave e endereços de armazenamento
Conforme mostrado na figura abaixo, a chave obtém uma posição de índice de baldes através da função de hash.
A obtenção do índice através da função de hash ocorrerá inevitavelmente a mesma situação, ou seja, conflito. Aqui estão algumas maneiras de resolver conflitos:
Endereço aberto: A idéia básica desse método é digitalizar posições sob a tabela em sequência ao encontrar conflitos e preencher se houver algum gratuito. O algoritmo específico não será mais explicado, a seguir é um diagrama esquemático:
Encadeamento separado: a idéia básica desse método é reunir a entrada com o mesmo valor de índice em uma lista vinculada ao encontrar conflitos. O algoritmo específico não será mais explicado, a seguir é um diagrama esquemático:
O método para resolver conflitos no hashmap no JDK é usar o método de encadeamento separado.
3. Análise do código -fonte HashMap (JDK1.7)
1. HashMap Read and Write Elements
Entrada
Os elementos armazenados no hashmap são do tipo de entrada. O código -fonte de entrada no código -fonte é fornecido abaixo:
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; } // Os métodos GET e Set de chave, o valor são omitidos, as operações GET e Set serão usadas nos iteradores subsequentes ... Public final boolean igual (objeto o) {if (! (O instanceof map.entry)) return 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; } // Aqui, faça ou opere o código de hash do Key e o HashCode of Value para obter o código de hashCode de entrada public final int hashCode () {return Objects.hashcode (getKey ()) ^ Objects.hashcode (getValue ()); } public final string tostring () {return getKey () + "=" + getValue (); } /** * Este método é chamado sempre que o valor em uma entrada é * substituído por uma invocação de put (k, v) para uma chave k que já está * no hashmap. * / void recordAccess (hashmap <k, v> m) {} / ** * Este método é chamado sempre que a entrada é * removida da tabela. */ void RecordRemoval (hashmap <k, v> m) {}}Uma entrada inclui chave, valor, hash e uma referência à próxima entrada. É óbvio que esta é uma única lista vinculada, que implementa a interface do mapa.Entry.
RecordAcess (Hashmap <k, v> e registroRemoval (hashmap <k, v>) não são implementados no hashmap. No entanto, os dois métodos do LinkedHashmap são usados para implementar o algoritmo LRU.
Get: Leia elementos para obter a entrada correspondente do Hashmap. A seguir, o código -fonte de GET:
public v get (chave do objeto) {// a situação em que a chave é nula se (key == null) retorna getFornullKey (); // Encontre a entrada com base na entrada da chave <k, v> Entrada = getentry (chave); retornar nulo == entrada? null: entrada.getValue (); }GetForNullKey Código fonte
private v getForNullKey () {if (size == 0) {return null; } // Transtrair a cadeia de conflitos para (entrada <k, v> e = tabela [0]; e! = Null; e = e.next) {if (e.key == null) retornar e.value; } retornar nulo; }A entrada com uma chave nula é armazenada na tabela [0], mas a cadeia de conflitos na tabela [0] não tem necessariamente uma chave como nula, por isso precisa ser atravessada.
Obtenha entrada de acordo com a chave:
entrada final <k, v> getentry (chave do objeto) {if (size == 0) {return null; } int hash = (key == null)? 0: Hash (chave); // Obtenha a posição do índice na tabela através do hash e, em seguida, atravessa a lista vinculada conflitante para encontrar a chave para (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; }O exposto acima é o processo de hashmap lendo uma entrada e seu código -fonte. Complexidade do tempo o (1)
Put: Escreva elementos
A operação de put no hashmap é relativamente complicada porque haverá uma operação de expansão de hashmap durante a operação de put.
Quando um novo elemento é escrito, se houver uma chave para escrever o elemento no hashmap, a operação de substituir o valor é executada, o que é equivalente a atualizar. Aqui está o código -fonte de put:
public V PUT (Key K, Value V) {// Se a tabela estiver vazia, preencha se (tabela == vazio_table) de acordo com o limiar do tamanho {inflatetable (limite); } // preencha a entrada com a chave como nulo if (key == null) retorna putformullkey (valor); // gerar hash para obter o mapeamento do índice INSH HASH = HASH (chave); int i = indexfor (hash, tabela.length); // Transular a cadeia de conflitos do índice atual para descobrir se existe uma chave correspondente para (entrada <k, v> e = tabela [i]; e! = Null; e = e.next) {objeto k; // Se a chave correspondente existir, substitua o antigo e retorne o antigo valor se (e.hash == hash && ((k = e.key) == key || key.equals (k))) {v antiga = e.value; E.Value = Value; E.RecordAccess (isto); retornar OldValue; }} // A chave de entrada recém -escrita não existe no modCount ++ da cadeia de conflitos ++; // Insira uma nova entrada Addentry (hash, chave, valor, i); retornar nulo; }Addentry e CreateEntry Código -fonte:
Void Addentry (int hash, K Key, V Valor, int BucketIndex) {// Antes de inserir uma nova entrada, primeiro julgue o tamanho do hashmap atual e seu tamanho limite e selecione se deve expandir se ((tamanho> = limiar) && (null! = Tabela [BucketIndEx])) {reaise (2 *.lngthngth); hash = (null! = chave)? hash (chave): 0; bucketIndex = indexfor (hash, tabela.length); } createEntry (hash, chave, valor, bucketIndex); } void createEntry (int hash, k key, v valor, int bucketIndex) {entrada <k, v> e = tabela [bucketIndex]; // Método de inserção da cabeça, a entrada recém -escrita é inserida na frente da primeira entrada na cadeia de conflitos na posição atual do índice. tabela [bucketIndex] = nova entrada <> (hash, chave, valor, e); tamanho ++; }O exposto acima é o processo de escrever uma entrada em um hashmap e seu código -fonte. Complexidade do tempo o (1)
Remover o elemento Remover:
entrada final <k, v> removentryforkey (chave do objeto) {if (size == 0) {return null; } // Calcule o valor de hash de acordo com a chave e obtenha o índice int hash = (key == null)? 0: Hash (chave); int i = indexfor (hash, tabela.length); // Exclua a lista vinculada, defina dois ponteiros, Presente a entrada do antecessor <k, v> prev = tabela [i]; Entrada <k, v> e = prev; // Transtrair a cadeia de conflitos e excluir todas as chaves while (e! = Null) {Entrada <k, v> next = e.next; Objeto k; // se encontrado (e.hash == hash && ((k = e.key) == key || (key! = Null && key.equals (k)))) {modCount ++; tamanho--; // Encontrar o primeiro nó é o nó a ser excluído se (prev == e) tabela [i] = próximo; else prev.next = a seguir; E.RecordRemoval (this); retornar e; } prev = e; e = próximo; } retornar e; }O exposto acima é o processo de hashmap excluir uma entrada e seu código -fonte. Complexidade do tempo o (1)
2. Princípio do hash de hashmap (função de hash)
A implementação da função de hash no hashmap é feita por hash (objeto k) e índice (int h, int length). Vamos dar uma olhada no código -fonte abaixo:
final int hash (objeto k) {int h = hashseed; if (0! = h && k instanceof string) {return sun.misc.hashing.stringhash32 ((string) k); } 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). // para reduzir a chance de conflito h ^ = (h >>> 20) ^ (h >>> 12); retornar h ^ (h >>> 7) ^ (h >>> 4); }Obtenha o código fonte do índice do índice:
estático int indexfor (int h, int length) {// afirma inteiro.bitcount (comprimento) == 1: "O comprimento deve ser uma potência diferente de zero de 2"; retornar h & (comprimento-1); }O hashmap mapeia as teclas dos índices dentro do intervalo de [0, tabela.length] através de uma função de hash. Geralmente, existem dois tipos de métodos de indexação:
Hash (key) % tabela.length, onde o comprimento deve ser um número primo. Hashtable usa essa implementação no JDK.
Por razões específicas para o uso de números primos, você pode encontrar provas de dados relevantes do algoritmo, que não serão declaradas aqui.
Hash (key) & (tabela.length - 1) onde o comprimento deve estar com a potência exponencial 2. O hashmap no JDK usa esse método de implementação.
Como o tamanho do comprimento é de 2 tempos exponenciais, hash (chave) e (tabela.length - 1) sempre estarão entre [0, comprimento - 1]. No entanto, se você fizer isso sozinho, haverá um grande problema com o conflito, porque o valor do código de hash em Java é de 32 bits. Quando a capacidade do hashmap é pequena, por exemplo, quando 16, ao fazer operação XOR, o bit alto é sempre descartado, mas após a operação de bit baixa, a probabilidade de conflito ocorre aumenta.
Portanto, para reduzir a probabilidade de ocorrência de conflitos, muitas operações de bits e exclusivas ou operações são realizadas no código.
3. Estratégia de alocação de memória de hashmap
Capacidade variável de membro e fator de carga
A capacidade necessária é um múltiplo exponencial de 2 no hashmap e a capacidade padrão é 1 << 4 = 16. Há também um fator de equilíbrio (fator de carga) no hashmap. Fatores excessivamente altos reduzirão o espaço de armazenamento, mas o tempo para a pesquisa (pesquisa, incluindo métodos de put e Get no hashmap) aumentará. O valor padrão do Factor de Load é 0,75, que é o valor ideal dado através da pesar a complexidade do tempo e a complexidade do espaço.
Final estático int default_initial_capacity = 1 << 4; // aka 16 estático final int maximum_capacity = 1 << 30; Float final estático default_load_factor = 0,75f;
Construtor de hashmap
A construção do hashmap é definir a capacidade e o valor inicial do Factor de Load
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); this.loadFactor = loadFactor; limiar = inicialCaPacity; init (); } Eu disse antes que essa capacidade no hashmap deve ser tempos exponenciais de 2, e não há limite no construtor. Então, como garantir que o valor da capacidade seja os tempos exponenciais de 2?
Durante a operação de put, o código -fonte determinará se a tabela de hash atual é uma tabela vazia. Nesse caso, ligue para o Inflatetable (int tosize)
Inflatable de vazio privado (int tosize) {// Encontre uma potência de 2> = tosize int capacidade = rounduptopowerOf2 (tosize); limite = (int) math.min (capacidade * loadFactor, maximum_capacity + 1); tabela = nova entrada [capacidade]; inithashSeedasNeeded (Capacidade); }Onde RounduptopowerOf2 é obter o poder N de 2 maior ou igual ao parâmetro dado
private estático int rounduptopowerOf2 (Int Number) {// ASSERT NUMBER> = 0: "O número deve ser não negativo"; Número de retorno> = Maximum_Capacity? Maximum_Capacity: (Número> 1)? Integer.HighestOneBit ((Número - 1) << 1): 1; }Integer.hightoNeBit (int) é uma operação que mantém o bit mais alto de um determinado parâmetro e altera o 0 restante. Simplificando, é alterar o parâmetro int para n poderes menos ou iguais ao seu máximo 2.
Se o número for N potência de 2, o bit mais alto está no segundo bit original após o decréscimo 1 e depois mude 1 bit esquerdo para ainda ser posicionado para a posição mais alta de bits. Se o número não for a potência n de 2, o bit mais alto ainda é o bit mais alto original após a diminuição de 1 bit para a mudança de 1 bit para ser
Expandir a capacidade:
O hashmap terá um comportamento de redimensionamento ao colocar operação. O código -fonte específico é o seguinte:
Void REDIMENT (int newCapacity) {Entry [] OldTable = tabela; int OldCapacity = OldTable.Length; // A tabela de hash atingiu sua capacidade máxima, 1 << 30 if (OldCapacity == MAXIMUM_CAPACIDADE) {limite = Integer.max_value; retornar; } Entrada [] newTable = nova entrada [newCapacity]; // Transfira a entrada na antiga para o NewTable // O valor de retorno do InithashSeedasNeeded determina se deve recalcular a transferência de valor de hash (newTable, InithashSeedasNeeded (NewCapacity)); tabela = newTable; // limiar de limiar recalculado = (int) math.min (newCapacity * loadFactor, maximum_capacity + 1); } void transfer (entrada [] newTable, boolean rehash) {int newCapacity = newtable.length; // transweep OldTable para (entrada <k, v> e: tabela) {// Cadeia de conflito transweep while (null! = E) {Entrada <k, v> a seguir = e.next; if (rehash) {// recalcula o valor do hash e.hash = null == e.key? 0: Hash (e.Key); } int i = indexfor (e.hash, newCapacity); // Insira o elemento na cabeça, o método de inserção do cabeçalho e.next = newTable [i]; newTable [i] = e; e = próximo; }}}O exposto acima é todo o processo de alocação de memória de hashmap. Em resumo, quando o Hashmap coloca uma entrada, ele verificará a capacidade atual e o tamanho do limite para selecionar se deve expandir a capacidade. O tamanho de cada expansão é 2 * tabela.length. Durante o período de expansão, ele determinará se o valor do hash precisa ser recalculado com base no InithashSeedasNeeded.
4. Iterador de hashmap
Iteradores como ValueIterator, Keyiterator, EntryIterator e outros no HashMap são todos baseados no HashIterator. Vamos dar uma olhada em seu código -fonte:
classe abstrata privada HashIterator <e> implementa o iterador <E> {Entrada <k, v> Em seguida; // Próxima entrada para retornar int esperamodCount; // para Índice Int Fast-Fail; // slot atual, entrada do índice de tabela <k, v> atual; // hashIterator de entrada atual () {esperamModCount = modCount; // Encontre a primeira entrada na tabela de hash if (tamanho> 0) {Entry [] t = tabela; while (índice <t.Length && (next = t [index ++]) == null); }} public final boolean hasNext () {return a seguir! = null; } Entrada final <k, v> nextEntry () {// hashmap é não-thread-sAFE e, ao percorrer, ainda determina se existe alguma modificação da estrutura da tabela se (modCount! = esperamodCount) lançar nova concorrência ModificationException (); Entrada <k, v> e = a seguir; if (e == NULL) lançar novas NosuchElementException (); if ((next = e.next) == null) {// Encontre a próxima entrada de entrada [] t = tabela; while (índice <t.Length && (next = t [index ++]) == null); } atual = e; retornar e; } public void remover () {if (current == null) lança new ilegalStateException (); if (modCount! = esperadoModCount) lança nova concorrentemodificaçãoException (); Objeto k = current.key; atual = nulo; Hashmap.This.RemoveEntryForKey (K); esperadomodCount = modCount; }}Os três iteradores, chave, valor e entrada são encapsulados e se tornam três perspectivas de coleta: tecla, valores e conjunto de entrada. Essas três perspectivas de coleção suportam as operações Remover, Removeall e Clear do HashMap e não suportam operações de adição e adição.