Java集合框架分析(五)LinkedHashMap分析

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>
复制代码

继承自 HashMap，一个有序的 Map 接口实现，这里的有序指的是元素可以按插入顺序或访问顺序排列；与 HashMap 相比，因为 LinkedHashMap 是继承自 HashMap，因此LinkedHashMap，同样是基于散列表实现。同时实现了 Serializable 和 Cloneable 接口，支持序列化和克隆。并且同样不是线程安全的。区别是其内部维护了一个双向循环链表，该链表是有序的，可以按元素插入顺序或元素最近访问顺序 (LRU) 排列。

LinkedHashMap数据结构

LinkedHashMap 不仅像 HashMap 那样对其进行基于哈希表和单链表的 Entry 数组+ next 链表的存储方式，而且还结合了 LinkedList 的优点，为每个 Entry 节点增加了前驱和后继，并增加了一个为 header 头结点，构造了一个双向循环链表。也就是说，每次 put 进来 KV，除了将其保存到对哈希表中的对应位置外，还要将其插入到双向循环链表的尾部。

上图是 LinkedHashMap 的全部数据结构，包含散列表和循环双向链表，由于循环双向链表线条太多了，不好画，简单的画了一个节点(黄色圈出来的)示意一下，注意左边的红色箭头引用为 Entry 节点对象的 next 引用(散列表中的单链表)，绿色线条为 Entry 节点对象的 before, after 引用(循环双向链表的前后引用)；

上图专门把循环双向链表抽取出来，直观一点，注意该循环双向链表的头部存放的是最久访问的节点或最先插入的节点，尾部为最近访问的或最近插入的节点，迭代器遍历方向是从链表的头部开始到链表尾部结束，在链表尾部有一个空的 header 节点，该节点不存放 key-value 内容，为 LinkedHashMap 类的成员属性，循环双向链表的入口；

LinkedHashMap源码

上面是分析 LinkedHashMap 源码的常规知识点，了解一下，才能更好的分析它的源码，下面我们便开始正式的进行分析工作。

属性：

//属性设置，序列化ID
private static final long serialVersionUID = 3801124242820219131L;
//双向链表的头部
private transient LinkedHashMapEntry<K,V> header;
//迭代的时候所用到的顺序，如果为FALSE，则按照插入的时候顺序
private final boolean accessOrder;
复制代码

这些属性虽然简单，但是比较重要，一开始就直接详细说明，不大好理解，等我们分析完了代码再来回顾一下它们所表示的意思。我们来分析分析它的构造函数。

构造器分析

设置初始容量和加载因子的构造器

/**
  * 设置初始容量和加载因子的构造器
  */
 public LinkedHashMap(int initialCapacity, float loadFactor) {
     super(initialCapacity, loadFactor);
     accessOrder = false;
 }
复制代码

设置初始容量的构造器

/**
  * 设置初始容量的构造器
  * @param  initialCapacity the initial capacity
  * @throws IllegalArgumentException if the initial capacity is negative
  */
 public LinkedHashMap(int initialCapacity) {
     super(initialCapacity);
     accessOrder = false;
 }
复制代码

默认的空参数的构造器，默认容量为16以及加载因子为0.75

/**
  * 默认的空参数的构造器，默认容量为16以及加载因子为0.75
  * with the default initial capacity (16) and load factor (0.75).
  */
 public LinkedHashMap() {
     super();
     accessOrder = false;
 }
复制代码

使用一个现有的Map来构造LinkedHashMap

/**
  * 使用一个现有的Map来构造LinkedHashMap
  * @param  m the map whose mappings are to be placed in this map
  * @throws NullPointerException if the specified map is null
  */
 public LinkedHashMap(Map<? extends K, ? extends V> m) {
     super(m);
     accessOrder = false;
 }
复制代码

设定迭代顺序的构造器

/**
  * 设定迭代顺序的构造器
  * @param  initialCapacity the initial capacity
  * @param  loadFactor      the load factor
  * @param  accessOrder     the ordering mode - <tt>true</tt> for
  *         access-order, <tt>false</tt> for insertion-order
  * @throws IllegalArgumentException if the initial capacity is negative
  *         or the load factor is nonpositive
  */
 public LinkedHashMap(int initialCapacity,
                      float loadFactor,
                      boolean accessOrder) {
     super(initialCapacity, loadFactor);
     this.accessOrder = accessOrder;
 }
复制代码

这些构造器都比较简单，我们稍微提及一下，若未指定初始容量 initialCapacity，则默认为使用 HashMap 的初始容量，即 16。若未指定加载因子 loadFactor，则默认为 0.75。accessOrder 默认为 faslse。这里需要介绍一下这个布尔值，它是双向链表中元素排序规则的标志位。

accessOrder 若为 false，遍历双向链表时，是按照插入顺序排序。 accessOrder 若为 true，表示双向链表中的元素按照访问的先后顺序排列，最先遍历到（链表头）的是最近最少使用的元素。

从构造方法中可以看出，默认都采用插入顺序来维持取出键值对的次序。所有构造方法都是通过调用父类的构造方法来创建对象的。

在父类的构造器中我们可以看到它调用了 init 方法，即在 Map 类中的构造器中调用了 init 方法，我们进入查看一下内容

@Override
    void init() {
        header = new LinkedHashMapEntry<>(-1, null, null, null);
        header.before = header.after = header;
    }
复制代码

这个 init 方法主要是对 header 节点进行初始化的，构成一个双向链表。分析完了构造器，接着我们分析一下最常见的一个属性 Entry。

LinkedHashMapEntry分析

//这个Entry继承自HashMapEntry
 private static class LinkedHashMapEntry<K,V> extends HashMapEntry<K,V> {
        //双向节点的前后引用
        // These fields comprise the doubly linked list used for iteration.
        LinkedHashMapEntry<K,V> before, after;
        
        //构造器
        LinkedHashMapEntry(int hash, K key, V value, HashMapEntry<K,V> next) {
            super(hash, key, value, next);
        }
        //移除一个节点
        private void remove() {
            before.after = after;
            after.before = before;
        }
        /**
         * 在指定的位置前面插入一个节点
         */
        private void addBefore(LinkedHashMapEntry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }
        /*
         *在HashMap的put和get方法中，会调用该方法，在HashMap中该方法为空
         * 在LinkedHashMap中，当按访问顺序排序时，该方法会将当前节点插入到链表尾部(头结点的前一个节点)，否则不做任何事
         */
        void recordAccess(HashMap<K,V> m) {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
            //当LinkedHashMap按访问排序时
            if (lm.accessOrder) {
                lm.modCount++;
                //移除当前节点
                remove();
                //将当前节点插入到头结点前面
                addBefore(lm.header);
            }
        }
        void recordRemoval(HashMap<K,V> m) {
            remove();
        }
    }
复制代码

接着分析最常用的方法 put。

put分析

我们在使用 LinkedHashMap 的 put 方法时，发现它调用的是 HashMap 的 put 方法，自己本身没有复写 put 方法，所以这种情况下，我们就得分两种情况来讨论 LinkedHashMap 的 put 操作了。

Key已存在的情况

在 HashMap 的 put 方法中，在发现插入的 key 已经存在时，除了做替换工作，还会调用recordAccess() 方法，在 HashMap 中该方法为空。LinkedHashMap 覆写了该方法，（调用LinkedHashmap 覆写的 get 方法时，也会调用到该方法），LinkedHashMap 并没有覆写 HashMap 中的 put 方法，recordAccess() 在 LinkedHashMap 中的实现如下：

//如果当前标明的accessOrder为TRUE的话，则将当前访问的Entry放置到双向循环链表的尾部，以标明最近访问 ，这也是为什么在HashMap.Entry中有一个空的 recordAccess(HashMap<K,V> m)方法的原因
void recordAccess(HashMap<K,V> m) {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
            //LRU算法，将访问的节点插入到链表尾部
            if (lm.accessOrder) {
                lm.modCount++;
                //删除当前节点
                remove();
                //将当前节点插入到头结点前面
                addBefore(lm.header);
            }
        }
        
//将当前节点插入到头结点前面
private void addBefore(LinkedHashMapEntry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }
     
复制代码

key不存在的情况下

在 put 新 Entry 的过程中，如果发现 key 不存在时，除了将新 Entry 放到哈希表的相应位置，还会调用 addEntry 方法，它会调用 creatEntry 方法，该方法将新插入的元素放到双向链表的尾部，这样做既符合插入的先后顺序，又符合了访问的先后顺序。

//创建节点，插入到LinkedHashMap中，该方法覆盖HashMap的addEntry方法
void addEntry(int hash, K key, V value, int bucketIndex) {
        //注意头结点的下个节点即header.after，存放于链表头部，是最不经常访问或第一个插入的节点，
        LinkedHashMapEntry<K,V> eldest = header.after;
        //如果有必要，则删除掉该近期最少使用的节点
        if (eldest != header) {
            boolean removeEldest;
            size++;
            try {
                //removeEldestEntry方法的实现，这里默认为false
                removeEldest = removeEldestEntry(eldest);
            } finally {
                size--;
            }
            if (removeEldest) {
                removeEntryForKey(eldest.key);
            }
        }
        //调用HashMap的addEntry方法
        super.addEntry(hash, key, value, bucketIndex);
    }
    
//创建节点，并将该节点插入到链表尾部
 void createEntry(int hash, K key, V value, int bucketIndex) {
        HashMapEntry<K,V> old = table[bucketIndex];
        LinkedHashMapEntry<K,V> e = new LinkedHashMapEntry<>(hash, key, value, old);
        table[bucketIndex] = e;
        //并将其移到双向链表的尾部  
        e.addBefore(header);
        size++;
    }
复制代码

在上面的 addEntry 方法中有一个 removeEldestEntry 方法，这个方法可以被覆写，比如可以将该方法覆写为如果设定的内存已满，则返回 true，这样就可以将最近最少使用的节点（header 后的节点）删除掉。

为什么这个方法始终返回 false？

结合上面的 addEntry(int hash,K key,V value,int bucketIndex) 方法，这样设计可以使LinkedHashMap 成为一个正常的 Map，不会去移除“最老”的节点。 为什么不在代码中直接去除这部分逻辑而是设计成这样呢？这为开发者提供了方便，若希望将 Map 当做 Cache 来使用，并且限制大小，只需继承 LinkedHashMap 并重写 removeEldestEntry(Entry<K,V> eldest) 方法，像这样：

private static final int MAX_ENTRIES = 100;
protected boolean removeEldestEntry(Map.Entry eldest) {
      return size() > MAX_ENTRIES;
}
复制代码

总结一下只要是 put 进来的新元素，不管 accessOrder 标志位是什么，均将新元素放到双链表尾部，并且可以在需要实现Lru算法时时覆写 removeEldestEntry 方法，剔除最近最少使用的节点。

get分析

//覆写HashMap中的get方法，通过getEntry方法获取Entry对象。  
//注意这里的recordAccess方法，  
//如果链表中元素的排序规则是按照插入的先后顺序排序的话，该方法什么也不做，  
//如果链表中元素的排序规则是按照访问的先后顺序排序的话，则将e移到链表的末尾处。
public V get(Object key) {
        LinkedHashMapEntry<K,V> e = (LinkedHashMapEntry<K,V>)getEntry(key);
        if (e == null)
            return null;
        e.recordAccess(this);
        return e.value;
    }
    
void recordAccess(HashMap<K,V> m) {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
            if (lm.accessOrder) {
                lm.modCount++;
                remove();
                addBefore(lm.header);
            }
        }
复制代码

get(Object key) 方法通过 HashMap 的 getEntry(Object key) 方法获取节点，并返回该节点的 value 值，获取节点如果为 null 则返回 null。通过 key 获取 value，与 HashMap 的区别是：当 LinkedHashMap 按访问顺序排序的时候，会将访问的当前节点移到链表尾部(头结点的前一个节点)。

到这里我们来具体总结一下 accessOrder 标志位的作用原理。

1、accessOrder 不起作用

对于 put 操作时，不管 accessOrder 标志位是什么，我们都将节点插入到链表的尾部，但是呢，可以在需要实现 Lru 算法时时覆写 removeEldestEntry 方法，剔除最近最少使用的节点。

2、accessOrder 起作用

当我们进行 put 操作是，如果 key 不等于 null 的话，会调用 recordAccess 方法，在该方法中 accessOrder 就得起作用了，如果 accessOrder 为 fasle 时，什么也不做，也就是说当我们放入已经存在 Key 的键值对，它在双链表中的位置是不会变的。accessOrder 设置为 true 时， put 操作会将相关元素放置到双链表的尾部。

另外一种情况就是 get 操作，get 操作我们同时也会调用 recordAccess 方法，对于这个方法，我们需要判断 accessOrder 的状态，如果 accessOrder 为 fasle 时，什么也不做，也就是说当我们放入已经存在 Key 的键值对，它在双链表中的位置是不会变的。accessOrder 设置为 true 时，put 操作会将相关元素放置到双链表的尾部。在缓存的角度来看，这就是所谓的“脏数据”，即最近被访问过的数据，因此在需要清理内存时（添加进新元素时），就可以将双链表头节点（空节点）后面那个节点剔除。

不常用方法

到此为止，基本上 LinkedHashMap 比较重要的方法就分析过了，还剩一些比较不重要的方法，我们一次性给它注视下，稍微看下。

//
@Override
void transfer(HashMapEntry[] newTable) {
    int newCapacity = newTable.length;
    for (LinkedHashMapEntry<K,V> e = header.after; e != header; e = e.after) {
        int index = indexFor(e.hash, newCapacity);
        e.next = newTable[index];
        newTable[index] = e;
    }
}
复制代码

transfer(HashMap.Entry[] newTable) 方法和 init() 方法一样也在 HashTable 中被调用。transfer(HashMap.Entry[] newTable) 方法在 HashMap 调用 resize(int newCapacity) 方法的时候被调用。根据链表节点 e 的哈希值计算 e 在新容量的 table 数组中的索引，并将 e 插入到计算出的索引所引用的链表中。

public boolean containsValue(Object value) {
        // Overridden to take advantage of faster iterator
        if (value==null) {
            for (LinkedHashMapEntry e = header.after; e != header; e = e.after)
                if (e.value==null)
                    return true;
        } else {
            for (LinkedHashMapEntry e = header.after; e != header; e = e.after)
                if (value.equals(e.value))
                    return true;
        }
        return false;
    }
复制代码

重写父类的 containsValue(Object value) 方法，直接通过 header 遍历链表判断是否有值和 value 相等，利用双向循环链表的特点进行查询，少了对数组的外层 for 循环 ,而不用查询 table 数组。

public void clear() {
       super.clear();
       header.before = header.after = header;
   }
复制代码

clear() 方法先调用父类的方法 clear() 方法，之后将链表的 header 节点的 before 和 after 引用都指向 header 自身，即 header 节点就是一个双向循环链表。这样就无法访问到原链表中剩余的其他节点，他们都将被 GC 回收。清空 HashMap 的同时，将双向链表还原为只有头结点的空链表。

以上便是 LinkedHashMap 源码主要方法的分析，到这里就要结束了，我们来总结一下关于 HashMap 和 LinkedHashMap 的相关东西。

总结

对于 LinkedHashMap，我们总结了以下几点内容：

1、由于 LinkedHashMap 继承自 HashMap，所以它不仅像 HashMap 那样对其进行基于哈希表和单链表的 Entry 数组+ next 链表的存储方式，而且还结合了 LinkedList 的优点，为每个 Entry 节点增加了前驱和后继，并增加了一个为 header 头结点，构造了一个双向循环链表。（多一个以 header 为头结点的双向循环链表，也就是说，每次 put 进来 KV，除了将其保存到对哈希表中的对应位置外，还要将其插入到双向循环链表的尾部。）

2、LinkedHashMap 的属性比 HashMap 多了一个 accessOrder 属性。当它 false 时，表示双向链表中的元素按照 Entry 插入 LinkedHashMap 到中的先后顺序排序，即每次 put 到 LinkedHashMap 中的 Entry 都放在双向链表的尾部，这样遍历双向链表时，Entry 的输出顺序便和插入的顺序一致，这也是默认的双向链表的存储顺序；当它为 true 时，表示双向链表中的元素按照访问的先后顺序排列，可以看到，虽然 Entry 插入链表的顺序依然是按照其 put 到 LinkedHashMap 中的顺序，但 put 和 get 方法均有调用 recordAccess 方法（put 方法在 key 相同，覆盖原有的 Entry 的情况下调用 recordAccess 方法）， 该方法判断 accessOrder 是否为 true，如果是，则将当前访问的 Entry（put 进来的 Entry 或 get 出来的 Entry）移到双向链表的尾部（key 不相同时，put 新 Entry 时，会调用 addEntry，它会调用 creatEntry，该方法同样将新插入的元素放入到双向链表的尾部，既符合插入的先后顺序，又符合访问的先后顺序，因为这时该 Entry 也被访问了），否则，什么也不做。

3、构造函数中有设置 accessOrder 的方法，如果我们需要实现 LRU 算法时，就需要将 accessOrder 的值设定为 TRUE。

4、在 HashMap 的 put 方法中，如果 key 不为 null 时且哈希表中已经在存在时，循环遍历 table[i] 中的链表时会调用 recordAccess 方法，而在 HashMap 中这个方法是个空方法，在LinkedHashMap中则实现了该方法，该方法会判断 accessOrder 是否为 true，如果为 true，它会将当前访问的 Entry（在这里指 put 进来的 Entry）移动到双向循环链表的尾部，从而实现双向链表中的元素按照访问顺序来排序（最近访问的 Entry 放到链表的最后，这样多次下来，前面就是最近没有被访问的元素，在实现 LRU 算法时，当双向链表中的节点数达到最大值时，将前面的元素删去即可，因为前面的元素是最近最少使用的），否则什么也不做。