前段时间去网易面试，被这个问题卡住，先做总结如下：
常用缓存淘汰算法
- FIFO类：First In First Out，先进先出。判断被存储的时间，离目前最远的数据优先被淘汰。
- LRU类：Least Recently Used，最近最少使用。判断最近被使用的时间，目前最远的数据优先被淘汰。
- LFU类：Least Frequently Used，最不经常使用。在一段时间内，数据被使用次数最少的，优先被淘汰。
FIFO类 先进先出
※ FIFO
原理： 按照“先进先出（First In，First Out）”的原理淘汰数据
实现：
1. 新访问的数据插入FIFO队列尾部，数据在FIFO队列中顺序移动；
2. 淘汰FIFO队列头部的数据；
特点：
>> 命中率 命中率很低，因为命中率太低，实际应用中基本上不会采用。
>> 复杂度 简单
>> 代价 实现代价很小
※ Second Chance
原理： FIFO改进版，如果被淘汰的数据之前被访问过，则给其第二次机会（Second Chance）
实现：
每个数据会增加一个访问标志位，用于标识此数据放入缓存队列后是否被再次访问过。
如上图，A是FIFO队列中最旧的数据，且其放入队列后没有被再次访问，则A被立刻淘汰；否则如果放入队列后被访问过，则将A移到FIFO队列头，并且将访问标志位清除。
如果所有的数据都被访问过，则经过一次循环后就会按照FIFO的原则淘汰数据。
特点：
>> 命中率 命中率比FIFO高。
>> 复杂度 与FIFO相比，需要记录数据的访问标志位，且需要将数据移动
>> 代价 实现代价比FIFO高
※ Clock
原理： Clock是Second Chance的改进版，通过一个环形队列，避免将数据在FIFO队列中移动
实现：
l 当前指针指向C，如果C被访问过，则清除C的访问标志，并将指针指向D；
l 如果C没有被访问过，则将新数据插入到C的位置,将指针指向D。
特点：
>> 命中率 命中率比FIFO高，和Second Chance一样
>> 复杂度 与FIFO相比，需要记录数据的访问标志位，且需要将数据指针移动
>> 代价 实现代价比FIFO高，比Second Chance低
FIFO类对比
|
命中率 |
Clock = Second Chance > FIFO |
|
复杂度 |
Second Chance > Clock > FIFO |
|
代价 |
Second Chance > Clock > FIFO |
由于FIFO类算法命中率相比其他算法要低不少，因此实际应用中很少使用此类算法