LinkedHashMap 的核心就 2 点，搞清楚，也就掌握了-白红宇

LinkedHashMap 的核心就 2 点，搞清楚，也就掌握了

阅读量：233 次

发布时间：2019-02-28

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

HashMap 有一个不足之处就是在迭代元素时与插入顺序不一致。而大多数人都喜欢按顺序做某些事情，所以，LinkedHashMap 就是针对这一点对 HashMap 进行扩展，主要新增了**「两种迭代方式」**：

按插入顺序 - 保证迭代元素的顺序与插入顺序一致

按访问顺序 - 一种特殊的迭代顺序，从最近最少访问到最多访问的元素访问顺序，非常适合构建 LRU 缓存
LinkedHashMap 的重点就是这两点，搞清楚了，也就掌握了。由于它继承自 HashMap，所以在分析源码之前一定要先看看 HashMap 的源码，可查看此文。

在 JDK 8 中，因为 LinkedHashMap 子类的存在，HashMap 引入的红黑树，在普通模式和树模式之间的转换变得复杂，那么它是如何设计和简化的呢？接下来看看 JDK 8 中的 LinkedHashMap 源码的设计和实现。

（想自学习编程的小伙伴请搜索，更多行业相关资讯更有行业相关免费视频教程。完全免费哦!）

1. 按插入顺序迭代

HashMap 为什么在迭代时就杂乱无章了？看下它在迭代时获取下一个元素的方式，你就明白了：

final Node
   
     nextNode() {  Node
    
     [] t;  Node
     
       e = next; // 下一个元素要访问节点  if (modCount != expectedModCount)    throw new ConcurrentModificationException();  if (e == null) throw new NoSuchElementException();  // 首先迭代自身所在链表  if ((next = (current = e).next) == null && (t = table) != null) {    // 如果链表访问结束，遍历哈希桶数组中下一个非空元素    do {} while (index < t.length && (next = t[index++]) == null);  }  return e;}

可以看到，HashMap 是按照哈希桶数组中非空的槽依次遍历的，再加上哈希冲突（链表）的情况，与插入顺序相比，更加乱了。

那 LinkedHashMap 怎么解决的？它维护了一个贯穿所有元素的双向链表，遍历时，迭代器直接对双向链表进行迭代，从而保证了与插入顺序一致，关键成员属性和节点信息定义如下：

// 双向链表头节点，也是最久没有访问的元素transient LinkedHashMap.Entry
   
     head;// 双向链表尾节点，也是最近刚刚访问的元素transient LinkedHashMap.Entry
    
      tail;// 迭代方式，true-按访问顺序迭代，false-按插入顺序迭代，默认 falsefinal boolean accessOrder;// 添加了构建双向链表的前驱和后继指针static class Entry
     
       extends HashMap.Node
      
        {  Entry
       
         before, after;   Entry(int hash, K key, V value, Node
        
          next) { super(hash, key, value, next); }}

HashMap 在元素插入、删除和访问时定义并调用了一些 Hook 方法，这些方法使得 LinkedHashMap 内部保持有序的机制相对独立，降低了普通模式和树模式转换的复杂度。

此外，红黑树节点继承的是 LinkedHashMap 的 Entry，固然可能多了两个指针，但在实现时有助于避免操作指针出现混淆错误。

LinkedHashMap 在元素插入时，覆盖的回调方法主要有 newNode, replacementNode, replacementTreeNode, newTreeNode，主要就是保持双向链表，核心是下面两个方法：

// 插入到双向链表的尾部private void linkNodeLast(LinkedHashMap.Entry
   
     p) {  LinkedHashMap.Entry
    
      last = tail; // 临时记住尾节点  tail = p; // 将尾指针指向新节点  if (last == null)    head = p; // 第一个插入的节点  else { // 关联前后节点    p.before = last;    last.after = p;  }}// 连接两个节点之间的前后指针private void transferLinks(LinkedHashMap.Entry
     
       src,                           LinkedHashMap.Entry
      
        dst) {  LinkedHashMap.Entry
       
         b = dst.before = src.before;  LinkedHashMap.Entry
        
          a = dst.after = src.after; if (b == null) head = dst; else b.after = dst; if (a == null) tail = dst; else a.before = dst;}

迭代器的实现就比较简单了，直接对这个双向链表迭代即可，此时的迭代顺序就插入顺序。

2. 按访问顺序迭代

为了让元素按访问顺序排列，HashMap 定义了以下 Hook 方法，供 LinkedHashMap 实现：

void afterNodeAccess(Node
   
     p) { }void afterNodeInsertion(boolean evict) { }void afterNodeRemoval(Node
    
      p) { }

各个方法实现的原理如下：

afterNodeAccess 的原理是：访问的元素如果不是尾节点，那么就把它与尾节点交换，所以随着元素的访问，访问次数越多的元素越靠后

afterNodeRemoval 这个没有特殊操作，正常的断开链条

afterNodeInsertion 的原理是：元素插入后，可能会删除最旧的、访问次数最少的元素，也就是头节点

重点看下插入之后的实现：

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);  }}

是否会删除头节点，是由 removeEldestEntry 方法决定的，默认返回 false。在覆盖这个方法时，不能简单的返回 true，因为这样可能会导致一个空的 LinkedHashMap，通常的做法是在插入指定数量的元素后再删除，具体见下面 LRU 缓存的实现。

3. 实现一个 LRU 缓存

借助 LinkedHashMap 可以很方便的实现一个 LRU 缓存数据结构，只需设置 accessOrder 为 true，并覆盖 removeEldestEntry 方法即可，代码如下：

final int MAX_CACHE_SIZE = 100;LinkedHashMap
   
     lru = new LinkedHashMap
    
     (MAX_CACHE_SIZE, 0.75f, true) {    private static final long serialVersionUID = 1L;    protected boolean removeEldestEntry(Map.Entry
     
       eldest) {      return size() > MAX_CACHE_SIZE;    }};

4. 小结

LinkedHashMap 代码比较简单，难的都被 HashMap 实现了:)，它们的异同点分别如下：

底层都是数组+链表+红黑树（废话）

迭代器都是快速失败的，都是非线程安全

LinkedHashMap 有按插入和访问两种迭代顺序，而HashMap 乱序，迭代顺序不可预测

看这个类的源码，最主要的还是看 HashMap 定义 Hook 方法，使得 LinkedHashMap 保持有序的机制相对独立的设计，这是模板模式的应用。

转载地址：http://mxbp.baihongyu.com/

你可能感兴趣的文章