java - LinkedHashMap 中的removeEldestEntry 是如何实现的以及该方法的运行时/复杂度是多少？

Question

所以我环顾四周，找不到任何直接的答案。就我个人而言，我猜测 Java 可能会操纵插入 LinkedHashMap 中的项目的时间戳，并可能以某种方式在其排序中使用它。

我知道removeEldestEntry需要做的只是返回true/false，但是当它真正从 map 中删除最旧的条目时，运行时间似乎是O(n)，这是什么？真的吗？

谢谢。

Answer 1

Java 不执行任何操作。该方法的 JDK 实现是:

返回错误；

对于那些想要在自己的子类中自定义 map 行为的人来说，它是一个扩展点。

如果将其更改为返回 true，则运行时间仍然是 O(1)。该列表按插入顺序维护。它所做的只是删除头部，不需要任何迭代。只需执行标准 HashMap 删除，然后重新分配两个指针即可。

// Remove eldest entry if instructed, else grow capacity if appropriate
        Entry<K,V> eldest = header.after;
        if (removeEldestEntry(eldest)) {
            //This is the standard HashMap remove, which then finishes by
            //calling Map.Entry#remove() on the removed entry.
            removeEntryForKey(eldest.key);
        }


private static class Entry<K,V> extends HashMap.Entry<K,V> {
    // These fields comprise the doubly linked list used for iteration.
    Entry<K,V> before, after;

    /**
     * Removes this entry from the linked list.
     */
    private void remove() {
        before.after = after;
        after.before = before;
    }