手把手教你用LinkedHashMap打造FIFO和LRU缓存系统

JAVA herman 176浏览
公告:“业余草”微信公众号提供免费CSDN下载服务(只下Java资源),关注业余草微信公众号,添加作者微信:xmtxtt,发送下载链接帮助你免费下载!
本博客日IP超过1800,PV 2600 左右,急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包,请加博主新的微信号:xttblog,之前的微信号好友位已满,备注:返现
所有面试题(java、前端、数据库、springboot等)一网打尽,请关注文末小程序

对于缓存来说,我相信很多人都不会陌生。一般的,对于常用的一些数据,基础数据等,也或者是为了高并发,比如抢购等把热点数据放入缓存中以实现高并发快速响应。

说到缓存,Redis、memcached 等在面试中属于必问的知识点了。虽然这些专门的缓存系统做的很强大,看起来很复杂,但底层的原理其实很简单。今天我们一起来通过 LinkedHashMap 来打造两个 FIFO 和 LRU 机制的缓存系统。

FIFO 很好理解,就是 First In First Out,先入先出。就和队列一样,先进队列的先出队列。根据这个 FIFO 的这个特点,我们就可以通过 LinkedHashMap 来实现这种机制的缓存系统了。

public class FIFOCache<K,V> extends LinkedHashMap<K, V> {
    private final int SIZE;
    public FIFOCache(int size) {
        super();
        SIZE = size;
    }
    /**
     * 重写淘汰机制
     * @param eldest
     * @return
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        //如果缓存存储达到最大值删除最后一个
        return size() > SIZE;
    }
}

上面几行代码就搞定了 FIFO 机制的缓存。测试代码也很简单,如下所示:

public static void main(String[] args) {
    //设置容量为10
    FIFOCache<Integer, Integer> map = new FIFOCache<Integer, Integer>(5);
    //放入5个数据
    for (int i = 0; i++ < 5;) {
        map.put(i, i);
    }
    //打印起始存储情况
    System.out.println("起始存储情况:"+map.toString());
    //存入一个已存在的数据,也就是命中一次缓存中的数据
    map.put(2, 2);
    //打印命中之后的情况
    System.out.println("命中一个已存在的数据:"+map.toString());
    //又存入缓存之外的数据
    map.put(6, 6);
    //打印又存储一个数据之后的情况
    System.out.println("新增一个数据后:"+map.toString());
}

测试结果截图如下所示:

FIFO 缓存源码实现

通过上面这个测试结果,可以看出,这个缓存系统并不完美。当我更新元素后,我想让它重新插入队列,相当于重新入队。因为它刚刚被更新过,说明使用频次可能更高一些。于是 LRU,这种缓存淘汰机制就应用而生了。

LRU 就是(Least Recently Used),最近最少使用,意思就是最近读取的数据放在最前面,最早读取的数据放在最后面,如果这个时候有新的数据进来,当缓存空间不够时,那么最后面存储的数据淘汰。实现代码如下所示:

public class LRUCache<K,V> extends LinkedHashMap<K, V> {
    private final int SIZE;
    public LRUCache(int size) {
        /** int initialCapacity, float loadFactor, boolean accessOrder
         * 这3个分别表示容量,加载因子和是否启用LRU规则
         */
        super(size, 0.75f, true);
        SIZE = size;
    }
    @Override
    protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
        return size() > SIZE;
    }
}

下面我们来看看测试代码:

public static void main(String[] args) {
    LRUCache<Integer, Integer> map = new LRUCache<Integer, Integer>(5);
    //放入5个数据
    for (int i = 0; i++ < 5; ) {
        map.put(i, i);
    }
    //打印起始存储情况
    System.out.println("起始存储情况:"+map.toString());
    map.get(3);
    //打印命中之后的情况
    System.out.println("命中一个已存在的数据:"+map.toString());
    //存入一个已存在的数据,也就是命中一次缓存中的数据
    map.put(5, 6);
    //打印命中之后的情况
    System.out.println("覆盖一个已存在的数据:"+map.toString());
    //又存入缓存之外的数据
    map.put(6, 6);
    //打印又存储一个数据之后的情况
    System.out.println("新增一个数据后:"+map.toString());
}

运行之后的效果截图如下所示:

LRU 缓存源码实现

关于缓存算法,还有 LFU 算法。这个代码较多,我后面单独来实现。关于本文的实现,其实还是非常基础的,比如关于线程安全问题,以及过期淘汰等问题可以根据自己的需要进行添加对应的功能。与代码相比,其实更重要的是编程思想,编程思路。

业余草公众号

最后,欢迎关注我的个人微信公众号:业余草(yyucao)!可加QQ1群:135430763(2000人群已满),QQ2群:454796847(已满),QQ3群:187424846(已满)。QQ群进群密码:xttblog,想加微信群的朋友,之前的微信号好友已满,请加博主新的微信号:xttblog,备注:“xttblog”,添加博主微信拉你进群。备注错误不会同意好友申请。再次感谢您的关注!后续有精彩内容会第一时间发给您!原创文章投稿请发送至532009913@qq.com邮箱。商务合作可添加助理微信进行沟通!

本文原文出处:业余草: » 手把手教你用LinkedHashMap打造FIFO和LRU缓存系统