LRU和LFU缓存策略
1. LRU（Least Recently Used）
定义
LRU 是一种基于时间的缓存淘汰策略，其核心思想是：如果一个数据最近被访问过，那么在未来一段时间内被再次访问的可能性较高；反之，如果一个数据很久没有被访问过，那么它在未来被访问的可能性较低。因此，当缓存空间不足时，优先淘汰最久未被访问的数据。
实现方式
-
数据结构：通常使用一个双向链表和一个哈希表来实现。
-
双向链表：用于记录数据的访问顺序。最近访问的数据放在链表头部，最久未访问的数据放在链表尾部。
-
哈希表：用于快速定位数据在双向链表中的位置，键是数据的标识符，值是对应节点的指针。
-
-
操作逻辑：
-
访问数据：
-
如果数据在缓存中，将其从当前位置移动到双向链表的头部（表示最近访问）。
-
如果数据不在缓存中，直接返回不存在。
-
-
插入数据：
-
如果数据已存在，更新其值，并将其移动到双向链表的头部。
-
如果数据不存在，且缓存未满，直接插入到双向链表头部。
-
如果缓存已满，删除双向链表尾部的数据（最久未访问的数据），然后插入新数据到头部。
-
-
删除数据：
-
直接删除双向链表尾部的数据。
-
-
优点
-
实现简单：逻辑清晰，容易实现。
-
时间复杂度低：查找、插入和删除操作的时间复杂度均为 O(1)。
-
性能较好：在大多数场景下，能够较好地利用缓存空间。
缺点
-
对突发访问不友好：如果一个数据很久未被访问，但突然被频繁访问，LRU 无法快速响应其重要性变化。
-
容量限制问题：如果缓存容量较小，可能会频繁淘汰数据，导致缓存命中率较低。
2. LFU（Least Frequently Used）
定义
LFU 是一种基于频率的缓存淘汰策略，其核心思想是：如果一个数据被访问的频率较高，那么它在未来被访问的可能性也较高；反之，如果一个数据被访问的频率较低，那么它在未来被访问的可能性较低。因此，当缓存空间不足时，优先淘汰访问频率最低的数据。
实现方式
-
数据结构：通常使用一个哈希表和一个频率队列来实现。
-
哈希表：用于快速定位数据，键是数据的标识符，值是数据的节点。
-
频率队列：用于记录每个频率对应的节点集合。每个频率对应一个双向链表，存储访问频率相同的数据。
-
-
操作逻辑：
-
访问数据：
-
如果数据在缓存中，将其从当前频率的双向链表中移除，并将其加入到频率加1的双向链表中。
-
如果数据不在缓存中，直接返回不存在。
-
-
插入数据：
-
如果数据已存在，更新其值，并将其频率加1。
-
如果数据不存在，且缓存未满，直接插入到频率为1的双向链表中。
-
如果缓存已满，删除频率最低的双向链表中的尾部数据（访问频率最低的数据），然后插入新数据。
-
-
删除数据：
-
直接删除频率最低的双向链表中的尾部数据。
-
-
优点
-
对突发访问友好：能够快速响应数据访问频率的变化。
-
缓存命中率较高：在某些场景下，比 LRU 更能准确地预测未来会被访问的数据。
缺点
-
实现复杂：需要维护多个频率队列，逻辑较为复杂。
-
时间复杂度较高：查找、插入和删除操作的时间复杂度通常为 O(log n) 或 O(n)，具体取决于实现方式。
3. LRU 和 LFU 的对比
表格
复制
| 特性 | LRU | LFU |
|---|---|---|
| 淘汰依据 | 最久未被访问 | 访问频率最低 |
| 实现复杂度 | 简单 | 复杂 |
| 时间复杂度 | O(1) | O(log n) 或 O(n) |
| 对突发访问的响应 | 不友好 | 友好 |
| 适用场景 | 访问模式较为规律，数据的访问时间间隔较短 | 访问模式较为随机，数据的访问频率差异较大 |
4. 实际应用场景
-
LRU 适用场景：
-
数据访问模式较为规律，例如 Web 缓存、数据库查询缓存等。
-
缓存容量较大，能够容纳大部分热点数据。
-
-
LFU 适用场景：
-
数据访问模式较为随机，例如分布式缓存、文件系统缓存等。
-
对缓存命中率要求较高，且需要快速响应突发访问。
-