Java集合 - LinkedHashMap

LinkedHashMap

一：认识 LRU 缓存淘汰算法

1：什么是缓存淘汰算法

缓存是提高数据读取性能的通用技术，在硬件和软件设计中被广泛使用，例如 CPU 缓存，Glide 内存缓存，数据库缓存等。

由于缓存空间不可能无限大，当缓存容量占满时，就需要利用某种策略将部分数据换出缓存，这就是缓存的替换策略 / 淘汰问题。

常见缓存淘汰策略有：

随机策略

使用一个随机数生成器随机地选择要被淘汰的数据块

FIFO 先进先出策略

记录各个数据块的访问时间，最早访问的数据最先被淘汰

LRU （Least Recently Used）最近最少策略

记录各个数据块的访问 “时间戳” ，最近最久未使用的数据最先被淘汰。

与前 2 种策略相比，LRU 策略平均缓存命中率更高

因为 LRU 策略利用了 “局部性原理”：最近被访问过的数据，将来被访问的几率较大，最近很久未访问的数据，将来访问的几率也较小

LFU （Least Frequently Used）最不经常使用策略

与 LRU 相比，LFU 更加注重使用的 “频率” 。

LFU 会记录每个数据块的访问次数，最少访问次数的数据最先被淘汰。但是有些数据在开始时使用次数很高，以后不再使用，这些数据就会长时间污染缓存。

可以定期将计数器右移一位，形成指数衰减

2：LRU的变型

其实，在标准的 LRU 算法上还有一些变型实现，这是因为 LRU 算法本身也存在一些不足。

例如，当数据中热点数据较多时，LRU 能够保证较高的命中率。

但是当有偶发的批量的非热点数据产生时，就会将热点数据寄出缓存，使得缓存被污染。

因此，LRU 也有一些变型：

• LRU-K： 提供两个 LRU 队列，一个是访问计数队列，一个是标准的 LRU 队列，两个队列都按照 LRU 规则淘汰数据。当访问一个数据时，数据先进入访问计数队列，当数据访问次数超过 K 次后，才会进入标准 LRU 队列。标准的 LRU 算法相当于 LRU-1；
• Two Queue： 相当于 LRU-2 的变型，将访问计数队列替换为 FIFO 队列淘汰数据数据。当访问一个数据时，数据先进入 FIFO 队列，当第 2 次访问数据时，才会进入标准 LRU 队列；
• Multi Queue： 在 LRU-K 的基础上增加更多队列，提供多个级别的缓冲。

3：如何实现LRU

我们可以定义一个缓存系统的基本操作：

• 操作 1 - 添加数据： 先查询数据是否存在，不存在则添加数据，存在则更新数据，并尝试淘汰数据；
• 操作 2 - 删除数据： 先查询数据是否存在，存在则删除数据；
• 操作 3 - 查询数据： 如果数据不存在则返回 null；
• 操作 4 - 淘汰数据： 添加数据时如果容量已满，则根据缓存淘汰策略一个数据。

我们发现，前 3 个操作都有 “查询” 操作， 所以缓存系统的性能主要取决于查找数据和淘汰数据是否高效。

下面，我们用递推的思路推导 LRU 缓存的实现方案，主要分为 3 种方案：

• 方案 1 - 基于时间戳的数组： 在每个数据块中记录最近访问的时间戳，当数据被访问（添加、更新或查询）时，将数据的时间戳更新到当前时间。当数组空间已满时，则扫描数组淘汰时间戳最小的数据。
  • 查找数据： 需要遍历整个数组找到目标数据，时间复杂度为 O(n)；
  • 淘汰数据： 需要遍历整个数组找到时间戳最小的数据，且在移除数组元素时需要搬运数据，整体时间复杂度为 O(n)。
• 方案 2 - 基于双向链表： 不再直接维护时间戳，而是利用链表的顺序隐式维护时间戳的先后顺序。当数据被访问（添加、更新或查询）时，将数据插入到链表头部。当空间已满时，直接淘汰链表的尾节点。
  • 查询数据：需要遍历整个链表找到目标数据，时间复杂度为 O(n)；
  • 淘汰数据：直接淘汰链表尾节点，时间复杂度为 O(1)。
• 方案 3 - 基于双向链表 + 散列表： 使用双向链表可以将淘汰数据的时间复杂度降低为 O(1)，但是查询数据的时间复杂度还是 O(n)，我们可以在双向链表的基础上增加散列表，将查询操作的时间复杂度降低为 O(1)。
  • 查询数据：通过散列表定位数据，时间复杂度为 O(1)；
  • 淘汰数据：直接淘汰链表尾节点，时间复杂度为 O(1)。

方案 3 这种数据结构就叫哈希链表，因为当这两个数据结构相结合时，我们更看重的是它作为链表的排序能力。

二：LinkedHashMap概述

1：LinkedHashMap 的特点

LinkedHashMap 中的 “Linked” 实际上是指双向链表，并不是指解决散列冲突中的分离链表法

LinkedHashMap 是继承于 HashMap 实现的哈希链表，它同时具备双向链表和散列表的特点。

事实上，LinkedHashMap 继承了 HashMap 的主要功能，并通过 HashMap 预留的 Hook 点维护双向链表的逻辑。

• 当 LinkedHashMap 作为散列表时，主要体现出 O(1) 时间复杂度的查询效率；
• 当 LinkedHashMap 作为双向链表时，主要体现出有序的特性。

LinkedHashMap 支持 2 种排序模式，这是通过构造器参数 accessOrder 标记位控制的，表示是否按照访问顺序排序，默认为 false 按照插入顺序。

• 插入顺序（默认）： 按照数据添加到 LinkedHashMap 的顺序排序，即 FIFO 策略；
• 访问顺序： 按照数据被访问（包括插入、更新、查询）的顺序排序，即 LRU 策略。

在有序性的基础上，LinkedHashMap 提供了维护了淘汰数据能力，并开放了淘汰判断的接口 removeEldestEntry()。

在每次添加数据时，会回调 removeEldestEntry() 接口，开发者可以重写这个接口决定是否移除最早的节点

与 HashMap 相同，LinkedHashMap 也不考虑线程同步，也会存在线程安全问题。

可以使用 Collections.synchronizedMap 包装类，其原理也是在所有方法上增加 synchronized 关键字。

2：和 HashMap 的区别

HashMap 和 LinkedHashMap 并不是平行的关系，而是继承的关系，LinkedHashMap 是继承于 HashMap 实现的哈希链表

两者主要的区别在于有序性： LinkedHashMap 会维护数据的插入顺序或访问顺序，而且封装了淘汰数据的能力。在迭代器遍历时，HashMap 会按照数组顺序遍历桶节点，从开发者的视角看是无序的。而是按照双向链表的顺序从 head 节点开始遍历，从开发者的视角是可以感知到的插入顺序或访问顺序。

三：HashMap预留的Hook点

LinkedHashMap 继承于 HashMap，在后者的基础上通过双向链表维护节点的插入顺序或访问顺序。

除此了这 3 个空方法外，LinkedHashMap 也重写了部分 HashMap 的方法，在其中插入双链表的维护逻辑，也相当于 Hook 点。

在 HashMap 的添加、获取、移除方法中，与 LinkedHashMap 有关的 Hook 点如下：

1：加方法中的 Hook 点

2：获取方法中的 Hook 点

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    // Hook：节点访问回调
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

public V getOrDefault(Object key, V defaultValue) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return defaultValue;
    // Hook：节点访问回调
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

3：移除方法中的 Hook 点

直接复用 HashMap 的移除方法，在移除节点后，增加 afterNodeRemoval() 回调

// 移除节点
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key)/*计算散列值*/, key, null, false, true)) == null ? null : e.value;
}

final Node<K,V> removeNode(int hash, Object key, Object value,
				boolean matchValue, boolean movable) {
    Node<K,V>[] tab; 
    Node<K,V> p; 
    int n, index;
    // (n - 1) & hash：散列值转数组下标
    if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        // 省略遍历桶的代码，具体分析见 HashMap 源码讲解
        // 删除 node 节点
        if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) {
            // 省略删除节点的代码，具体分析见 HashMap 源码讲解
            ++modCount;
            --size;
            // Hook：删除节点回调
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

四：源码分析

1：LinkedHashMap属性

LinkedHashMap 继承于 HashMap，并且新增 head 和 tail 指针指向链表的头尾节点（与 LinkedList 类似的头尾节点）

LinkedHashMap 的双链表节点 Entry 继承于 HashMap 的单链表节点 Node，而 HashMap 的红黑树节点 TreeNode 继承于 LinkedHashMap 的双链表节点 Entry

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {
    // 头指针
    transient LinkedHashMap.Entry<K,V> head;
    // 尾指针
    transient LinkedHashMap.Entry<K,V> tail;
    // 是否按照访问顺序排序
    final boolean accessOrder;

    // 双向链表节点
    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);
        }
    }
}

🙋🏻‍♀️疑问 1：HashMap.TreeNode 和 LinkedHashMap.Entry 的继承顺序是不是反了？

由于 Java 是单继承的，如果按照常规的做法让 HashMap.TreeNode 直接继承 HashMap.Node，那么在 LinkedHashMap 中就需要区分 LinkedHashMap.Entry 和 LinkedHashMap.TreeEntry，再使用接口统一两种类型。

2：LinkedHashMap构造方法

LinkedHashMap 有 5 个构造方法，作用与 HashMap 的构造方法基本一致，区别只在于对 accessOrder 字段的初始化。

// 带初始容量和装载因子的构造方法
public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}

// 带初始容量的构造方法
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}

// 无参构造方法
public LinkedHashMap() {
    super();
    accessOrder = false;
}

// 带 Map 的构造方法
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super();
    accessOrder = false;
    putMapEntries(m, false);
}

// 带初始容量、装载因子和 accessOrder 的构造方法
// 是否按照访问顺序排序，为 true 表示按照访问顺序排序，默认为 false
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

3：LinkedHashMap迭代器

与 HashMap 类似，LinkedHashMap 也提供了 3 个迭代器：

• LinkedEntryIterator： 键值对迭代器
• LinkedKeyIterator： 键迭代器
• LinkedValueIterator： 值迭代器

区别在于 LinkedHashMap 自己实现了 LinkedHashIterator。

在迭代器遍历时，HashMap 会按照数组顺序遍历桶节点，从开发者的视角看是无序的。

而 LinkedHashMap 是按照双向链表的顺序从 head 节点开始遍历，从开发者的视角是可以感知到的插入顺序或访问顺序。

abstract class LinkedHashIterator {
    LinkedHashMap.Entry<K,V> next;
    LinkedHashMap.Entry<K,V> current;
    // 修改计数
    int expectedModCount;

    LinkedHashIterator() {
        // 从头结点开始遍历 <--------------------- 此处为核心
        next = head;
        expectedModCount = modCount; // 修改计数
        current = null;
    }

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

    final LinkedHashMap.Entry<K,V> nextNode() {
        LinkedHashMap.Entry<K,V> e = next;
        // 检查修改计数
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (e == null)
            throw new NoSuchElementException();
        current = e;
        next = e.after; // 指向下一个节点
        return e;
    }
    ...
}

4：LinkedHashMap序列化过程

与 HashMap 相同，LinkedHashMap 也重写了 JDK 序列化的逻辑，并保留了 HashMap 中序列化的主体结构

LinkedHashMap 只是重写了 internalWriteEntries()，按照双向链表的顺序进行序列化，这样在反序列化时就能够恢复双向链表顺序

// ------------- HashMap ----------------
// 序列化过程
private void writeObject(java.io.ObjectOutputStream s) throws IOException {
    int buckets = capacity(); // 拿到桶容量
    s.defaultWriteObject();
    // 写入容量
    s.writeInt(buckets);
    // 写入有效元素个数
    s.writeInt(size);
    // 写入有效元素
    internalWriteEntries(s);
}

// 不关心键值对所在的桶，在反序列化会重新映射
void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
    Node<K,V>[] tab;
    if (size > 0 && (tab = table) != null) {
        for (int i = 0; i < tab.length; ++i) {
            for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                s.writeObject(e.key);
                s.writeObject(e.value);
            }
        }
    }
}

// Linked Hash Map
// 重写：按照双向链表顺序写入
void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
    // 从头到尾，顺序写入
    for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
        s.writeObject(e.key);
        s.writeObject(e.value);
    }
}

五：实现 LRU 缓存

• 首先，我们已经知道，LinkedHashMap 支持 2 种排序模式，这是通过构造器参数 accessOrder 标记位控制的。所以我们需要将 accessOrder 设置为 true 表示使用 LRU 模式的访问顺序排序。
• 其次，我们不需要实现淘汰数据的逻辑，只需要重写淘汰判断接口 removeEldestEntry()，当缓存数量大于缓存容量时返回 true，表示移除最早的节点。

public class MaxSizeLruCacheDemo extends LinkedHashMap {

    private int maxElements; // 定义一个最大数量

    // LRU缓存
    public LRUCache(int maxSize) {
        super(maxSize, 0.75F, true); // 调用LinkedHashMap，第三个参数将accessOrder => true，表示LRU方式访问
        maxElements = maxSize; // 设置最大值
    }

    /**
     * 重写淘汰判断接口, 当缓存数量大于缓存容量时返回 true，表示移除最早的节点
     */
    @Override
    protected boolean removeEldestEntry(java.util.Map.Entry eldest) {
        // 超出容量
        return size() > maxElements;
    }
}

六：总结

LRU 是一种缓存淘汰算法，与其他淘汰算法相比，LRU 算法利用了 “局部性原理”，缓存的平均命中率更高

使用双向链表 + 散列表实现的 LRU，在添加、查询、移除和淘汰数据的时间复杂度都是 O(1)，这种数据结构也叫哈希链表

• 查询数据： 通过散列表定位数据，时间复杂度为 O(1)；
• 淘汰数据： 直接淘汰链表尾节点，时间复杂度为 O(1)。

使用 LinkedHashMap 时，主要关注 2 个 API：

• accessOrder 标记位： LinkedHashMap 同时实现了 FIFO 和 LRU 两种淘汰策略，默认为 FIFO 排序，可以使用 accessOrder 标记位修改排序模式。
• removeEldestEntry() 接口： 每次添加数据时，LinkedHashMap 会回调 removeEldestEntry() 接口。
  • 开发者可以重写 removeEldestEntry() 接口决定是否移除最早的节点
  • 在 FIFO 策略中是最早添加的节点，在 LRU 策略中是最久未访问的节点。