LRU缓存淘汰算法

LRU是最近最少使用策略的缩写,是根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。

双向链表实现LRU

将Cache的所有位置都用双链表连接起来,当一个位置被访问(get/put)之后,通过调整链表的指向,将该位置调整到链表头的位置,新加入的Cache直接加到链表头中。

这样,在多次操作后,最近被访问(get/put)的,就会被向链表头方向移动,而没有访问的,向链表后方移动,链表尾则表示最近最少使用的Cache。

当达到缓存容量上限时,链表的最后位置就是最少被访问的Cache,我们只需要删除链表最后的Cache便可继续添加新的Cache

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
71
72
73
74
75
type Node struct {
Key int
Value int
pre *Node
next *Node
}

type LRUCache struct {
limit int
HashMap map[int]*Node
head *Node
end *Node
}

func Constructor(capacity int) LRUCache{
lruCache := LRUCache{limit:capacity}
lruCache.HashMap = make(map[int]*Node, capacity)
return lruCache
}

func (l *LRUCache) Get(key int) int {
if v,ok:= l.HashMap[key];ok {
l.refreshNode(v)
return v.Value
}else {
return -1
}
}

func (l *LRUCache) Put(key int, value int) {
if v,ok := l.HashMap[key];!ok{
if len(l.HashMap) >= l.limit{
oldKey := l.removeNode(l.head)
delete(l.HashMap, oldKey)
}
node := Node{Key:key, Value:value}
l.addNode(&node)
l.HashMap[key] = &node
}else {
v.Value = value
l.refreshNode(v)
}
}

func (l *LRUCache) refreshNode(node *Node){
if node == l.end {
return
}
l.removeNode(node)
l.addNode(node)
}

func (l *LRUCache) removeNode(node *Node) int{
if node == l.end {
l.end = l.end.pre
}else if node == l.head {
l.head = l.head.next
}else {
node.pre.next = node.next
node.next.pre = node.pre
}
return node.Key
}

func (l *LRUCache) addNode(node *Node){
if l.end != nil {
l.end.next = node
node.pre = l.end
node.next = nil
}
l.end = node
if l.head == nil {
l.head = node
}
}