FIFO算法
FIFO（First in First out），先进先出。其实在操作系统的设计理念中很多地方都利用到了先进先出的思想，比如作业调度（先来先服务），为什么这个原则在很多地方都会用到呢？因为这个原则简单、且符合人们的惯性思维，具备公平性，并且实现起来简单，直接使用数据结构中的队列即可实现。
在 FIFO Cache 设计中，核心原则就是：如果一个数据最先进入缓存中，则应该最早淘汰掉。也就是说，当缓存满的时候，应当把最先进入缓存的数据给淘汰掉。在 FIFO Cache 中应该支持以下操作;
get(key)：如果 Cache 中存在该 key，则返回对应的 value 值，否则，返回 -1；set(key,value)：如果 Cache 中存在该 key，则重置 value 值；如果不存在该 key，则将该 key 插入到到 Cache 中，若 Cache 已满，则淘汰最早进入 Cache 的数据。
举个例子：假如 Cache 大小为 3，访问数据序列为 set(1,1),set(2,2),set(3,3),set(4,4),get(2),set(5,5)
则 Cache 中的数据变化为：
1 | (1,1) set(1,1) |
那么利用什么数据结构来实现呢？
下面提供一种实现思路：
利用一个双向链表保存数据，当来了新的数据之后便添加到链表末尾，如果 Cache 存满数据，则把链表头部数据删除，然后把新的数据添加到链表末尾。在访问数据的时候，如果在 Cache 中存在该数据的话，则返回对应的 value 值；否则返回 -1。如果想提高访问效率，可以利用 hashmap 来保存每个 key 在链表中对应的位置。
LFU 算法
LFU（Least Frequently Used）最近最少使用算法。它是基于“如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小”的思路。
注意 LFU 和 LRU 算法的不同之处，LRU 的淘汰规则是基于访问时间，而 LFU 是基于访问次数的。举个简单的例子：
假设缓存大小为 3，数据访问序列为 set(2,2),set(1,1),get(2),get(1),get(2),set(3,3),set(4,4)，
则在 set(4,4) 时对于 LFU 算法应该淘汰 (3,3)，而 LRU 应该淘汰 (1,1)。
那么 LFU Cache 应该支持的操作为：
get(key)：如果 Cache 中存在该 key，则返回对应的 value 值，否则，返回 -1；set(key,value)：如果 Cache 中存在该 key，则重置 value 值；如果不存在该 key，则将该 key 插入到到 Cache 中，若 Cache 已满，则淘汰最少访问的数据。
为了能够淘汰最少使用的数据，因此 LFU 算法最简单的一种设计思路就是 利用一个数组存储数据项，用 hashmap 存储每个数据项在数组中对应的位置，然后为每个数据项设计一个访问频次，当数据项被命中时，访问频次自增，在淘汰的时候淘汰访问频次最少的数据。这样一来的话，在插入数据和访问数据的时候都能达到 $O(1)$ 的时间复杂度，在淘汰数据的时候，通过选择算法得到应该淘汰的数据项在数组中的索引，并将该索引位置的内容替换为新来的数据内容即可，这样的话，淘汰数据的操作时间复杂度为 $O(n)$。
另外还有一种实现思路就是利用小顶堆+hashmap，小顶堆插入、删除操作都能达到 $O(logn)$ 时间复杂度，因此效率相比第一种实现方法更加高效。
LRU
LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。
- 新数据插入到链表头部；
- 每当缓存命中（即缓存数据被访问），则将数据移到链表头部；
- 当链表满的时候，将链表尾部的数据丢弃。
过程如下：
- 最开始时，内存空间是空的，因此依次进入 A、B、C 是没有问题的
- 当加入 D 时，就出现了问题，内存空间不够了，因此根据 LRU 算法，内存空间中 A 待的时间最为久远，选择 A，将其淘汰
- 当再次引用 B 时，内存空间中的 B 又处于活跃状态，而 C 则变成了内存空间中，近段时间最久未使用的
- 当再次向内存空间加入 E 时，这时内存空间又不足了，选择在内存空间中待的最久的C将其淘汰出内存，这时的内存空间存放的对象就是 E->B->D