LinkedHashMap原理详解—从LRU缓存机制说起
写在前面从一道Leetcode标题说起
起首，来看一下Leetcode里面的一道经典标题：146.LRU缓存机制，标题形貌如下：
请你计划并实现一个满足 LRU (最近最少使用) 缓存 束缚的数据结构。
实现 LRUCache 类：
[*]LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
[*]int get(int key) 假如关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
[*]void put(int key, int value) 假如关键字 key 已经存在，则变动其数据值 value ；假如不存在，则向缓存中插入该组 key-value 。假如插入操作导致关键字数量凌驾 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
LRU 的全称是 Least Recently Used，也就是说我们认为最近使用过的数据应该是是「有用的」，好久都没用过的数据应该是无用的，内存满了就优先删那些好久没用过的数据。
分析
要让 LRU 的 put 和 get 方法的时间复杂度为 O(1)，可以总结出 LRU 这个数据结构必要的条件：
[*]显然LRU中的元素必须有时序，以区分最近使用的和久未使用的数据，当容量满了之后要删除最久未使用的那个元素腾位置。
[*]要在LRU 中快速找某个 key 是否已存在并得到对应的 val；
[*]每次访问LRU中的某个 key，必要将这个元素变为最近使用的，也就是说LRU要支持在恣意位置快速插入和删除元素。
那么，什么数据结构同时符合上述条件呢？哈希表查找快，但是数据无固定顺序；链表有顺序之分，插入删除快，但是查找慢。所以结合一下，形成一种新的数据结构：哈希链表 LinkedHashMap。
LRU 缓存算法的核心数据结构就是哈希链表，双向链表和哈希表的结合体。这个数据结构长这样：
https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202409081809746.png
借助这个结构，逐一分析上面的 3 个条件：
[*]假如我们每次默认从链表尾部添加元素，那么显然越靠尾部的元素就是最近使用的，越靠头部的元素就是最久未使用的。
[*]对于某一个 key，我们可以通过哈希表快速定位到链表中的节点，从而取得对应 val。
[*]链表显然是支持在恣意位置快速插入和删除的，改改指针就行。只不过传统的链表无法按照索引快速访问某一个位置的元素，而这里借助哈希表，可以通过 key 快速映射到恣意一个链表节点，然后举行插入和删除。
put方法流程图：
https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202409081810983.png
代码实现
class LRUCache {
int cap;
LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();
public LRUCache(int capacity) {
this.cap = capacity;
}
public int get(int key) {
if (!cache.containsKey(key)) {
return -1;
}
// 将 key 变为最近使用
makeRecently(key);
return cache.get(key);
}
public void put(int key, int val) {
if (cache.containsKey(key)) {
// 修改 key 的值
cache.put(key, val);
// 将 key 变为最近使用
makeRecently(key);
return;
}
if (cache.size() >= this.cap) {
// 链表头部就是最久未使用的 key
int oldestKey = cache.keySet().iterator().next();
cache.remove(oldestKey);
}
// 将新的 key 添加链表尾部
cache.put(key, val);
}
private void makeRecently(int key) {
int val = cache.get(key);
// 删除 key，重新插入到队尾
cache.remove(key);
cache.put(key, val);
}
}LinkedHashMap介绍
LinkedHashSet和LinkedHashMap实在也是一回事。LinkedHashSet和LinkedHashMap在Java里也有着雷同的实现，前者仅仅是对后者做了一层包装，也就是说LinkedHashSet里面有一个LinkedHashMap(适配器模式)。
LinkedHashMap实现了Map接口，即允许放入key为null的元素，也允许插入value为null的元素。从名字上可以看出该容器是linked list和HashMap的混合体，也就是说它同时满足HashMap和linked list的某些特性。可将LinkedHashMap看作采用linked list增强的HashMap。
https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202404250918723.jpg
事实上LinkedHashMap是HashMap的直接子类，二者唯一的区别是LinkedHashMap在HashMap的基础上，采用双向链表(doubly-linked list)的情势将全部entry连接起来，这样的好处：
[*]可以保证元素的迭代顺序跟插入顺序雷同。跟HashMap相比，多了header指向双向链表的头部(是一个哑元)，该双向链表的迭代顺序就是entry的插入顺序。
[*]迭代LinkedHashMap时不必要像HashMap那样遍历整个table，而只必要直接遍历header指向的双向链表即可，也就是说LinkedHashMap的迭代时间就只跟entry的个数相关，而跟table的大小无关。
有两个参数可以影响LinkedHashMap的性能：初始容量(inital capacity)和负载系数(load factor)。初始容量指定了初始table的大小，负载系数用来指定自动扩容的临界值。当entry的数量凌驾capacity*load_factor时，容器将自动扩容并重新哈希。对于插入元素较多的场景，将初始容量设大可以淘汰重新哈希的次数。这点与HashMap是一样的
方法分析
get()
get(Object key)方法根据指定的key值返回对应的value。该方法跟HashMap.get()方法的流程几乎完全一样
put()
put(K key, V value)方法是将指定的key, value对添加到map里。该方法起首会对map做一次查找，看是否包含该元组，假如已经包含则直接返回，查找过程类似于get()方法；假如没有找到，则会通过addEntry(int hash, K key, V value, int bucketIndex)方法插入新的entry。
注意，这里的插入有两重含义:
[*]从table的角度看，新的entry必要插入到对应的bucket里，当有哈希冲突时，采用头插法将新的entry插入到冲突链表的头部。
[*]从header的角度看，新的entry必要插入到双向链表的尾部。
https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202404250918720.jpg
addEntry()代码如下:
// LinkedHashMap.addEntry()
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table)) {
resize(2 * table.length);// 自动扩容，并重新哈希
hash = (null != key) ? hash(key) : 0;
bucketIndex = hash & (table.length-1);// hash%table.length
}
// 1.在冲突链表头部插入新的entry
HashMap.Entry<K,V> old = table;
Entry<K,V> e = new Entry<>(hash, key, value, old);
table = e;
// 2.在双向链表的尾部插入新的entry
e.addBefore(header);
size++;
}上述代码中用到了addBefore()方法将新entry e插入到双向链表头引用header的前面，这样e就成为双向链表中的最后一个元素。addBefore()的代码如下:
// LinkedHashMap.Entry.addBefor()，将this插入到existingEntry的前面
private void addBefore(Entry<K,V> existingEntry) {
after= existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}remove()
remove(Object key)的作用是删除key值对应的entry，该方法的具体逻辑是在removeEntryForKey(Object key)里实现的。removeEntryForKey()方法会起首找到key值对应的entry，然后删除该entry(修改链表的相应引用)。查找过程跟get()方法类似。
注意，这里的删除也有两重含义:
[*]从table的角度看，必要将该entry从对应的bucket里删除，假如对应的冲突链表不空，必要修改冲突链表的相应引用。
[*]从header的角度来看，必要将该entry从双向链表中删除，同时修改链表中前面以及后面元素的相应引用。
https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202404250918717.jpg
removeEntryForKey()对应的代码如下:
// LinkedHashMap.removeEntryForKey()，删除key值对应的entry
final Entry<K,V> removeEntryForKey(Object key) {
......
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);// hash&(table.length-1)
Entry<K,V> prev = table;// 得到冲突链表
Entry<K,V> e = prev;
while (e != null) {// 遍历冲突链表
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {// 找到要删除的entry
modCount++; size--;
// 1. 将e从对应bucket的冲突链表中删除
if (prev == e) table = next;
else prev.next = next;
// 2. 将e从双向链表中删除
e.before.after = e.after;
e.after.before = e.before;
return e;
}
prev = e; e = next;
}
return e;
}LinkedHashSet
LinkedHashSet是对LinkedHashMap的简单包装，对LinkedHashSet的函数调用都会转换成符合的LinkedHashMap方法，因此LinkedHashSet的实现非常简单
public class LinkedHashSet<E>
extends HashSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
......
// LinkedHashSet里面有一个LinkedHashMap
public LinkedHashSet(int initialCapacity, float loadFactor) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
......
public boolean add(E e) {//简单的方法转换
return map.put(e, PRESENT)==null;
}
......
}关于作者
来自一线程序员Seven的探索与实践，持续学习迭代中~
本文已收录于我的个人博客：https://www.seven97.top
公众号：seven97，接待关注~
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]