缓存基础----LRU算法和FIFO算法的Java实现

小灰灰 2022-10-12 01:19 179阅读 0赞

Java里面实现LRU缓存算法的通常有两种选择，一种是自己设计数据结构：链表+HashMap（链表用来表示**位置**，哈希表用来**存储和查找**），另一种是使用Java中的LinkedHashMap。我们这边文章是使用Java的LinkedHashMap来实现缓存的LRU算法和FIFO算法。

### 一、LinkedHashMap实现缓存LRU算法 ###

LinkedHashMap有两种数据的存储方式，一种是按照数据的添加顺序存储，另一种是按照数据的访问顺序存储，默认情况下是按照数据的添加顺序存储的。即最近读取的数据放在链表头部，最早读取的数据放在链表尾部。并且LinkedHashMap还有一个判断是否删除老数据的方法，默认返回false，即不删除数据。我们通过LinkedHashMap实现LRU缓存就是继承LinkedHashMap类并重写父类的removeEldestEntry方法。代码如下：

/**
     * LinkedHashMap实现LRU算法
     * @author Administrator
     *
     */
    public class CacheLRU<K, V> extends LinkedHashMap<K, V>
    {
        private static final long serialVersionUID = 1L;
        
        /*
         * 元素最大值，当数据个数超过最大值时，就要删除一些很久没有被访问到的数据
         */
        private final int MAX_CACHE_SIZE;
        
        /**
         * CacheLRU构造函数，调用父类LinkedHashMap的构造函数
         * @param cacheSize 缓存数据的最大值
         */
        public CacheLRU(int cacheSize) {
            /*
             * 调用父类构造函数，当参数accessOrder为true时，即会按照访问顺序排序，最近访问的放在最前，最早访问的放在后面
             * (int) Math.ceil(cacheSize / 0.75) + 1  计算LinkedHashMap的初始化容量
             */
            super((int) Math.ceil(cacheSize / 0.75) + 1, 0.75f, true);
            //元素最大值
            MAX_CACHE_SIZE = cacheSize;
        }
        
        /**
         * 重写LinkedHashMap的removeEldestEntry方法，removeEldestEntry方法是LinkedHashMap自带的判断是否删除最老元素的方法，默认返回false，即不删除老数据
         */
        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            //当linkedhashmap中数据量大于指定的最大值时，返回true，就自动删除老数据
            return size() > MAX_CACHE_SIZE;
        }
    
    }

但是实际使用中这样写还是有些繁琐，更实用的方法时像下面这样写，省去了单独见一个类的麻烦

private final int cacheSize = 100;
    Map<String, Integer> map = new LinkedHashMap<String, Integer>((int) Math.ceil(cacheSize/0.75f) + 1, 0.75f, true) {
        @Override
        protected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {
        return size() > cacheSize;
        }
    };

### 二、LinkedHashMap实现缓存FIFO算法 ###

FIFO算法的核心思想是先进先出，即按照添加顺序最先添加的数据最先被删除。默认情况下LinkedHashMap就是按照数据的添加顺序存储的，所以实现FIFO算法时，我们只需重写下removeEldestEntry方法即可轻松实现一个FIFO缓存算法。代码如下：

public class CacheFIFO<K, V> extends LinkedHashMap<K, V>
    {
        private static final long serialVersionUID = 1L;
        
        /*
         * 元素最大值，当数据个数超过最大值时，就要删除一些很久没有被访问到数据
         */
        private final int MAX_CACHE_SIZE;
        
        /**
         * CacheFIFO构造函数，这里不用调用父类的LinkedHashMap构造函数
         * FIFO原则就是先进先出的，默认情况下LinkedHashMap就是按照添加顺序保存，所以不需要更改排序方式，只需要重写removeEldestEntry方法即可
         * @param cacheSize 缓存数据的最大值
         */
        public CacheFIFO(int cacheSize) {
            this.MAX_CACHE_SIZE = cacheSize;
        }
        
        /**
         * 重写LinkedHashMap的removeEldestEntry方法，removeEldestEntry方法是LinkedHashMap自带的判断是否删除最老元素的方法，默认返回false，即不删除老数据
         */
        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            //当linkedhashmap中数据量大于指定的最大值时，返回true，就自动删除老数据
            return size() > MAX_CACHE_SIZE;
        }
    
    }

简化版的实现代码如下：

private final int cacheSize = 5;
    LinkedHashMap<String, Integer> lru = new LinkedHashMap<String, Integer>() {
        @Override
        protected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {
        return size() > cacheSize;
        }
    };

### 三、调用示例 ###

测试代码如下：

public class CacheLRUTest
    {
    
        public static void main(String[] args)
        {
            System.out.println("===========================LRU LinkedHashMap实现开始===========================");
            CacheLRU<String, Integer> lru = new CacheLRU<String, Integer>(5);
            //存入数据，最大值为5
            for(int i=0; i<5; i++) {
                lru.put("test"+i, i);
            }
            System.out.println("目前所有缓存为：" +lru.toString());
            //最近访问的几个数据
            lru.get("test0");
            lru.get("test3");
            lru.get("test3");
            lru.get("test4");
            //新添加两个数据
            lru.put("test5", 5);
            lru.put("test6", 6);
            System.out.println("删除老数据后所有缓存为：" +lru.toString());
            System.out.println("===========================LRU LinkedHashMap实现结束===========================");
            System.out.println();
    
            System.out.println();
            System.out.println("===========================FIFO LinkedHashMap实现开始===========================");
            CacheFIFO<String, Integer> fifo = new CacheFIFO<String, Integer>(5);
            //存入数据，最大值为5
            for(int i=0; i<5; i++) {
                fifo.put("test"+i, i);
            }
            System.out.println("目前所有缓存为：" +fifo.toString());
            //最近访问的几个数据
            fifo.get("test1");
            fifo.get("test1");
            fifo.get("test2");
            fifo.get("test3");
            //新添加两个数据
            fifo.put("test5", 5);
            fifo.put("test6", 6);
            System.out.println("删除老数据后所有缓存为：" +fifo.toString());
            System.out.println("===========================FIFO LinkedHashMap实现结束===========================");
        }
    
    }

运行结果如下：

===========================LRU LinkedHashMap实现开始===========================
    目前所有缓存为：{test0=0, test1=1, test2=2, test3=3, test4=4}
    删除老数据后所有缓存为：{test0=0, test3=3, test4=4, test5=5, test6=6}
    ===========================LRU LinkedHashMap实现结束===========================
    
    
    ===========================FIFO LinkedHashMap实现开始===========================
    目前所有缓存为：{test0=0, test1=1, test2=2, test3=3, test4=4}
    删除老数据后所有缓存为：{test2=2, test3=3, test4=4, test5=5, test6=6}
    ===========================FIFO LinkedHashMap实现结束===========================