LinkedHashMap的實現與HashMap有什麼不同？

27

LinkedHashMap將佔用更多內存。正常的HashMap中的每個條目都具有密鑰和值。每個LinkedHashMap條目具有對下一個和前一個條目的引用和的引用。還有一點家務要做，儘管這通常是無關緊要的。

2010-06-11 06:29:55

+0

其結果是，性能稍低相比HashMap中的。 – Snehal 2010-06-11 06:32:21

+0

@Jon Skeet它是不是像LinkedHashMap中的值包含對上一個值和下一個值的額外引用，刪除或插入任何項目都需要額外的費用來重新連接？如果我得到完整的實現或者有鏈接或解釋，那將是非常棒的。 – 2010-06-11 06:39:41

+0

@熱情的程序員：源代碼是公開的 - 爲什麼不看那裏？是的，插入和刪除確實需要更新鏈接列表。 – 2010-06-11 06:58:24

10

LinkedHashMap還維護一個雙向鏈接列表，其中運行所有條目，這將提供一個可重複的順序。這個鏈表定義了迭代排序，這通常是鍵被插入映射的順序（插入順序）。
HashMap沒有這些額外成本（運行時間，空間），並且當您不關心廣告訂單時應該首選LinkedHashMap。

來源

2010-06-11 06:31:48 stacker

+0

我認爲你的意思是迭代次序？ – 2011-11-13 00:29:39

+0

@MichaelDeardeuff你是對的，但答案通常是正確的，因爲迭代順序=插入順序deafult。可能替代*插入順序*是*訪問順序*。 – 2014-12-16 09:58:31

5

當你需要知道鍵的映射順序時，LinkedHashMap是一個有用的數據結構。一個合適的用例是用於實現LRU緩存。由於LinkedHashMap的維護順序，與HashMap相比，數據結構需要額外的內存。在插入順序不是要求的情況下，您應該始終使用HashMap。

來源

2010-06-11 06:35:45 Snehal

20

如果LinkedHashMap的時間複雜度與HashMap的複雜度相同，爲什麼我們需要HashMap？

您不應該將複雜性與性能混淆。兩種算法可以具有相同的複雜性，但是可以一致地執行比其他更好的算法。

記住f(N) is O(N)意味着：

C1*N <= limit(f(N), N -> infinity) <= C2*N

其中C1和C2是嚴格爲正的常數。複雜性沒有說明數值有多大或多麼小。對於兩種不同的算法，常數很可能是不同的。

（請記住，大O的複雜性有關的行爲/性能N變得非常大。它會告訴你什麼關於小N值的行爲/性能。）

話雖如此，在等效用例中的HashMap和LinkedHashMap操作之間的性能差異相對較小。通常，更多相關的額外內存開銷。

來源

2010-06-11 06:43:40

+1

這是一組優秀的區別。 – Jared 2016-02-26 20:33:07

4

HashMap和LinkedHashMap之間還有另一個主要區別：在LinkedHashMap的情況下，迭代更有效率。

如LinkedHashMap的元素被相互連接，以便迭代需要時間正比於地圖的大小，不管其容量。但是在HashMap;因爲沒有固定的順序，所以迭代它需要時間與其容量成正比。

我在我的blog上放了更多細節。

來源

2012-12-28 11:10:20

0

重新上漿應該是較快，因爲它通過其雙鏈表遍歷到的內容傳送到一個新的表陣列。
containsValue（）被覆蓋以利用更快的迭代器。
LinkedHashMap也可用於創建LRU緩存。提供了一個特殊的 LinkedHashMap（capacity，loadFactor，accessOrderBoolean）構造函數用於創建鏈接哈希映射，其迭代順序爲上次訪問它的條目的順序，從最近最少訪問到最近訪問的。在這種情況下，只有用get（）查詢地圖是一個結構修改。

來源

2013-02-05 13:54:25 Satish

1

LinkedHashMap繼承了HashMap，這意味着它使用HashMap的現有實現在Node（Entry對象）中存儲鍵和值。除此之外，它存儲一個單獨的雙向鏈表實現來維護已輸入密鑰的插入順序。

它看起來像這樣：

頭節點< --->節點1 < --->節點2 < --->節點3 < ---->節點4 < --->頭節點。

所以額外的重載是在這個雙向鏈表中保持插入和刪除。好處是：迭代順序保證是插入順序，它不在HashMap中。

來源

2014-02-01 18:33:47 punitusingh

2

HashMap不維護插入順序，因此不保留任何雙向鏈表。

LinkedHashMap最突出的特點是它保持鍵值對的插入順序。 LinkedHashMap使用雙重鏈接列表來執行此操作。

的LinkedHashMap入境看起來是這樣的：

static class Entry<K, V> { 
    K key; 
    V value; 
    Entry<K,V> next; 
    Entry<K,V> before, after;  //For maintaining insertion order  
    public Entry(K key, V value, Entry<K,V> next){ 
     this.key = key; 
     this.value = value; 
     this.next = next; 
    } 
    }

通過使用之前和之後 - 我們跟蹤的LinkedHashMap新添加的條目，這有助於我們維護插入順序的。

之前參考前條目和之後提到LinkedHashMap的下一個條目。

對於圖和一步一步的說明請參考http://www.javamadesoeasy.com/2015/02/linkedhashmap-custom-implementation.html

來源

2015-05-04 09:41:02

LinkedHashMap的實現與HashMap有什麼不同？

回答

相關問題