LRU的java实现

落日映苍穹つ 2022-10-29 00:46 55阅读 0赞

## 什么是LRU ##

LRU（Least Recently Used）直译来看，就是最近最少使用，因为LRU是一个淘汰算法，所以指的是，每次都淘汰离当前时间最远的被使用到的那一个。也就是最久没有被使用到的那个。

## 为什么需要LRU ##

LRU其实大部分操作系统为最大化页面命中率而广泛采用的一种页面置换算法，是为了提高页面的命中率而使用的算法，就应用开发来说，Redis的内存淘汰策略使用的就是LRU算法，当Redis内存使用打到上限，如果采用的 allkeys-lru 删除策略，此时我们再增加key，redis就会根据LRU来挑选一个key进行删除。

## LRU的使用场景 ##

*  操作系统的一些内存管理，页面置换算法
 *  redis/memcache/mysql
 *  业务使用

## LRU的实现方案 ##

对于添加新的k-v，和删除已存在的key，我们都想达到O(1)的时间复杂度，所以我们使用双向链表+hash的实现方案。  
hashmap负责定位数据位置，双向链表负责转移和增减数据。  
涉及到删除的话，那我们使用的链表应该是个定长链表，当满了的时候，进行LRU的删除。  
代码如下：

package com.vipkid.modelserving.web;
    
    import java.util.HashMap;
    import java.util.LinkedList;
    
    public class LRUCache { 
    
        private int capacity;
        //hashmap
        private HashMap<Integer,Integer> map;
        //双向链表
        private LinkedList<Integer> list;
    
        //初始化容量
        public LRUCache(int capacity) { 
            this.capacity=capacity;
            map=new HashMap<>();
            list=new LinkedList<Integer>();
        }
    
        //取值，存在则将最新访问的挪到最后
        public int get(int key) { 
            //key存在
            if (map.containsKey(key)){ 
                list.remove(key);
                //移到最后
                list.addLast(key);
                return map.get(key);
            }
    
            return -1;
        }
    
        //存入值，存在则将最新访问的挪到最后
        //不存在则存入最后，若容量满，从最开始开始删除
        public void put(int key, int value) { 
            //key 已存在
            if (map.containsKey(key)){ 
                //删除旧的
                list.remove(key);
                //放到最后
                list.addLast(key);
                return;
            }
            //key不存在，满了
            if (list.size()==capacity){ 
                //从最开始开始删除
                int remove=list.removeFirst();
                map.remove(remove);
                map.put(key,value);
                list.addLast(key);
            }else { 
                //key不存在，没满
                map.put(key,value);
                list.addLast(key);
            }
    
    
        }
    
    }