如何使用 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 开源组件专栏。

版权声明

本文为稀土技能社区首发签约文章，14天内制止转载，14天后未获授权制止转载，侵权必究！

参考资料

数据结构与算法剖析 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. 总结

版权声明

参考资料

相关文章

Hadoop YARN Cgroups 资源隔离讲解

Spring Boot项目如何实现分布式日志链路追踪

语言篇|现代C记录—简略篇

掌握C++ copy-and-swap 语义

作者信息