java - LinkedHashMap removeEldestEntry 删除 2 个元素？

Question

我看了这个帖子:LinkedHashMap removeEldestEntry: How many elements are removed?

它指出removeEldestEntry仅删除1个元素。这对我来说很有意义，但是当我调试代码时，它似乎删除了 2 个元素。我不知道为什么。

public class LRUCache {
    LinkedHashMap<Integer, Integer> LRUMap;

    public LRUCache(int capacity) {
        LRUMap = new LinkedHashMap<Integer, Integer>() {
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return LRUMap.size() > capacity;
            }
        };
    }

    public int get(int key) {
        if (LRUMap.containsKey(key)) {
            int val = LRUMap.remove(key);
            LRUMap.put(key,  val);
            return val;
        }
        return -1;
    }

    public void set(int key, int value) {
        LRUMap.put(key, value);
    }

    public static void main(String[] args) {    
        LRUCache c = new LRUCache(2);
        c.set(2,1);
        c.set(1,1);
        c.set(2,3);
        c.set(4,1);
    }
}

所以你可以从中看到它将插入:(2,1)和(1,1)。下一个因素是事情变得困惑的地方。由于键 2 已存在，因此它会用 (2,3) 覆盖 (2,1) 元素。此后，当我插入 (4,1) 时，我已经有 2 个元素，因此它应该删除最旧的条目:(1,1)。但是，它删除了 (2,3) 和 (1,1)，在 map 中只留下 (4,1) 。

有什么想法吗？我认为这与被替换的 key 和 (2,3) 位于列表的开头有关，就像它是最旧的条目一样，尽管它不应该是。但我仍然很困惑为什么它会删除 2 个元素。

顺便说一句，它看起来像是将最老的元素存储在 LinkedHashMap 的前面，这也让我们能够以恒定的时间删除最老的条目。这是真的吗？

Answer 1

LinkedHashMap 的关键行为特征要理解的是Map.Entry<Integer, Integer> map 成员的组织方式是为了保留插入顺序，这回答了您与 Map 中成员的排序相关的问题。 。因此，如果我们遍历 main 中的每一行代码方法，我们将看到以下内容:

1. 之后c.set(2,1) LRUMap的内容将是:{2=1} .
2. 之后c.set(1,1) LRUMap的内容将是:{2=1, 1=1} .
3. 之后c.set(2,3) LRUMap的内容将是:{2=3, 1=1} 。此操作只是更新从 2 映射到键 ( 1 ) 的值。至3并且不被视为结构性变化，因此成员的顺序保持不变。
4. 之后c.set(4,1) LRUMap的内容将是:{1=1, 4=1} 。映射:2=3被认为是最旧的条目，因此它被删除(并且映射: 1=1 被保留)。

由于从您的意图中可以清楚地看出您想要创建最近最少使用缓存，因此您应该考虑更改 LinkedHashMap 的结构放弃插入顺序成员存储，转而采用最后访问成员排序。 LinkedHashMap类提供了一个替代构造函数来支持这种类型的用法:

public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)

如果传递值:true对于accessOrder参数，成员映射将存储在访问顺序中(这是您想要用于 LRU 缓存的内容)，或者如果您传递值:false对于accessOrder参数，成员映射将以插入顺序存储。