如何用LinkedHashMap实现LRU缓存算法

你的名字 2021-06-24 14:34 594阅读 0赞

缓存这个东西就是为了提高运行速度的，由于缓存是在寸土寸金的内存里面，不是在硬盘里面，所以容量是很有限的。LRU这个算法就是把最近一次使用时间离现在时间最远的数据删除掉。先说说List：每次访问一个元素后把这个元素放在 List一端，这样一来最远使用的元素自然就被放到List的另一端。缓存满了t的时候就把那最远使用的元素remove掉。但更实用的是 HashMap。因为List太慢，要删掉的数据总是位于List底层数组的第一个位置，删掉之后，后面的数据要向前补位。。所以复杂度是O(n)，那就用链表结构的LinkedHashMap呗~，LinkedHashMap默认的元素顺序是put的顺序，但是如果使用带参数的构造函数，那么 LinkedHashMap会根据访问顺序来调整内部 顺序。 LinkedHashMap的get()方法除了返回元素之外还可以把被访问的元素放到链表的底端，这样一来每次顶端的元素就是remove的元素。

构造函数如下：

public LinkedHashMap (int initialCapacity, float loadFactor, boolean accessOrder)；

initialCapacity   初始容量

loadFactor    加载因子，一般是 0.75f

accessOrder   false 基于插入顺序  true  基于访问顺序（get一个元素后，这个元素被加到最后，使用了LRU  最近最少被使用的调度算法）

来个例子吧：

import java.util.*; 
       
    class Test 
    { 
        public static void main(String[] args) throws Exception{ 
           
            Map<Integer,Integer> map=new LinkedHashMap<>(10,0.75f,true); 
            map.put(9,3); 
            map.put(7,4); 
            map.put(5,9); 
            map.put(3,4); 
            //现在遍历的话顺序肯定是9,7,5,3 
            //下面访问了一下9,3这个键值对，输出顺序就变喽~ 
            map.get(9); 
            for(Iterator<Map.Entry<Integer,Integer>> it=map.entrySet().iterator();it.hasNext();){ 
                System.out.println(it.next().getKey()); 
            } 
        } 
    }

输出

7  
5  
3  
9

好玩吧~

下面开始实现LRU缓存喽~

import java.util.*; 
    //扩展一下LinkedHashMap这个类，让他实现LRU算法 
    class LRULinkedHashMap<K,V> extends LinkedHashMap<K,V>{ 
        //定义缓存的容量 
        private int capacity; 
        private static final long serialVersionUID = 1L; 
        //带参数的构造器    
        LRULinkedHashMap(int capacity){ 
            //调用LinkedHashMap的构造器，传入以下参数 
            super(16,0.75f,true); 
            //传入指定的缓存最大容量 
            this.capacity=capacity; 
        } 
        //实现LRU的关键方法，如果map里面的元素个数大于了缓存最大容量，则删除链表的顶端元素 
        @Override 
        public boolean removeEldestEntry(Map.Entry<K, V> eldest){  
            System.out.println(eldest.getKey() + "=" + eldest.getValue());   
            return size()>capacity; 
        }   
    } 
    //测试类 
    class Test{ 
    public static void main(String[] args) throws Exception{ 
       
        //指定缓存最大容量为4 
        Map<Integer,Integer> map=new LRULinkedHashMap<>(4); 
        map.put(9,3); 
        map.put(7,4); 
        map.put(5,9); 
        map.put(3,4); 
        map.put(6,6); 
        //总共put了5个元素，超过了指定的缓存最大容量 
        //遍历结果 
            for(Iterator<Map.Entry<Integer,Integer>> it=map.entrySet().iterator();it.hasNext();){ 
                System.out.println(it.next().getKey()); 
            } 
        } 
    }

输出结果如下

9=3  
9=3  
9=3  
9=3  
9=3  
7  
5  
3  
6

分析一下：使用带参数构造器，且启用LRU模式的LinkedHashMap会在每次有新元素加入的时候，判断当前储存元素是否超过了缓存上限，也就是执行

一次 removeEldestEntry方法，看最后的遍历结果，发现果然把9删除了，LRU发挥作用了~