如何使用 LinkedHashMap 实现 LRU 缓存？-阿里云开发者社区

本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 提问。

前言

大家好，我是小彭。

在上一篇文章里，我们聊到了 HashMap 的实现原理和源码分析，在源码分析的过程中，我们发现一些 LinkedHashMap 相关的源码，当时没有展开，现在它来了。

那么，LinkedHashMap 与 HashMap 有什么区别呢？其实，LinkedHashMap 的使用场景非常明确 —— LRU 缓存。今天，我们就来讨论 LinkedHashMap 是如何实现 LRU 缓存的。

本文源码基于 Java 8 LinkedHashMap。

思维导图：

1. 认识 LRU 缓存淘汰算法

1.1 什么是缓存淘汰算法？

缓存是提高数据读取性能的通用技术，在硬件和软件设计中被广泛使用，例如 CPU 缓存、Glide 内存缓存，数据库缓存等。由于缓存空间不可能无限大，当缓存容量占满时，就需要利用某种策略将部分数据换出缓存，这就是缓存的替换策略 / 淘汰问题。常见缓存淘汰策略有：

1、随机策略： 使用一个随机数生成器随机地选择要被淘汰的数据块；
2、FIFO 先进先出策略： 记录各个数据块的访问时间，最早访问的数据最先被淘汰；
3、LRU （Least Recently Used）最近最少策略： 记录各个数据块的访问 “时间戳” ，最近最久未使用的数据最先被淘汰。与前 2 种策略相比，LRU 策略平均缓存命中率更高，这是因为 LRU 策略利用了 “局部性原理”：最近被访问过的数据，将来被访问的几率较大，最近很久未访问的数据，将来访问的几率也较小；
4、LFU （Least Frequently Used）最不经常使用策略： 与 LRU 相比，LFU 更加注重使用的 “频率” 。LFU 会记录每个数据块的访问次数，最少访问次数的数据最先被淘汰。但是有些数据在开始时使用次数很高，以后不再使用，这些数据就会长时间污染缓存。可以定期将计数器右移一位，形成指数衰减。

FIFO 与 LRU 策略

1.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 的基础上增加更多队列，提供多个级别的缓冲。

小彭在 Redis 和 Vue 中有看到这些 LRU 变型的应用，在 Android 领域的框架中还没有看到具体应用，你知道的话可以提醒我。

1.3 如何实现 LRU 缓存淘汰算法？

这一小节，我们尝试找到 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 这种数据结构就叫 “哈希链表或链式哈希表”，我更倾向于称为哈希链表，因为当这两个数据结构相结合时，我们更看重的是它作为链表的排序能力。

我们今天要讨论的 Java LinkedHashMap 就是基于哈希链表的数据结构。

2. 认识 LinkedHashMap 哈希链表

2.1 说一下 LinkedHashMap 的特点

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

1、LinkedHashMap 是继承于 HashMap 实现的哈希链表，它同时具备双向链表和散列表的特点。事实上，LinkedHashMap 继承了 HashMap 的主要功能，并通过 HashMap 预留的 Hook 点维护双向链表的逻辑。
- 1.1 当 LinkedHashMap 作为散列表时，主要体现出 O(1) 时间复杂度的查询效率；
- 1.2 当 LinkedHashMap 作为双向链表时，主要体现出有序的特性。
2、LinkedHashMap 支持 2 种排序模式，这是通过构造器参数 accessOrder 标记位控制的，表示是否按照访问顺序排序，默认为 false 按照插入顺序。
- 2.1 插入顺序（默认）： 按照数据添加到 LinkedHashMap 的顺序排序，即 FIFO 策略；
- 2.2 访问顺序： 按照数据被访问（包括插入、更新、查询）的顺序排序，即 LRU 策略。
3、在有序性的基础上，LinkedHashMap 提供了维护了淘汰数据能力，并开放了淘汰判断的接口 removeEldestEntry()。在每次添加数据时，会回调 removeEldestEntry() 接口，开发者可以重写这个接口决定是否移除最早的节点（在 FIFO 策略中是最早添加的节点，在 LRU 策略中是最早未访问的节点）；
4、与 HashMap 相同，LinkedHashMap 也不考虑线程同步，也会存在线程安全问题。可以使用 Collections.synchronizedMap 包装类，其原理也是在所有方法上增加 synchronized 关键字。

2.2 说一下 HashMap 和 LinkedHashMap 的区别？

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

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

LinkedHashMap 示意图

3. HashMap 预留的 Hook 点

LinkedHashMap 继承于 HashMap，在后者的基础上通过双向链表维护节点的插入顺序或访问顺序。因此，我们先回顾下 HashMap 为 LinkedHashMap 预留的 Hook 点：

afterNodeAccess： 在节点被访问时回调；
afterNodeInsertion： 在节点被插入时回调，其中有参数 evict 标记是否淘汰最早的节点。在初始化、反序列化或克隆等构造过程中，evict 默认为 false，表示在构造过程中不淘汰。
afterNodeRemoval： 在节点被移除时回调。

HashMap.java

// 节点访问回调
void afterNodeAccess(Node<K,V> p) { }
// 节点插入回调
// evict：是否淘汰最早的节点
void afterNodeInsertion(boolean evict) { }
// 节点移除回调
void afterNodeRemoval(Node<K,V> p) { }

除此了这 3 个空方法外，LinkedHashMap 也重写了部分 HashMap 的方法，在其中插入双链表的维护逻辑，也相当于 Hook 点。在 HashMap 的添加、获取、移除方法中，与 LinkedHashMap 有关的 Hook 点如下：

3.1 HashMap 的添加方法中的 Hook 点

LinkedHashMap 直接复用 HashMap 的添加方法，也支持批量添加：

HashMap#put： 逐个添加或更新键值对；
HashMap#putAll： 批量添加或更新键值对。

不管是逐个添加还是批量添加，最终都会先通过 hash 函数计算键（Key）的散列值，再通过 HashMap#putVal 添加或更新键值对，这些都是 HashMap 的行为。关键的地方在于：LinkedHashMap 在 HashMap#putVal 的 Hook 点中加入了双线链表的逻辑。区分 2 种情况：

添加数据： 如果数据不存在散列表中，则调用 newNode() 或 newTreeNode() 创建节点，并回调 afterNodeInsertion()；
更新数据： 如果数据存在散列表中，则更新 Value，并回调 afterNodeAccess()。

HashMap.java

// 添加或更新键值对
public V put(K key, V value) {
    return putVal(hash(key) /*计算散列值*/, key, value, false, true);
}

// hash：Key 的散列值（经过扰动）
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; 
    Node<K,V> p; 
    int n;
    int i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // (n - 1) & hash：散列值转数组下标
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 省略遍历桶的代码，具体分析见 HashMap 源码讲解

        // 1.1 如果节点不存在，则新增节点
        p.next = newNode(hash, key, value, null);
        // 2.1 如果节点存在更新节点 Value
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            // 2.2 Hook：访问节点回调
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 扩容
    if (++size > threshold)
        resize();
    // 1.2 Hook：新增节点回调
    afterNodeInsertion(evict);
    return null;
}

HashMap#put 示意图

3.2 HashMap 的获取方法中的 Hook 点

LinkedHashMap 重写了 HashMap#get 方法，在 HashMap 版本的基础上，增加了 afterNodeAccess() 回调。

HashMap.java

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

LinkedHashMap.java

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

HashMap#get 示意图

3.3 HashMap 的移除方法中的 Hook 点

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

HashMap.java

// 移除节点
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;
}

HashMap#remove 示意图

4. LinkedHashMap 源码分析

这一节，我们来分析 LinkedHashMap 中主要流程的源码。

4.1 LinkedHashMap 的属性

LinkedHashMap 继承于 HashMap，并且新增 head 和 tail 指针指向链表的头尾节点（与 LinkedList 类似的头尾节点）；
LinkedHashMap 的双链表节点 Entry 继承于 HashMap 的单链表节点 Node，而 HashMap 的红黑树节点 TreeNode 继承于 LinkedHashMap 的双链表节点 Entry。

节点继承关系

LinkedHashMap.java

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

LinkedList.java

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
    // 头指针（// LinkedList 中也有类似的头尾节点）
    transient Node<E> first;
    // 尾指针
    transient Node<E> last;

    // 双向链表节点
    private static class Node<E> {
        // 节点数据
        // （类型擦除后：Object item;）
        E item;
        // 前驱指针
        Node<E> next;
        // 后继指针
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
}

LinkedHashMap 的属性很好理解的，不出意外的话又有小朋友出来举手提问了：

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

我的理解是作者希望简化节点类型，所以采用了非常规的做法（不愧是标准库）。由于 Java 是单继承的，如果按照常规的做法让 HashMap.TreeNode 直接继承 HashMap.Node，那么在 LinkedHashMap 中就需要区分 LinkedHashMap.Entry 和 LinkedHashMap.TreeEntry，再使用接口统一两种类型。

常规实现

4.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;
}

4.3 LinkedHashMap 如何维护双链表

现在，我们看下 LinkedHashMap 是如何维护双链表的。其实，我们将上一节所有的 Hook 点汇总，会发现这些 Hook 点正好组成了 LinkedHashMap 双向链表的行为：

添加数据： 将数据链接到双向链表的尾节点，时间复杂度为 O(1)；
访问数据（包括添加、查询、更新）： 将数据移动到双向链表的尾节点，亦相当于先移除再添加到尾节点，时间复杂度为 O(1)；
删除数据： 将数据从双向链表中移除，时间复杂度为 O(1)；
淘汰数据： 直接淘汰双向链表的头节点，时间复杂度为 O(1)。

LinkedHashMap.java

// -> 1.1 如果节点不存在，则新增节点
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    // 新建双向链表节点
    LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    // 添加到双向链表尾部，等价于 LinkedList#linkLast
    linkNodeLast(p);
    return p;
}

// -> 1.1 如果节点不存在，则新增节点
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);
    // 添加到双向链表尾部，等价于 LinkedList#linkLast
    linkNodeLast(p);
    return p;
}

// 添加到双向链表尾部，等价于 LinkedList#linkLast
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        // last 为 null 说明首个添加的元素，需要修改 first 指针
        head = p;
    else {
        // 将新节点的前驱指针指向 last 
        p.before = last;
        // 将 last 的 next 指针指向新节点
        last.after = p;
    }
}

// 节点插入回调
// evict：是否淘汰最早的节点
void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    // removeEldestEntry：是否淘汰最早的节点，即是否淘汰头节点（由子类实现）
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        // 移除 first 节点，腾出缓存空间
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

// 移除节点回调
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 指针
        head = a;
    else
        // 修正前驱节点的后继指针，指向被删除节点的后继节点
        b.after = a;
    if (a == null)
        // 删除的是尾节点，则修正 tail 指针
        tail = b;
    else
        // 修正后继节点的前驱指针，指向被删除节点的前驱节点
        a.before = b;
}

// 节点访问回调
void afterNodeAccess(Node<K,V> e) { // move node to last
    // 先将节点 e 移除，再添加到链表尾部
    LinkedHashMap.Entry<K,V> last;
    // accessOrder：是否按照访问顺序排序，为 false 则保留插入顺序
    if (accessOrder && (last = tail) != e) {
        // 这两个 if 语句块就是 afterNodeRemoval 的逻辑
        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 (a != null)
            a.before = b;
        else
            last = b;
        // 这个 if 语句块就是 linkNodeLast 的逻辑
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

// 淘汰判断接口，由子类实现
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

4.4 LinkedHashMap 的迭代器

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

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

区别在于 LinkedHashMap 自己实现了 LinkedHashIterator。在迭代器遍历时，HashMap 会按照数组顺序遍历桶节点，从开发者的视角看是无序的。而 LinkedHashMap 是按照双向链表的顺序从 head 节点开始遍历，从开发者的视角是可以感知到的插入顺序或访问顺序。

LinkedHashMap.java

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.5 LinkedHashMap 的序列化过程

与 HashMap 相同，LinkedHashMap 也重写了 JDK 序列化的逻辑，并保留了 HashMap 中序列化的主体结构。LinkedHashMap 只是重写了 internalWriteEntries()，按照双向链表的顺序进行序列化，这样在反序列化时就能够恢复双向链表顺序。

HashMap.java

// 序列化过程
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);
            }
        }
    }
}

LinkedHashMap.java

// 重写：按照双向链表顺序写入
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);
    }
}

5. 基于 LinkedHashMap 实现 LRU 缓存

这一节，我们来实现一个简单的 LRU 缓存。理解了 LinkedHashMap 维护插入顺序和访问顺序的原理后，相信你已经知道如何实现 LRU 缓存了。

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

MaxSizeLruCacheDemo.java

public class MaxSizeLruCacheDemo extends LinkedHashMap {

    private int maxElements;

    public LRUCache(int maxSize) {
        super(maxSize, 0.75F, true);
        maxElements = maxSize;
    }

    protected boolean removeEldestEntry(java.util.Map.Entry eldest) {
        // 超出容量
        return size() > maxElements;
    }
}

6. 总结

1、LRU 是一种缓存淘汰算法，与其他淘汰算法相比，LRU 算法利用了 “局部性原理”，缓存的平均命中率更高；
2、使用双向链表 + 散列表实现的 LRU，在添加、查询、移除和淘汰数据的时间复杂度都是 O(1)，这种数据结构也叫哈希链表；
- 查询数据： 通过散列表定位数据，时间复杂度为 O(1)；
- 淘汰数据： 直接淘汰链表尾节点，时间复杂度为 O(1)。
3、使用 LinkedHashMap 时，主要关注 2 个 API：
- accessOrder 标记位： LinkedHashMap 同时实现了 FIFO 和 LRU 两种淘汰策略，默认为 FIFO 排序，可以使用 accessOrder 标记位修改排序模式。
- removeEldestEntry() 接口： 每次添加数据时，LinkedHashMap 会回调 removeEldestEntry() 接口。开发者可以重写 removeEldestEntry() 接口决定是否移除最早的节点（在 FIFO 策略中是最早添加的节点，在 LRU 策略中是最久未访问的节点）。
4、Android 的 LruCache 内存缓存和 DiskLruCache 磁盘缓存中，都直接复用了 LinkedHashMap 的 LRU 能力。

今天，我们分析了 LinkedHashMap 的实现原理。在下篇文章里，我们来分析 LRU 的具体实现应用，例如 Android 标准库中的 LruCache 内存缓存。

可以思考一个问题，LinkedHashMap 是非线程安全的，Android 的 LruCache 是如何解决线程安全问题的？请关注小彭说 · Android 开源组件专栏。

参考资料

数据结构与算法分析 · Java 语言描述（第 5 章 · 散列）—— [美] Mark Allen Weiss 著
算法导论（第 11 章 · 散列表）—— [美] Thomas H. Cormen 等著
数据结构与算法之美（第 6、18~22 讲） —— 王争著，极客时间出品
LinkedHashMap 源码详细分析（JDK1.8）—— 田小波著
LRU 算法及其优化策略——算法篇 —— 豆豉辣椒炒腊肉著
缓冲池(buffer pool)，这次彻底懂了！ —— 58 沈剑著
LeetCode 146. LRU 缓存 —— LeetCode
Cache replacement policies —— Wikipedia

如何使用 LinkedHashMap 实现 LRU 缓存？

前言

1. 认识 LRU 缓存淘汰算法

1.1 什么是缓存淘汰算法？

1.2 向外看：LRU 的变型

1.3 如何实现 LRU 缓存淘汰算法？

2. 认识 LinkedHashMap 哈希链表

2.1 说一下 LinkedHashMap 的特点

2.2 说一下 HashMap 和 LinkedHashMap 的区别？

3. HashMap 预留的 Hook 点

3.1 HashMap 的添加方法中的 Hook 点

3.2 HashMap 的获取方法中的 Hook 点

3.3 HashMap 的移除方法中的 Hook 点

4. LinkedHashMap 源码分析

4.1 LinkedHashMap 的属性

4.2 LinkedHashMap 的构造方法

4.3 LinkedHashMap 如何维护双链表

4.4 LinkedHashMap 的迭代器

4.5 LinkedHashMap 的序列化过程

5. 基于 LinkedHashMap 实现 LRU 缓存

6. 总结

参考资料

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

如何使用 LinkedHashMap 实现 LRU 缓存？

前言

1. 认识 LRU 缓存淘汰算法

1.1 什么是缓存淘汰算法？

1.2 向外看：LRU 的变型

1.3 如何实现 LRU 缓存淘汰算法？

2. 认识 LinkedHashMap 哈希链表

2.1 说一下 LinkedHashMap 的特点

2.2 说一下 HashMap 和 LinkedHashMap 的区别？

3. HashMap 预留的 Hook 点

3.1 HashMap 的添加方法中的 Hook 点

3.2 HashMap 的获取方法中的 Hook 点

3.3 HashMap 的移除方法中的 Hook 点

4. LinkedHashMap 源码分析

4.1 LinkedHashMap 的属性

4.2 LinkedHashMap 的构造方法

4.3 LinkedHashMap 如何维护双链表

4.4 LinkedHashMap 的迭代器

4.5 LinkedHashMap 的序列化过程

5. 基于 LinkedHashMap 实现 LRU 缓存

6. 总结

参考资料

热门文章

最新文章

相关电子书