干货|漫画算法：LRU从实现到应用层层剖析（第一讲）
以下文章来源于小浩算法 ，作者程序员浩哥
小浩算法
.
90后程序员，毕业五年赚了500万！写过代码、做过产品、创过业。曾用名「小浩算法」，苦于涉猎庞杂，特此更名~
今天为大家分享很出名的LRU算法，第一讲共包括4节。
LRU概述
LRU使用
LRU实现
Redis近LRU概述
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
进阶:你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例:
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
首先说一下LRUCache的示例解释一下
第一步：我们申明一个LRUCache，长度为2
第二步：我们分别向cache里边put(1,1)和put(2,2)，这里因为最近使用的是2（put也算作使用）所以2在前，1在后。
第三步：我们get(1)，也就是我们使用了1，所以需要将1移到前面。
第四步：此时我们put(3,3)，因为2是最近最少使用的，所以我们需要将2进行作废。此时我们再get(2)，就会返回-1。
第五步：我们继续put(4,4)，同理我们将1作废。此时如果get(1)，也是返回-1。
第六步：此时我们get(3)，实际为调整3的位置。
第七步：同理，get(4)，继续调整4的位置。
通过上面的分析大家应该都能理解LRU的使用了。现在我们聊一下实现。LRU一般来讲，我们是使用双向链表实现。这里我要强调的是，其实在项目中，并不绝对是这样。比如Redis源码里，LRU的淘汰策略，就没有使用双向链表，而是使用一种模拟链表的方式。因为Redis大多是当内存在用（我知道可以持久化），如果再在内存中去维护一个链表，就平添了一些复杂性，同时也会多耗掉一些内存，后面我会单独拉出来Redis的源码给大家分析，这里不细说。 回到题目，为什么我们要选择双向链表来实现呢？看看上面的使用步骤图，大家会发现，在整个LRUCache的使用中，我们需要频繁的去调整首尾元素的位置。而双向链表的结构，刚好满足这一点（再啰嗦一下，前几天我刚好看了groupcache的源码，里边就是用双向链表来做的LRU，当然它里边做了一些改进。groupcache是memcache作者实现的go版本，如果有go的读者，可以去看看源码，还是有一些收获。） 下面，我们采用hashmap+双向链表的方式进行实现。
1type LRUCache struct {
2 m map[int]*LinkNode
3 cap int
4 head, tail *LinkNode
5}
现在有了LinkNode，自然需要一个Cache来存储所有的Node。我们定义cap为cache的长度，m用来存储元素。head和tail作为Cache的首尾。
1type LRUCache struct {
2 m map[int]*LinkNode
3 cap int
4 head, tail *LinkNode
5}
接下来我们对整个Cache进行初始化。在初始化head和tail的时候将它们连接在一起。
1func Constructor(capacity int) LRUCache {
2 head := &LinkNode{0, 0, nil, nil}
3 tail := &LinkNode{0, 0, nil, nil}
4 head.next = tail
5 tail.pre = head
6 return LRUCache{make(map[int]*LinkNode), capacity, head, tail}
7}
大概是这样：
1func (this *LRUCache) Get(key int) int {
2 head := this.head
3 cache := this.m
4 if v, exist := cache[key]; exist {
5 v.pre.next = v.next
6 v.next.pre = v.pre
7 v.next = head.next
8 head.next.pre = v
9 v.pre = head
10 head.next = v
11 return v.val
12 } else {
13 return -1
14 }
15}
大概就是下面这个样子（假若2是我们get的元素）
我们很容易想到这个方法后面还会用到，所以将其抽出。
1func (this *LRUCache) moveToHead(node *LinkNode){
2 head := this.head
3 //从当前位置删除
4 node.pre.next = node.next
5 node.next.pre = node.pre
6 //移动到首位置
7 node.next = head.next
8 head.next.pre = node
9 node.pre = head
10 head.next = node
11}
12
13func (this *LRUCache) Get(key int) int {
14 cache := this.m
15 if v, exist := cache[key]; exist {
16 this.moveToHead(v)
17 return v.val
18 } else {
19 return -1
20 }
21}
现在我们开始完成Put。实现Put时，有两种情况需要考虑。假若元素存在，其实相当于做一个Get操作，也是移动到最前面（但是需要注意的是，这里多了一个更新值的步骤）。
1func (this *LRUCache) Put(key int, value int) {
2 head := this.head
3 tail := this.tail
4 cache := this.m
5 //假若元素存在
6 if v, exist := cache[key]; exist {
7 //1.更新值
8 v.val = value
9 //2.移动到最前
10 this.moveToHead(v)
11 } else {
12 //TODO
13 }
14}
假若元素不存在，我们将其插入到元素首，并把该元素值放入到map中。
1func (this *LRUCache) Put(key int, value int) {
2 head := this.head
3 tail := this.tail
4 cache := this.m
5 //存在
6 if v, exist := cache[key]; exist {
7 //1.更新值
8 v.val = value
9 //2.移动到最前
10 this.moveToHead(v)
11 } else {
12 v := &LinkNode{key, value, nil, nil}
13 v.next = head.next
14 v.pre = head
15 head.next.pre = v
16 head.next = v
17 cache[key] = v
18 }
19}
但是我们漏掉了一种情况，如果恰好此时Cache中元素满了，需要删掉最后的元素。处理完毕，附上Put函数完整代码。
1func (this *LRUCache) Put(key int, value int) {
2 head := this.head
3 tail := this.tail
4 cache := this.m
5 //存在
6 if v, exist := cache[key]; exist {
7 //1.更新值
8 v.val = value
9 //2.移动到最前
10 this.moveToHead(v)
11 } else {
12 v := &LinkNode{key, value, nil, nil}
13 if len(cache) == this.cap {
14 //删除最后元素
15 delete(cache, tail.pre.key)
16 tail.pre.pre.next = tail
17 tail.pre = tail.pre.pre
18 }
19 v.next = head.next
20 v.pre = head
21 head.next.pre = v
22 head.next = v
23 cache[key] = v
24 }
25}
最后，我们完成所有代码：
1type LinkNode struct {
2 key, val int
3 pre, next *LinkNode
4}
5
6type LRUCache struct {
7 m map[int]*LinkNode
8 cap int
9 head, tail *LinkNode
10}
11
12func Constructor(capacity int) LRUCache {
13 head := &LinkNode{0, 0, nil, nil}
14 tail := &LinkNode{0, 0, nil, nil}
15 head.next = tail
16 tail.pre = head
17 return LRUCache{make(map[int]*LinkNode), capacity, head, tail}
18}
19
20func (this *LRUCache) Get(key int) int {
21 cache := this.m
22 if v, exist := cache[key]; exist {
23 this.moveToHead(v)
24 return v.val
25 } else {
26 return -1
27 }
28}
29
30func (this *LRUCache) moveToHead(node *LinkNode) {
31 head := this.head
32 //从当前位置删除
33 node.pre.next = node.next
34 node.next.pre = node.pre
35 //移动到首位置
36 node.next = head.next
37 head.next.pre = node
38 node.pre = head
39 head.next = node
40}
41
42func (this *LRUCache) Put(key int, value int) {
43 head := this.head
44 tail := this.tail
45 cache := this.m
46 //存在
47 if v, exist := cache[key]; exist {
48 //1.更新值
49 v.val = value
50 //2.移动到最前
51 this.moveToHead(v)
52 } else {
53 v := &LinkNode{key, value, nil, nil}
54 if len(cache) == this.cap {
55 //删除末尾元素
56 delete(cache, tail.pre.key)
57 tail.pre.pre.next = tail
58 tail.pre = tail.pre.pre
59 }
60 v.next = head.next
61 v.pre = head
62 head.next.pre = v
63 head.next = v
64 cache[key] = v
65 }
66}
优化后：
1type LinkNode struct {
2 key, val int
3 pre, next *LinkNode
4}
5
6type LRUCache struct {
7 m map[int]*LinkNode
8 cap int
9 head, tail *LinkNode
10}
11
12func Constructor(capacity int) LRUCache {
13 head := &LinkNode{0, 0, nil, nil}
14 tail := &LinkNode{0, 0, nil, nil}
15 head.next = tail
16 tail.pre = head
17 return LRUCache{make(map[int]*LinkNode), capacity, head, tail}
18}
19
20func (this *LRUCache) Get(key int) int {
21 cache := this.m
22 if v, exist := cache[key]; exist {
23 this.MoveToHead(v)
24 return v.val
25 } else {
26 return -1
27 }
28}
29
30func (this *LRUCache) RemoveNode(node *LinkNode) {
31 node.pre.next = node.next
32 node.next.pre = node.pre
33}
34
35func (this *LRUCache) AddNode(node *LinkNode) {
36 head := this.head
37 node.next = head.next
38 head.next.pre = node
39 node.pre = head
40 head.next = node
41}
42
43func (this *LRUCache) MoveToHead(node *LinkNode) {
44 this.RemoveNode(node)
45 this.AddNode(node)
46}
47
48func (this *LRUCache) Put(key int, value int) {
49 tail := this.tail
50 cache := this.m
51 if v, exist := cache[key]; exist {
52 v.val = value
53 this.MoveToHead(v)
54 } else {
55 v := &LinkNode{key, value, nil, nil}
56 if len(cache) == this.cap {
57 delete(cache, tail.pre.key)
58 this.RemoveNode(tail.pre)
59 }
60 this.AddNode(v)
61 cache[key] = v
62 }
63}
因为该算法过于重要，给一个Java版本的：
1//java版本
2public class LRUCache {
3 class LinkedNode {
4 int key;
5 int value;
6 LinkedNode prev;
7 LinkedNode next;
8 }
9
10 private void addNode(LinkedNode node) {
11 node.prev = head;
12 node.next = head.next;
13 head.next.prev = node;
14 head.next = node;
15 }
16
17 private void removeNode(LinkedNode node){
18 LinkedNode prev = node.prev;
19 LinkedNode next = node.next;
20 prev.next = next;
21 next.prev = prev;
22 }
23
24 private void moveToHead(LinkedNode node){
25 removeNode(node);
26 addNode(node);
27 }
28
29 private LinkedNode popTail() {
30 LinkedNode res = tail.prev;
31 removeNode(res);
32 return res;
33 }
34
35 private Hashtable<Integer, LinkedNode> cache = new Hashtable<Integer, LinkedNode>();
36 private int size;
37 private int capacity;
38 private LinkedNode head, tail;
39
40 public LRUCache(int capacity) {
41 this.size = 0;
42 this.capacity = capacity;
43 head = new LinkedNode();
44 tail = new LinkedNode();
45 head.next = tail;
46 tail.prev = head;
47 }
48
49 public int get(int key) {
50 LinkedNode node = cache.get(key);
51 if (node == null) return -1;
52 moveToHead(node);
53 return node.value;
54 }
55
56 public void put(int key, int value) {
57 LinkedNode node = cache.get(key);
58
59 if(node == null) {
60 LinkedNode newNode = new LinkedNode();
61 newNode.key = key;
62 newNode.value = value;
63 cache.put(key, newNode);
64 addNode(newNode);
65 ++size;
66 if(size > capacity) {
67 LinkedNode tail = popTail();
68 cache.remove(tail.key);
69 --size;
70 }
71 } else {
72 node.value = value;
73 moveToHead(node);
74 }
75 }
76}
上文完成了咱们自己的LRU实现，现在现在聊一聊Redis中的近似LRU。由于真实LRU需要过多的内存（在数据量比较大时），所以Redis是使用一种随机抽样的方式，来实现一个近似LRU的效果。说白了，LRU根本只是一个预测键访问顺序的模型。
在Redis中有一个参数，叫做 “maxmemory-samples”，是干嘛用的呢？
1# LRU and minimal TTL algorithms are not precise algorithms but approximated
2# algorithms (in order to save memory), so you can tune it for speed or
3# accuracy. For default Redis will check five keys and pick the one that was
4# used less recently, you can change the sample size using the following
5# configuration directive.
6#
7# The default of 5 produces good enough results. 10 Approximates very closely
8# true LRU but costs a bit more CPU. 3 is very fast but not very accurate.
9#
10maxmemory-samples 5
这个图解释一下，绿色的点是新增加的元素，深灰色的点是没有被删除的元素，浅灰色的是被删除的元素。最下面的这张图，是真实LRU的效果，第二张图是默认该参数为5的效果，可以看到浅灰色部分和真实的契合还是不错的。第一张图是将该参数设置为10的效果，已经基本接近真实LRU的效果了。
由于时间关系本文基本就说到这里。那Redis中的近似LRU是如何实现的呢？请关注下一期的内容~
文章来源：本文由小浩算法授权转载
⭐️⭐️⭐️欢迎加入“宜信技术交流群”。进群方式：请加小助手微信（微信号：18910316664）。
◆ ◆ ◆ ◆ ◆
如需转载请与小助手（微信号：18910316664）联系。发现文章有错误、对内容有疑问，都可以通过关注宜信技术学院微信公众号（CE_TECH），在后台留言给我们。我们每周会挑选出一位热心小伙伴，送上一份精美的小礼品。快来扫码关注我们吧！
⏬点击“阅读原文”查看更多技术干货