Analisamos os dois conjuntos de ArrayList e LinkedList. Sabemos que o ArrayList é implementado com base em matrizes e o LinkedList é implementado com base em listas vinculadas. Cada um tem suas próprias vantagens e desvantagens. Por exemplo, o ArrayList será melhor do que o LinkedList ao posicionar e procurar elementos, enquanto o LinkedList será melhor que o ArrayList ao adicionar e remover elementos. O hashmap introduzido neste artigo combina as vantagens de ambos. Sua camada subjacente é implementada com base em uma tabela de hash. Se o conflito de hash não for considerado, a complexidade do tempo do hashmap, além disso, as operações de exclusão, modificação e pesquisa podem atingir um surpreendente O (1). Vamos primeiro olhar para a estrutura da tabela de hash na qual ela se baseia.
Como pode ser visto na figura acima, uma tabela de hash é uma estrutura composta por uma matriz e uma lista vinculada. Obviamente, a figura acima é um mau exemplo. Uma boa função de hash deve tentar calcular a média da distribuição de elementos na matriz, reduzir os conflitos de hash e reduzir a duração da lista vinculada. Quanto maior o comprimento da lista vinculada significa que quanto mais nós precisarão ser percorridos durante a pesquisa, pior será o desempenho da tabela de hash. Em seguida, vamos dar uma olhada em algumas variáveis de membro do hashmap.
// Capacidade inicial padrão estática final int default_initial_capacity = 1 << 4; // Capacidade máxima padrão estática final int maximum_capacity = 1 << 30; // fator de carregamento padrão refere -se a quanto a tabela de hash pode atingir a entrada final da float static <facor_load_factor = 0,75f; // vazio] tabela entrada transitória <k, v> [] tabela = (entrada <k, v> []) email_table; // tamanho do hashmap, ou seja, o número de pares de valor-chave armazenados no tamanho do transiente do hashmap; // o limite de uso do número de chaves do hashMap é que a capacidade de carga do hash precisa ser ampliada; mecanismo de falha-fast transitório int modCount; // use o limiar padrão do hash alternativo estático int alternative_hashing_threshold_default = INTEGER.MAX_VALUE; // A semente de hash aleatória ajuda a reduzir o número de colisões de hash transitório int hashseed = 0;
Como pode ser visto nas variáveis do membro, a capacidade inicial padrão do hashmap é 16 e o fator de carregamento padrão é de 0,75. O limiar é o limite do par de valores-chave que pode ser armazenado no conjunto. O padrão é o fator de carregamento da capacidade inicial*, ou seja, 16*0,75 = 12. Quando o par de valores-chave precisa exceder o limite, isso significa que a tabela de hash já está saturada no momento. Se os elementos continuarem a ser adicionados, o conflito de hash será adicionado, o que degradará o desempenho do hashmap. No momento, o mecanismo de expansão da capacidade automática será acionada para garantir o desempenho do hashmap. Também podemos ver que a tabela de hash é na verdade uma matriz de entrada, e cada entrada armazenada na matriz é o nó de cabeçalho da lista vinculada de mão única. Esta entrada é uma classe interna estática de hashmap, vamos dar uma olhada nas variáveis de entrada de membros.
Classe estática Entrada <k, v> implementa mapa.entry <k, v> {final k key; // Chave V Valor; // Entrada de valor <k, v> Em seguida; // a referência à próxima entrada int hash; // Histocode ... // omita o seguinte código}Uma instância de entrada é um par de valores-chave que contém chave e valor. Cada instância de entrada tem uma referência à próxima instância de entrada. Para evitar cálculos repetidos, cada instância de entrada também armazena o código de hash correspondente. Pode -se dizer que a matriz de entrada é o núcleo do hashmap e todas as operações são feitas para essa matriz. Como o código -fonte do Hashmap é relativamente longo, é impossível introduzir todos os seus métodos de maneira abrangente, por isso nos concentramos apenas nos pontos -chave para apresentá -los. Em seguida, seremos orientados a problemas e exploraremos o mecanismo interno do hashmap em profundidade para os seguintes problemas.
1. Que operações o Hashmap faz durante a construção?
// Construtor, passa na capacidade de inicialização e fator de carga HashMap (int InitialCapacity, Float LoadFactor) {if (InitialCapacidade <0) {lança nova ilegalArgumentException ("Capacidade inicial ilegal:" + InitialCapacity); } // Se a capacidade de inicialização for maior que a capacidade máxima, defina -a na capacidade máxima se (InitialCapacidade> Máximo_Capacity) {InitialCapacity = Maximum_Capacity; } // Se o fator de carga for menor que 0 ou o fator de carga não for um número de ponto flutuante, uma exceção será lançada se (LoadFactor <= 0 || float.isnan (LoadFactor)) {lança nova ilegalArgumentException ("Fator de carga ilegal:" + LoadFactor); } // Defina o fator de carga this.loadFactor = loadFactor; // O limite é limite de capacidade de inicialização = inicialCaPacity; init ();} void init () {}Todos os construtores chamarão esse construtor. Nesse construtor, vemos que, além de fazer alguma verificação dos parâmetros, ele faz duas coisas: defina o fator de carga para o fator de carga recebido e defina o limite para o tamanho da inicialização de entrada. O método init está vazio e não faz nada. Observe que, neste momento, nenhuma nova matriz de entrada é criada com base no tamanho da inicialização de entrada. Então, quando criaremos uma nova matriz? Continue lendo.
2. Quais operações serão executadas quando o Hashmap adicionar pares de valor-chave?
// Coloque os pares do valor-chave no hashmap public V put (K-Key, V Value) {// Inicialize if (tabela == emailt_table) {// Inicialize a tabela de hash Inflatetable (limite); } if (key == null) {return putformullkey (valor); } // Calcule o código de hash do key int hash = hash (chave); // posicionar a posição da tabela de hash de acordo com o código de hash int = indexfor (hash, tabela.length); para (entrada <k, v> e = tabela [i]; e! = null; e = e.next) {objeto k; // Se a chave correspondente já existir, substitua seu valor de valor e retorne o valor original se (e.hash == hash && ((k = e.key) == key || key.equals (k))) {v antiga = e.value; E.Value = Value; E.RecordAccess (isto); retornar OldValue; }} modCount ++; // Se não houver chave correspondente, adicione a entrada ao hashmap addentry (hash, chave, valor, i); // retornar NULL Return null;}Você pode ver que, ao adicionar pares de valor-chave, primeiro verificará se a tabela de hash é uma tabela vazia e, se for uma tabela vazia, será inicializada. Em seguida, execute operações subsequentes e chame a função de hash para calcular o código de hash da tecla passada. Posicione o slot especificado da matriz de entrada de acordo com o código de hash e, em seguida, atravesse a lista vinculada de uma via do slot. Se já existir o passado, execute uma operação de substituição, caso contrário, uma nova entrada será criada e adicionada à tabela de hash.
3. Como a tabela de hash é inicializada?
// Inicialize a tabela de hash e a capacidade da tabela de hash se expandirá, porque é possível que a capacidade de entrada não seja uma potência de 2 inflatedable privado (int tosize) {// a capacidade da tabela de hash deve ser uma potência de 2 capacidade integral = rounduppowowerOf2 (tosize); // Defina o limite, aqui é geralmente a capacidade * LIMPADOR DO FACTOR DO LOUTE = (int) Math.Min (Capacidade * LoadFactor, Maximum_Capacity + 1); // Crie uma nova tabela de hash com uma tabela de capacidade especificada = nova entrada [capacidade]; // Inicialize a semente de hash inithashSeedasNeeded (Capacidade);}Como sabemos acima, ao construir um hashmap, não criaremos uma nova matriz de entrada, mas verifique se a tabela de hash atual é uma tabela vazia durante a operação de put. Se for uma tabela vazia, chame o método inflatável de inicialização. O código para este método é publicado acima. Você pode ver que a capacidade da matriz de entrada será recalculada dentro do método, porque o tamanho da inicialização passada ao construir o hashmap pode não ser uma potência de 2, portanto, você precisa converter esse número em uma potência de 2 e criar uma nova matriz de entrada com base na nova capacidade. Ao inicializar a tabela de hash, redefine o limite novamente e o limite geralmente é capacidade*Factor de carga. Além disso, a semente de hash (hashseed) será inicializada ao inicializar a tabela de hash. Esta hashseed é usada para otimizar a função de hash. O padrão é 0, e nenhum algoritmo de hash alternativo é usado, mas você também pode definir o valor da hash por si mesmo para alcançar o efeito de otimização. Isso será discutido em detalhes abaixo.
4. Quando o Hashmap determina se precisa expandir a capacidade e como expande a capacidade?
// Adicione o método de entrada e primeiro determine se você deseja expandir a capacidade vazia addentry (int hash, k -chave, v valor, int bucketIndex) {// se o tamanho do hashmap for maior que o limiar e o valor do slot correspondente da tabela de hash não estiver vazio (tamanho> = limhold) && (Nul! Limiar, indica que um conflito de hash está prestes a ocorrer, portanto, expanda a capacidade redimensione (2 * tabela.length); hash = (null! = chave)? hash (chave): 0; bucketIndex = indexfor (hash, tabela.length); } // É mostrado aqui que o tamanho do hashmap não excede o limite; portanto, não há necessidade de expandir a capacidade CreateEntry (hash, chave, valor, bucketIndex);} // estender a tabela de hash void (int newCapacity) {Entry [] Oldtable = tabela; int OldCapacity = OldTable.Length; // Se a capacidade máxima atual já estiver em uso, você só poderá aumentar o limite se (OldCapacity == MAXIMUM_CAPACIDADE) {Threshold = Integer.max_value; retornar; } // Caso contrário, expanda a entrada da capacidade [] newTable = nova entrada [newCapacity]; // o método para migrar a transferência de tabela de hash (newTable, inithashSeedasNeeded (NewCapacity)); // Defina a tabela de hash atual para a nova tabela de hash = newTable; // Atualize o limite da tabela de hash = (int) math.min (newCapacity * loadFactor, maximum_capacity + 1);}Ao chamar o método PUT para adicionar um par de valores-chave, se não houver chave na coleção, ligue para o método Addentry e crie uma nova entrada. Quando você vê o código Addentry publicado acima, antes de criar uma nova entrada, primeiro determinará se o tamanho do elemento de coleta atual excede o limite. Se o limiar exceder o limite, a chamada redimensione para expansão. A nova capacidade aprovada é o dobro da tabela de hash original. No método de redimensionamento, uma nova matriz de entrada com capacidade de duas vezes a tabela de hash original será criada. Em seguida, todos os elementos da tabela antiga de hash são migrados para a nova tabela de hash, onde a rehash pode ser realizada e se deve executar a rehash é executada de acordo com o valor calculado pelo método InithashSeedasNeeded. Após a conclusão da migração da tabela de hash, a tabela de hash atual é substituída por uma nova e, finalmente, o valor limite do hashmap é recalculado com base na nova capacidade da tabela de hash.
5. Por que o tamanho da matriz de entrada deve ser uma potência de 2?
// retorna o índice de matriz correspondente ao código de hash static int indexfor (int h, int length) {return h & (comprimento-1); }O método do índice para calcula o subscrito correspondente na matriz com base no código de hash. Podemos ver que o operador (&) é usado dentro deste método. A operação é executar operações de bit em dois operandos. Se os dois bits correspondentes forem 1, o resultado será 1, caso contrário, são 0. As operações são frequentemente usadas para remover valores de alto bit de operandos, como: 01011010 & 00001111 = 00001010. Vamos voltar ao código e ver o que H & (comprimento-1) faz.
Sabe -se que o comprimento passado é o comprimento da matriz de entrada. Sabemos que o subscrito da matriz é calculado a partir de 0, portanto o subscrito máximo da matriz é o comprimento-1. Se o comprimento for uma potência de 2, os bits binários do comprimento-1 são seguidos por 1. Nesse momento, a função de H & (comprimento-1) é remover o valor de alto bit de H e deixar apenas o valor baixo de H como o subscrito da matriz. A partir disso, podemos ver que o tamanho da matriz de entrada é definido como uma potência de 2 para usar esse algoritmo para determinar o subscrito da matriz.
6. Como a função de hash calcula o código de hash?
// a função que gera código de hash final int hash (objeto k) {int h = hashseed; // Se a chave for do tipo de string, use outro algoritmo de hash if (0! = H && k instanceof string) {return sun.misc.hashing.stringhash32 ((string) k); } h ^= k.hashcode (); // a função de perturbação h ^ = (h >>> 20) ^ (h >>> 12); retornar h ^ (h >>> 7) ^ (h >>> 4);}As duas últimas linhas do método hash são o algoritmo que realmente calcula o valor do hash. O algoritmo que calcula o código de hash é chamado de função de perturbação. A chamada função de perturbação é misturar tudo. Você pode ver que quatro operações de turno direito à direita são usadas aqui. O objetivo é misturar o alto valor de H e o baixo valor para aumentar a aleatoriedade do valor baixo. Como acima, sabemos que o subscrito da matriz de posicionamento é determinado com base no valor de baixo bit do código de hash. O código de hash da chave é gerado pelo método HashCode e o baixo valor do código de hash gerado por um método ruim de hashcode pode ter muita repetição. Para tornar o código de hash mapeado relativamente uniformemente na matriz, a função de perturbação é útil, combinando as características do valor de alto bit no valor de baixo bit, aumentando a aleatoriedade do valor de baixo bit, tornando assim a distribuição de hash mais solta, melhorando o desempenho. A figura a seguir dá um exemplo para ajudar a entender.
7. O que está acontecendo com o hash de substituição?
Vemos que no método hash, o hashseed será atribuído primeiro a h. Esta hashseed é uma semente de hash, que é um valor aleatório, e é usado para ajudar a otimizar a função de hash. A hash de hash padrão é 0, o que significa que o algoritmo de hash alternativo não é usado por padrão. Então, quando usar a hashseed? Primeiro, você precisa definir o hash alternativo para ativar e definir o valor de jdk.map.althashing.threshold na propriedade do sistema. Este valor é -1 por padrão na propriedade do sistema. Quando é -1, o valor limite do uso do hash alternativo é inteiro.max_value. Isso também significa que você nunca pode usar um hash de substituição. É claro que você pode definir esse limite um pouco menor, para que uma hash de semente aleatória seja gerada quando o elemento definido atingir o limite. Isso aumenta a aleatoriedade da função de hash. Por que usar hash alternativo? Quando o elemento definido atinge o limite que você define, significa que a tabela de hash está relativamente saturada e a possibilidade de conflitos de hash aumentará bastante. No momento, o uso de uma função de hash mais aleatória para os elementos adicionados pode tornar os elementos adicionados mais aleatoriamente distribuídos na tabela de hash.
Nota: Toda a análise acima é baseada no JDK1.7, e haverá grandes mudanças entre diferentes versões, os leitores precisam prestar atenção.