本文共 14817 字，大约阅读时间需要 49 分钟。

LinkedHashMap简介

• LinkedHashMap内部维护了一个双向链表，能保证元素按插入的顺序访问，也能以访问顺序访问。
• LinkedHashMap可以看成是 LinkedList + HashMap。
• LinkedHashMap继承HashMap，拥有HashMap(参考链接：)的所有特性，并且额外增加了按一定顺序访问的特性，LinkedHashMap 默认存储顺序为插入顺序，也可按照访问顺序存储元素。

案例

@Testpublic void test01(){
       HashMap hashMap = new HashMap();    hashMap.put("name","csp");    hashMap.put("name","csp1999");    hashMap.put("age","22");    hashMap.put("sex","man");    hashMap.put("school","haust");    hashMap.put("class","1801");    System.out.println(hashMap);// key不允许重复，无序集合{school=haust, sex=man, name=csp1999, class=1801, age=22}        LinkedHashMap linkedHashMap = new LinkedHashMap();    linkedHashMap.put("name","csp");    linkedHashMap.put("name","csp1999");    linkedHashMap.put("age","22");    linkedHashMap.put("sex","man");    linkedHashMap.put("school","haust");    linkedHashMap.put("class","1801");    System.out.println(linkedHashMap);// key不允许重复，有序集合{name=csp1999, age=22, sex=man, school=haust, class=1801}    // LinkedHashMap 默认存储顺序为插入顺序，也可按照访问顺序存储元素}

LinkedHashMap继承体系

HashMap使用的是（数组 + 单链表 + 红黑树）的存储结构，通过上面的继承体系，我们知道LinkedHashMap继承了HashMap，所以它的内部也有这三种结构，但是它还额外添加了一种“双向链表”的结构存储所有元素的顺序。

添加删除元素的时候需要同时维护在HashMap中的存储，也要维护在LinkedList中的存储，所以性能上来说会比HashMap稍慢。

LinkedHashMap源码分析

1. 属性

/** * 序列化版本号 */private static final long serialVersionUID = 3801124242820219131L;/** * 双向链表的头节点.   * 被transient关键字修饰的对象不能被序列化 */transient LinkedHashMap.Entry
   
     head;/** * 双向链表的尾节点. */transient LinkedHashMap.Entry
    
      tail;/** * 是否按访问顺序排序  * true : 按照访问顺序排序 * false: 按照插入顺序排序 * @serial */final boolean accessOrder;
    
   

• head：双向链表的头节点，旧数据存在头节点。
• tail：双向链表的尾节点，新数据存在尾节点。
• accessOrder：是否需要按访问顺序排序，如果为false则按插入顺序存储元素，如果是true则按访问顺序存储元素。

2. 内部类

/** * 位于LinkedHashMap中 HashMap的子类. */static class Entry
   
     extends HashMap.Node
    
      {
       Entry
     
       before, after;    Entry(int hash, K key, V value, Node
      
        next) {
           super(hash, key, value, next);    }}/** * 位于HashMap中. */static class Node
       
         implements Map.Entry
        
          { final int hash;// hash用来存储key计算得来的hash值 final K key;// 键 V value;// 值 Node
         
           next;// 下一个node节点 Node(int hash, K key, V value, Node
          
            next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } ...}
          
         
        
       
      
     
    
   

存储节点，继承自HashMap的Node类，next用于单链表存储于桶中，before和after用于双向链表存储所有元素。

3. 构造方法

//默认是false，则迭代时输出的顺序是插入节点的顺序。若为true，则输出的顺序是按照访问节点的顺序。    //为true时，可以在这基础之上构建一个LruCach    final boolean accessOrder;    public LinkedHashMap() {
           super();        accessOrder = false;    }    //指定初始化时的容量，    public LinkedHashMap(int initialCapacity) {
           super(initialCapacity);        accessOrder = false;    }    //指定初始化时的容量，和扩容的加载因子    public LinkedHashMap(int initialCapacity, float loadFactor) {
           super(initialCapacity, loadFactor);        accessOrder = false;    }    //指定初始化时的容量，和扩容的加载因子，以及迭代输出节点的顺序    public LinkedHashMap(int initialCapacity,                         float loadFactor,                         boolean accessOrder) {
           super(initialCapacity, loadFactor);        this.accessOrder = accessOrder;    }    //利用另一个Map 来构建，    public LinkedHashMap(Map
    m) {
           super();        accessOrder = false;        //该方法上文分析过，批量插入一个map中的所有数据到 本集合中。        putMapEntries(m, false);    }

前四个构造方法accessOrder都等于false，说明双向链表是按插入顺序存储元素。

最后一个构造方法accessOrder从构造方法参数传入，如果传入true，则就实现了按访问顺序存储元素，这也是实现LRU缓存策略的关键。

4. 成员方法

4.1 增

LinkedHashMap并没有重写任何put方法。但是其重写了构建新节点的newNode()方法.

newNode()会在HashMap的putVal()方法里被调用，putVal()方法会在批量插入数据putMapEntries(Map<? extends K, ? extends V> m, boolean evict)或者插入单个数据public V put(K key, V value)时被调用。

LinkedHashMap重写了newNode(),在每次构建新节点时，通过linkNodeLast(p);将新节点链接在内部双向链表的尾部。

//在构建新节点时，构建的是`LinkedHashMap.Entry` 不再是`Node`.    Node
   
     newNode(int hash, K key, V value, Node
    
      e) {
           LinkedHashMap.Entry
     
       p =            new LinkedHashMap.Entry
      
       (hash, key, value, e);        linkNodeLast(p);        return p;    }    //将新增的节点，连接在链表的尾部    private void linkNodeLast(LinkedHashMap.Entry
       
         p) {
           LinkedHashMap.Entry
        
          last = tail; tail = p; //集合之前是空的 if (last == null) head = p; else { //将新节点连接在链表的尾部 p.before = last; last.after = p; } }
        
       
      
     
    
   

以及HashMap专门预留给LinkedHashMap的afterNodeAccess() afterNodeInsertion() afterNodeRemoval() 方法。

// Callbacks to allow LinkedHashMap post-actions    void afterNodeAccess(Node
   
     p) {
    }    void afterNodeInsertion(boolean evict) {
    }    void afterNodeRemoval(Node
    
      p) {
    }
    
   

//回调函数，新节点插入之后回调 ， 根据evict 和 判断是否需要删除最老插入的节点。如果实现LruCache会用到这个方法。    void afterNodeInsertion(boolean evict) {
    // possibly remove eldest        LinkedHashMap.Entry
   
     first;        //LinkedHashMap 默认返回false 则不删除节点        if (evict && (first = head) != null && removeEldestEntry(first)) {
               K key = first.key;            removeNode(hash(key), key, null, false, true);        }    }    //LinkedHashMap 默认返回false 则不删除节点。 返回true 代表要删除最早的节点。通常构建一个LruCache会在达到Cache的上限是返回true    protected boolean removeEldestEntry(Map.Entry
    
      eldest) {
           return false;    }
    
   

void afterNodeInsertion(boolean evict)以及boolean removeEldestEntry(Map.Entry<K,V> eldest)是构建LruCache需要的回调，在LinkedHashMap里可以忽略它们。

4.2 删

LinkedHashMap也没有重写remove()方法，因为它的删除逻辑和HashMap并无区别。

但它重写了afterNodeRemoval()这个回调方法。该方法会在Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable)方法中回调，removeNode()会在所有涉及到删除节点的方法中被调用，是删除节点操作的真正执行者。

//在删除节点e时，同步将e从双向链表上删除    void afterNodeRemoval(Node
   
     e) {
    // unlink        LinkedHashMap.Entry
    
      p =            (LinkedHashMap.Entry
     
      )e, b = p.before, a = p.after;        //待删除节点 p 的前置后置节点都置空        p.before = p.after = null;        //如果前置节点是null，则现在的头结点应该是后置节点a        if (b == null)            head = a;        else//否则将前置节点b的后置节点指向a            b.after = a;        //同理如果后置节点时null ，则尾节点应是b        if (a == null)            tail = b;        else//否则更新后置节点a的前置节点为b            a.before = b;    }
     
    
   

4.3 查

LinkedHashMap重写了get()和getOrDefault()方法：

public V get(Object key) {
           Node
   
     e;        if ((e = getNode(hash(key), key)) == null)            return null;        if (accessOrder)            afterNodeAccess(e);        return e.value;    }    public V getOrDefault(Object key, V defaultValue) {
          Node
    
      e;       if ((e = getNode(hash(key), key)) == null)           return defaultValue;       if (accessOrder)           afterNodeAccess(e);       return e.value;   }
    
   

对比HashMap中的实现,LinkedHashMap只是增加了在成员变量(构造函数时赋值)accessOrder为true的情况下，要去回调void afterNodeAccess(Node<K,V> e)函数。

public V get(Object key) {
           Node
   
     e;        return (e = getNode(hash(key), key)) == null ? null : e.value;    }
   

在afterNodeAccess()函数中，会将当前被访问到的节点e，移动至内部的双向链表的尾部。

void afterNodeAccess(Node
   
     e) {
    // move node to last        LinkedHashMap.Entry
    
      last;//原尾节点        //如果accessOrder 是true ，且原尾节点不等于e        if (accessOrder && (last = tail) != e) {
               //节点e强转成双向链表节点p            LinkedHashMap.Entry
     
       p =                (LinkedHashMap.Entry
      
       )e, b = p.before, a = p.after;            //p现在是尾节点， 后置节点一定是null            p.after = null;            //如果p的前置节点是null，则p以前是头结点，所以更新现在的头结点是p的后置节点a            if (b == null)                head = a;            else//否则更新p的前直接点b的后置节点为 a                b.after = a;            //如果p的后置节点不是null，则更新后置节点a的前置节点为b            if (a != null)                a.before = b;            else//如果原本p的后置节点是null，则p就是尾节点。 此时 更新last的引用为 p的前置节点b                last = b;            if (last == null) //原本尾节点是null  则，链表中就一个节点                head = p;            else {
   //否则 更新 当前节点p的前置节点为 原尾节点last， last的后置节点是p                p.before = last;                last.after = p;            }            //尾节点的引用赋值成p            tail = p;            //修改modCount。            ++modCount;        }    }
      
     
    
   

值得注意的是，afterNodeAccess()函数中，会修改modCount,因此当你正在accessOrder=true的模式下,迭代LinkedHashMap时，如果同时查询访问数据，也会导致fail-fast，因为迭代的顺序已经改变。

4.4 遍历

重写了entrySet()如下：

public Set
   
    
     > entrySet() {
           Set
     
      
       > es;        //返回LinkedEntrySet        return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;    }    final class LinkedEntrySet extends AbstractSet
       
        
         > { public final Iterator
         
          
           > iterator() { return new LinkedEntryIterator(); } }
          
         
        
       
      
     
    
   

最终的EntryIterator:

final class LinkedEntryIterator extends LinkedHashIterator        implements Iterator
   
    
     > {
           public final Map.Entry
     
       next() {
    return nextNode(); }    }    abstract class LinkedHashIterator {
           //下一个节点        LinkedHashMap.Entry
      
        next;        //当前节点        LinkedHashMap.Entry
       
         current;        int expectedModCount;        LinkedHashIterator() {
               //初始化时，next 为 LinkedHashMap内部维护的双向链表的扁头            next = head;            //记录当前modCount，以满足fail-fast            expectedModCount = modCount;            //当前节点为null            current = null;        }        //判断是否还有next        public final boolean hasNext() {
               //就是判断next是否为null，默认next是head  表头            return next != null;        }        //nextNode() 就是迭代器里的next()方法 。        //该方法的实现可以看出，迭代LinkedHashMap，就是从内部维护的双链表的表头开始循环输出。        final LinkedHashMap.Entry
        
          nextNode() { //记录要返回的e。 LinkedHashMap.Entry
         
           e = next; //判断fail-fast if (modCount != expectedModCount) throw new ConcurrentModificationException(); //如果要返回的节点是null，异常 if (e == null) throw new NoSuchElementException(); //更新当前节点为e current = e; //更新下一个节点是e的后置节点 next = e.after; //返回e return e; } //删除方法 最终还是调用了HashMap的removeNode方法 public final void remove() { Node
          
            p = current; if (p == null) throw new IllegalStateException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); current = null; K key = p.key; removeNode(hash(key), key, null, false, false); expectedModCount = modCount; } }
          
         
        
       
      
     
    
   

值得注意的就是：nextNode() 就是迭代器里的next()方法 。

该方法的实现可以看出，迭代LinkedHashMap，就是从内部维护的双链表的表头开始循环输出。 而双链表节点的顺序在LinkedHashMap的增、删、改、查时都会更新。以满足按照插入顺序输出，还是访问顺序输出。

4.5 afterNodeInsertion(boolean evict)方法

在节点插入之后做些什么，在HashMap中的putVal()方法中被调用，可以看到HashMap中这个方法的实现为空。

void afterNodeInsertion(boolean evict) {
    // possibly remove eldest    LinkedHashMap.Entry
   
     first;    if (evict && (first = head) != null && removeEldestEntry(first)) {
           K key = first.key;        removeNode(hash(key), key, null, false, true);    }}protected boolean removeEldestEntry(Map.Entry
    
      eldest) {
       return false;}
    
   

evict，驱逐的意思。

（1）如果evict为true，且头节点不为空，且确定移除最老的元素，那么就调用HashMap.removeNode()把头节点移除（这里的头节点是双向链表的头节点，而不是某个桶中的第一个元素）；

（2）HashMap.removeNode()从HashMap中把这个节点移除之后，会调用afterNodeRemoval()方法；

（3）afterNodeRemoval()方法在LinkedHashMap中也有实现，用来在移除元素后修改双向链表，见下文；

（4）默认removeEldestEntry()方法返回false，也就是不删除元素。

4.6 afterNodeAccess(Node e)方法

在节点访问之后被调用，主要在put()已经存在的元素或get()时被调用，如果accessOrder为true，调用这个方法把访问到的节点移动到双向链表的末尾。

void afterNodeAccess(Node
   
     e) {
    // move node to last    LinkedHashMap.Entry
    
      last;    // 如果accessOrder为true，并且访问的节点不是尾节点    if (accessOrder && (last = tail) != e) {
           LinkedHashMap.Entry
     
       p =                (LinkedHashMap.Entry
      
       )e, b = p.before, a = p.after;        // 把p节点从双向链表中移除        p.after = null;        if (b == null)            head = a;        else            b.after = a;                if (a != null)            a.before = b;        else            last = b;                // 把p节点放到双向链表的末尾        if (last == null)            head = p;        else {
               p.before = last;            last.after = p;        }        // 尾节点等于p        tail = p;        ++modCount;    }}
      
     
    
   

• 如果accessOrder为true，并且访问的节点不是尾节点；

• 从双向链表中移除访问的节点；

• 把访问的节点加到双向链表的末尾；（末尾为最新访问的元素）

4.7 afterNodeRemoval(Node e)方法

在节点被删除之后调用的方法。

void afterNodeRemoval(Node
   
     e) {
    // unlink    LinkedHashMap.Entry
    
      p =        (LinkedHashMap.Entry
     
      )e, b = p.before, a = p.after;    p.before = p.after = null;    if (b == null)        head = a;    else        b.after = a;    if (a == null)        tail = b;    else        a.before = b;}
     
    
   

经典的把节点从双向链表中删除的方法。

4.8 get(Object key)方法

获取元素。

public V get(Object key) {
       Node
   
     e;    if ((e = getNode(hash(key), key)) == null)        return null;    if (accessOrder)        afterNodeAccess(e);    return e.value;}
   

如果查找到了元素，且accessOrder为true，则调用afterNodeAccess()方法把访问的节点移到双向链表的末尾。

总结

（1）LinkedHashMap继承自HashMap，具有HashMap的所有特性；

（2）LinkedHashMap内部维护了一个双向链表存储所有的元素；

（3）如果accessOrder为false，则可以按插入元素的顺序遍历元素；

（4）如果accessOrder为true，则可以按访问元素的顺序遍历元素；

（5）LinkedHashMap的实现非常精妙，很多方法都是在HashMap中留的钩子（Hook），直接实现这些Hook就可以实现对应的功能了，并不需要再重写put()等方法；

（6）默认的LinkedHashMap并不会移除旧元素，如果需要移除旧元素，则需要重写removeEldestEntry()方法设定移除策略；

（7）LinkedHashMap可以用来实现LRU缓存淘汰策略；

LinkedHashMap相对于HashMap的源码比，是很简单的。因为大树底下好乘凉。它继承了HashMap，仅重写了几个方法，以改变它迭代遍历时的顺序。这也是其与HashMap相比最大的不同。

在每次插入数据，或者访问、修改数据时，会增加节点、或调整链表的节点顺序。以决定迭代时输出的顺序。

• accessOrder ,默认是false，则迭代时输出的顺序是插入节点的顺序。若为true，则输出的顺序是按照访问节点的顺序。为true时，可以在这基础之上构建一个LruCache.
• LinkedHashMap并没有重写任何put方法。但是其重写了构建新节点的newNode()方法.在每次构建新节点时，将新节点链接在内部双向链表的尾部
• accessOrder=true的模式下,在afterNodeAccess()函数中，会将当前被访问到的节点e，移动至内部的双向链表的尾部。值得注意的是，afterNodeAccess()函数中，会修改modCount,因此当你正在accessOrder=true的模式下,迭代LinkedHashMap时，如果同时查询访问数据，也会导致fail-fast，因为迭代的顺序已经改变。
• nextNode() 就是迭代器里的next()方法 。
  该方法的实现可以看出，迭代LinkedHashMap，就是从内部维护的双链表的表头开始循环输出。
  而双链表节点的顺序在LinkedHashMap的增、删、改、查时都会更新。以满足按照插入顺序输出，还是访问顺序输出。
• 它与HashMap比，还有一个小小的优化，重写了containsValue()方法，直接遍历内部链表去比对value值是否相等。

扩展

LinkedHashMap如何实现LRU缓存淘汰策略呢？

首先，我们先来看看LRU是个什么鬼。LRU，Least Recently Used，最近最少使用，也就是优先淘汰最近最少使用的元素。

如果使用LinkedHashMap，我们把accessOrder设置为true是不是就差不多能实现这个策略了呢？答案是肯定的。请看下面的代码：

/** * @author: csp1999 * @date: 2020/11/10 */public class LRUTest {
       public static void main(String[] args) {
           // 创建一个只有5个元素的缓存        LRU
   
     lru = new LRU<>(5, 0.75f);        lru.put(1, 1);        lru.put(2, 2);        lru.put(3, 3);        lru.put(4, 4);        lru.put(5, 5);        lru.put(6, 6);        lru.put(7, 7);            System.out.println(lru.get(4));            lru.put(6, 666);            // 输出: {3=3, 5=5, 7=7, 4=4, 6=666}        // 可以看到最旧的元素被删除了        // 且最近访问的4被移到了后面        System.out.println(lru);    }}class LRU
    
      extends LinkedHashMap
     
       {
       // 保存缓存的容量    private int capacity;        public LRU(int capacity, float loadFactor) {
           super(capacity, loadFactor, true);        this.capacity = capacity;    }        /**    * 重写removeEldestEntry()方法设置何时移除旧元素    * @param eldest    * @return     */    @Override    protected boolean removeEldestEntry(Map.Entry
      
        eldest) {
           // 当元素个数大于了缓存的容量, 就移除元素        return size() > this.capacity;    }}
      
     
    
   

转载地址：https://csp1999.blog.csdn.net/article/details/112510142 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！