LinkedHashMap与HashMap中的删除

Question

删除是否正确LinkedHashMap需要线性时间.由于我们需要从保持插入顺序的链表中删除密钥,因此需要O(n)时间.在常规HashMap删除需要恒定的时间.

Answer 1

根据Javadocs,它不是:

此类提供所有可选Map操作,并允许null元素.像HashMap,它提供为基本操作稳定的性能(add,contains和remove),假设散列函数散桶中适当的元件.由于维护链表的额外费用,性能可能略低于HashMap的性能,但有一个例外:对集合视图的迭代LinkedHashMap需要时间与映射的大小成比例,而不管其容量如何.对a的迭代HashMap可能更昂贵,需要与其容量成比例的时间.

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