LFU(Least Frequently Used)
LFU (Least Frequently Used) 最近最不常用算法,它是根据频率维度来选择将要淘汰的元素,即删除访问频率最低的元素。如果两个元素的访问频率相同,则淘汰最久没被访问的元素。
也就是说 LFU 淘汰的时候会选择两个维度,先比较频率,选择访问频率最小的元素;如果频率相同,则按时间维度淘汰掉最久远的那个元素。
实现
LRU 的实现是一个哈希表加上一个双链表,而 LFU 则要复杂多了,需要用两个哈希表再加上 N 个双链表才能实现,我们先看看 LFU 的两个哈希表里面都存了什么。
第一个哈希表是 key-value 的哈希表 (以下简称 kv 哈希表)
这里的 key 就是输入的 key,没什么特别的。关键是 value,它的 value 不是一个简单的 value,而是一个节点对象。
节点对象 Node 包含了 key,value,以及频率,这个 Node 又会出现在第二个哈希表的 value 中。
至于为什么 Node 中又重复包含了 key,因为某些情况下我们不是通过 k-v 哈希表拿到 Node 的,而是通过其他方式获得了 Node,之后需要用 Node 中的 key 去 k-v 哈希表中做一些操作,所以 Node 中包含了一些冗余信息。
第二张哈希表,频率哈希表,这个就要复杂多了
这张哈希表中的 key 是频率,也就是元素被访问的频率 (被访问了 1 次,被访问了两次等等),它的 value 是一个双向链表。
刚才说的 Node 对象,现在又出现了,这里的 Node 其实是双向链表中的一个节点。
第一张图中我们介绍了 Node 中包含了一个冗余的 key,其实它还包含了一个冗余的频率值,因为某些情况下,我们需要通过 Node 中的频率值,去频率哈希表中做查找,所以也需要一个冗余的频率值。
下面我们将两个哈希表整合起来看看完整的结构:
k-v 哈希表中 key1 指向一个 Node,这个 Node 的频率为 1,位于频率哈希表中 key=1 下面的双链表中 (处于第一个节点)。
具体操作
下面我们来看看具体操作,get 操作相对简单一些,我们就先说 get 操作吧。
Get
get 操作的具体逻辑大致是这样:
- 如果 key 不存在则返回 - 1
- 如果 key 存在,则返回对应的 value,同时:
- 将元素的访问频率 + 1
- 将元素从访问频率 i 的链表中移除,放到频率 i+1 的链表中
- 如果频率 i 的链表为空,则从频率哈希表中移除这个链表
第一个很简单就不用说了,我们看下第二点的执行过程
假设某个元素的访问频率是 3,现在又被访问了一次,那么就需要将这个元素移动到频率 4 的链表中。如果这个元素被移除后,频率 3 的那个链表变成空了,即只剩下头结点和尾节点) 就需要删除这个链表,同时删除对应的频率(也就是删除 key=3)。
Put
put 操作就要复杂多了,大致包括下面几种情况
- 如果 key 已经存在,修改对应的 value,并将访问频率 + 1
- 将元素从访问频率 i 的链表中移除,放到频率 i+1 的链表中
- 如果频率 i 的链表为空,则从频率哈希表中移除这个链表
- 如果 key 不存在
- 缓存超过最大容量,则先删除访问频率最低的元素,再插入新元素
- 新元素的访问频率为 1,如果频率哈希表中不存在对应的链表,则需要创建
- 缓存没有超过最大容量,则插入新元素
- 新元素的访问频率为 1,如果频率哈希表中不存在对应的链表,则需要创建
- 缓存超过最大容量,则先删除访问频率最低的元素,再插入新元素
我们在代码实现中还需要维护一个 minFreq 的变量,用来记录 LFU 缓存中频率最小的元素,在缓存满的时候,可以快速定位到最小频繁的链表,以达到 O (1) 时间复杂度删除一个元素。
具体做法是:
- 更新 / 查找的时候,将元素频率 + 1,之后如果 minFreq 不在频率哈希表中了,说明频率哈希表中已经没有元素了,那么 minFreq 需要 + 1,否则 minFreq 不变。
- 插入的时候,这个简单,因为新元素的频率都是 1,所以只需要将 minFreq 改为 1 即可。
我们重点看下缓存超过最大容量时是怎么处理的