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

前语

大家好,我是小彭。

在上一篇文章里,咱们聊到了 HashMap 的完成原理和源码剖析,在源码剖析的进程中,咱们发现一些 LinkedHashMap 相关的源码,当时没有打开,现在它来了。

那么,LinkedHashMap 与 HashMap 有什么差异呢?其实,LinkedHashMap 的运用场景十分明确 —— LRU 缓存。今日,咱们就来讨论 LinkedHashMap 是怎么完成 LRU 缓存的。

本文源码根据 Java 8 LinkedHashMap。


思维导图:

如何使用 LinkedHashMap 实现 LRU 缓存?


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 战略

如何使用 LinkedHashMap 实现 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 示意图

如何使用 LinkedHashMap 实现 LRU 缓存?


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 示意图

如何使用 LinkedHashMap 实现 LRU 缓存?

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 示意图

如何使用 LinkedHashMap 实现 LRU 缓存?

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 示意图

如何使用 LinkedHashMap 实现 LRU 缓存?


4. LinkedHashMap 源码剖析

这一节,咱们来剖析 LinkedHashMap 中首要流程的源码。

4.1 LinkedHashMap 的特点

  • LinkedHashMap 承继于 HashMap,而且新增 headtail 指针指向链表的头尾节点(与 LinkedList 相似的头尾节点);
  • LinkedHashMap 的双链表节点 Entry 承继于 HashMap 的单链表节点 Node,而 HashMap 的红黑树节点 TreeNode 承继于 LinkedHashMap 的双链表节点 Entry。

节点承继联系

如何使用 LinkedHashMap 实现 LRU 缓存?

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,再运用接口统一两种类型。

惯例完成

如何使用 LinkedHashMap 实现 LRU 缓存?

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 缓存?