缓存算法是指令的一个明细表，用于提示 计算设备的 缓存信息中 哪些条目应该被删去。常见缓存算法包括FIFO、LFU、LRU、ARC、MRU。
1、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存满数据，则把链表头部数据删除，然后把新的数据添加到链表末尾。在访问数据的时候，如果在Cache中存在该数据的话，则返回对应的value值；否则返回-1。如果想提高访问效率，可以利用hashmap来保存每个key在链表中对应的位置。
2、LRU
LRU全称是Least Recently Used，即最近最久未使用的意思。LRU算法的设计原则是：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。
用什么数据结构来实现LRU算法呢？
可能大多数人都会想到：用一个数组来存储数据，给每一个数据项标记一个访问时间戳，每次插入新数据项的时候，先把数组中存在的数据项的时间戳自增，并将新数据项的时间戳置为0并插入到数组中。每次访问数组中的数据项的时候，将被访问的数据项的时间戳置为0。当数组空间已满时，将时间戳最大的数据项淘汰。
这种实现思路很简单，但是有什么缺陷呢？需要不停地维护数据项的访问时间戳，另外，在插入数据、删除数据以及访问数据时，时间复杂度都是O(n)。
那么有没有更好的实现办法呢？
有一种流行的思路是利用链表和哈希表。当需要插入新的数据项的时候，如果新数据项在链表中存在（一般称为命中），则把该节点移到链表头部，如果不存在，则新建一个节点，放到链表头部，若缓存满了，则把链表最后一个节点删除即可。在访问数据的时候，如果数据项在链表中存在，则把该节点移到链表头部，否则返回-1。这样一来在链表尾部的节点就是最近最久未访问的数据项。详细的实现可以参考我的另一篇博文：LRU缓存算法到底是怎么一回事？
3、LFU
LFU（Least Frequently Used）最近最少使用算法。它是基于“如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小”的思路。
LFU和LRU算法的不同之处，LRU的淘汰规则是基于访问时间，而LFU是基于访问次数的。
用什么数据结构来实现LFU算法呢？
有一种实现方式是使用三个HashMap，一个Map维护Key-Value的关系，一个Map维护Key-Freq的关系，前两个Map可以保证查找和插入是O(1)的时间复杂度，不能保证删除也是O(1)的时间复杂度，因此还需要使用一个类似LinkList的数据结构维护插入的时间顺序，并且还需要肯定是需要freq到key的映射，用来找到freq最小的key，因此可以维护一个Map<Integer，LinkedHashSet>类型的Map，这是个一对多的关系，一方就是频率，多方就是key，因为具有某个频率的key可能有多个，并且在使用一个变量minFreq维护系统当前访问频次最低的次数，当表满了的时候直接删除minFreq对应的LinkedHashSet中的第一个key就好了。详细的代码实现可以参考我的另一篇博文：LFU缓存算法到底是怎么一回事？
4、自适应缓存替换算法(ARC)
由IBM Almaden研究中心开发，这个缓存算法同时跟踪记录LFU和LRU，以及驱逐缓存条目，来获得可用缓存的最佳使用。
5、最近最常使用算法（MRU）
这个缓存算法最先移除最近最常使用的条目。一个MRU算法擅长处理一个条目越久，越容易被访问的情况。
