LinkedList 实现 LRU 缓存

LRU（Least Recently Used，最近最少使用）缓存是一种缓存淘汰策略，用于在缓存满时淘汰最久未使用的元素。

关键：

缓存选什么结构？

怎么实现访问顺序？

import java.util.*;public class LRUCache<K, V> {private final int capacity; // 缓存容量private final Map<K, V> cache; // 用于存储缓存数据private final LinkedList<K> order; // 用于维护访问顺序public LRUCache(int capacity) {this.capacity = capacity;this.cache = new HashMap<>(capacity);this.order = new LinkedList<>();}public V get(K key) {if (!cache.containsKey(key)) {return null; // 如果缓存中不存在该键，返回 null}// 将访问的键移到队列的尾部，表示最近使用order.remove(key);order.addLast(key);return cache.get(key);}public void put(K key, V value) {if (cache.containsKey(key)) {// 如果缓存中已经存在该键，更新值并将键移到队列的尾部cache.put(key, value);order.remove(key);order.addLast(key);} else {if (cache.size() >= capacity) {// 如果缓存满了，移除最久未使用的键K oldestKey = order.removeFirst();cache.remove(oldestKey);}// 添加新键值对到缓存cache.put(key, value);order.addLast(key);}}public static void main(String[] args) {LRUCache<String, String> lruCache = new LRUCache<>(3);lruCache.put("1", "one");lruCache.put("2", "two");lruCache.put("3", "three");System.out.println(lruCache.get("1")); // 输出: onelruCache.put("4", "four");System.out.println(lruCache.get("2")); // 输出: null (因为2是最久未使用的)}
}

 测试讲解：

先定义了大小为3的缓存，然后存1,2,3，此时的访问顺序1-2-3，list头部是最早访问的，尾部是最晚访问的，此时缓存已满，然后访问了1，则现在的顺序是2-3-1，可见，2是那个最久没被访问的，我再添加新元素4时，需要删除的是2，顺序变成3-1-4。