关于android:如何使用-LinkedHashMap-实现-LRU-缓存

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

大家好，我是小彭。

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

那么，LinkedHashMap 与 HashMap 有什么区别呢？其实，LinkedHashMap 的应用场景十分明确 —— LRU 缓存。明天，咱们就来探讨 LinkedHashMap 是如何实现 LRU 缓存的。

本文源码基于 Java 8 LinkedHashMap。

小彭的 Android 交换群 02 群曾经建设啦，扫描文末二维码进入~

思维导图：

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

小彭的 Android 交换群 02 群