LinkedHashMap实现LRU算法

我就是我 2024-03-26 10:43 87阅读 0赞

#### 目录 ####

*   *  LRU 简介
     *  LinkedHashMap的使用
     *  手写LRU缓存淘汰算法

### LRU 简介 ###

LRU 是 Least Recently Used 的缩写，这种算法认为最近使用的数据是热门数据，下一次很大概率将会再次被使用。而最近很少被使用的数据，很大概率下一次不再用到。当缓存容量的满时候，优先淘汰最近很少使用的数据。

假设现在缓存内部数据如图所示：  
**这里我们将列表第一个节点称为头结点，最后一个节点为尾结点。(可以想象成队列)**  
![在这里插入图片描述][8ef734033686442398314d6dc3d03901.png]

当调用缓存获取 key=1 的数据，LRU 算法需要将 1 这个节点移动到头结点，其余节点不变  
![在这里插入图片描述][b87d0c1df1374ed5a03dd5ee94513dc9.png]

然后我们插入一个 key=8 节点，此时缓存容量到达上限，所以加入之前需要先删除数据。由于每次查询都会将数据移动到头结点，未被查询的数据就将会下沉到尾部节点，尾部的数据就可以认为是最少被访问的数据，所以删除尾结点的数据。  
![在这里插入图片描述][8204ea9ff0924cfba0265018920c391e.png]  
然后我们直接将数据添加到头结点。  
![在这里插入图片描述][e6fe225f15d7475fa0db23745e33f2eb.png]  
这里总结一下 LRU 算法具体步骤：

*  新数据直接插入到列表头部
 *  缓存数据被命中，将数据移动到列表头部
 *  缓存已满的时候，移除列表尾部数据。

### LinkedHashMap的使用 ###

会把添加查找的元素放到尾结点，删除的会从头结点删除

public class Test01 {
        
        public static void main(String[] args) {
        
            LinkedHashMap<String,String> linkedHashMap
                    = new LinkedHashMap<>(16,0.75f,true);
            linkedHashMap.put("a","a");
            linkedHashMap.put("b","b");
            linkedHashMap.put("c","c");
            //acb
            linkedHashMap.get("b");
            //cba
            linkedHashMap.get("a");
            linkedHashMap.forEach((k,v)->{
        
                System.out.println("k:"+k+","+v);
            });
    
        }
    }

![在这里插入图片描述][baea533769ad4a8aa0b3a357e160550e.png]

### 手写LRU缓存淘汰算法 ###

public class LruCache<K,V> extends LinkedHashMap<K,V> {
        
    
        /**
         * 容量
         */
        private int capacity;
    
        public LruCache(int capacity){
        
            super(capacity,0.75f,true);
            this.capacity = capacity;
        }
    
        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        
            return size()>capacity;
        }
    
        public static void main(String[] args) {
        
            LruCache<String, String> lruCache = new LruCache<>(3);
            lruCache.put("a","a");
            lruCache.put("b","b");
            lruCache.put("c","c");
            lruCache.put("d","d");
            lruCache.forEach((k,v)->{
        
                System.out.println("k:"+k+","+v);
            });
        }
    }

![在这里插入图片描述][a82952e78e054d029df9250353a32256.png]

[8ef734033686442398314d6dc3d03901.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/e7296cd039f94dc9b6d7251f457cd526.png
[b87d0c1df1374ed5a03dd5ee94513dc9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/505feba78bf449a093b7a3d1e2d62852.png
[8204ea9ff0924cfba0265018920c391e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/49368c18c512414dab17e464342b5fb5.png
[e6fe225f15d7475fa0db23745e33f2eb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/9e831989c44d43219b066c24e337386e.png
[baea533769ad4a8aa0b3a357e160550e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/b48cfbf522d64fe88bc876035868d93a.png
[a82952e78e054d029df9250353a32256.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/591e788b915f4e2a879c9d3b4c336f50.png