LinkedHashMap中的單鏈表使用雙鏈表

Question

我知道我的問題與以前發佈的問題非常相似。我已經通過多個帖子瞭解了這個問題，但仍然不太清楚答案。這就是爲什麼我再次發佈。

爲什麼鏈接HashMap在Single LinkedList上使用雙重LinkedList，而訂單也可以通過Single LinkedList維護。

在它被提到了一些以前的職位的答案是LinkedHashMap的刪除提供了O（1）複雜性，因爲它以前和未來元素的指針，但我認爲HashMap中還（1）刪除提供O操作。

感謝，

Answer 1

我想的HashMap也（1）刪除

這是真的爲O，但HashMap不必維持鍵的順序。因此，在刪除條目時，只需修改從中刪除條目的存儲區的小鏈接列表（在Java 8之前的實現中，Java 8實現使用樹），這應該佔用預期的時間。另一方面，

LinkedHashMap另一方面必須保持密鑰添加到地圖的順序，該順序與包含地圖的所有條目的附加鏈接列表一起進行。因此，當您刪除條目時，如果您無法訪問此大鏈接列表中的上一條目，則必須從其開始迭代鏈接列表直到找到它，這將需要線性時間。

這裏你可以看到移除條目之後什麼LinkedHashMap做：

void afterNodeRemoval(Node<K,V> e) { // unlink 
    LinkedHashMap.Entry<K,V> p = 
     (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; 
    p.before = p.after = null; 
    if (b == null) 
     head = a; 
    else 
     b.after = a; 
    if (a == null) 
     tail = b; 
    else 
     a.before = b; 
} 

這可能不是在固定時間來完成一個單向鏈表。