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)，地图中只剩下 (4,1)。

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

附带说明一下，它似乎将最老的元素存储在 LinkedHashMap 的前面，这也会给我们一个恒定的时间删除最老的条目。这是真的吗？

Answer 1

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

在 c.set(2,1) 之后 LRUMap 的内容将是：{2=1}。
在 c.set(1,1) 之后 LRUMap 的内容将是：{2=1, 1=1}。
在 c.set(2,3) 之后 LRUMap 的内容将是：{2=3, 1=1}。此操作只是将映射到键 (2) 的值从 1 更新为 3 并且 而不是 被视为结构更改，因此维持成员的顺序。
在 c.set(4,1) 之后 LRUMap 的内容将是：{1=1, 4=1}。映射：2=3 被认为是最老的条目，因此将其删除（并保留映射：1=1）。

由于从您的意图中可以清楚地看出您想要创建一个最近最少使用的 缓存，因此您应该考虑更改 LinkedHashMap 的构造以移动远离 insertion-order 成员存储，转而使用 last-access 成员排序。 LinkedHashMap class 提供了一个替代构造函数来支持这种类型的用法：

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

如果您为 accessOrder 参数传递值：true，成员映射将存储在 access-order 中（这是您想用于 LRU 缓存）或者如果您为 accessOrder 参数传递值：false，成员映射将存储在 insertion-order 中。

LinkedHashMap removeEldestEntry 删除 2 个元素？

LinkedHashMap removeEldestEntry removing 2 elements?

java

linkedhashmap