-Hashmap -
Vantagens: Velocidade super rápida da consulta e estruturas de dados que podem atingir o (1) A complexidade do tempo é hashmap. Dados de armazenamento dinâmicos de comprimento variável (em relação às matrizes).
Desvantagens: o valor do hash precisa ser calculado extra e, se não for tratado corretamente, ocupará um espaço extra.
―Como usar o hashmap -
Geralmente usamos o hashmap da seguinte maneira
Mapa <número inteiro, string> maps = new hashmap <inteiro, string> (); maps.put (1, "A"); maps.put (2, "b");
O código acima cria um novo hashmap e insere dois dados. Os tipos de dados básicos não são aceitos aqui para fazer K e V.
Se você escrever isso, haverá problemas:
Mapa <int, duplo> maps = new hashmap <int, duplo> ();
Por que usamos dessa maneira? Consulte o código -fonte:
Classe pública Hashmap <k, v> estende abstractmap <k, v> implementa mapa <k, v>, clonável, serializável
Esta é a definição da classe de implementação de hashmap.
―Hashmap é uma estrutura de dados dinamicamente variável-
Ao usar o hashmap, para melhorar a eficiência da execução, geralmente definimos a capacidade de inicialização do hashmap:
Mapa <string, string> rm = novo hashmap <string, string> (2)
Ou use mapas de classe de ferramentas de goiaba para criar facilmente uma coleção e inicializar o valor com o tamanho apropriado.
Mapa <string, objeto> map = maps.newhashmapWithExpetedSize (7);
Então, por que usá -lo assim? Vejamos o construtor de origem deles.
Construtor sem parâmetros:
public hashmap () {this.loadFactor = default_load_factor; limite = (int) (default_initial_capacity * default_load_factor); tabela = nova entrada [default_initial_capacity]; init (); } public hashmap () {
this.loadFactor = default_load_factor;
limite = (int) (default_initial_capacity * default_load_factor);
tabela = nova entrada [default_initial_capacity];
init ();
}
/** * 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); }Explicação de substantivos:
Default_load_factor // Fator de carregamento padrão, 0,75 se não for especificado. Default_initial_capacity // Capacidade de inicialização padrão, o padrão é 16 limite // o valor do limite (YU) é calculado com base no fator de carga e na capacidade de inicialização. <span style = "cor: rgb (54, 46, 43); font-família:" Microsoft yahei ";"> limiar significa que quando o tamanho do hashmap for maior que o limiar, a operação de redimensionamento será realizada.
Então, sabemos que, se chamarmos o construtor sem parâmetros, obteremos uma matriz de 16 capacidade.
Portanto, a pergunta é: e se a capacidade inicial não for suficiente?
As matrizes são de comprimento fixo, como usar dados de comprimento fixo para representar dados de comprimento incerto? A resposta é encontrar uma mais longa, mas reduz a eficiência quando redimensiona. Por isso, recomendamos que o hashmap tenha uma capacidade confiável ao inicializar.
―Hashmap Put Method -
public V put (K -Key, V Valor) {if (key == null) // Se a chave estiver vazia, uma diferença entre hashmap e retornos de hashtable PutformornKey (valor); int hash = hash (key.hashcode ()); // quadro o valor do hash com base no código de hash da chave int i = indexfor (hash, tabela.length); // quadro o subscrito da matriz a ser colocado com base no valor do hash para (entrada <k, v> e = tabela [i]; e! = Null; e = e.next) {// o inteiro para o loop implementa que, se k existir, substitua o objeto v 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 ++; // Counter addentry (hash, chave, valor, i); // Adicionar ao Array Retornar NULL; }Se os dados inseridos excederem a capacidade existente, eles serão executados
addentry (hash, chave, valor, i);
Void Addentry (int hash, K Key, V Valor, int BucketIndex) {Entrada <k, v> e = tabela [BucketIndex]; tabela [bucketIndex] = nova entrada <k, v> (hash, chave, valor, e); if (size ++> = limiar) <span style = "cor:#ff0000;"> <strong> redimensione (2 * tabela.length);}Aqui, se o tamanho atual ++> o limite for exibido, o tamanho atual será expandido duas vezes e redimensione (2*tabela.length) será executado. Então, como eles se expandem?
Void REDIMENT (int newCapacity) {Entry [] OldTable = tabela; int OldCapacity = OldTable.Length; if (OldCapacity == MAXIMUM_CAPACIDADE) {LHRESHOLD = INTEGER.MAX_VALUE; retornar; } Entrada [] newTable = nova entrada [newCapacity]; <span style = "cor: rgb (51, 51, 51); font-family: Arial;"> Novo uma nova matriz, </span> <strong> <span style = "cor:#ff0000;"> transfer (newtable); </span> </strong> // transfira a matriz para uma nova tabela de array = newTable; limiar = (int) (newCapacity * loadFactor); // recalcula a capacidade}Como a transferência de transferência é transferida?
transferência void (entrada [] newTable) {Entry [] src = tabela; int newCapacity = newtable.length; for (int j = 0; j <src.length; j ++) {entradas <k, v> e = src [j]; if (e! = null) {src [j] = null; do {entradas <k, v> próximo = e.next; int i = <strong> <span style = "color:#ff0000;"> indexfor (e.hash, newcapacity); // recalcula o índice com base na capacidade de valor de hash </span> </strong> e.next = newTable [i]; newTable [i] = e; e = próximo; } while (e! = nulo); }}}“O número de execuções adicionais de expansão de hashmap-
Então, se queremos adicionar um hashmap de 1000 elementos, se usarmos o valor padrão, quantos cálculos adicionais eu preciso calcular?
Quando é superior a 16*0,75 = 12, precisa ser recalculado 12 vezes
Quando é superior a 16*2*0,75 = 24, são necessários 24 cálculos adicionais.
...
Quando é superior a 16*n*0,75 = 768, são necessários 768 cálculos adicionais.
Por isso, calculamos 12+24+48+…+768 vezes no processo de expansão
Portanto, é fortemente recomendado que devemos especificar manualmente o tamanho inicial se soubermos o escopo do projeto como este:
Mapa <número inteiro, string> maps = new hashmap <inteiro, string> (1000);
Resumo: É por isso que a eficiência da execução do hashmap é severamente reduzida se exceder a capacidade inicial durante o uso.
O exposto acima é sobre o uso do Hashmap neste artigo sobre a análise do código -fonte Java, espero que seja útil para todos. Amigos interessados podem continuar se referindo a outros tópicos relacionados neste site. Se houver alguma falha, deixe uma mensagem para apontá -la. Obrigado amigos pelo seu apoio para este site!