深读源码-java集合之LinkedHashMap源码分析

简介

LinkedHashMap内部维护了一个双向链表，能保证元素按插入的顺序访问，也能以访问顺序访问，可以用来实现LRU缓存策略。

LinkedHashMap可以看成是 LinkedList + HashMap。

类继承体系

深读源码-java集合之LinkedHashMap源码分析

LinkedHashMap继承HashMap，拥有HashMap的所有特性，并且额外增加了按一定顺序访问的特性。

Entry的继承关系

深读源码-java集合之LinkedHashMap源码分析

Entry作为基本的节点，可以看到LinkedHashMap的Entry继承自HashMap的Node，在其基础上加上了before和after两个指针，而TreeNode作为HashMap和LinkedHashMap的树节点，继承自LinkedHahsMap的Entry，并且加上了树节点的相关指针，另外提一点：before和parent的两个概念是不一样的，before是相对于链表来的，parent是相对于树操作来的，所以要分两个。

Iterator的继承关系

深读源码-java集合之LinkedHashMap源码分析

LinkedHashMap的迭代器为遍历节点提供了自己的实现——LinkedHashIterator，对于Key、Value、Entry的3个迭代器，都继承自它。而且内部采用的遍历方式就是在前面提到的Entry里加的新的指向下一个节点的指针after，后面我们将具体看它的代码实现。

存储结构

深读源码-java集合之LinkedHashMap源码分析

双链表是链表的一种，由节点组成，每个数据结点中都有两个指针，分别指向直接后继和直接前驱

深读源码-java集合之LinkedHashMap源码分析

我们知道HashMap使用（数组 + 单链表 + 红黑树）的存储结构，那LinkedHashMap是怎么存储的呢？

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

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

源码解析

属性

/**
 * 双向链表头节点 
 */
transient LinkedHashMap.Entry<K,V> head;

/**
 * 双向链表尾节点 
 */
transient LinkedHashMap.Entry<K,V> tail;

/**
 * 是否需要按访问顺序排序，用来指定LinkedHashMap的迭代顺序。
 * true则表示按照基于访问的顺序来排列，意思就是最近使用的entry，放在链表的最末尾
 * false则表示按照插入顺序排序
 */ 
final boolean accessOrder;

（1）head

双向链表的头节点，旧数据存在头节点。

（2）tail

双向链表的尾节点，新数据存在尾节点。

（3）accessOrder

是否需要按访问顺序排序， true则表示按照基于访问的顺序来排列，意思就是最近使用的entry，放在链表的最末尾；false则表示按照插入顺序排序。

注意：

accessOrder是

final关键字，说明我们要在构造方法里给它初始化。

内部类

// 位于LinkedHashMap中
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

// 位于HashMap中
static class Node<K, V> implements Map.Entry<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K, V> next;
}

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

构造方法

public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}

public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}

public LinkedHashMap() {
    super();
    accessOrder = false;
}

public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super();
    accessOrder = false;
    putMapEntries(m, false);
}

public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

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

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

get(Object key)方法

获取元素。

public V get(Object key) {
    Node<K,V> e;
    // 调用HashMap的getNode的方法，详见上一篇HashMap源码解析
    if ((e = getNode(hash(key), key)) == null)
        return null;
    // 在取值后对参数accessOrder进行判断，如果为true，执行afterNodeAccess
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

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

afterNodeAccess(Node<K,V> e)方法

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

// 此函数执行的效果就是将最近使用的Node，放在链表的最末尾
void afterNodeAccess(Node<K,V> e) {
  LinkedHashMap.Entry<K,V> last;
  // 仅当按照LRU原则且e不在最末尾，才执行修改链表，将e移到链表最末尾的操作
  if (accessOrder && (last = tail) != e) {
    // 将e赋值临时节点p， b是e的前一个节点， a是e的后一个节点
    LinkedHashMap.Entry<K,V> p =
      (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    // 设置p的后一个节点为null，因为执行后p在链表末尾，after肯定为null
    p.after = null;
    // p前一个节点不存在，情况一
    if (b == null) // ①
      head = a;// p为头部，前一个节点b不存在，那么考虑到p要放到最后面，则设置p的后一个节点a为head
    else
      b.after = a;// P不是头部，前一个节点b存在，重新设置b的后一个节点为a
    if (a != null) 
      a.before = b;// P不是尾部，设置a的前一个节点为b
    // p的后一个节点不存在，情况二
    else // ②
      last = b;// p为尾部，后一个节点a不存在，那么考虑到统一操作，设置last为b
    // 情况三
    if (last == null) // ③
      head = p;// p为链表里的第一个节点，head=p
    // 正常情况，将p设置为尾节点的准备工作，p的前一个节点为原先的last，last的after为p
    else {
      p.before = last;
      last.after = p;
    }
    // 将p设置为尾节点
    tail = p;
    // 修改计数器+1
    ++modCount;
  }
}

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

（2）从双向链表中移除访问的节点；

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

标注的情况如下图所示（特别说明一下，这里是显示链表的修改后指针的情况，实际上在桶里面的位置是不变的，只是前后的指针指向的对象变了）：

深读源码-java集合之LinkedHashMap源码分析

下面来简单说明一下：

正常情况下：查询的p在链表中间，那么将p设置到末尾后，它原先的前节点b和后节点a就变成了前后节点。
情况一：p为头部，前一个节点b不存在，那么考虑到p要放到最后面，则设置p的后一个节点a为head
情况二：p为尾部，后一个节点a不存在，那么考虑到统一操作，设置last为b
情况三：p为链表里的第一个节点，head=p

put()方法

LinkedHashMap的put方法调用的还是HashMap里的put，不同的是重写了里面的部分方法：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
  	...
    tab[i] = newNode(hash, key, value, null);
  	...
    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  	...
    if ((e = p.next) == null) {
      p.next = newNode(hash, key, value, null);
    ...
        afterNodeAccess(e);
    ...
        afterNodeInsertion(evict);
      return null;
}

由于在之前《深读源码-java集合之HashMap源码分析》分析过了put方法，这里笔者就省略了部分代码，LinkedHashMap将其中

newNode

方法以及之前设置下的钩子方法

afterNodeAccess

和

afterNodeInsertion

进行了重写，从而实现了加入链表的目的：

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
  // 秘密就在于 new的是自己的Entry类，然后调用了linkedNodeLast
  LinkedHashMap.Entry<K,V> p =
    new LinkedHashMap.Entry<K,V>(hash, key, value, e);
  linkNodeLast(p);
  return p;
}

// 顾名思义就是把新加的节点放在链表的最后面
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
  // 将tail给临时变量last
  LinkedHashMap.Entry<K,V> last = tail;
  // 把new的Entry给tail
  tail = p;
  // 若没有last，说明p是第一个节点，head=p
  if (last == null)
    head = p;
  // 否则就做准备工作，你懂的 (￣▽￣)"
  else {
    p.before = last;
    last.after = p;
  }
}

// 这里笔者也把TreeNode的重写也加了进来，因为putTreeVal里有调用了这个
TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
  TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
  linkNodeLast(p);
  return p;
}

// 插入后把最老的Entry删除，不过removeEldestEntry总是返回false，所以不会删除，估计又是一个钩子方法给子类用的
void afterNodeInsertion(boolean evict) {
  LinkedHashMap.Entry<K,V> first;
  if (evict && (first = head) != null && removeEldestEntry(first)) {
    K key = first.key;
    removeNode(hash(key), key, null, false, true);
  }
}

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
  return false;
}

afterNodeInsertion(boolean evict)方法

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

// 插入后把最老的Entry删除，不过removeEldestEntry总是返回false，所以不会删除，估计又是一个钩子方法给子类用的
void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

evict，驱逐的意思。

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

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

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

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

remove()方法

remove里面设计者也设置了一个钩子方法：

final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
  ...
      // node即是要删除的节点
      afterNodeRemoval(node);
  ...
}

afterNodeRemoval(Node<K,V> e)方法

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

void afterNodeRemoval(Node<K,V> e) { // unlink
    LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    // p已删除，前后指针都设置为null，便于GC回收
    p.before = p.after = null;
    // 与afterNodeAccess差不多逻辑
    if (b == null)
        head = a;
    else
        b.after = a;
    if (a == null)
        tail = b;
    else
        a.before = b;
}

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

LinkedHashMap的迭代器

abstract class LinkedHashIterator {
  // 记录下一个Entry
  LinkedHashMap.Entry<K,V> next;
  // 记录当前的Entry
  LinkedHashMap.Entry<K,V> current;
  // 记录是否发生了迭代过程中的修改
  int expectedModCount;

  LinkedHashIterator() {
    // 初始化的时候把head给next
    next = head;
    expectedModCount = modCount;
    current = null;
  }

  public final boolean hasNext() {
    return next != null;
  }

  // 这里采用的是链表方式的遍历方式，有兴趣的读者可以去之前的《深读源码-java集合之HashMap源码分析》看看HashMap的遍历方式
  final LinkedHashMap.Entry<K,V> nextNode() {
    LinkedHashMap.Entry<K,V> e = next;
    if (modCount != expectedModCount)
      throw new ConcurrentModificationException();
    if (e == null)
      throw new NoSuchElementException();
    //记录当前的Entry
    current = e;
    //直接拿after给next
    next = e.after;
    return e;
  }

  public final void remove() {
    Node<K,V> 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;
  }
}

总结

（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如何实现LRU缓存淘汰策略呢？

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

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

package cn.com.sdd.study.list;

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * @author suidd
 * @name LRUTest
 * @description LRU缓存淘汰策略测试
 * @date 2020/5/9 16:54
 * Version 1.0
 **/
public class LRUTest {
    public static void main(String[] args) {
        // 创建一个只有5个元素的缓存
        LRU<Integer, Integer> 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被移到了后面
        // 如果LRU构造accessOrder设置为false，则输出{3=3, 4=4, 5=5, 6=666, 7=7}
        System.out.println(lru);
    }
}

class LRU<K, V> extends LinkedHashMap<K, V> {

    // 保存缓存的容量
    private int capacity;

    public LRU(int capacity, float loadFactor) {
        //accessOrder：true:按访问顺序排序（LRU），false:按插入顺序排序；
        super(capacity, loadFactor, true);
        this.capacity = capacity;
    }

    /**
     * 重写removeEldestEntry()方法设置何时移除旧元素
     *
     * @param eldest
     * @return
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        // 当元素个数大于了缓存的容量, 就移除元素
        return size() > this.capacity;
    }
}

参考链接：https://www.cnblogs.com/tong-yuan/p/10639263.html

参考链接：https://www.cnblogs.com/joemsu/p/7787043.html

深读源码-java集合之LinkedHashMap源码分析

简介

类继承体系

Entry的继承关系

Iterator的继承关系

存储结构

源码解析

属性

内部类

构造方法

get(Object key)方法

afterNodeAccess(Node<K,V> e)方法

put()方法

afterNodeInsertion(boolean evict)方法

remove()方法

afterNodeRemoval(Node<K,V> e)方法

LinkedHashMap的迭代器

总结

彩蛋

继续阅读

nginx location中斜线的位置的重要性

数据结构与算法（27）——排序（二）

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的简单使用

neo4j之cypher使用文档

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

spark/scala关于【资源文件】加载方法概述外部文件加载方案测试资源文件打包入jar包中小结

mybatis_入门程序Mybatis入门

AOP编程_Android优雅权限框架(1)概念基础，2021金三银四前言正文大纲正文

Effective Java 8:通用程序设计

OOM三种类型

工厂模式-三种类型

【递归】高效率求2的n次幂

win10本地scala和spark安装安装scala安装spark

Linux设备模型（中）之上层容器

scala (3) Function 和 Method