LinkedHashMap
中的删除操作需要线性时间,这是正确的吗?因为我们需要从维护插入顺序的链表中删除键,这需要 O(n)
的时间。在普通的 HashMap
中,删除操作只需要常数时间。
LinkedHashMap
中的删除操作需要线性时间,这是正确的吗?因为我们需要从维护插入顺序的链表中删除键,这需要 O(n)
的时间。在普通的 HashMap
中,删除操作只需要常数时间。
LinkedHashMap
不覆盖 HashMap#remove(Object key)
方法。后者从表中删除与键对应的条目,并在删除的条目上调用 recordRemoval()
方法,该方法调整前一个和后一个链接到被删除的条目。没有迭代列表以按索引删除节点。/**
* Removes this entry from the linked list.
*/
private void remove() {
before.after = after;
after.before = before;
以下是操作顺序:
该段代码如下:
remove implementation in HashMap calls removeEntryForKey (HashMap:line551)
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
removeEntryForKey in HashMap calls entry.recordRemoval(this) (HashMap:line560)
final Entry<K,V> removeEntryForKey(Object key) {
[...]
while (e != null) {
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
[...]
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
recordRemoval implementation in LinkedHasMap.Entry calls remove method above, which is O(1) (LinkedHashMap:line357)
void recordRemoval(HashMap<K,V> m) {
remove();
}