Dans cet article, nous avons commencé à analyser le code source de LinkedHashMap. LinkedHashMap hérite de Hashmap, ce qui signifie que LinkedHashMap est étendu sur la base de HashMap. Par conséquent, avant de regarder le code source de LinkedHashMap, les lecteurs doivent comprendre le code source de HashMap. Vous pouvez vérifier l'introduction de mon article précédent "Java Collection Series [3] ---- HashMap Source Code Analysis". Tant que vous avez une compréhension approfondie du principe de mise en œuvre de HashMap, puis examinez les codes source de LinkedHashMap, HashSet et LinkedHashSet sont tous très simples. Par conséquent, les lecteurs doivent être patients et étudier le code source HashMap. Il s'agit d'une bonne entreprise d'achat d'un obtenez-en trois gratuitement. Lors de l'analyse du code source HashMap plus tôt, j'ai utilisé une analyse axée sur les problèmes du code source afin que je ne l'analyse pas au hasard comme une mouche sans tête, et les lecteurs pourraient également avoir une compréhension plus profonde du problème. Dans cet article, j'ai décidé d'utiliser cette méthode pour analyser LinkedHashMap.
1. Quel type de structure est utilisé à l'intérieur de LinkedHashmap?
Comme vous pouvez le voir, puisque LinkedHashMap hérite de Hashmap, il y a toujours une table de hash à l'intérieur de LinkedHashmap, mais LinkedHashMap a réécrit une entrée et ajouté deux variables de membre à la saisie de nœud de hashmap d'origine, à savoir la référence de nœud précédente et la référence de nœud du successeur. De cette façon, tous les nœuds sont liés ensemble pour former une liste liée à double sens. Lors de l'obtention d'éléments, il suffit de parcourir directement la liste liée bidirectionnelle. Voyons à quoi ressemble l'implémentation de l'entrée LinkedHashmap.
Entrée de classe statique privée <k, v> étend hashmap.entry <k, v> {// référence du nœud précédent du nœud actuel dans la liste liée bidirectionnelle <k, v> avant; // Référence du nœud suivant du nœud actuel dans l'entrée de liste liée bidirectionnelle <k, v> après; Entrée (int hash, k key, vale v, hashmap.entry <k, v> suivant) {super (hash, key, valeur, suivant); } // Supprimez ce nœud de la liste liée bidirectionnelle private void remove () {before.after = after; après.before = avant; } // Insérez le nœud actuel dans un nœud existant dans la liste liée bidirectionnelle private void addBefore (entrée <k, v> existentEntentry) {// La référence du nœud suivant du nœud actuel pointe vers le nœud donné après = existant; // La référence du nœud précédent du nœud actuel pointe vers le nœud précédent du nœud donné avant = existant.before; // La référence du nœud suivant du nœud donné pointe vers le nœud actuel avant.after = this; // La référence du nœud précédent du nœud donné pointe vers le nœud actuel après.before = this; } // Trié dans l'ordre d'accès, enregistrez chaque fois que l'opération est obtenue VOID RecordAccess (hashmap <k, v> m) {LinkedHashmap <k, v> lm = (LinkedHashmap <k, v>) m; // Si trié dans l'ordre d'accès si (lm.accessOrder) {lm.modCount ++; // Retirez-vous d'abord de la liste liée bidirectionnelle; // Mettez-vous à la queue de la liste liée bidirectionnelle addBefore (lm.Header); }} void RecordRemoval (hashmap <k, v> m) {reous (); }}2. Comment LinkedHashmap implémente-t-il le tri dans l'ordre d'insertion?
// La méthode qui sera appelée dans la méthode de put de la classe parent void Addentry (int hash, k key, Vale V, int bucketIndex) {// appelant la méthode d'addentry de la classe parent super.addentry (hash, key, valeur, bucketIndex); // L'opération suivante est pratique pour la mise en œuvre du cache LRU. Si la capacité de cache est insuffisante, supprimez la plus ancienne entrée d'élément <k, v> âgé = en-tête. if (devoielDestentry (aîné)) {devoieEntryForkey (eldest.key); }} // La méthode void CreateEntry (int hash, k key, Vale V, int bucketIndex) {// Obtenez d'abord le hashmap d'entrée de hashmap.entry <k, v> old = table [bucketIndex]; // enveloppez-le dans la propre entrée de LinkedHashmap <k, v> e = nouvelle entrée <> (hachage, clé, valeur, ancien); Tableau [bucketIndex] = E; // insérer le nœud actuel à la queue de la liste liée bidirectionnelle e.AddBefore (en-tête); taille ++;}LinkedHashMap remplace les méthodes d'addentry et de création de sa classe parent hashmap. Lorsque vous souhaitez insérer une paire de valeurs de clé, la méthode de put de sa classe de parent HashMap sera appelée en premier. Dans la méthode de put, nous vérifierons si la clé correspondante existe dans la table de hachage. S'il existe, remplacez simplement sa valeur directement. S'il n'existe pas, appelez la méthode Addentry pour créer une nouvelle entrée. Notez que pour le moment, la propre méthode d'addentry de LinkedHashMap est appelée. Nous voyons le code ci-dessus. En plus de rappeler la méthode AddelDestentry de la classe parent, cet AddelDestentry appellera également devayElDestentry pour supprimer l'élément le plus ancien. Cette opération consiste principalement à mettre en œuvre l'algorithme LRU, qui sera discuté ci-dessous. Nous voyons que LinkedHashMap réécrit également la méthode CreateEntry. Lorsque vous souhaitez créer une nouvelle entrée, cette méthode sera appelée. Après chaque fois que l'entrée est mise dans la table de hachage, la méthode AddBefore sera appelée pour insérer le nœud actuel dans la queue de la liste liée bidirectionnelle. De cette façon, la liste liée bidirectionnelle enregistre l'ordre de chaque nœud inséré. Lors de l'obtention d'éléments, parcourez simplement la liste liée bidirectionnelle. La figure suivante montre le fonctionnement de chaque appel à AddBefore. Puisqu'il s'agit d'une liste liée bidirectionnelle, avant d'insérer le nœud actuel dans le nœud de tête, il insére en fait le nœud actuel dans la queue de la liste liée bidirectionnelle.
3. Comment utiliser LinkedHashmap pour implémenter le cache LRU?
Nous savons que la mise en œuvre du cache dépend de la mémoire de l'ordinateur et que les ressources de mémoire sont assez limitées, et il est impossible de stocker des éléments sans limite. Par conséquent, nous devons supprimer de manière appropriée certains éléments lorsque la capacité est insuffisante. Alors, quel élément est le mieux supprimé? L'idée de l'algorithme LRU est que si des données ont été accessibles récemment, les chances d'être accessibles à l'avenir sont également plus élevées. Nous pouvons donc supprimer des données qui ne sont pas souvent accessibles. Ensuite, jetons un coup d'œil à la façon dont LinkedHashMap implémente le mécanisme LRU.
classe publique LinkedHashmap <k, v> étend Hashmap <k, v> implémente Map <k, v> {// En-tête de liste liée à l'en-tête privée transitoire <k, v> en-tête; // Trier un accès booléen final privé par ordre d'accès; ... public LinkedHashMap (int initialCapacity, float loadFactor, boolean accessOrder) {super (initialCapacity, loadFactor); this.AccessOrder = AccessOrder; } // Obtenez la valeur en fonction de Key Public V get (clé d'objet) {// Appel de la méthode de la classe parent pour obtenir l'entrée correspondante de l'entrée <k, v> e = (entrée <k, v>) GetEntry (clé); if (e == null) {return null; } // S'il est trié dans l'ordre d'accès, le nœud après chaque utilisation sera placé à la fin de la liste liée bidirectionnelle e.RecordAccess (this); retour e.value; } Entrée de classe statique privée <k, v> étend hashmap.entry <k, v> {... // insérer le nœud actuel à l'avant d'un nœud existant dans la liste liée bidirectionnelle private void addBefore (entrée <k, v> existant) {// La référence du nœud suivant du nœud actuel pointe vers le nœud donné après = existant; // La référence du nœud précédent du nœud actuel pointe vers le nœud précédent du nœud donné avant = existant.before; // La référence du nœud suivant du nœud donné pointe vers le nœud actuel avant.after = this; // La référence du nœud précédent du nœud donné pointe vers le nœud actuel après.before = this; } // Tri dans l'ordre d'accès, enregistrez chaque fois que l'opération void enregistreccess (hashmap <k, v> m) {linkedhashmap <k, v> lm = (linkedhashmap <k, v>) m; // Si trié dans l'ordre d'accès si (lm.accessOrder) {lm.modCount ++; // Retirez-vous d'abord de la liste liée bidirectionnelle; // Mettez-vous à la queue de la liste liée bidirectionnelle addBefore (lm.Header); }} ...} // Cette méthode sera appelée dans la méthode de la classe parent de put void addentry (int hash, k key, v valeur, int bucketIndex) {// Calculez la méthode d'addentry de la classe parent super.addentry (hash, key, value, bucketIndex); // L'opération suivante est pratique pour la mise en œuvre du cache LRU. Si la capacité de cache est insuffisante, supprimez la plus ancienne entrée d'élément <k, v> âgé = en-tête. if (devoieElDestentry (aîné)) {devayelDestForkey (eldest.key); }} // où supprimer l'élément le plus ancien? Cette méthode est conçue pour être écrasée par les sous-classes protégées booléen devayelDestentry (map.entry <k, v> âgé) {return false; }}Pour être plus intuitif, j'ai omis un code non pertinent dans le code publié ci-dessus. Nous pouvons voir que LinkedHashMap a un membre de la variable d'accessoire de membre, qui enregistre si elle doit être triée par ordre d'accès. Il fournit un constructeur qui peut spécifier la valeur d'accès à l'ordre lui-même. Chaque fois que vous appelez la méthode GET pour obtenir l'élément, E.RecordAccess (this) est appelé, qui déplacera le nœud actuel à la fin de la liste liée bidirectionnelle. Maintenant, nous savons que si AccessOrder est vrai, alors chaque fois que nous obtenons l'élément, nous déplacerons cet élément à la fin de la liste des liens bidirectionnels. Le but de cette étape est de distinguer les éléments les plus couramment utilisés de ceux qui ne sont pas souvent utilisés, et les éléments souvent utilisés sont placés à la fin et les éléments moins couramment utilisés sont placés à la tête. Revenons au code ci-dessus et voyons que chaque fois que la méthode d'addentry est appelée, nous déterminerons si l'élément le plus ancien doit être supprimé. La logique du jugement est implémentée par DeventilDestentry, qui est conçue pour être remplacée par les sous-classes et réécrivez la logique à l'intérieur. Notez que depuis que les nœuds récemment visités sont déplacés vers la queue de la liste liée bidirectionnelle, le nœud le plus ancien est retiré de la tête de la liste liée bidirectionnelle pour la suppression. L'exemple suivant implémente un cache LRU simple.
La classe publique LRUMAP <K, V> étend LinkedHashMap <K, V> {Private int Capacité; LRUMAP (INT CAPATION) {// Appelant le constructeur de classe Parent, défini pour trier dans l'ordre d'accès super (capacité, 1f, true); this.capacity = capacité; } @Override public boolean devatelDestentry (map.entry <k, v> âgé) {// Lorsque la paire de valeurs de clé est supérieure ou égale à la capacité de la table de hachage renvoie ce.size ()> = capacité; } public static void main (string [] args) {lrumap <nteger, string> map = new LRUMAP <Integer, String> (4); map.put (1, "a"); map.put (2, "b"); map.put (3, "C"); System.out.println ("Collection originale:" + map); String s = map.get (2); System.out.println ("Get Element:" + Map); map.put (4, "d"); System.out.println ("After Insertion:" + Map); }}Les résultats sont les suivants:
Remarque: Toute l'analyse ci-dessus est basée sur JDK1.7, et il y aura des différences entre différentes versions, les lecteurs doivent faire attention.
Ce qui précède est tout le contenu de cet article. J'espère que cela sera utile à l'apprentissage de tous et j'espère que tout le monde soutiendra davantage Wulin.com.