简述

缓存算法是指令的一个明细表，用于提示计算设备的缓存信息中哪些条目应该被删去。我们经常使用的有FIFO、LRU和LFU。今天我们来看看这三种缓存算法的区别。

FIFO算法

FIFO算法是一种比较容易实现的算法，意思是first in first out，先进先出。如果一个数据越早存在，未来访问可能性越小小，那么可以用FIFO算法，空间满的时候，把最先进入的数据淘汰掉。
实现其实很简单。我们维护一个FIFO队列，按照时间顺序将数据放入队列中。当队列满后，把最先进队列的数据淘汰掉，然后在队列尾部插入最新数据即可。
判断一个页面置换算法的优劣指标是缺页率。FIFO算法在某个特定的时刻，缺页率会随分配页面增加而增加，这是Belady现象。产品原因是因为被置换掉的内存页往往是被频繁访问的，FIFO算法会使这些被频繁访问的页面频繁替换和重新申请内存，从而导致缺页率增加。

LRU算法

LRU算法全称是Least Recently Used最近最久未使用算法。他是一种常见的缓存算法，我们使用的本地缓存、Redis等都有使用。LRU算法的思想是：如果一个数据在最近一段时间没有被访问到，那么该数据在未来被访问的可能性能效，所以当空间满后，最近未使用的数据最先被淘汰。
我们可以使用双向链表+哈希表实现，Java中LinkedHashMap也有此功能。

LinkedHashMap实现LRU

我们可以使用LinkHashMap简单实现LRU。

public class LRUCache<K, V> extends LinkedHashMap<K, V> {

    private final int size;


    public LRUCache(int size) {
        // 当accessOrder设置为false时，会按照插入顺序进行排序; 当accessOrder为true是，会按照访问顺序
        super(16, 0.75f, true);
        this.size = size;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        // 大于设置的大小时候，移除最老的键值对
        return size() > size;
    }

    public static void main(String[] args) {
        LRUCache<Integer, Integer> cache = new LRUCache<>(10);
        IntStream.range(0, 10).forEach(value -> cache.put(value, value));
        System.out.println("all cache              : " + cache.toString());
        Integer number = cache.get(0);
        System.out.println("all cache after get 0  : " + cache.toString());
        number = cache.get(5);
        System.out.println("all cache after get 5  : " + cache.toString());
        cache.put(11, 11);
        System.out.println("all cache after put 11 : " + cache.toString());
        cache.put(15, 15);
        System.out.println("all cache after put 15 : " + cache.toString());
    }
}

输出结果：

all cache              : {0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9}
all cache after get 0  : {1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9, 0=0}
all cache after get 5  : {1=1, 2=2, 3=3, 4=4, 6=6, 7=7, 8=8, 9=9, 0=0, 5=5}
all cache after put 11 : {2=2, 3=3, 4=4, 6=6, 7=7, 8=8, 9=9, 0=0, 5=5, 11=11}
all cache after put 15 : {3=3, 4=4, 6=6, 7=7, 8=8, 9=9, 0=0, 5=5, 11=11, 15=15}

LFU算法

LFU全称是Least Frequently Used最近最少使用算法。LFU算法的思想是：如果一个数据最近的一段时间内很少被访问到，那么可以认为它在将来被访问的可能性也很小，所以当空间满时，被访问次数最小的数据会先被淘汰。
至于实现方式，LFU算法本质上就是一个top问题，排除最近最少使用的数据。我们可以使用二项堆来查询最小频率的元素，使用小顶堆+哈希表。

参考

缓存算法