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) .

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

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

Answer 1

LinkedHashMap 的关键行为特征要理解的是 Map.Entry<Integer, Integer>映射的成员被组织以保留插入顺序，这回答了您与 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参数，成员映射将存储在access-order(这是你想要用于 LRU 缓存的)或者如果你传递值:false对于 accessOrder参数，成员映射将按插入顺序存储。