LinkedHashMap 实现 LRU:真实验证淘汰的是最久没访问的,不是最早插入的

两个开关:accessOrder 和 removeEldestEntry

LinkedHashMap 默认按插入顺序迭代,把构造函数第三个参数传 true 就能切换成访问顺序;搭配重写 removeEldestEntry,插入超出容量时自动淘汰队首元素。

LruDemo.java(核心实现) static class LruCache<K, V> extends LinkedHashMap<K, V> { final int capacity; LruCache(int capacity) { super(16, 0.75f, true); // accessOrder=true:迭代顺序按访问顺序 this.capacity = capacity; } @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > capacity; } }

真实验证:访问过的 key 真的被移到了队尾

容量设成 3,插入 1、2、3 之后先看默认顺序,再 get(1) 一次,看迭代顺序有没有真实变化。

插入 1,2,3 之后,迭代顺序 = [1, 2, 3]
get(1) 之后,迭代顺序 = [2, 3, 1]
put(4) 之后,迭代顺序 = [3, 1, 4]
2 是否还在(预期:被淘汰,不在) = false
1 是否还在(预期:因为刚访问过,在)  = true

真实结果和预期完全一致:get(1) 之后,1 被真实移到了迭代顺序的最后(表示"最近访问过"),2 反而变成了顺序最靠前的("最久没被碰过")。插入第 4 个元素超出容量 3 时,removeEldestEntry 真实淘汰的是队首的 2,而不是插入时间更早的 1——1 虽然先于 2 插入,但因为中途被访问过,真实活了下来。

真实验证:更明确的连续访问顺序

再做一组区分度更大的实验:两次连续 get,制造出清晰的"谁更新"的顺序关系。

访问顺序: put 10,20,30 -> get(20) -> get(10),迭代顺序 = [30, 20, 10]
put(40) 之后,迭代顺序 = [20, 10, 40]
30 是否还在(预期:被淘汰) = false

分步演示:put 10/20/30、get 20/10、put 40 的每一步真实顺序

把"真实验证二"的六次操作串成动画:每一帧的迭代顺序都是真实跑出来的 LinkedHashMap.keySet(),不是手工排的。