HashMap é uma implementação de interface de mapa com base em tabelas de hash, fornecendo todas as operações de mapeamento opcional e permitindo valores nulos e construção nula, fora da sincronização e nenhuma garantia de ordem de mapeamento. Vamos registrar o princípio de implementação do Hashmap.
HASHMAP armazenamento interno
No Hashmap, todos os relacionamentos de pares de valor-chave são armazenados mantendo uma matriz de tabela de variáveis instantâneas (também conhecidas como balde). O balde é uma variedade de objetos de entrada. O tamanho do balde pode ser redimensionado conforme necessário, e o comprimento deve ser uma potência de 2. O seguinte código:
/ *** Uma matriz de entrada vazia, o valor padrão do bucket*/ entrada final estática <? ,?> [] emailt_table = {}; / *** Bucket, redimensione conforme necessário, mas deve ser uma potência de 2*/ entrada transitória <k, v> [] tabela = (entrada <k, v> []) emailt_table;Capacidade inicial e fator de carga
O hashmap possui dois parâmetros que afetam o desempenho, capacidade inicial e fator de carga. Capacidade é o número de baldes na tabela de hash, a capacidade inicial é apenas a capacidade da tabela de hash quando é criada, e o fator de carga é uma escala em que a tabela de hash pode atingir a cheia antes que sua capacidade aumente 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 deve ser reformulada (ou seja, reconstruir a estrutura de dados interna) e a reconstrução é criada com o dobro do número de capacidade atual. A capacidade inicial e o fator de carga podem ser definidos através do construtor. A capacidade inicial padrão é de 16 entradas, a capacidade máxima é de 2^30 entradas e o fator de carga padrão é 0,75
Um balde é como um balde que armazena água. Sua capacidade de armazenamento inicial padrão é de 16 unidades de água. Quando a água é derramada para 16*0,75, a capacidade será expandida primeiro para 32 unidades quando os dados forem adicionados na próxima vez. 0,75 é o fator de carga e a capacidade inicial e o fator de carga podem ser definidos ao criar um balde. A capacidade máxima de um balde é de 2 unidades de água até a potência de 30. Quando o número de configurações de capacidade inicial for maior que a capacidade máxima, a capacidade máxima prevalecerá. Ao expandir, ele será retornado diretamente se for maior ou igual à capacidade máxima.
A seguir, faz parte do código -fonte do Hashmap, que define a capacidade inicial padrão, o fator de carga e algumas outras constantes:
/ ** * A capacidade inicial padrão deve ser a potência de 2. */ Final estático int default_initial_capacity = 1 << 4; // aka 16/ *** Capacidade máxima, se a capacidade inicial for maior que a capacidade máxima através do parâmetro do construtor, a capacidade também será usada como a capacidade inicial* deve ser a potência de 2 e menor ou igual a 30ª potência de 2*/ estático final int maximum_capacity = 1 << 30; / *** O fator de carga padrão pode ser especificado pelo construtor*/ float final estático default_load_factor = 0,75f; / *** Uma tabela de matriz vazia, quando o balde não é inicializado*/ entrada final estática <? ,?> [] emailt_table = {}; / *** Bucket, armazena todas as entradas dos pares de valor-chave e pode ser redimensionado conforme necessário, e o comprimento deve ser uma potência de 2*/ entrada transitória <k, v> [] tabela = (entrada <k, v> []) emailt_table; /*** O número de pares de valor -chave no mapa, o tamanho será de +1 ou -1 operação toda vez que for adicionado ou excluído. */ Tamanho Int transitório; /** * O valor crítico do valor de carga, que precisa ser redimensionado é: (Capacidade * Fator de carga). Após cada redimensionamento, a nova capacidade será calculada usando a nova capacidade. * @Serial */ // se tabela == emailt_table, então essa é a capacidade inicial na qual a tabela // será criada quando inflada. limiar int; / ** * Fator de carga, se não for especificado no construtor, o fator de carga padrão é usado, * * @Serial */ Final Float LoadFactor; /** * Número de modificações de estrutura de hashmap de vezes, altere o número de mapas no hashmap ou modifique sua estrutura interna quando a estrutura for modificada (por exemplo, o método * Rehash, reconstrua a estrutura de dados interna). Este campo é usado em * Os iteradores gerados na visualização de coleta de hashmap são processados em falha rápida */transitório Int modCount;Capacidade inicial e ajuste de desempenho do fator de carga
Normalmente, o fator de carga padrão (0,75) busca um compromisso nos custos de tempo e espaço. Embora o fator de carga seja muito alto, também aumenta o custo da consulta (isso se reflete na maioria das operações de hashmap, incluindo operações GET e PUST). Ao definir a capacidade inicial, o número de entradas necessárias no mapa e seu fator de carga deve ser levado em consideração para minimizar o número de operações de rehash. Se a capacidade inicial for maior que o número máximo de entradas divididas pelo fator de carga, a operação de rehash não ocorrerá.
Se muitos relacionamentos de mapeamento forem armazenados em uma instância de hashmap, criá -lo com uma capacidade inicial grande o suficiente fará com que o relacionamento de mapeamento seja armazenado com mais eficiência em relação à execução de operações automáticas de rehash sob demanda para aumentar a capacidade da tabela.
A seguir, é apresentado o código para reconstruir a estrutura de dados de hashmap:
Void REDIMENT (int newCapacity) {Entry [] OldTable = tabela; int OldCapacity = OldTable.Length; if (OldCapacity == MAXIMUM_CAPACIDADE) {// Se a capacidade atingiu o limite máximo, defina o valor de carga e retorne diretamente para limiar = Integer.max_value; retornar; } // Crie uma nova tabela para armazenar a entrada de dados [] newTable = nova entrada [newCapacity]; // Transfira os dados da tabela antiga para a nova tabela, esta etapa levará muito tempo para transferir (newTable, inithashSeedasNeeded (NewCapacity)); tabela = newTable; // finalmente defina o valor de carga do próximo limite de redimensionamento = (int) math.min (newcapacity * loadFactor, maximum_capacity + 1);}Método de construção de hashmap
O quarto método de construção é criar um novo hashmap com um mapa existente. Vamos falar sobre isso mais tarde. De fato, os três primeiros métodos de construção são chamados no terceiro método final com dois parâmetros. Se nenhum parâmetros for passado, o valor padrão será usado. O código é o seguinte:
/** * Construa um hashmap vazio <Tt> </tt> com a capacidade inicial padrão * (16) e o fator de carga padrão (0,75). */ public hashmap () {this (default_initial_capacity, default_load_factor); } /** * Construa um hashmap vazio <Tt> </tt> com a capacidade inicial * especificada e o fator de carga padrão (0,75). * * @param InitialCapacidade A capacidade inicial. * @THOWSOWS ILAGELARGUMENTEXCECTION se a capacidade inicial for negativa. */ public hashmap (int inicialCapacity) {this (InitialCapacity, default_load_factor); } /** * Construa um hashmap vazio <Tt> </tt> com a capacidade inicial * especificada e fator de carga. * * @param InitialCapacity A capacidade inicial * @param LoadFactor O fator de carga * @THOWSows IllegalarMGumentException Se a capacidade inicial for negativa * ou o fator de carga não for positivo */ hashmap público (int InitialCapacity, Float LoadFactor) {if (InitialCapacity <0) lança new ilegalArgumentExcender ("Capacidade inicial) {if (InitialCapacity <0) <0) 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 (); }Como pode ser visto no exposto, no construtor, se a capacidade inicial for maior que a capacidade máxima, a capacidade máxima será substituída diretamente.
Método de colocar
Em seguida, vamos dar uma olhada nas partes mais importantes do hashmap
/*** Neste mapa, o valor especificado e a construção especificada estão associados. If the map previously contained a mapping relationship of the key, the old value was replaced* * @param Specifies the key to be associated* @param Specifies the value to be associated* @return The old value associated with the key, if the key has no mapping relationship, it returns null (returning null may also mean that the mapping was associated with the key before) */ public V put(K key, V value) { if (table == EMPTY_TABLE) {inflatetable (limiar); } 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; }1. Primeiro, no método PUT, primeiro determine se o balde está no estado não inicializado padrão. Se não for inicializado, chame o método inflatável para inicializá -lo e determine se a chave do parâmetro é nula. Se for nulo, ligue especificamente no putformullkey para colocar os dados com a chave como nula. O método PutfornullKey é realmente o mesmo que a seguinte etapa 3, exceto que o local de armazenamento padrão dos dados com a chave como nulo é o primeiro, ou seja, o subscrito padrão é 0.
2. Se a chave não for nula, chame o método hash () para obter o valor de hash da chave. Você pode calcular a posição em que a chave pode ser colocada no balde com base no valor do hash e no comprimento do balde.
3. Existe um atributo a seguir no objeto de entrada, que pode formar uma lista vinculada unidirecional para armazenar elementos com o mesmo valor de hash. Portanto, quando o valor de hash da chave for calculado, o local de armazenamento também será repetido. Basta julgar se o elemento do local de armazenamento e a próxima lista de atributos do elemento é exatamente o mesmo que o valor de hash da chave e a chave fornecidas. Se houver um completamente consistente, significa que já existe, substitua o valor antigo e retorne o valor antigo diretamente como o valor de retorno.
4. Aumente o número de modificações estruturais em 1
5. Ligue para o método Addentry para adicionar o novo par de valor-chave ao hashmap. O método da adição primeiro determina se os dados de entrada atual são maiores ou iguais ao valor da carga (a capacidade do fator de carga do balde *) e a posição especificada do balde não é nula. Se já for maior que a posição especificada não for nula, a capacidade do balde de ajuste é o dobro da capacidade atual. A capacidade do balde de ajuste é referenciada à capacidade inicial e diretório de ajuste de desempenho do fator de carga acima. Recalcule o valor do hash e calcule o local de armazenamento. Ligue para o método CreateEntry para armazená -lo no balde
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 valor, int bucketIndex) {entrada <k, v> e = tabela [bucketIndex]; tabela [bucketIndex] = nova entrada <> (hash, chave, valor, e); tamanho ++; } /*** Método do construtor de entrada para criar uma nova entrada. */ Entrada (int h, k k, v v, entrada <k, v> n) {value = v; próximo = n; chave = k; hash = h; }6. No método CreateEntry, primeiro obtenha a entrada no local especificado e, em seguida, gera uma nova entrada. Ao gerar a entrada, armazene a entrada original na próxima propriedade da entrada recém -gerada (consulte o método de construção de entrada) e substitua a entrada no local especificado pelo recém -gerado.
Porque ao adicionar novas entradas, o valor do hash precisa ser calculado e quando o comprimento não é suficiente, o comprimento precisa ser ajustado. Quando há elementos no local de armazenamento calculado, a lista vinculada precisa ser armazenada; portanto, a eficiência do uso do HashMap para adicionar novas operações não é muito alta.
Obter método
Primeiro, vejamos o código -fonte do método get:
/*** Retorne o valor mapeado pela chave especificada; Se este mapa não contiver nenhum relacionamento de mapeamento para essa chave, ele retornará NULL * retornar um valor nulo não significa necessariamente que o mapa não contenha o mapeamento da chave e também pode alterar o mapeamento para NULL. Você pode usar a operação ContainsKey para distinguir entre essas duas situações * @see #put (objeto, objeto) */ public v get (chave do objeto) {if (key == null) return getFornullKey (); Entrada <k, v> entrada = getentry (chave); retornar nulo == entrada? null: entrada.getValue (); } entrada final <k, v> getentry (chave do objeto) {if (size == 0) {return null; } 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;}O método GET é simples de implementar, e a seguir são algumas etapas:
Observando o código -fonte do GET, podemos descobrir que o método GET calcula o local de armazenamento através do valor de hash da chave e o comprimento do balde. Basicamente, você pode localizar o elemento que está procurando. Mesmo se você atravessar algumas chaves com valores de hash repetidos, é muito rápido. Como o valor do hash é relativamente único, o hashmap é muito rápido para a pesquisa.
Objeto personalizado como chave para o hashmap
classe usuário {// Número de identificação protegido int idNumber; usuário público (int id) {idNumber = id; }} classe pública testUser {public static void main (string [] args) {map <user, string> map = new hashmap <user, string> (); for (int i = 0; i <5; i ++) {map.put (novo usuário (i), "nome:"+i); } System.out.println ("nome do usuário3:" + map.get (novo usuário (3))); }} Saída: Usuário3 Nome: NULLComo mencionado acima, ao usar uma instância de classe de usuário personalizada como um objeto HashMap, o nome do Usuário3 não pode ser encontrado ao imprimir, porque a classe do usuário herda automaticamente o objeto de classe base; portanto, o método de objeto HashCode será usado automaticamente para gerar um valor de hash e ele usa o endereço do objeto para calcular o valor do hash por padrão. Portanto, o valor de hash da primeira instância gerado pelo novo usuário (3) é diferente do valor de hash da segunda instância gerada. No entanto, se você precisar apenas substituir o método HashCode, ele não funcionará corretamente, a menos que você substitua o método igual ao mesmo tempo, ele também faz parte do objeto. Hashmap usa iguals () para determinar se a chave atual é a mesma das teclas presentes na tabela. Você pode consultar o método GET ou PUST acima.
O método correto Equals () deve atender às seguintes 5 condições: --- Consulte "Java Programming Thoughts" -Página 489
Novamente : o objeto padrão.equals () é apenas o endereço do objeto de comparação; portanto, um novo usuário (3) não é igual a outro novo usuário (3). Portanto, se você deseja usar sua própria classe como a chave para o hashmap, você deve sobrecarregar o hashcode () e o igual ().
O código a seguir funciona normalmente:
classe usuário {// Número de identificação protegido int idNumber; usuário público (int id) {idNumber = id; } @Override public int hashCode () {return iDNumber; } @Override public boolean equals (object obj) {return obj instanceof user && (idnumber == ((user) obj) .idnumber); }} classe pública testUser {public static void main (string [] args) {map <user, string> map = new hashmap <user, string> (); for (int i = 0; i <5; i ++) {map.put (novo usuário (i), "nome:"+i); } System.out.println ("nome do usuário3:" + map.get (novo usuário (3))); }} Saída: User3 Nome: Nome: 3O exposto acima retorna o IDNumber como a única discriminação no HashCode, e os usuários também podem implementar seus próprios métodos de acordo com seus próprios negócios. No método Equals, a Instância de verificará silenciosamente se o objeto é nulo. Se o parâmetro à esquerda da instância for nulo, False será retornado. Se o parâmetro de Equals () não for nulo e o tipo estiver correto, a comparação será baseada no IDNumber real em cada objeto. Como pode ser visto na saída, o método atual está correto.
Consulte:
"Pensamentos de programação java"
JDK 1.6 Manual de Ajuda Chinesa
O exposto acima é todo o conteúdo deste artigo. Espero que o conteúdo deste artigo seja de ajuda para estudar ou trabalhar de todos. Eu também espero apoiar mais wulin.com!