19.LRU Cache的实现、应用和题解
Cache缓存
我们先来认识一下cache以及cache在现实中的应用，cache的话就叫做缓存，比如之前文章提到过的 Fibonacci数列以及爬楼梯问题，解这些题就需要做一个所谓的记忆化搜索，其实我们就建列一个cache，你可以用数组来表示，Python可以直接用@LRU Cache 来写。那么缓存到底是什么呢？在现实中其实应用很多。
- 记忆
- 钱包 - 储物柜
- 代码模块
比如说我们人类的记忆，其实很多时候就是一个缓存，很多东西我们会记在纸上，写在书籍里面，因为我们怕我们记不住，好处就是说书上那些东西永远会存在，但是它问题就在于你要把它载入到你的脑子里面来，需要花不少的时间，经常用的东西肯就记者我们脑子里面，它的速度就特别快，但是问题就是说经常会有误或者是说会遗忘，这就是人脑记忆所做成一个缓存的问题。
Cache本身的话，从CPU里面的话就讲来很多了，就比如说我们刚接触计算的时候对硬件比较感兴趣，当时特别出名的就是英特尔的处理器。
它当时就 L1 的 cache，L2 的 cache，L3 的 cache，它就有吧所谓的三级缓存。
Understanding the Meltdown exploit – in my own simple words
在这里它是四核的一个CPU，每一个核里面就有 L1 D-Cache、L1 l-Cache、L2 Cache、L3 Cache，指的是最常用的数据，马上要给CPU的计算模块进行计算处理的，就放在L1里面，另外的话更多一点的淘汰下来，次之不太常用的就放在 L1 l-Cache，再次之就放在 L2 Cache里面，最后的话放在 L3 Cache里面，当然外面的话就是内存，它的速度的话一个比一个快，但是它的体积也就是能存的数据的多少，肯定是L3 Cache是最大的，L1 D-Cache是最小的。这就是它所谓的缓存机制。
LRU Cache
那么说到缓存的话，它的基本特性主要有两点：
两个要素：大小、替换策略
- 第一点的话就是缓存总体的大小是多少？如果缓存非常大的话就类似于CPU的缓存抵一个内存，有1G的缓存的话，那么很多东西就只管往里面存就行了。对于人的话就是这个人的记性特别好。
- 第二个的话它的替换策略，也就是说我 L1 最快的，但是因为容量有限不够装了，那么我们要把哪一些不常用的把它放在后面来，以及我们怎么鉴别哪些信息是不常用的，这就是要得到所谓的替换算法了。
Hash Table + Double LinkedList
那么基于LRU Cache的话，它的替换算法就是 LRU 这三个字代表着它的含义，那么指的是 least recent use，指的是最近最少使用的就把它昂在最后去淘汰它一般来说，它的实现最后的话是用哈希表再加一个双向链表来实现，这样的的一个结构会是O(1)的查询时间复杂度，也就是说这个元素到底是否存在，直接可以在哈希表里面O(1)的时间可以查到，同时的话你要进行修改和更新的话，具体存元素是存在Double LinkedList里面去，也可以用O(1)的时间去进行修改和更新。
- O(1)查询
- O(1)修改、更新
LRU Cache 工作示例
这个是 LRU Cache，就是这么一段内存放在这个地方，当然它底层的数据结构，就是前面所说的一个双向链表，当然还要配一个哈希表在这个地方。上图就是整个 LRU Cache它的更新原则，那么LRU的话指的是 least recently used 就是最近最少被使用的元素就被淘汰出去。
替换策略
- LFU - least frequently used （最少使用）
- LRU - least recently used （最近最少使用）
替换算法总览：https://en.wikipedia.org/wiki/Cache_replacement_policies
实战题目
实现本题的两种操作，需要用到一个哈希表和一个双向链表。在面试中，面试官一般会期望读者能够自己实现一个简单的双向链表，而不是使用语言自带的、封装好的数据结构。在 Python 语言中，有一种结合了哈希表与双向链表的数据结构 OrderedDict，只需要短短的几行代码就可以完成本题。在 Java 语言中，同样有类似的数据结构 LinkedHashMap。
方法一：Java语言自带的LinkedHashMap
实现的基本原理，可以看下我的另外一篇文章《深入LinkedHashMap源码解析（JDK1.8）》
class LRUCache extends LinkedHashMap<Integer, Integer>{
private int capacity;
public LRUCache(int capacity) {
super(capacity, 0.75F, true);
this.capacity = capacity;
}
public int get(int key) {
return super.getOrDefault(key, -1);
}
public void put(int key, int value) {
super.put(key, value);
}
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
}
方法二：哈希表+双向链表
算法
LRU 缓存机制可以通过哈希表辅以双向链表实现，我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。
- 双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠靠近尾部的键值对是最久魏使用的。
- 哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射其在双向链表中的位置。
这样以来，我们首先使用哈希表进行定位，找出缓存项在双向链表中的位置，随后将其移动到双向链表的头部，即可在O(1)的时间内完成 get 或者 put 操作。具体方法如下：
- 对于
get操作，首先判断key是否存在：- 如果 key 不存在，则返回 -1；
- 如果 key 存在，则 key 对应的结点是最近被使用的结点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该结点的值。
- 对于
put，首先判断key是否存在：- 如果 key 不存在，使用 key 和 value 创建一个新的结点，在双向链表的头部添加该结点，并将 key 和该结点添加进哈希表中。然后判断双向链表的结点是否超出容量，如果超出容量，则删除双向链表的尾部结点，并删除哈希表中对应的项；
- 如果 key 存在，则与 get 操作类似，先通过哈希表定位，再将对应的结点的值更新为 value，并将该结点移动到双向链表的头部。
上述各项操作中，访问哈希表的时间复杂度为O(1), 在双向链表的头部添加结点、在双向链表的尾部删除结点的复杂度也为O(1)。而将一个结点移动到双向链表的头部，可以分成「删除该结点」和「在双向链表的头部添加结点」两步操作，都可以在O(1)时间内完成。
class LRUCache {
class DLinkedNode {
int key;
int value;
DLinkedNode prev;
DLinkedNode next;
public DLinkedNode() {}
public DLinkedNode(int key, int value) {
this.key = key;
this.value = value;
}
}
private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
private int size;
private int capacity;
private DLinkedNode head, tail;
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
// 使用伪头部和伪尾部结点
head = new DLinkedNode();
tail = new DLinkedNode();
head.next = tail;
tail.prev = head;
}
public int get(int key) {
DLinkedNode node = cache.get(key);
if (node == null) {
return -1;
}
// 如果 key 存在，先通过哈希表定位，再移到头部
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if (node == null) {
// 如果 key 不存在，创建一个新的结点
DLinkedNode newNode = new DLinkedNode(key, value);
// 添加进哈希表
cache.put(key, newNode);
// 添加至双向链表的头部
addToHead(newNode);
++size;
if (size > capacity) {
// 如果超出容量，删除双向链表的尾部结点
DLinkedNode tail = removeTail();
// 删除哈希表中对应的项
cache.remove(tail.key);
--size;
}
} else {
// 如果 key 存在，先通过哈希表定位，再修改value，并移动到头部
node.value = value;
moveToHead(node);
}
}
private void addToHead(DLinkedNode node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void removeNode(DLinkedNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void moveToHead(DLinkedNode node) {
removeNode(node);
addToHead(node);
}
private DLinkedNode removeTail() {
DLinkedNode res = tail.prev;
removeNode(res);
return res;
}
}
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得关键字 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得关键字 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
复杂度分析
- 时间复杂度：对于 put 和 get 都是
。
- 空间复杂度：
，因为哈希表和双向链表最多存储
个元素。
部分图片来源于网络，版权归原作者，侵删。
网友评论