使用LinkedHashMap实现一个简易的LRU缓存

超、凢脫俗 2022-02-02 16:13 387阅读 0赞

对于缓存系统，我们在开发中经常用到的，除了本地缓存，还有像memcached、redis这样优秀的分布式缓存服务器，在这些缓存服务器中，有一个经常听说的术语，叫做淘汰策略，也就是当系统中缓存越来越多时，需要执行一定的策略，来实现缓存的合理利用，下图是redis配置文件中关于淘汰策略的相关配置：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwZW9wbA_size_16_color_FFFFFF_t_70][]

在redis提供的这些可选择的淘汰策略中，有一个叫做LRU的组合策略，下面也有了说明：LRU means Least Recently Used，也就是最近最少使用的，当触发淘汰策略时，会找出最近最少使用的缓存进行淘汰，下面就使用Java中自带的LinkedHashMap来实现这个LRU的缓存系统。

对于本地的缓存系统，一般使用集合来实现，最常用的就是HashMap，存储键值对，但是缓存越来越多时，想要淘汰其中一些不常用的缓存时，就比较麻烦，首先要标记哪些缓存是常用的，哪些是不常用的，淘汰的时候还要进行遍历，影响性能，好在JDK中提供了一个集合类，可以简易实现一个LRU的缓存系统，那就是LinkedHashMap。

LinkedHashMap是由数组+链表+红黑树的结构实现的，它的构造方法中，有一个是这样的：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwZW9wbA_size_16_color_FFFFFF_t_70 1][]

注意第三个参数，boolean accessOrder，这个参数默认为false，从它的注释说明来看，当参数为true时，按照访问顺序，当参数为false时，按照插入顺序，这就为我们实现一个LRU的缓存系统提供了很大的遍历，因为我们要利用这个访问顺序来实现。再来看另外一个方法：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwZW9wbA_size_16_color_FFFFFF_t_70 2][]

顾名思义，就是移除最老的那些元素，可以通过重写这个方法来控制缓存元素的删除，当缓存满了后，就可以通过返回true删除最久未被使用的元素，达到LRU的要求。多说无益，上代码。

package com.zjl.test;
    
    import java.util.LinkedHashMap;
    import java.util.Map;
    import java.util.Set;
    
    public class SimpleLRUCache<K, V> {
        private final int MAX_CACHE_SIZE;
        private final float DEFAULT_LOAD_FACTORY = 0.75f;
    
        LinkedHashMap<K, V> map;
    
        public SimpleLRUCache(int cacheSize) {
            MAX_CACHE_SIZE = cacheSize;
            int capacity = (int)Math.ceil(MAX_CACHE_SIZE / DEFAULT_LOAD_FACTORY) + 1;
            map = new LinkedHashMap<K, V>(capacity, DEFAULT_LOAD_FACTORY, true) {
    			private static final long serialVersionUID = 1L;
    			@Override
                protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                    return size() > MAX_CACHE_SIZE;
                }
            };
        }
    
        public synchronized void put(K key, V value) {
            map.put(key, value);
        }
        public synchronized V get(K key) {
            return map.get(key);
        }
        public synchronized void remove(K key) {
            map.remove(key);
        }
        public synchronized Set<Map.Entry<K, V>> getAll() {
            return map.entrySet();
        }
        @Override
        public String toString() {
            StringBuilder stringBuilder = new StringBuilder();
            for (Map.Entry<K, V> entry : map.entrySet()) {
                stringBuilder.append(String.format("%s: %s  ", entry.getKey(), entry.getValue()));
            }
            return stringBuilder.toString();
        }
    }

下面就来测试一下，大家都知道，NBA每队首发球员都是5人，就那这个来举例：

package com.zjl.test;
    
    public class LRUTest {
    	public static void main(String[] args) {
    		SimpleLRUCache<String, String> lru = new SimpleLRUCache<>(5);
            lru.put("球员1", "杜兰特");
            lru.put("球员2", "表妹");
            lru.put("球员3", "库里");
            System.out.println(lru);
            lru.get("球员1");
            System.out.println(lru);
            lru.put("球员4", "一哥");
            lru.put("球员5", "汤姆");
            System.out.println(lru);
            lru.put("球员6", "格林");
            System.out.println(lru);
    	}
    }

运行结果如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwZW9wbA_size_16_color_FFFFFF_t_70 3][]

可以看出，当我们访问杜兰特时，他的位置就变成的最新的位置，继续添加首发，会综合访问顺序和之后的添加作出一个合理的顺序，而这时追蛋格林必须要求首发，就把表妹给淘汰掉了！

重点在这个get()方法，当我们get时，这个集合就会把元素进行LRU的策略排序，进入源码来看究竟：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwZW9wbA_size_16_color_FFFFFF_t_70 4][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwZW9wbA_size_16_color_FFFFFF_t_70 5][]

它的注释简单，但是特别明了，move node to last，无须多言，源码就是最好的解释，开源的精神不仅仅在于贡献，更是让你知其然，并知其所以然，这样结合源码，一个简易的LRU缓存的核心就实现了！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwZW9wbA_size_16_color_FFFFFF_t_70]: /images/20220202/78e6eb19e08d4870934d811da20d2871.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwZW9wbA_size_16_color_FFFFFF_t_70 1]: /images/20220202/1d2438a4b82c44ec8f29da521bfdc4e2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwZW9wbA_size_16_color_FFFFFF_t_70 2]: /images/20220202/0b92bf474a2b45cdb30f4a090cd8f5d4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwZW9wbA_size_16_color_FFFFFF_t_70 3]: /images/20220202/3366a206b7f549fc842b767dfa6bada3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwZW9wbA_size_16_color_FFFFFF_t_70 4]: /images/20220202/c79443ab0f3548aabdaf2835a98a8e4f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwZW9wbA_size_16_color_FFFFFF_t_70 5]: /images/20220202/e9a8e50385ad49d48fe9d0574958ed82.png