算法&OJ--其他--LRU算法实现

发表于 | 分类于 | 阅读次数:

缓存淘汰算法–LRU算法的实现

  • LRU
    • Least recently used, 最近最少使用
    • 根据数据的历史访问记录来进行淘汰数据
    • 其核心思想是”如果数据最近被访问过，那么将来被访问的几率也更高”
      image
  • 实现保存缓存数据
    • 循环数组实现的队列
      • 数字在小范围的遍历很快
      • 队列实现LRU
    • 链表
      • 链表的插入和删除时间复杂度都为O(1)–>用链表不用数组
      • 具体过程
        1. 新数据插入到链表头部
        2. 每当缓存命中(即缓存数据被访问)，则将数据移到链表头部
        3. 当链表满的时候，将链表尾部的数据丢弃
      • 分析
        • 【命中率】当存在热点数据时，LRU的效率很好，但偶发性的、周期性的批量操作会导致LRU命中率急剧下降，缓存污染情况比较严重
        • 【复杂度】实现简单
        • 【代价】 命中时需要遍历链表，找到命中的数据块索引，然后需要将数据移到头部
    • LinkedHashMap
      • 利用hashmap的特点–命中很快(是否在缓存中)
      • 双向链表的队列实现LRU
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        25
        26
        27
        28
        29
        30
        31
        32
        33
        34
        35
        36
        37
        38
        39
        import java.util.*;

        class LRULinkedHashMap<K,V> extends LinkedHashMap<K,V> {
            //定义缓存的容量--LinkedHashMap默认超过最大容量自动扩容，不存在remove eldest的问题
            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){
                // 每次增加都会调用该方法看是否需要remove eldest
                System.out.println(eldest.getKey() + "=" + eldest.getValue());
                return size()>capacity;
                /*return false;*/
            }
        }
        //测试类
        public class Main{
            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());
                }
            }
        }

参考