Golang - LRUCache | Ningzi's Blog

一些链接

LeetCode 🔗: https://leetcode-cn.com/problems/lru-cache/

wiki 🔗: https://en.wikipedia.org/wiki/Cache_replacement_policies

TL;DR

思路

根据 wiki 的介绍，我们需要维护 lru-cache 中每一个元素的 age，或者称为优先级。新增元素的优先级总是最高的。当 lru-cache 的容量满了以后，再添加新元素之前需要删除优先级最低的元素从而腾出位置给新的元素。每次命中 lru-cache 中的元素，都会将命中的元素的优先级提高为最高

如果真的为每个元素维护一个优先级的数值的话，那 lru-cache 的每一次操作过后，都需要为缓存元素排序以便快速找到优先级最高和最低的元素，题目中要求我们在 O(1) 的时间复杂度下完成 Get 和 Put 两种操作，显然这样是不行的。

我们知道链表新增和删除节点的时间复杂度为 O(1)，而获取其中的某个节点需要 O(n) 的时间复杂度，这只达成了要求的一半，那有什么办法可以是获取元素的复杂度也为 O(1) 么？有啊，散列表。如果我们可以将这两种数据结构组合起来，就可以在 O(1) 的复杂度下完成题目的要求。

如何实现？

首先我们需要实现一个双向环形链表，首尾相连，头部表示最近被使用的元素（或者新增的），尾部为最少被使用的元素。lru-cache 维护链表的 root 节点，只需要使用 root.Next 和 root.Prev 即可访问最近和最久被使用的元素。

btw, golang 标准库中其实已经为我们实现了环形链表

然后，我们维护一个散列表，key 为缓存元素的 key，value 为链表中的节点。我们得到节点后就可以方便的做很多事，比如移动节点到链表的顶端。

实现环形链表

定义链表结构，为了实现 leetcode 的题目，所以 val 的类型比较单一，其实可以使用 interface 来代替，可以接收更丰富的类型（等一个泛型）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


type LinkedList struct {
	Prev, Next *LinkedList
	Key, Val   int
}

// NewLinkedList 创建一个环形链表，返回 root 节点，root 节点不存储任何实际内容，
// 只维护 Next(Head) 和 Prev(Tail) 节点，新创建的节点的 Next 和 Prev 总是指向
// 自己。
func NewLinkedList() *LinkedList {
	node := &LinkedList{}
	node.Next = node
	node.Prev = node
	return node
}

我们只实现能满足 lru-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


// AddToHead 创建一个节点，并将新建的节点指向 root 的 Next
func (l *LinkedList) AddToHead(key int, val int) {
	node := &LinkedList{
		Key: key,
		Val: val,
	}

	node.Next = l.Next
	node.Prev = l
	l.Next.Prev = node
	l.Next = node
}

// MoveToHead 将节点指向 root 的 Next
func (l *LinkedList) MoveToHead(node *LinkedList) {
	node.Prev.Next = node.Next
	node.Next.Prev = node.Prev

	node.Prev = l
	node.Next = l.Next

	l.Next.Prev = node
	l.Next = node
}

// DeleteNode 将节点从链表中删除
func (l *LinkedList) DeleteNode(node *LinkedList) {
	node.Next.Prev = node.Prev
	node.Prev.Next = node.Next
}

lru-cache

有了环形链表后，就可以开始实现我们的主角 lru-cache，惯例先定义结构体

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


type LRUCache struct {
	// capacity lru-cache 能存储的最大容量，超过这个值后需要
	// 删除最久没有使用的元素
	capacity int
	// used 记录着当前 lru-cache 已使用的容量
	used     int
	// store 指向环形链表的 root 节点
	store    *LinkedList
	// cache 记录 lru-cache 中的每个 key 和在链表中
	// 的节点，方便读取
	cache    map[int]*LinkedList
}

// Constructor 创建实例
func Constructor(capacity int) LRUCache {
	return LRUCache{
		capacity: capacity,
		used:     0,
		store:    NewLinkedList(),
		cache:    make(map[int]*LinkedList),
	}
}

Put 方法

根据规则，如果元素已存在于 lru-cache 中则需要更新元素的值，同时将元素移动到链表的顶端。我们的 cache 的用处就体现出来了，可以非常方便的获取元素。

1
2
3
4
5
6
7
8


// key 是否已经存在，如果已经存在就更新节点
// 更新的同时也需要把节点移动到链表的顶端
node, exist := l.cache[key]
if exist {
  node.Val = value
  l.store.MoveToHead(node)
  return
}

如果新增的元素不存在时，我们就新增一个元素，但是在新增元素之前，我们还需要检查 lru-cache 的容量，如果没有剩余空间给新增的元素，那么我们需要删除一个倒霉蛋

1
2
3
4
5
6


if l.used == l.capacity {
  // 删除最少使用的元素，给新加入的元素空出位置
  delete(l.cache, l.store.Prev.Key)
  l.store.DeleteNode(l.store.Prev)
  l.used -= 1
}

这是我们可以添加元素了，不仅仅需要把元素添加到链表中，还需要写入 cache 中，同时更新已使用的数量

1
2
3
4
5


	// 新添加的元素放在链表的顶端
	l.store.AddToHead(key, value)
	// 存入 cache 中，方便 Get 时获取
	l.cache[key] = l.store.Next
	l.used += 1

完整代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


func (l *LRUCache) Put(key int, value int) {
	// key 是否已经存在，如果已经存在就更新节点
	// 更新的同时也需要把节点移动到链表的顶端
	node, exist := l.cache[key]
	if exist {
		node.Val = value
		l.store.MoveToHead(node)
		return
	}

	if l.used == l.capacity {
		// 删除最少使用的元素，给新加入的元素空出位置
		delete(l.cache, l.store.Prev.Key)
		l.store.DeleteNode(l.store.Prev)
		l.used -= 1
	}

	// 新添加的元素放在链表的顶端
	l.store.AddToHead(key, value)
	// 存入 cache 中，方便 Get 时获取
	l.cache[key] = l.store.Next
	l.used += 1
}

Get

get 方法的实现就相对容易很多，我们从 cache 中获取 key 的值，如果没有，就返回 -1

1
2
3
4


	node, exist := l.cache[key]
	if !exist {
		return -1
	}

否则，我们需要将节点移动到链表的顶端，然后返回结果

1
2
3


	// 最近使用过的节点移动到链表的顶端
	l.store.MoveToHead(node)
	return node.Val

完整代码

1
2
3
4
5
6
7
8
9


func (l *LRUCache) Get(key int) int {
	node, exist := l.cache[key]
	if !exist {
		return -1
	}
	// 最近使用过的节点移动到链表的顶端
	l.store.MoveToHead(node)
	return node.Val
}

完整代码

 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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93


package main

type LRUCache struct {
	capacity int
	used     int
	store    *LinkedList
	cache    map[int]*LinkedList
}

func Constructor(capacity int) LRUCache {
	return LRUCache{
		capacity: capacity,
		used:     0,
		store:    NewLinkedList(),
		cache:    make(map[int]*LinkedList),
	}
}

func (l *LRUCache) Get(key int) int {
	node, exist := l.cache[key]
	if !exist {
		return -1
	}
	// 最近使用过的节点移动到链表的顶端
	l.store.MoveToHead(node)
	return node.Val
}

// Put put
func (l *LRUCache) Put(key int, value int) {
	// key 是否已经存在，如果已经存在就更新节点
	// 更新的同时也需要把节点移动到链表的顶端
	node, exist := l.cache[key]
	if exist {
		node.Val = value
		l.store.MoveToHead(node)
		return
	}

	if l.used == l.capacity {
		// 删除最少使用的元素，给新加入的元素空出位置
		delete(l.cache, l.store.Prev.Key)
		l.store.DeleteNode(l.store.Prev)
		l.used -= 1
	}

	// 新添加的元素放在链表的顶端
	l.store.AddToHead(key, value)
	// 存入 cache 中，方便 Get 时获取
	l.cache[key] = l.store.Next
	l.used += 1
}

type LinkedList struct {
	Prev, Next *LinkedList
	Key, Val   int
}

func NewLinkedList() *LinkedList {
	node := &LinkedList{}
	node.Next = node
	node.Prev = node
	return node
}

func (l *LinkedList) AddToHead(key int, val int) {
	node := &LinkedList{
		Key: key,
		Val: val,
	}

	node.Next = l.Next
	node.Prev = l
	l.Next.Prev = node
	l.Next = node
}

func (l *LinkedList) MoveToHead(node *LinkedList) {
	node.Prev.Next = node.Next
	node.Next.Prev = node.Prev

	node.Prev = l
	node.Next = l.Next

	l.Next.Prev = node
	l.Next = node
}

func (l *LinkedList) DeleteNode(node *LinkedList) {
	node.Next.Prev = node.Prev
	node.Prev.Next = node.Next
}

TL;DR#

思路#

如何实现？#

实现环形链表#

lru-cache#

Put 方法#

Get#

完整代码#

TL;DR

思路

如何实现？

实现环形链表

lru-cache

Put 方法

Get

完整代码