缓存淘汰策略

常见的缓存淘汰策略有三种：
1.FIFO（First In First out）：先见先出，淘汰最先近来的页面，新进来的页面最迟被淘汰（队列）。
2.LRU（Least recently used）:最近最少使用，淘汰最近不使用的页面。
3.LFU（Least frequently used）: 最近使用次数最少， 淘汰使用次数最少的页面。
下面进行详细介绍：

一、FIFO

按照“先进先出（First In，First Out）”的原理淘汰数据。如果一个数据最先进入缓存中，则应该最早淘汰掉。
1、利用一个双向链表保存数据，
2、当来了新的数据之后便添加到链表末尾，
3、如果Cache存满数据，则把链表头部数据删除，
4、然后把新的数据添加到链表末尾。
5、在访问数据的时候，如果在Cache中存在该数据的话，则返回对应的value值；
6、否则返回-1。如果想提高访问效率，可以利用hashmap来保存每个key在链表中对应的位置。

二、LRU

least recently used，最近最少使用，如果数据最近被访问过，那么将来访问的几率也很高。
1、新数据插入到链表头部；
2、每当缓存命中（即缓存数据被访问），则将数据移到链表头部；
3、当链表满的时候，将链表尾部的数据丢弃。

三、LFU

最近最少使用算法。如果一个数据在最近一段时间内使用次数最少，那么将来一段时间使用的可能性也很少。
1、新加入数据插入到队列尾部（因为引用计数为1）；
2、 队列中的数据被访问后，引用计数增加，队列重新排序；
3、当需要淘汰数据时，将已经排序的列表最后的数据块删除。