Neste artigo, começamos a analisar o código -fonte do LinkedHashmap. O LinkedHashMap herda o hashmap, o que significa que o LinkedHashMap é estendido com base no hashmap. Portanto, antes de analisar o código -fonte do LinkedHashmap, os leitores precisam entender o código -fonte do hashmap. Você pode verificar a introdução do meu artigo anterior "Java Collection Series [3] ---- HASHMAP Código-fonte Análise". Contanto que você tenha uma compreensão profunda do princípio de implementação do HashMap e, em seguida, observe os códigos de origem do LinkedHashmap, Hashset e LinkedHashSet são todos muito simples. Portanto, os leitores devem ser pacientes e estudar o código -fonte do hashmap. Este é um bom negócio de comprar um recebe três de graça. Ao analisar o código-fonte do hashmap anteriormente, usei uma análise orientada para problemas do código-fonte para que não o analisasse aleatoriamente como uma mosca sem cabeça, e os leitores também pudessem ter um entendimento mais profundo do problema. Neste artigo, decidi usar esse método para analisar o LinkedHashmap.
1. Que tipo de estrutura é usada dentro do LinkedHashmap?
Como você pode ver, como o LinkedHashMap herda do Hashmap, ainda existe uma tabela de hash dentro do LinkedHashmap, mas o LinkedHashmap reescreveu uma entrada e adicionou duas variáveis de membros à entrada original do HashMap, a saber, a referência anterior de nós e a referência do nó sucessor. Dessa forma, todos os nós estão ligados para formar uma lista vinculada de mão dupla. Ao obter elementos, basta atravessar a lista vinculada de mão dupla diretamente. Vamos ver como é a implementação da entrada do LinkedHashmap.
Classe estática privada entrada <k, v> estende hashmap.entry <k, v> {// referência do nó anterior do nó atual na entrada da lista vinculada bidirecional <k, v> antes; // Referência do nó subsequente do nó atual na entrada da lista vinculada bidirecional <k, v> depois; Entrada (int hash, k key, v valor, hashmap.entry <k, v> próximo) {super (hash, chave, valor, próximo); } // Remova este nó da lista vinculada bidirecional private void remover () {antes.after = depois; depois.Before = antes; } // Insira o nó atual em um nó existente na lista vinculada bidirecional private void addbefore (entrada <k, v> existingEntry) {// a referência do próximo nó do nó atual aponta para o nó dado depois = existingEntry; // A referência do nó anterior do nó atual aponta para o nó anterior do nó dado antes = existingEntry.EBE; // A referência do próximo nó do nó dado aponta para o nó atual antes.AFTER = this; // a referência do nó anterior do nó dado aponta para o nó atual depois.Before = this; } // classificado em ordem de acesso, registre cada vez que a operação é obtida e void recordaccess (hashmap <k, v> m) {linkedhashmap <k, v> lm = (LinkedHashmap <k, v>) m; // se classificado em ordem de acesso if (lm.accessOrder) {lm.modCount ++; // Remova -se da lista vinculada bidirecional primeiro; // Coloque -se na cauda da lista vinculada bidirecional AddBefore (lm.Header); }} void RecordRemoval (hashmap <k, v> m) {remove (); }}2. Como o LinkedHashMap implementa a classificação em ordem de inserção?
// O método que será chamado no método put da classe pai Void addentry (int hash, K -Key, V Valor, int bucketIndex) {// chamando o método addentry da classe pai Super.addentry (hash, chave, valor, bucketIndex); // A operação a seguir é conveniente para a implementação do cache da LRU. Se a capacidade do cache for insuficiente, remova a entrada mais antiga do elemento <k, v> idosa = cabeçalho.after; if (removelDestEntry (mais velho)) {removeEntryforkey (mais eldest.key); }} // o método void createEntry (int hash, k key, v value, int bucketIndex) {// primeiro obtenha o hashmap de entrada de hashmap.entry <k, v> old = tabela [bucketIndex]; // Enrole -o na própria entrada do LinkedHashmap <k, v> e = nova entrada <> (hash, chave, valor, antigo); tabela [bucketIndex] = e; // Insira o nó atual na cauda da lista vinculada bidirecional e.Addbefore (cabeçalho); tamanho ++;}O LinkedHashMap substitui os métodos Addentry e CreateEntry de seu hashmap da classe pai. Quando você deseja inserir um par de valores-chave, o método put de sua classe pai hashmap será chamado primeiro. No método put, verificaremos se a chave correspondente existe na tabela de hash. Se existir, basta substituir seu valor diretamente. Se não existir, ligue para o método Addentry para criar uma nova entrada. Observe que, neste momento, o método Addentry do LinkedHashmap é chamado. Vemos o código acima. Além de chamar de volta o método addelDestEntry da classe pai, este addelDestEntry também ligará para remover o RemowDestEntry para remover o elemento mais antigo. Esta operação é principalmente para implementar o algoritmo LRU, que será discutido abaixo. Vemos que o LinkedHashmap também reescreve o método CreateEntry. Quando você deseja criar uma nova entrada, esse método será chamado. Após cada vez que a entrada é colocada na tabela de hash, o método AddBefore será chamado para inserir o nó atual na cauda da lista vinculada bidirecional. Dessa forma, a lista vinculada bidirecional registra a ordem de cada nó inserido. Ao obter elementos, basta atravessar a lista vinculada bidirecional. A figura a seguir mostra a operação de cada chamada para adicionar antes. Como é uma lista vinculada bidirecional, antes de inserir o nó atual no nó da cabeça, ele está realmente inserindo o nó atual na cauda da lista vinculada bidirecional.
3. Como usar o LinkedHashmap para implementar o cache da LRU?
Sabemos que a implementação do cache depende da memória do computador e os recursos de memória são bastante limitados e é impossível armazenar elementos sem limite. Portanto, precisamos excluir adequadamente alguns elementos quando a capacidade é insuficiente. Então, qual elemento é melhor excluir? A idéia do algoritmo LRU é que, se um dados tiver sido acessado recentemente, as chances de serem acessadas no futuro também serão maiores. Portanto, podemos excluir dados que nem sempre são acessados. Em seguida, vamos dar uma olhada em como o LinkedHashmap implementa o mecanismo da LRU.
classe pública LinkedHashmap <k, v> estende o hashmap <k, v> implementa mapa <k, v> {// bosquelly lister listert de entrada de cabeçalho privado <k, v> cabeçalho; // Classifique o Pedido de Acesso Booleano Privado em ordem de acesso; ... public LinkedHashMap (int InitialCapacity, Float LoadFactor, Boolean AccessOrder) {Super (InitialCapacity, LoadFactor); this.accessOrder = AccessOrder; } // Obtenha o valor de acordo com a chave pública v get (chave do objeto) {// chamando o método da classe pai para obter a entrada correspondente <k, v> e = (entrada <k, v>) getentry (chave); if (e == null) {return null; } // Se for classificado em ordem de acesso, o nó após cada uso será colocado no final da lista vinculada bidirecional E.RecordAccess (this); retornar e.value; } Entrada de classe estática privada <k, v> estende o hashmap.entry <k, v> {... // insira o nó atual na frente de um nó existente na lista bidirecional vinculada a um nó de vazio privado antes (entrada <k, v> existingentry) {// a referência do próximo nó dos pontos atuais para o dado isto dado) {// a seguinte nó atual do nó atual para o dado o dado a. // A referência do nó anterior do nó atual aponta para o nó anterior do nó dado antes = existingEntry.EBE; // A referência do próximo nó do nó dado aponta para o nó atual antes.AFTER = this; // a referência do nó anterior do nó dado aponta para o nó atual depois.Before = this; } // classificado em ordem de acesso, registre sempre que a operação void recordaccess (hashmap <k, v> m) {linkedhashmap <k, v> lm = (linkedhashmap <k, v>) m; // se classificado em ordem de acesso if (lm.accessOrder) {lm.modCount ++; // Remova -se da lista vinculada bidirecional primeiro; // Coloque -se na cauda da lista vinculada bidirecional AddBefore (lm.Header); }} ...} // Este método será chamado na classe pai Put Method ADDENTRY (int hash, K Key, V Valor, int bucketIndex) {// Calcule o método addentry da classe pai Super.Addentry (Hash, Key, Value, BucketIndex); // A operação a seguir é conveniente para a implementação do cache da LRU. Se a capacidade do cache for insuficiente, remova a entrada mais antiga do elemento <k, v> idosa = cabeçalho.after; if (removelDestEntry (mais velho)) {removeLDestForKey (Eldest.Key); }} // Onde excluir o elemento mais antigo? Este método foi projetado para ser substituído por subclasses protegidas booleanas removetElDestEntry (map.entry <k, v> idosas) {return false; }}Para ser mais intuitivo, omiti algum código irrelevante no código publicado acima. Podemos ver que o LinkedHashmap possui um pedido de acesso variável de membro, que registra se ele precisa ser classificado em ordem de acesso. Ele fornece um construtor que pode especificar o valor do próprio pedido de acesso. Cada vez que você chama o método get para obter o elemento, é chamado E.RecordAccess (isso), que moverá o nó atual para o final da lista vinculada bidirecional. Agora sabemos que, se o AccessOrder for verdadeiro, toda vez que obtivermos o elemento, moveremos esse elemento para o final da lista de links bidirecionais. O objetivo desta etapa é distinguir os elementos mais usados daqueles que geralmente não são usados, e os elementos frequentemente usados são colocados no final e os elementos menos usados são colocados na cabeça. Vamos voltar ao código acima e ver que toda vez que o método Addentry é chamado, determinaremos se o elemento mais antigo precisa ser excluído. A lógica do julgamento é implementada pelo RemonelDestEntry, que foi projetado para ser substituído por subclasses e reescrever a lógica dentro. Observe que, como os nós visitados recentemente são movidos para a cauda da lista vinculada bidirecional, o nó mais antigo é retirado da cabeça da lista vinculada bidirecional para exclusão. O exemplo a seguir implementa um cache LRU simples.
classe pública lrumap <k, v> estende LinkedHashmap <k, v> {private int capacidade; LRUMAP (INT Capacidade) {// chamando o construtor da classe pai, defina para classificar na ordem de acesso super (capacidade, 1f, true); this.Capacity = Capacidade; } @Override Public boolean RemoverElDestEntry (map.entry <k, v> idosos) {// Quando o par de valores-chave é maior ou igual à capacidade da tabela de hash retornar isso.size ()> = Capacidade; } public static void main (string [] args) {lrumap <Integer, string> map = new lrumap <Integer, string> (4); map.put (1, "A"); map.put (2, "b"); map.put (3, "c"); System.out.println ("Coleção original:" + mapa); String s = map.get (2); System.out.println ("Get Element:" + map); map.put (4, "d"); System.out.println ("Após a inserção:" + mapa); }}Os resultados são os seguintes:
Nota: Toda a análise acima é baseada no JDK1.7, e haverá diferenças entre diferentes versões, os leitores precisam prestar atenção.
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.