如何用Java内置数据结构实现LRU缓存？

嘿，这个问题我之前折腾过好一阵！确实，Java标准库的LinkedList内部节点是私有类，根本没法直接拿到它的前后引用，这就导致你想让HashMap直接指向链表节点来做O(1)操作的路子走不通——毕竟LinkedList.remove(Object)是O(n)的，得遍历整个链表找元素，完全达不到LRU缓存需要的效率。

不过别担心，有个完美的内置方案，还有个退而求其次的手动实现思路，给你捋清楚：

最推荐：直接用Java内置的LinkedHashMap #

其实Java早就把HashMap+双向链表的组合封装好了，就是LinkedHashMap！它默认按插入顺序维护链表，还支持切换成访问顺序（也就是LRU需要的“最近使用的放前面，最少使用的放后面”）。你只需要两步就能把它改成LRU缓存：

1. 构造LinkedHashMap时把accessOrder参数设为true
2. 重写removeEldestEntry方法，控制缓存的最大容量

直接上代码示例：

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxCapacity;

    public LRUCache(int maxCapacity) {
        // 参数说明：初始容量、负载因子、accessOrder=true（开启访问顺序排序）
        super(maxCapacity, 0.75f, true);
        this.maxCapacity = maxCapacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        // 当缓存大小超过设定的最大容量时，自动移除最久未使用的条目
        return size() > maxCapacity;
    }
}

用起来也超简单：

public class Main {
    public static void main(String[] args) {
        LRUCache<Integer, String> cache = new LRUCache<>(3);
        cache.put(1, "A");
        cache.put(2, "B");
        cache.put(3, "C");
        
        cache.get(1); // 访问1，会把它移到链表头部（最近使用位置）
        cache.put(4, "D"); // 容量超出，自动移除最久未使用的2
        
        System.out.println(cache); // 输出 {1=A, 3=C, 4=D}
    }
}

这个方案完全依赖Java内置数据结构，不需要自己手写双向链表，所有操作都是O(1)时间复杂度，完美匹配你的需求。

如果你非要手动实现（不推荐，效率低） #

要是你铁了心要自己用HashMap+LinkedList拼，那只能接受O(n)的操作效率——因为没法直接操作链表节点，每次访问元素都得先从HashMap拿到值，再遍历LinkedList找到对应的元素，移除后再放到头部。比如：

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class ManualLRUCache<K, V> {
    private final int maxCapacity;
    private final Map<K, V> map;
    private final LinkedList<K> list;

    public ManualLRUCache(int maxCapacity) {
        this.maxCapacity = maxCapacity;
        this.map = new HashMap<>();
        this.list = new LinkedList<>();
    }

    public V get(K key) {
        V value = map.get(key);
        if (value != null) {
            // 移除旧位置，放到头部
            list.remove(key);
            list.addFirst(key);
        }
        return value;
    }

    public void put(K key, V value) {
        if (map.containsKey(key)) {
            // 已存在，更新位置
            list.remove(key);
        } else if (list.size() >= maxCapacity) {
            // 容量满了，移除最久未使用的（链表尾部）
            K oldestKey = list.removeLast();
            map.remove(oldestKey);
        }
        list.addFirst(key);
        map.put(key, value);
    }
}

但这个版本的get和put里的list.remove(key)是O(n)的，数据量大的时候性能会很差，所以真的不推荐这么做。

总而言之，用LinkedHashMap是最省心、最高效的方案，完全符合你“仅用Java内置数据结构”的要求。

内容的提问来源于stack exchange，提问作者Elimination