LRU算法实现

本文最后更新于：2021年9月20日 上午

介绍了Redis最常用的缓存淘汰策略LRU(最近最少使用)

LRU算法实现

这里我们来使用链表+Map的方式来实现LRU，这里不考虑并发，我们只实现固定容量的Get、Put算法。

先来讲一下大致的思路

思路

首先是底层结构，底层结构是链表+Map，其中链表保存的就是访问顺序，我们可以定义首部是最近访问的元素，而尾部是不访问的元素（也可以反过来），Map用来定位一个Key的具体的Node。

Get算法：我们获取一个key的val，并且把这个key对应的Node移动到首部

Put算法：如果本来就存在这个key的话就更新值并移动到首部，如果不存在就新建一个Node到首部。并且判断容量是否超出，如果超出的话就在Map和链表中分别移除这个key的Node。

链表实现

这里我们使用 双向链表，（这是为了加快访问速度，否则即使我们使用了Map来定位还是需要循环访问到Node）。

首先来定义Node和List的结构，这里我们使用头尾虚拟指针来简化编程的思路。

1
2
3
4
5
6
7
8
9
10
11
type list struct {
	head *node
	foot *node
}

type node struct {
	prev *node
	next *node
	key  int
	val  int
}

然后我们来实现 CD算法(因为不设计到UR所以没有实现)。我们知道我们使用了Map来定位Node，所以我们不在需要key作为参数来循环遍历

1
2
3
4
5
6
7
8
9
10
11
func (l *list) removeNode(n *node) {
	n.prev.next = n.next
	n.next.prev = n.prev
}

func (l *list) InsertHeadByNode(n *node) {
	n.next = l.head.next
	n.prev = l.head
	l.head.next.prev = n
	l.head.next = n
}

到此为止我们实现的都是公共的算法，和LRU没有任何关系。接下来我们思考一下LRU算法实现，是不是有

  1. 把这个key对应的Node移动到首部
  2. 移除这个key的Node

这里所代表的移动到首部实际上就是先从链表中删除一个Node，再往链表的首部增加这个Node，这也就是移动操作啦。第二点的移除操作实际上只会移除尾部的Node。基于这两点我们来稍微封装一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 至于这里为什么需要返回node我们等待再说
func (l *list) RemoveFoot() *node {
	var n = l.foot.prev
	l.removeNode(l.foot.prev)
	return n
}

func (l *list) MoveHeader(n *node) {
	// 解除引用
    removeNode(n)

	// 放到头
	l.InsertHeadByNode(n)
}

Map实现

这里我们就直接使用内置结构 map 来实现吧，如果需要手动实现一个 map 的话可以采用 数组+链表为底层数据结构，拉链法做hash冲突解决方案实现。这里我们就直接定义 map[int]*node 吧

LRU结构

我们来定义一下LRU的结构，我们上文提到链表+Map的方式来实现LRU，那么我们的结构体就必须包含这两个机构，并且还需要一个最大容量。所以我们得出

1
2
3
4
5
6
7
8
9
10
11
12
13
type LRUCache struct {
	m        map[int]*node
	l        list
	capacity int
}

func Constructor(capacity int) LRUCache {
	return LRUCache{
		capacity: capacity,
		m:        map[int]*node{},
		l:        newList(),
	}
}

其中 newList() 函数是一个初始化双向链表的函数，定义如下

1
2
3
4
5
6
func newList() list {
	l := list{head: &node{}, foot: &node{}}
	l.head.next = l.foot
	l.foot.prev = l.head
	return l
}

接下来是最重要的两个算法，我们一一来书写

第一个是Get算法，还记得我们的思路吗？ 我们获取一个key的val，并且把这个key对应的Node移动到首部，所以我们得出

1
2
3
4
5
6
7
8
func (this *LRUCache) Get(key int) int {
	var n, ok = this.m[key]
	if !ok {
		return -1
	}
	this.l.MoveHeader(n)
	return n.val
}

Put算法一样的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func (this *LRUCache) Put(key int, value int) {
	var n, ok = this.m[key]
	if ok {
		// 存在
		this.m[key] = n
		n.val = value
		this.l.MoveHeader(n)
	} else {
		// 不存在key
		n = &node{key: key, val: value}
		this.m[key] = n
		this.l.InsertHeadByNode(n)
	}
	if len(this.m) > this.capacity {
		removed := this.l.RemoveFoot()
		delete(this.m, removed.key)
	}
}

单元测试

我截取了两段 Leetcode 的测试函数来进行测试

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
func TestConstructor(t *testing.T) {
	var val int

	lRUCache := Constructor(2)

	lRUCache.Put(1, 0)
	lRUCache.Put(2, 2)

	val = lRUCache.Get(1)
	assert.Equal(t, val, 0)

	lRUCache.Put(3, 3)

	val = lRUCache.Get(2)
	assert.Equal(t, val, -1)

	lRUCache.Put(4, 4)

	val = lRUCache.Get(1)
	assert.Equal(t, val, -1)

	val = lRUCache.Get(3)
	assert.Equal(t, val, 3)

	val = lRUCache.Get(4)
	assert.Equal(t, val, 4)

	lRUCache.Put(1, 1)    // 缓存是 {1=1}
	lRUCache.Put(2, 2)    // 缓存是 {1=1, 2=2}
	val = lRUCache.Get(1) // 返回 1
	assert.Equal(t, val, 1)
	lRUCache.Put(3, 3)    // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
	val = lRUCache.Get(2) // 返回 -1 (未找到)
	assert.Equal(t, val, -1)
	lRUCache.Put(4, 4)    // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
	val = lRUCache.Get(1) // 返回 -1 (未找到)
	assert.Equal(t, val, -1)
	val = lRUCache.Get(3) // 返回 3
	assert.Equal(t, val, 3)
	val = lRUCache.Get(4) // 返回 4
	assert.Equal(t, val, 4)
}

全部代码

  • list.go
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
package lru

type list struct {
	head *node
	foot *node
}

type node struct {
	prev *node
	next *node
	key  int
	val  int
}

func newList() list {
	l := list{head: &node{}, foot: &node{}}
	l.head.next = l.foot
	l.foot.prev = l.head
	return l
}

func (l *list) MoveHeader(n *node) {
	// 解除引用
	l.removeNode(n)

	// 放到头
	l.InsertHeadByNode(n)
}

func (l *list) InsertHeadByVal(val int) {
	var n = &node{val: val}
	l.InsertHeadByNode(n)
}

func (l *list) InsertHeadByNode(n *node) {
	n.next = l.head.next
	n.prev = l.head
	l.head.next.prev = n
	l.head.next = n
}

func (l *list) RemoveFoot() *node {
	var n = l.foot.prev
	l.removeNode(l.foot.prev)
	return n
}

func (l *list) removeNode(n *node) {
	n.prev.next = n.next
	n.next.prev = n.prev
}
  • lru.go
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
package lru

type LRUCache struct {
	m        map[int]*node
	l        list
	capacity int
}

func Constructor(capacity int) LRUCache {
	return LRUCache{
		capacity: capacity,
		m:        map[int]*node{},
		l:        newList(),
	}
}

func (this *LRUCache) Get(key int) int {
	var n, ok = this.m[key]
	if !ok {
		return -1
	}
	this.l.MoveHeader(n)
	return n.val
}

func (this *LRUCache) Put(key int, value int) {
	var n, ok = this.m[key]
	if ok {
		// 存在
		this.m[key] = n
		n.val = value
		this.l.MoveHeader(n)
	} else {
		// 不存在key
		n = &node{key: key, val: value}
		this.m[key] = n
		this.l.InsertHeadByNode(n)
	}
	if len(this.m) > this.capacity {
		removed := this.l.RemoveFoot()
		delete(this.m, removed.key)
	}
}
  • lru_test.go

单元测试 即是全部代码

写在最后

写代码要先想思路，思路有了的话写代码就是把思路转化为代码的过程

Redis
Redis 基础知识

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！