缓存算法
算法 

众所周知，内存的读取速度比硬盘类存储设备快的多。为了降低硬件设备的负载，提高响应速度，增加吞吐率，我们可以将最近使用过，并且将来还要使用的数据缓存到内存中。因为内存的容量是有限的，所以根据怎么选择将来还要使用的数据，产生了各种缓存算法。

一些术语

  1. 命中：当客户发起一个请求，如果在缓存中，就成为缓存命中
  2. Cache Miss：如果还有缓存空间，没有命中的就会被存储到缓存中；如果缓存满了，而又没命中缓存，那么久会按照缓存算法，用新对象替换旧对象。
  3. 存储成本：将数据放到缓存所需要的时间和空间
  4. 失效：当存在缓存中的数据需要更新时，缓存中的这个数据就失效了

Least Frequently Used (LFU):

LFU算法认为：如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小。

命中率

LFU的命中率还要看数据的访问顺序。一旦访问内容发生较大的变化，LFU需要更长的时间来适应。因为他是根据频率来淘汰数据的，新的数据访问频率低，很容易被淘汰掉。这样会导致之前经常而现在不被访问的数据，一直赖在缓存中。所以，一般相比LFU，会采用LRU算法

Least Recently Used (LRU):

LRU算法认为：如果数据最近被访问过，那么将来被访问的几率也更高。 LRU算法将最近最少使用的数据淘汰。最近使用的数据会被放到缓存的顶部，当缓存达到容量上限时，将底部的数据移除。

命中率

如果存在热点数据，LRU的命中率比较高。但是针对偶然性、周期性或者随机性的批量操作会导致LRU的命中率急剧下降，缓存污染情况也比较严重。

复杂度

实现简单，java中可以通过扩展LinkedHashMap来实现。

import java.util.LinkedHashMap;
import java.util.Map;
//扩展LinkedHashMap，实现LRU
public class LRUCache<K,V> extends LinkedHashMap<K,V>{
    //定义缓存的容量
    private int capacity;
    private static final long serialVersionUID = 1L;
    //带参数的构造器
    public LRUCache(int capacity){
        //调用LinkedHashMap的构造器，传入以下参数
        super(capacity);
        this.capacity=capacity;
    }
    //实现LRU的关键方法，如果map里面的元素个数大于了缓存最大容量，则删除链表的顶端元素
    @Override
    public boolean removeEldestEntry(Map.Entry<K, V> eldest){
        System.out.println(eldest.getKey() + "=" + eldest.getValue());
        return size() > capacity;
    }
}

Least Recently Used 2 (LRU2)：

LRU2算法认为： 将被两次访问过的对象放入缓存池，当缓存池满了，会移除两次最少使用的缓存对象。因为要跟踪对象两次，访问负载就会随着缓存池的增加而增加，所以不能用于大容量的缓存池。

Two Queues (2Q)：

将被访问的数据放到LRU的缓存中，如果这个对象再一次被访问，就将它转移到更大的LRU缓存中。移除对象是为了保持第一个缓存池是第二个缓存池的1/3，当缓存访问负载是固定的时候，把LRU换成LRU2，比增加缓存容量更好，是adoptive to access模式

Adaptive Replacement Cache (ARC):

介于LRU和LFU之间。由两个LRU组成，第一个L1，包含的条目是最近值被使用过一次的，而L2，包含的是最近被使用过两次的数据。L1放的是新对象，L2放的是常用对象。

Most Recently Used (MRU):

移除最近最多被使用的对象。每当一次缓存记录的使用，就会被放到栈顶，当栈满了，将栈顶的对象移除。

First In First Out (FIFO):

先进先出，低负载的算法，通过队列跟踪所有的缓存对象，最近最常用的对象放在后边，当缓存容量满的时，会移除前边缓存的更早的对象。很快，但是不适用

local_offer #算法 
navigate_before navigate_next