LFU算法实现笔记
LFU算法概述
- 名称: Least Frequently Used（最不经常使用）
- 用途: 缓存淘汰策略
- 核心思想: 根据缓存访问次数进行排序，优先淘汰访问次数最少的缓存项
LFU列表操作
-
写入缓存
- 新增缓存: 当缓存不存在时，添加到访问次数为1的链表头部，超过容量时删除尾部节点。
- 更新缓存: 当缓存已存在时，更新值并增加访问次数，移动至相应访问次数链表的头部。
-
读取缓存
- 缓存不存在: 返回null或其他默认值。
- 缓存存在: 返回缓存值，增加访问次数，并移动至相应访问次数链表的头部。
LFU算法设计思路
- 数据结构选择: 使用链表，因为频繁进行节点的新增和删除。
- 快速定位: 使用哈希表，key为访问次数，value为缓存节点链表。
- 虚拟头节点: 通过
head.next快速定位访问次数链表的头节点。 - 最小访问次数链表: 使用
minFreq变量记录，并用双向链表和虚拟尾节点快速定位尾节点。
代码实现
- 核心思想: 双哈希表
- 类定义:
LFUCache- 成员变量:
size: 当前缓存大小cap: 最大容量minFreq: 最小访问次数keyMap: 缓存key到节点的映射freqMap: 访问次数到链表的映射
- 方法:
get(int key): 根据key获取缓存值put(int key, int value): 添加或更新缓存项
- 成员变量:
get方法流程
- 检查key是否存在于
keyMap。 - 如果存在，获取节点，更新访问次数，移动至相应访问次数链表头部。
- 如果不存在，返回-1。
put方法流程
- 检查key是否存在于
keyMap。 - 如果不存在，且缓存已满，则删除
minFreq链表尾部节点。 - 添加或更新节点，更新访问次数，移动至相应访问次数链表头部。
辅助类定义
MLinkedNode: 链表节点，包含key、value、访问次数及前后指针。MLinkedList: 双向链表，包含虚拟头尾节点，提供添加和删除节点的方法。
使用示例
- 实例化
LFUCache对象。 - 使用
get(key)和put(key, value)方法进行操作。
总结
LFU算法通过维护一个按访问次数排序的缓存列表，实现了高效的缓存淘汰机制。通过双哈希表和双向链表的设计，算法能够快速地进行缓存的读写操作，同时保持较低的时间复杂度。