LRU算法实现

LRU缓存

由于内存是有限的,因此缓存总有满的时候,那么当缓存满了的时候,这时候又有新的数据需要加入到缓存中时,我们该怎么办了?没什么别的办法,只有从缓存中删除旧数据为新数据腾出空间,那么究竟删除原来缓存的哪些数据了?这就涉及到缓存的替换策略,LRU就是一种缓存策略。

LRU,Least Recently Used的简写,翻译过来就是“最近最少使用”, 其淘汰旧数据的策略是,距离当前最久没有被访问过的数据应该被淘汰。

LRU原理

假设内存只能容纳3个页大小,按照 7 0 1 2 0 3 0 4 的次序访问页。假设内存按照栈的方式来描述访问时间,在上面的,是最近访问的,在下面的是,最远时间访问的,LRU就是这样工作的。

lru

这样设计可能问题很多,内存按照访问时间进行了排序,会有大量的内存拷贝操作,所以性能肯定是不能接受的。

那么如何设计一个LRU缓存,使得放入和移除都是 O(1) 的,我们需要把访问次序维护起来,但是不能通过内存中的真实排序来反应,有一种方案就是使用双向链表。

HashMap+双向链表

基于 HashMap 和 双向链表实现 LRU的整体的设计思路是,可以使用 HashMap 存储 key,这样可以做到 save 和 get key的时间都是 O(1),而 HashMap 的 Value 指向双向链表实现的 LRU 的 Node 节点,如图所示:

lru

LRU 存储是基于双向链表实现的,下面的图演示了它的原理。其中 head 代表双向链表的表头,tail 代表尾部。首先预先设置 LRU 的容量,如果存储满了,可以通过 O(1) 的时间淘汰掉双向链表的尾部,每次新增和访问数据,都可以通过 O(1)的效率把新的节点增加到对头,或者把已经存在的节点移动到队头。

lru

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
// 双项链表

function DLinkedNode(key, data) {
this.key = key;
this.data = data;
this.next = null; // 指向下一个节点
this.prev = null; // 指向前一个节点
}

function LRUCache(capacity) {
var cache = {};
var count = 0;
var capacity;

head = new DLinkedNode();
tail = new DLinkedNode();
tail.prev = head;
head.next = tail;


this.get = function(key) {
var node = cache[key];
if (!node) return null;
this.moveToHead(node);
return node.data;
}

this.set = function(key, data) {
var node = cache[key];
if (!node) {
node = new DLinkedNode(key, data);
cache[key] = node;
this.addNode(node);
count++;
if (count > capacity) {
var tail = this.popTail();
delete cache[tail.key];
count--;
}
} else {
node.data = data;
this.moveToHead(node);
}
}

this.addNode = function(node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}

this.removeNode = function(node) {
var prev = node.prev;
var next = node.next;
prev.next = next;
next.prev = prev;
}

this.moveToHead = function(node) {
this.removeNode(node);
this.addNode(node);
}

this.popTail = function() {
var preNode = tail.prev;
this.removeNode(preNode);
return preNode;
}
}

参考文档

有用就打赏一下作者吧!