Java 实现 LRU 缓存算法

Myth丶恋晨 2024-03-22 13:45 108阅读 0赞

#### 一、什么是 LRU ####

**LRU**（**L**east **R**ecently **U**sed，***最近最少使用***）是一种缓存算法，其核心思想是将最近最少使用的缓存项移除，以便为更常用的缓存项腾出空间。

在实际应用中，LRU 算法被广泛用于缓存和页面置换。

#### 二、Java 实现 LRU 缓存算法 ####

在 Java 中，可以使用 LinkedHashMap 来实现 LRU 缓存算法。  
LinkedHashMap 是 HashMap 的一个子类，其内部使用双向链表维护元素的顺序。

具体实现思路如下：

1.  继承 LinkedHashMap，重写 removeEldestEntry 方法，该方法返回 true 表示需要移除最老的缓存项；
2.  在构造方法中指定 accessOrder 为 true，这样在访问元素时就会把该元素移动到链表尾部，方便后续查找和移除；
3.  在访问缓存项时，使用 get 方法获取元素，并通过 removeEldestEntry 方法来判断是否需要移除最老的缓存项；
4.  在添加缓存项时，使用 put 方法将元素加入 LinkedHashMap 中。

使用 LinkedHashMap 实现 LRU 缓存算法的示例代码如下：

import java.util.LinkedHashMap;
    import java.util.Map;
    
    public class LRUCache<K, V> extends LinkedHashMap<K, V> {
        
        private final 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<Integer, String> cache = new LRUCache<>(3);
            cache.put(1, "one");
            cache.put(2, "two");
            cache.put(3, "three");
            System.out.println(cache); // {1=one, 2=two, 3=three}
    
            cache.get(2);
            System.out.println(cache); // {1=one, 3=three, 2=two}
    
            cache.put(4, "four");
            System.out.println(cache); // {3=three, 2=two, 4=four}
        }
    }

在上面的示例代码中，我们创建了一个 LRUCache 类，继承了 LinkedHashMap，并在构造方法中指定了 accessOrder 为 true。  
在 removeEldestEntry 方法中，当缓存项数量超过容量时返回 true，表示需要移除最老的缓存项。  
在访问缓存项时，使用 get 方法获取元素，如果缓存项数量超过容量，则会移除最老的缓存项。  
在添加缓存项时，使用 put 方法将元素加入 LinkedHashMap 中。  
最后，在 main 方法中对缓存进行测试。

> 需要注意的是，在使用 LinkedHashMap 实现 LRU 缓存时，必须指定 accessOrder 为 true，否则 LinkedHashMap 会按照插入顺序维护元素的顺序，而不是访问顺序。