2022-08-05  阅读(1027)
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接:https://www.skjava.com/series/article/1341078593

LRU,即 Least Recently Use ,直译为 “最近最少使用”。它是根据数据的历史访问记录来进行数据淘汰的,淘汰掉最先访问的数据,其核心思想是 如果数据最近被访问过,那么将来被访问的几率也会更加高

要实现 LRU,需要做到两点:

  • 查询出最近最晚使用的项
  • 给最近使用的项做一个标记

实现的方案有多种,这里小编主要介绍两种:

  1. LinkedHashMap
  2. 双向链表 + HashMap

LinkedHashMap 实现

利用 LinkedHashMap 的原因就在于 LinkedHashMap 是有序的,默认情况下是按照元素的添加顺序存储的,也可以调整为根据访问顺序来调整内部顺序(设置参数 accessOrder 进行调整),即最近读取的数据放在最前面,我们就是利用 LinkedHashMap 的这个特性来实现 LRU。先来一个简单的例子吧:

            public static void main(String[] args){
                Map<String,String> map = new LinkedHashMap(10,0.75f,true);
        
                map.put("1","a");
                map.put("2","b");
                map.put("3","c");
                map.put("4","d");
        
                System.out.println("原始顺序为:");
                for(Iterator<Map.Entry<String,String>> it = map.entrySet().iterator();it.hasNext();){
                    System.out.print(it.next().getKey() + "    ");
                }
                System.out.println();
        
                map.get("2");
        
                System.out.println("访问 4 之后的顺序为:");
                for(Iterator<Map.Entry<String,String>> it = map.entrySet().iterator();it.hasNext();){
                    System.out.print(it.next().getKey() + "    ");
                }
            }

运行结果:

        原始顺序为:
        1    2    3    4    
        访问 4 之后的顺序为:
        1    3    4    2

更多关于 LinkedHashMap,请看这篇文章:图解集合6:LinkedHashMap

LinkedHashMap 实现 LRU 有两种方式,一种是继承 LinkedHashMap,一种是利用组合的方式,下面分别演示这两种情况。

继承 LinkedHashMap

采用继承的方式实现起来是非常简单的,因为 LinkedHashMap 本身就已经具备了 LRU 的特性,我们只需要实现一点:当容器中元素个数超过我们设定的容量后,删除第一个元素即可。同时由于 LinkedHashMap 本身不具备线程安全,我们需要确保他线程安全,这个也很简单,重写 LinkedHashMap 的 get()put() 方法即可,或者使用 Collections.synchronizedMap() 方法也可以。实现如下:

        public class LRUCacheLinkedHashMap<K,V> extends LinkedHashMap<K,V> {
        
            /**
             * 定一缓存容量
             */
            private int capacity;
        
            LRUCacheLinkedHashMap(int capacity){
                // AccessOrder = true
                super(capacity,0.75f,true);
        
                this.capacity = capacity;
            }
        
            /**
             * 实现LRU的关键方法,如果 map 里面的元素个数大于了缓存最大容量,则删除链表的顶端元素
             *
             * @param eldest
             * @return
             */
            @Override
            public boolean removeEldestEntry(Map.Entry<K, V> eldest){
                System.out.println(eldest.getKey() + "=" + eldest.getValue());
                return size()>capacity;
            }
        
            @Override
            public synchronized V get(Object key) {
                return super.get(key);
            }
        
            @Override
            public synchronized V put(K key, V value) {
                return super.put(key, value);
            }
        }

验证

           public static void main(String[] args){
                LRUCacheLinkedHashMap cache = new LRUCacheLinkedHashMap(5);
        
                cache.put("1","a");
                cache.put("2","b");
                cache.put("3","c");
                cache.put("4","d");
                cache.put("5","e");
        
                System.out.println("插入 5 个元素后的顺序");
                printlnCache(cache);
        
                // 插入第 6 个元素
                cache.put("6","e");
        
                System.out.println("插入第 6 个元素后的顺序");
                printlnCache(cache);
        
                // 访问 第 3 个元素
                cache.get("3");
        
                System.out.println("访问元素 3 后的顺序");
                printlnCache(cache);
        
            }
        
            private static void printlnCache(LRUCacheLinkedHashMap cacheMap){
                for(Iterator<Map.Entry<String,String>> it = cacheMap.entrySet().iterator(); it.hasNext();){
                    System.out.print(it.next().getKey() + "    ");
                }
                System.out.println();
            }

运行结果


        插入 5 个元素后的顺序
        1    2    3    4    5    
        插入第 6 个元素后的顺序
        2    3    4    5    6    
        访问元素 3 后的顺序
        2    4    5    6    3

运行结果完全符合我们的预期

组合 LinkedHashMap

使用组合的方式可能会更加优雅些,但是由于没有实现 Map 接口,所以就不能使用 Collections.synchronizedMap() 方式来保证线程安全性了,所以需要在每个方法处增加 synchronized 来确保线程安全。实现方式如下:

        public class LRUCache<K,V> {
            private int capacity;
        
            private Map<K,V> cacheMap;
        
            public LRUCache(int capacity){
                this.capacity = capacity;
        
                cacheMap = new LinkedHashMap<>(capacity,0.75f,true);
            }
        
            public synchronized void put(K k,V v){
                cacheMap.put(k,v);
        
                // 移除第一个元素
                if(cacheMap.size() > capacity){
                    K first = this.keyIterator().next();
        
                    cacheMap.remove(first);
                }
            }
        
            public synchronized V get(K k){
                return cacheMap.get(k);
            }
        
            public Iterator<K> keyIterator(){
                return cacheMap.keySet().iterator();
            }
        }

验证:

            public static void main(String[] args) {
                LRUCache lruCache = new LRUCache(5);
        
                lruCache.put("1","a");
                lruCache.put("2","b");
                lruCache.put("3","c");
                lruCache.put("4","d");
                lruCache.put("5","e");
        
                System.out.println("插入 5 个元素后的顺序");
                println(lruCache);
        
                // 插入第 6 个元素
                lruCache.put("6","e");
        
                System.out.println("插入 第 6 个元素后的顺序");
                println(lruCache);
        
                // 访问 第 3 个元素
                lruCache.get("3");
        
                System.out.println("访问元素 3 后的顺序");
                println(lruCache);
        
            }
        
            private static void println(LRUCache lruCache){
                for(Iterator it = lruCache.keyIterator(); it.hasNext();){
                    System.out.print(it.next() + "    ");
                }
                System.out.println();
            }

运行结果如下:

        插入 5 个元素后的顺序
        1    2    3    4    5    
        插入 第 6 个元素后的顺序
        2    3    4    5    6    
        访问元素 3 后的顺序
        2    4    5    6    3

组合的方式也显得非常简单,有两点需要注意:

  1. 保证每个方法的线程安全
  2. put 时,需要查看当前容量是否超过设置的容量,超过则需要删除第一个元素。当然小编这种是实现方式不是很优雅,这么做知识为了能够更加好阐述 LRU 的实现。更好的方案是在构造 LinkedHashMap 时,重写 removeEldestEntry(),如下:
                cacheMap = new LinkedHashMap<K,V>(capacity,0.75f,true){
                    @Override
                    protected boolean removeEldestEntry(Map.Entry eldest) {
                        return size()>capacity;
                    }
                };

链表 + HashMap 实现

我们想想,在不利用现存数据结构的条件(如 LinkedHashMap)如何实现一个 LRU 呢?缓存部分容易实现,我们都知道利用 HashMap 即可,但是如何实现缓存容量不足时丢弃最不常用的数据的功能?

  • 利用时间戳。每一个访问,增加的元素我们都给其更新一个时间戳,在 put 的时候,检查,删除时间戳最小的就可以了。这种方法可以实现,但是代价较高,就是我们需要遍历整个数据,得到最小的时间戳。
  • 我们可以换位思考,我们其实不需要关注每个节点的增加或者遍历时间,我们只需要知道那个节点是最先访问就可以了,所以我们可以利用链表记录访问记录,有新数据加入时放在链表的 head 节点,每次访问也将该数据放在 head 节点,那么链表的 tail 一定是最早访问的节点,所以每次当容量不足的时候删除 tail 节点数据并将它的前驱节点设置为 tail 就可以了。注意,这个链表是一个双向链表。代码如下:
        public class LinkedLRUCache<K,V> {
        
            private int capacity;
        
            private Map<K,LRUNode> map;
        
            private LRUNode head;
        
            private LRUNode tail;
        
            LinkedLRUCache(int capacity){
                this.capacity = capacity;
                this.map = new HashMap<>();
            }
        
            public synchronized void put(K k,V v){
                LRUNode node = map.get(k);
        
                // 存在该 key,将节点的设置为 head
                if(node != null){
                    node.value = v;
        
                    remove(node,false);
                }else{
                    /**
                     * 该节点不存在
                     * 1、将该节点加入缓存
                     * 2、设置该节点为 head
                     * 3、判断是否超出容量
                     */
                    node = new LRUNode(k,v);
        
                    if(map.size() >= capacity){
                        //删除 tail 节点
                        remove(tail,true);
                    }
        
                    map.put(k,node);
        
                    setHead(node);
                }
        
                // 设置当前节点为首节点
                setHead(node);
            }
        
            public Object get(String key) {
                LRUNode node = map.get(key);
                if (node != null) {
                    // 将刚操作的元素放到head
                    remove(node, false);
                    setHead(node);
                    return node.value;
                }
                return null;
            }
        
            /**
             * 设置头结点
             *
             * @param node
             */
            private void setHead(LRUNode node) {
                if(head != null){
                    node.next = head;
                    head.prev = node;
                }
        
                head = node;
        
                if(tail == null){
                    tail = node;
                }
            }
        
            /**
             * 从链表中删除此Node
             *
             * @param node
             * @param flag  为 true 就删除该节点的 key
             */
            private void remove(LRUNode node,boolean flag) {
                if (node.prev != null) {
                    node.prev.next = node.next;
                } else {
                    head = node.next;
                }
                if (node.next != null) {
                    node.next.prev = node.prev;
                } else {
                    tail = node.prev;
                }
                node.next = null;
                node.prev = null;
                if (flag) {
                    map.remove(node.key);
                }
            }
            
            private Iterator iterator(){
                return map.keySet().iterator();
            }
        
            private class LRUNode<K,V> {
        
                /**
                 * cache 的 key
                 */
                private K key;
        
                /**
                 * cache 的 value
                 */
                private V value;
        
                private LRUNode next;
        
                private LRUNode prev;
        
                LRUNode(K key, V value) {
                    this.key = key;
                    this.value = value;
                }
            }
        }

验证

           public static void main(String[] args){
                LRUCache lruCache = new LRUCache(5);
                
                lruCache.put("1","a");
                lruCache.put("2","b");
                lruCache.put("3","c");
                lruCache.put("4","d");
                lruCache.put("5","e");
               
                System.out.println("插入 5 个元素");
                println(lruCache);
        
                System.out.println("插入 3 元素");
                lruCache.put("3","c");
                println(lruCache);
        
                System.out.println("插入第  6 个元素");
                lruCache.put("6","f");
                println(lruCache);
        
                System.out.println("访问 4 元素");
                lruCache.get("4");
                println(lruCache);
            }
            
            private static void println(LRUCache lruCache){
                Iterator iterator = lruCache.keyIterator();
                while (iterator.hasNext()){
                    System.out.print(iterator.next() + "    ");
                }
                
                System.out.println();
            }

执行结果:

       此代码由 【Java 技术驿站】整理
        插入 5 个元素
        1    2    3    4    5    
        插入 3 元素
        1    2    4    5    3    
        插入第  6 个元素
        2    4    5    3    6    
        访问 4 元素
        2    5    3    6    4
阅读全文
  • 点赞