使用LinkedHashMap实现LRU算法

谁践踏了优雅 2022-10-25 14:01 258阅读 0赞

LRU算法，最近最少使用原则，如果要实现该算法，可以借助LinkedHashMap数据结构，LinkedHashMap继承HashMap，底层使用哈希表和双向链表来保存所有元素，使用LinkedHashMap可以确保元素按照顺序进行存储。

默认情况下，LinkedHashMap是按照元素的添加顺序存储，也可以启用按照访问顺序存储，即最近读取的数据放在最前面，最早读取的数据放在最后面，然后它还有一个判断是否删除最老数据的方法，默认是返回false，即不删除数据。

下面就基于这两种存储方式，简单展示一下如何实现LRU算法：

### 一、基于按添加顺序存储的方式实现LRU： ###

public class LRUTest
    {
        int capacity;
        LinkedHashMap<Integer, Integer> cache;
    
        LRUTest(int capacity)
        {
            cache = new LinkedHashMap<>();
            this.capacity = capacity;
        }
    
        //访问元素
        public int get(int key)
        {
            if(!cache.containsKey(key))
            {
                return -1;
            }
    
            //存在，先从链表头部删除删除，在插入到链表尾部
            int val = cache.get(key);
            cache.remove(key);
            cache.put(key, val);
    
            return val;
        }
    
        //添加元素
        public void put(int key, int val)
        {
            if(cache.containsKey(key))
            {
                cache.remove(key);
            }
    
            //如果链表已经满了，则删除头部节点
            if(cache.size() == capacity)
            {
                Set<Integer> keySet = cache.keySet();
                Iterator<Integer> iterator = keySet.iterator();
                cache.remove(iterator.next());
            }
    
            cache.put(key, val);
        }
    }

### 二、基于按访问顺序存储的方式实现LRU： ###

该方式的核心就是继承LinkedHashMap，并设置LinkedHashMap的accessOrder参数为true，然后重写LinkedHashMap的removeEldestEntry()方法。

public class LRUTest extends LinkedHashMap<String, String>
    {
        private int capacity;
    
        /**
         * 当LinkedHashMap的accessOrder参数为true时，即会按照访问顺序排序，最近访问的放在最前，最早访问的放在后面
         */
        public LRUTest(int capacity) {
            super(16, 0.75f, true);
            this.capacity = capacity;
        }
    
        /**
         * LinkedHashMap自带的判断是否删除最老的元素方法，默认返回false，即不删除老数据
         */
        @Override
        protected boolean removeEldestEntry(Map.Entry<String, String> eldest)
        {
            return size() > capacity;
        }
    }

测试方法：

public static void main(String[] args)
        {
            Map<String, String> linkedHashMap = new LRUTest(6);
    
            linkedHashMap.put("1", "1");
            linkedHashMap.put("2", "2");
            linkedHashMap.put("3", "3");
            linkedHashMap.put("4", "4");
            linkedHashMap.put("5", "5");
            linkedHashMap.put("6", "6");
            linkedHashMap.put("7", "7");
            linkedHashMap.put("8", "8");
            linkedHashMap.put("9", "9");
    
            System.out.println("size="+linkedHashMap.size());
            System.out.println(linkedHashMap.get("8"));
    
            linkedHashMap.forEach((k,v) ->{
                System.out.print(k + ":"+ v +"  ");
            });
    
            System.out.println();
            System.out.println("size="+linkedHashMap.size());
        }

输出结果：

size=6
    8
    4:4  5:5  6:6  7:7  9:9  8:8  
    size=6