java - LinkedHashMap 与 HashMap 中的删除

Question

LinkedHashMap 中的删除需要线性时间，这是否正确？由于我们需要从保持插入顺序的链表中删除键，这将花费 O(n) 时间。在常规的 HashMap 中，删除需要恒定的时间。

Answer 1

根据Javadocs ，它不是:

This class provides all of the optional Map operations, and permits null elements. Like HashMap, it provides constant-time performance for the basic operations (add, contains and remove), assuming the hash function disperses elements properly among the buckets. Performance is likely to be just slightly below that of HashMap, due to the added expense of maintaining the linked list, with one exception: Iteration over the collection-views of a LinkedHashMap requires time proportional to the size of the map, regardless of its capacity. Iteration over a HashMap is likely to be more expensive, requiring time proportional to its capacity.

LinkedHashMap不会覆盖HashMap#remove(Object key)方法。后者从表中删除与该键对应的条目并调用 recordRemoval()已删除条目上的方法，该方法调整已删除条目的上一个和下一个链接。列表中没有为了删除某个索引处的节点而进行的迭代。