引：如果有这样一种情形，我们需要按照元素插入的顺序来访问元素，这个时候LinkedHashMap大展身手了，它保存着元素插入的顺序，并且可以按照我们插入的顺序进行访问。

概览

LinkedHashMap 继承自 HashMap，在 HashMap 基础上，通过维护一条双向链表，解决了 HashMap 不能随时保持遍历顺序和插入顺序一致的问题。除此之外，LinkedHashMap 对访问顺序也提供了相关支持。在一些场景下，该特性很有用，比如缓存。在实现上，LinkedHashMap 很多方法直接继承自 HashMap，仅为维护双向链表覆写了部分方法。

它的结构示意图如下：

构造

主要就是设置初始容量、负载因子和迭代顺序

// 双向链表的头，最久访问的
transient LinkedHashMap.Entry<K,V> head;
// 双向链表的尾，最新访问的
transient LinkedHashMap.Entry<K,V> tail;
// 默认为false，迭代顺序是按照插入顺序，当为true时，迭代顺序是按照访问信息，最近访问在尾部
final boolean accessOrder;

public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    // 后面和HashMap一样
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

增

LinkedHashMap 本身并没有覆写父类的 put 方法，而是直接使用了父类的实现。但在 HashMap 中，put 方法插入的是 HashMap 内部类 Node 类型的节点，该类型的节点并不具备与 LinkedHashMap 内部类 Entry 及其子类型节点组成链表的能力。下面将展示建立链表的逻辑，其中和HashMap相同的代码这里就不多说，不知道的可以在先阅读在后面参考提到的HashMap解析。

// 1. 调用HashMap的put方法
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

// 2. 调用HashMap的putVal方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    // ...
    // 关键就在这里，这里会触发多态，去调用LinkedHashMap的方法
    tab[i] = newNode(hash, key, value, null);

    // ...
}

// 3. 多态调用LinkedHashMap的newNode方法
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    // 生成LinkedHashMap需要的节点
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    // 将 Entry 接在双向链表的尾部
    linkNodeLast(p);
    return p;
}
// 我们可以看一下这种节点的数据结构
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);
    }
}

// 4. 将新建的节点接在双向链表的尾部
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    // 拿到为节点
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    // 如果尾节点不存在，则代表了链表未生成
    if (last == null)
        head = p;
    // 设置指针
    else {
        p.before = last;
        last.after = p;
    }
}

// 5. 后面的内容就和HashMap一毛一样了

删

与插入操作一样，LinkedHashMap 删除操作相关的代码也是直接用父类的实现。在删除节点时，父类的删除逻辑并不会修复 LinkedHashMap 所维护的双向链表。维护操作都在删除及节点后的回调方法 afterNodeRemoval 中。LinkedHashMap 覆写该方法，并在该方法中完成了移除被删除节点的操作。分析方法同上。

// 1. 调用HashMap的remove方法
public boolean remove(Object key, Object value) {
    return removeNode(hash(key), key, value, true, true) != null;
}

// 2. 调用HashMap的removeNode方法
final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    // ...
    // 对应各种类型的节点删除。这些都不会改变链表的结构
    if (node != null && (!matchValue || (v = node.value) == value ||
                     (value != null && value.equals(v)))) {
    if (node instanceof TreeNode)
        ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
    else if (node == p)
        tab[index] = node.next;
    else
        p.next = node.next;
    ++modCount;
    --size;
    // 关键的来了，这个操作在HashMap是没有实现的，但是在LinkedHashMap中实现了
    afterNodeRemoval(node);
    return node;
    // ...
}

// 3. 调用LinkedHashMap方法的afterNodeRemoval操作来调整链表结构
void afterNodeRemoval(Node<K,V> e) { // unlink
    // 拿到删除节点以及它的前驱节点和后继节点
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)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;
}

改

与插入操作一样，LinkedHashMap 改操作相关的代码也是直接用父类的实现。分析方法同上。

// 1. 调用HashMap的replace方法
public V replace(K key, V value) {
    Node<K,V> e;
    // 前面的操作都和HashMap一致
    if ((e = getNode(hash(key), key)) != null) {
        V oldValue = e.value;
        e.value = value;
        // 重点在修改之后会执行这样一个回调操作
        afterNodeAccess(e);
        return oldValue;
    }
    return null;
}

// 2. 调用LinkedHashMap的afterNodeAccess访问回调方法来调整链表位置
// 将最近访问的节点，放在链表最后
void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    // 当accessOrder为ture 且 访问的不是尾部节点时才进行下面的一顿操作
    if (accessOrder && (last = tail) != e) {
        // 拿到访问节点以及它的前驱节点和后继节点
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        // 后继节点置空
        p.after = null;
        // 前驱节点为头节点
        if (b == null)
            head = a;
        else
            b.after = a;
        // 这里的if/else感觉也都没用，因为都确定不是尾节点了
        if (a != null)
            a.before = b;
        else
            last = b;
        // 表示不会会空，因为都访问到元素了
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        // 将访问节点放到尾部
        tail = p;
        ++modCount;
    }
}

查

查操作覆盖了HashMap的方法，但是也只是添加afterNodeAccess操作判断。

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    // 唯一不同的地方，当accessOrder为true时，则调整链表，和在改操作的分析一样
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

实现 LRU 缓存

LRU 缓存：LRU（Least Recently Used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

大家看到上面的定义就能想到就是在一定条件下删除Head节点嘛，因为最近访问过的都会被放在链表尾部，最近最少使用的一定是投节点。那么LinkedHashMap在哪里为我们留下了实现的接口，我们看看下面的源码：

// 可用于实现LRU缓存，evict就表示删除的意思
void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    // 根据条件判断是否移除最近最少被访问的节点，主要就是removeEldestEntry方法
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        // 删除节点
        removeNode(hash(key), key, null, false, true);
    }
}

// 默认返会false，就是不删除
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

// 当然在源码注释中也为我们重写提供了例子
private static final int MAX_ENTRIES = 100;

protected boolean removeEldestEntry(Map.Entry eldest) {
  // 当大于某个阈值，就移除最老的
  return size() > MAX_ENTRIES;
}

雨过，云过

JDK源码分析——LinkedHashMap

概览

构造

增

删

改

查

实现 LRU 缓存

参考