大家好,我是小彭。
[在上一篇文章里],我们聊到了 HashMap 的实现原理和源码分析,在源码分析的过程中,我们发现一些 LinkedHashMap 相关的源码,当时没有展开,现在它来了。
那么,LinkedHashMap 与 HashMap 有什么区别呢?其实,LinkedHashMap 的使用场景非常明确 —— LRU 缓存。今天,我们就来讨论 LinkedHashMap 是如何实现 LRU 缓存的。
本文源码基于 Java 8 LinkedHashMap。
思维导图:
缓存是提高数据读取性能的通用技术,在硬件和软件设计中被广泛使用,例如 [CPU 缓存]、Glide 内存缓存,数据库缓存等。由于缓存空间不可能无限大,当缓存容量占满时,就需要利用某种策略将部分数据换出缓存,这就是缓存的替换策略 / 淘汰问题。常见缓存淘汰策略有:
1、随机策略: 使用一个随机数生成器随机地选择要被淘汰的数据块;
2、FIFO 先进先出策略: 记录各个数据块的访问时间,最早访问的数据最先被淘汰;
3、LRU (Least Recently Used)最近最少策略: 记录各个数据块的访问 “时间戳” ,最近最久未使用的数据最先被淘汰。与前 2 种策略相比,LRU 策略平均缓存命中率更高,这是因为 LRU 策略利用了 “局部性原理”:最近被访问过的数据,将来被访问的几率较大,最近很久未访问的数据,将来访问的几率也较小;
4、LFU (Least Frequently Used)最不经常使用策略: 与 LRU 相比,LFU 更加注重使用的 “频率” 。LFU 会记录每个数据块的访问次数,最少访问次数的数据最先被淘汰。但是有些数据在开始时使用次数很高,以后不再使用,这些数据就会长时间污染缓存。可以定期将计数器右移一位,形成指数衰减。
FIFO 与 LRU 策略
其实,在标准的 LRU 算法上还有一些变型实现,这是因为 LRU 算法本身也存在一些不足。例如,当数据中热点数据较多时,LRU 能够保证较高的命中率。但是当有偶发的批量的非热点数据产生时,就会将热点数据寄出缓存,使得缓存被污染。因此,LRU 也有一些变型:
小彭在 Redis 和 Vue 中有看到这些 LRU 变型的应用,在 Android 领域的框架中还没有看到具体应用,你知道的话可以提醒我。
这一小节,我们尝试找到 LRU 缓存淘汰算法的实现方案。经过总结,我们可以定义一个缓存系统的基本操作:
我们发现,前 3 个操作都有 “查询” 操作, 所以缓存系统的性能主要取决于查找数据和淘汰数据是否高效。 下面,我们用递推的思路推导 LRU 缓存的实现方案,主要分为 3 种方案:
方案 1 - 基于时间戳的数组: 在每个数据块中记录最近访问的时间戳,当数据被访问(添加、更新或查询)时,将数据的时间戳更新到当前时间。当数组空间已满时,则扫描数组淘汰时间戳最小的数据。
方案 2 - 基于双向链表: 不再直接维护时间戳,而是利用链表的顺序隐式维护时间戳的先后顺序。当数据被访问(添加、更新或查询)时,将数据插入到链表头部。当空间已满时,直接淘汰链表的尾节点。
方案 3 - 基于双向链表 + 散列表: 使用双向链表可以将淘汰数据的时间复杂度降低为 O(1),但是查询数据的时间复杂度还是 O(n),我们可以在双向链表的基础上增加散列表,将查询操作的时间复杂度降低为 O(1)。
方案 3 这种数据结构就叫 “哈希链表或链式哈希表”,我更倾向于称为哈希链表,因为当这两个数据结构相结合时,我们更看重的是它作为链表的排序能力。
我们今天要讨论的 Java LinkedHashMap 就是基于哈希链表的数据结构。
需要注意:LinkedHashMap 中的 “Linked” 实际上是指双向链表,并不是指解决散列冲突中的分离链表法。
1、LinkedHashMap 是继承于 HashMap 实现的哈希链表,它同时具备双向链表和散列表的特点。事实上,LinkedHashMap 继承了 HashMap 的主要功能,并通过 HashMap 预留的 Hook 点维护双向链表的逻辑。
2、LinkedHashMap 支持 2 种排序模式,这是通过构造器参数 accessOrder
标记位控制的,表示是否按照访问顺序排序,默认为 false 按照插入顺序。
3、在有序性的基础上,LinkedHashMap 提供了维护了淘汰数据能力,并开放了淘汰判断的接口 removeEldestEntry()
。在每次添加数据时,会回调 removeEldestEntry()
接口,开发者可以重写这个接口决定是否移除最早的节点(在 FIFO 策略中是最早添加的节点,在 LRU 策略中是最早未访问的节点);
4、与 HashMap 相同,LinkedHashMap 也不考虑线程同步,也会存在线程安全问题。可以使用 Collections.synchronizedMap 包装类,其原理也是在所有方法上增加 synchronized 关键字。
事实上,HashMap 和 LinkedHashMap 并不是平行的关系,而是继承的关系,LinkedHashMap 是继承于 HashMap 实现的哈希链表。
两者主要的区别在于有序性: LinkedHashMap 会维护数据的插入顺序或访问顺序,而且封装了淘汰数据的能力。在迭代器遍历时,HashMap 会按照数组顺序遍历桶节点,从开发者的视角看是无序的。而是按照双向链表的顺序从 head 节点开始遍历,从开发者的视角是可以感知到的插入顺序或访问顺序。
LinkedHashMap 示意图
LinkedHashMap 继承于 HashMap,在后者的基础上通过双向链表维护节点的插入顺序或访问顺序。因此,我们先回顾下 HashMap 为 LinkedHashMap 预留的 Hook 点:
evict
标记是否淘汰最早的节点。在初始化、反序列化或克隆等构造过程中,evict
默认为 false,表示在构造过程中不淘汰。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 点如下:
LinkedHashMap 直接复用 HashMap 的添加方法,也支持批量添加:
不管是逐个添加还是批量添加,最终都会先通过 hash 函数计算键(Key)的散列值,再通过 HashMap#putVal
添加或更新键值对,这些都是 HashMap 的行为。关键的地方在于:LinkedHashMap 在 HashMap#putVal
的 Hook 点中加入了双线链表的逻辑。区分 2 种情况:
newNode()
或 newTreeNode()
创建节点,并回调 afterNodeInsertion()
;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 重写了 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 直接复用 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 中主要流程的源码。
head
和 tail
指针指向链表的头尾节点(与 LinkedList 类似的头尾节点);节点继承关系
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 的属性很好理解的,不出意外的话又有小朋友出来举手提问了:
我的理解是作者希望简化节点类型,所以采用了非常规的做法(不愧是标准库)。由于 Java 是单继承的,如果按照常规的做法让 HashMap.TreeNode 直接继承 HashMap.Node,那么在 LinkedHashMap 中就需要区分 LinkedHashMap.Entry 和 LinkedHashMap.TreeEntry,再使用接口统一两种类型。
常规实现
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; }
现在,我们看下 LinkedHashMap 是如何维护双链表的。其实,我们将上一节所有的 Hook 点汇总,会发现这些 Hook 点正好组成了 LinkedHashMap 双向链表的行为:
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; }
与 HashMap 类似,LinkedHashMap 也提供了 3 个迭代器:
区别在于 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; } ... }
与 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); } }
这一节,我们来实现一个简单的 LRU 缓存。理解了 LinkedHashMap 维护插入顺序和访问顺序的原理后,相信你已经知道如何实现 LRU 缓存了。
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; } }
1、LRU 是一种缓存淘汰算法,与其他淘汰算法相比,LRU 算法利用了 “局部性原理”,缓存的平均命中率更高;
2、使用双向链表 + 散列表实现的 LRU,在添加、查询、移除和淘汰数据的时间复杂度都是 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 内存缓存。