NOTE
3.1 缓存替换策略
1. 是什么 缓存能提高查找效率，但是缓存空间是有限的，需要把用不到的数据淘汰出缓存 2. 分类 2.1. FIFO 2.1.1. 是什么 First In First Out：优先淘汰最早进入被缓存的数据 2.1.2. 实现 队列即可 2.2. LRU 2.2.1. 是什么 Least Recen
这是历史学习笔记，可能存在过时或不完整的理解。
1. 是什么
缓存能提高查找效率，但是缓存空间是有限的，需要把用不到的数据淘汰出缓存
2. 分类
2.1. FIFO
2.1.1. 是什么
First In First Out：优先淘汰最早进入被缓存的数据
2.1.2. 实现
队列即可
2.2. LRU
2.2.1. 是什么
Least Recently Used【最近最少使用】：优先淘汰最久未被使用访问过的数据
- 
假设缓存的size是4, 初始状态都为NULL，左边为head，右边为tail，即最近最少使用的在head，最新插入的数据在tail
- 初始状态
NULL NULL NULL NULL - 加入1
NULL NULL NULL 1 - 加入2
NULL NULL 1 2 - 加入3
NULL 1 2 3 - 加入4
1 2 3 4 - 加入0，则head位置的1被驱逐出去
2 3 4 0 - 加入2，后面的2移动到tail
3 4 0 2
2.2.2. 实现
- HashMap+双向链表
- 设计LRU缓存结构.md（原链接已失效）
2.2.3. 问题
偶发性的、周期性的批量查询操作（包含冷数据）会淘汰掉大量的热点数据，导致 LRU 命中率急剧下降，缓存污染情况比较严重
2.3. LFU
2.3.1. 是什么
Least Frequently Used：最近最不常用。优先淘汰最不经常使用的数据
- 
2.3.2. 实现
相比LRU，这个是给每个缓存item加了一个访问频次，根据访问频次来决定顺序
2.3.3. 问题
早期的热点数据可能一直占用空间，比如缓存度量时间是 1 小时（数据根据最近一小时内的访问次数排序），则平均每小时访问 1000 次的数据可能会比前一个小时内访问次数为 1001 的数据更优先剔除掉