实现 LFU 缓存算法

实现 LFU 缓存算法

https://leetcode-cn.com/problems/lfu-cache/

https://mp.weixin.qq.com/s/oXv03m1J8TwtHwMJEZ1ApQ

需求分析

上一个 LRU 只需要替换最长时间未使用的，因此只需要一个哈希链表维护时序信息就够了。

而 LFU 需要维护频次信息，删除时如果有多个频次相同的，还要删除最长时间未使用的。

  • 调用 get(key) 方法时，要返回该 key 对应的 val：使用哈希表 keyToVal
  • 只要用 get 或者 put 方法访问一次某个 key，该 key 的 freq 就要加一：使用哈希表 keyToFreq 快速操作对应的频率
  • 要将 freq 最小的 key 删除：
    1. 要得知最小的 freq 是多少：用一个变量 minFreq 储存
    2. 要得知哪些 key 的频次是 freq：用哈希表 freqToKeys 储存 freq 对应的所有 key
    3. 如果最小 freq 有多个 key，删除最长时间未使用的：类似 LRU，用哈希链表储存 key
    4. 要快速删除 key 列表中的任意一个，因为它频次更新为 freq + 1后，应该从 freqToKeys[freq] 中删除，并加入到 freqToKeys[freq + 1] 中：还是类似 LRU，用哈希链表储存 key

至此，可以写出 LFU 所需要的所有数据结构：

1
2
3
4
5
6
7
8
type LFUCache struct {
    keyToVal  map[int]int             // key 映射为 val，用于记录 key 的值
    keyToFreq map[int]int             // key 映射为 freq，用于记录 key 的频率
    freqToKeys map[int]*LinkedHashSet  // freq 映射为 key 的哈希链表，用于找到最小频率且包含时序信息的 key

    minFreq int  // 记录最小频次
    cap     int  // 记录最大容量
}

组件实现

哈希链表实现

Golang 没有内置的哈希链表实现，按照 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
/* 链表节点类 */
type Node struct {
    Key, Value int
    Next, Prev *Node
}

/* 双链表类 */
type LinkedList struct {
    Head, Tail *Node
    Len int
}

/* 双链表类构造方法 */
func NewList() LinkedList {
    head := new(Node)
    tail := new(Node)
    head.Next = tail
    tail.Prev = head
    return LinkedList{head, tail, 0}
}

/* 向双链表尾部添加节点 */
func (this *LinkedList) AddLast(x *Node) {
    x.Prev = this.Tail.Prev
    x.Next = this.Tail

    this.Tail.Prev.Next = x
    this.Tail.Prev = x

    this.Len++
}

/* 删除双链表特定节点 */
func (this *LinkedList) Remove(x *Node) {
    x.Prev.Next = x.Next
    x.Next.Prev = x.Prev
    this.Len--
}

/* 删除双链表头部节点并返回 */
func (this *LinkedList) RemoveFirst() *Node {
    if this.Head.Next == this.Tail {
        return nil
    }

    x := this.Head.Next
    this.Remove(x)

    return x
}

根据双链表，实现哈希链表：

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
/* 哈希链表类 */
type LinkedHashSet struct {
    keyToNode map[int]*Node
    cache LinkedList
}

/* 哈希链表类构造方法 */
func NewLinkedHashSet() *LinkedHashSet {
    return &LinkedHashSet{make(map[int]*Node), NewList()}
}

/* 向哈希链表添加元素 */
func (this *LinkedHashSet) AddRecently(key, val int) {
    x := &Node{key, val, nil, nil}
    this.cache.AddLast(x)
    this.keyToNode[key] = x
}

/* 删除哈希链表指定元素 */
func (this *LinkedHashSet) DeleteKey(key int) {
    x := this.keyToNode[key]
    this.cache.Remove(x)
    delete(this.keyToNode, key)
}

/* 删除哈希链表头部元素 */
func (this *LinkedHashSet) DeleteLeastRecently() *Node {
    detetedNode := this.cache.RemoveFirst()
    delete(this.keyToNode, detetedNode.Key)
    return detetedNode
}

/* 哈希链表长度 */
func (this *LinkedHashSet) Len() int {
    return this.cache.Len
}

实现 LFU

实现 LFU 时，遇到跟频次有关的操作，先抽象为一个函数，后面再去实现函数具体逻辑：

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
type LFUCache struct {
    keyToVal  map[int]int             // key 映射为 val，用于记录 key 的值
    keyToFreq map[int]int             // key 映射为 freq，用于记录 key 的频率
    freqToKeys map[int]*LinkedHashSet  // freq 映射为 key 的哈希列表，用于找到最小频率且包含时序信息的 key

    minFreq int  // 记录最小频次
    cap     int  // 记录最大容量
}


func Constructor(capacity int) LFUCache {
    keyToVal := make(map[int]int)
    keyToFreq := make(map[int]int)
    freqToKeys := make(map[int]*LinkedHashSet)

    return LFUCache{keyToVal, keyToFreq, freqToKeys, 0, capacity}
}


func (this *LFUCache) Get(key int) int {
    if _, ok := this.keyToVal[key]; !ok {
        return -1
    }
    this.increaseFreq(key)  // 增加 key 对应的频率
    return this.keyToVal[key]
}


func (this *LFUCache) Put(key int, value int)  {
    // 注：测试用例有传入 0 容量的情况
    if this.cap <= 0 {
        return
    }

    // 如果 key 存在，只用更新它的 value，且增加对应频率
    if _, ok := this.keyToVal[key]; ok {
        this.keyToVal[key] = value
        this.increaseFreq(key)
        return
    }

    // 如果超出容量，移除最小频率的 key
    if this.cap <= len(this.keyToVal) {
        this.removeMinFreqKey()
    }

    // 插入 key 和 val
    this.keyToVal[key] = value
    this.keyToFreq[key] = 1
    if _, ok := this.freqToKeys[1]; !ok {
        this.freqToKeys[1] = NewLinkedHashSet()
    }
    this.freqToKeys[1].AddRecently(key, value)
    this.minFreq = 1
}

将跟新频率、移除最小频率元素的两个方法抽象了出来：

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
/* 两个频次相关的实用函数 */
func (this *LFUCache) removeMinFreqKey() {
    keyList := this.freqToKeys[this.minFreq]

    deletedNode := keyList.DeleteLeastRecently()
    if keyList.Len() == 0 {
        delete(this.freqToKeys, this.minFreq)
        // 由于此方法只会再插入新元素时调用，而插入后 minFreq 一定会更新为 1，因此这里不需要更新 minFreq 的值
    }

    delete(this.keyToVal, deletedNode.Key)
    delete(this.keyToFreq, deletedNode.Key)
}

func (this *LFUCache) increaseFreq(key int) {
    freq := this.keyToFreq[key]
    this.keyToFreq[key] = freq + 1  // 更新对应的频率

    // 在新的频率链表中加上它
    if _, ok := this.freqToKeys[freq + 1]; !ok {
        this.freqToKeys[freq + 1] = NewLinkedHashSet()
    }
    this.freqToKeys[freq + 1].AddRecently(key, this.keyToVal[key])

    // 在旧的频率链表中删除它
    this.freqToKeys[freq].DeleteKey(key)
    if this.freqToKeys[freq].Len() == 0 {
        delete(this.freqToKeys, freq)
        if freq == this.minFreq {
            this.minFreq++
        }
    }
}

完整代码

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
/* 链表节点类 */
type Node struct {
    Key, Value int
    Next, Prev *Node
}

/* 双链表类 */
type LinkedList struct {
    Head, Tail *Node
    Len int
}

/* 双链表类构造方法 */
func NewList() LinkedList {
    head := new(Node)
    tail := new(Node)
    head.Next = tail
    tail.Prev = head
    return LinkedList{head, tail, 0}
}

/* 向双链表尾部添加节点 */
func (this *LinkedList) AddLast(x *Node) {
    x.Prev = this.Tail.Prev
    x.Next = this.Tail

    this.Tail.Prev.Next = x
    this.Tail.Prev = x

    this.Len++
}

/* 删除双链表特定节点 */
func (this *LinkedList) Remove(x *Node) {
    x.Prev.Next = x.Next
    x.Next.Prev = x.Prev
    this.Len--
}

/* 删除双链表头部节点并返回 */
func (this *LinkedList) RemoveFirst() *Node {
    if this.Head.Next == this.Tail {
        return nil
    }

    x := this.Head.Next
    this.Remove(x)

    return x
}

/* 哈希链表类 */
type LinkedHashSet struct {
    keyToNode map[int]*Node
    cache LinkedList
}

/* 哈希链表类构造方法 */
func NewLinkedHashSet() *LinkedHashSet {
    return &LinkedHashSet{make(map[int]*Node), NewList()}
}

/* 向哈希链表添加元素 */
func (this *LinkedHashSet) AddRecently(key, val int) {
    x := &Node{key, val, nil, nil}
    this.cache.AddLast(x)
    this.keyToNode[key] = x
}

/* 删除哈希链表指定元素 */
func (this *LinkedHashSet) DeleteKey(key int) {
    x := this.keyToNode[key]
    this.cache.Remove(x)
    delete(this.keyToNode, key)
}

/* 删除哈希链表头部元素 */
func (this *LinkedHashSet) DeleteLeastRecently() *Node {
    detetedNode := this.cache.RemoveFirst()
    delete(this.keyToNode, detetedNode.Key)
    return detetedNode
}

/* 哈希链表长度 */
func (this *LinkedHashSet) Len() int {
    return this.cache.Len
}

type LFUCache struct {
    keyToVal  map[int]int             // key 映射为 val，用于记录 key 的值
    keyToFreq map[int]int             // key 映射为 freq，用于记录 key 的频率
    freqToKeys map[int]*LinkedHashSet  // freq 映射为 key 的哈希列表，用于找到最小频率且包含时序信息的 key

    minFreq int  // 记录最小频次
    cap     int  // 记录最大容量
}


func Constructor(capacity int) LFUCache {
    keyToVal := make(map[int]int)
    keyToFreq := make(map[int]int)
    freqToKeys := make(map[int]*LinkedHashSet)

    return LFUCache{keyToVal, keyToFreq, freqToKeys, 0, capacity}
}


func (this *LFUCache) Get(key int) int {
    if _, ok := this.keyToVal[key]; !ok {
        return -1
    }
    this.increaseFreq(key)  // 增加 key 对应的频率
    return this.keyToVal[key]
}


func (this *LFUCache) Put(key int, value int)  {
    // 注：测试用例有传入 0 容量的情况
    if this.cap <= 0 {
        return
    }

    // 如果 key 存在，只用更新它的 value，且增加对应频率
    if _, ok := this.keyToVal[key]; ok {
        this.keyToVal[key] = value
        this.increaseFreq(key)
        return
    }

    // 如果超出容量，移除最小频率的 key
    if this.cap <= len(this.keyToVal) {
        this.removeMinFreqKey()
    }

    // 插入 key 和 val
    this.keyToVal[key] = value
    this.keyToFreq[key] = 1
    if _, ok := this.freqToKeys[1]; !ok {
        this.freqToKeys[1] = NewLinkedHashSet()
    }
    this.freqToKeys[1].AddRecently(key, value)
    this.minFreq = 1
}

/* 两个频次相关的实用函数 */
func (this *LFUCache) removeMinFreqKey() {
    keyList := this.freqToKeys[this.minFreq]

    deletedNode := keyList.DeleteLeastRecently()
    if keyList.Len() == 0 {
        delete(this.freqToKeys, this.minFreq)
        // 由于此方法只会再插入新元素时调用，而插入后 minFreq 一定会更新为 1，因此这里不需要更新 minFreq 的值
    }

    delete(this.keyToVal, deletedNode.Key)
    delete(this.keyToFreq, deletedNode.Key)
}

func (this *LFUCache) increaseFreq(key int) {
    freq := this.keyToFreq[key]
    this.keyToFreq[key] = freq + 1  // 更新对应的频率

    // 在新的频率链表中加上它
    if _, ok := this.freqToKeys[freq + 1]; !ok {
        this.freqToKeys[freq + 1] = NewLinkedHashSet()
    }
    this.freqToKeys[freq + 1].AddRecently(key, this.keyToVal[key])

    // 在旧的频率链表中删除它
    this.freqToKeys[freq].DeleteKey(key)
    if this.freqToKeys[freq].Len() == 0 {
        delete(this.freqToKeys, freq)
        if freq == this.minFreq {
            this.minFreq++
        }
    }
}


/**
 * Your LFUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */