1

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

我知道 removeEldestEntry 需要做的只是简单地返回 true/false，但是当它实际从地图中删除最旧的条目时，运行时似乎是 O(n)，它到底是什么？

谢谢。

4

2 回答 2

2

Java什么都不做。该方法的JDK实现是：

return false;

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

如果将其更改为返回 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;
    }
于 2013-11-08T21:18:11.560 回答
0

来自http://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashMap.html

如果您跟踪插入的最旧密钥，则删除将是 O(1)，否则为 O(n)。

您也许还可以利用密钥插入顺序。请记住，即使根据插入键的时间对 LinkedHashMap 进行排序，如果重新插入键，它也不会更改顺序（这可能会使该键失效）。

于 2013-11-08T21:09:24.037 回答