Java LinkedHashMap指南

1.概述

在本文中，我們將探索LinkedHashMap類的內部實現。 LinkedHashMap是Map接口的常見實現。

此特定實現是HashMap的子類，因此共享HashMap實現的核心構建塊。因此，強烈建議您在繼續閱讀本文之前仔細研究一下。

2. LinkedHashMap與HashMap

LinkedHashMap類在大多數方面與HashMap非常相似。但是，鏈接哈希圖基於哈希表和鏈接列表，以增強哈希圖的功能。

除了默認大小為16的基礎數組之外，它還維護一個遍歷所有條目的雙向鏈接列表。

為了保持元素的順序，鏈接的哈希圖通過添加指向下一個和上一個條目的指針來修改HashMap的Map.Entry類：

static class Entry<K,V> extends HashMap.Node<K,V> {

 Entry<K,V> before, after;

 Entry(int hash, K key, V value, Node<K,V> next) {

 super(hash, key, value, next);

 }

 }

注意， Entry類只是添加了兩個指針。在此之前和之後，它可以使其自身鏈接到鏈接列表。除此之外，它使用HashMap的Entry類實現。

最後，請記住，此鍊錶定義了迭代順序，默認情況下是元素的插入順序（插入順序）。

3.插入順序LinkedHashMap

讓我們看一下鏈接的哈希映射實例，該實例根據其插入到映射中的方式對條目進行排序。它還保證在地圖的整個生命週期中都將保持此順序：

@Test

 public void givenLinkedHashMap_whenGetsOrderedKeyset_thenCorrect() {

 LinkedHashMap<Integer, String> map = new LinkedHashMap<>();

 map.put(1, null);

 map.put(2, null);

 map.put(3, null);

 map.put(4, null);

 map.put(5, null);



 Set<Integer> keys = map.keySet();

 Integer[] arr = keys.toArray(new Integer[0]);



 for (int i = 0; i < arr.length; i++) {

 assertEquals(new Integer(i + 1), arr[i]);

 }

 }

在這裡，我們只是對linked hash map中的條目順序進行了初步的，非結論性的測試。

我們可以保證該測試將始終通過，因為插入順序將始終保持不變。我們不能對HashMap做出相同的保證。

在接收任何地圖，製作副本進行操作並將其返回給調用代碼的API中，此屬性可能具有很大的優勢。如果客戶端需要在調用API之前以相同的方式對返回的映射進行排序，則可以使用鏈接的哈希映射。

如果將密鑰重新插入到映射中，則插入順序不會受到影響。

4.訪問順序LinkedHashMap

LinkedHashMap提供了一個特殊的構造函數，使我們能夠在自定義負載因子（LF）和初始容量之間指定不同的排序機制/策略，稱為access-order ：

LinkedHashMap<Integer, String> map = new LinkedHashMap<>(16, .75f, true);

第一個參數是初始容量，其後是負載係數，最後一個參數是訂購模式。因此，通過傳入true ，我們打開了訪問順序，而默認設置是插入順序。

這種機制確保元素的迭代順序是上次訪問元素的順序（從最近訪問的到最近訪問的）。

因此，使用這種地圖構建最近最少使用（LRU）緩存非常容易且實用。成功的放置或獲取操作將導致對條目的訪問：

@Test

 public void givenLinkedHashMap_whenAccessOrderWorks_thenCorrect() {

 LinkedHashMap<Integer, String> map

 = new LinkedHashMap<>(16, .75f, true);

 map.put(1, null);

 map.put(2, null);

 map.put(3, null);

 map.put(4, null);

 map.put(5, null);



 Set<Integer> keys = map.keySet();

 assertEquals("[1, 2, 3, 4, 5]", keys.toString());



 map.get(4);

 assertEquals("[1, 2, 3, 5, 4]", keys.toString());



 map.get(1);

 assertEquals("[2, 3, 5, 4, 1]", keys.toString());



 map.get(3);

 assertEquals("[2, 5, 4, 1, 3]", keys.toString());

 }

請注意，當我們在map上執行訪問操作時，鍵集中元素的順序是如何轉換的。

簡而言之，在map上進行的任何訪問操作都將導致以下順序：如果要立即執行迭代，則訪問的元素將最後出現。

在上述示例之後，很明顯， putAll操作為指定映射中的每個映射生成一個條目訪問。

自然地，在map視圖上的迭代不會影響後勤地圖的迭代順序。只有對map的顯式訪問操作才會影響順序。

LinkedHashMap還提供了一種機制，用於維護固定數量的映射，並在需要添加新映射的情況下保持丟棄最舊的映射。

可以重寫removeEldestEntry方法以強制執行此策略以自動刪除陳舊的映射。

為了在實踐中看到這一點，讓我們創建自己的鏈接哈希映射類，其唯一目的是通過擴展LinkedHashMap來強制刪除陳舊的映射：

public class MyLinkedHashMap<K, V> extends LinkedHashMap<K, V> {



 private static final int MAX_ENTRIES = 5;



 public MyLinkedHashMap(

 int initialCapacity, float loadFactor, boolean accessOrder) {

 super(initialCapacity, loadFactor, accessOrder);

 }



 @Override

 protected boolean removeEldestEntry(Map.Entry eldest) {

 return size() > MAX_ENTRIES;

 }



 }

我們在上面的覆蓋將使地圖最大可容納5個條目。當大小超過該大小時，將以丟失地圖中最舊的條目為代價插入每個新條目，即最後訪問時間在所有其他條目之前的條目：

@Test

 public void givenLinkedHashMap_whenRemovesEldestEntry_thenCorrect() {

 LinkedHashMap<Integer, String> map

 = new MyLinkedHashMap<>(16, .75f, true);

 map.put(1, null);

 map.put(2, null);

 map.put(3, null);

 map.put(4, null);

 map.put(5, null);

 Set<Integer> keys = map.keySet();

 assertEquals("[1, 2, 3, 4, 5]", keys.toString());



 map.put(6, null);

 assertEquals("[2, 3, 4, 5, 6]", keys.toString());



 map.put(7, null);

 assertEquals("[3, 4, 5, 6, 7]", keys.toString());



 map.put(8, null);

 assertEquals("[4, 5, 6, 7, 8]", keys.toString());

 }

請注意，在我們向地圖添加新條目時，鍵集開始處的最舊條目會如何下降。

5.性能考量

就像HashMap一樣， LinkedHashMap可以恆定時間執行添加，刪除和包含的基本Map操作，只要哈希函數的尺寸合理即可。它還接受一個空鍵以及空值。

但是， LinkedHashMap的這種恆定時間性能可能會比HashMap的恆定時間稍差一些，這是因為維護雙向鍊錶的開銷增加了。

LinkedHashMap的集合視圖上的迭代也需要類似於HashMap的線性時間O（n） 。另一方面， LinkedHashMap在迭代過程中的線性時間性能要好於HashMap的線性時間。

這是因為，對於LinkedHashMap的**，n的O（n）是僅在地圖中的條目數而不管容量。而對於HashMap ， n是容量，大小總和為O（size + capacity）。

負載因子和初始容量的定義與HashMap一樣。但是請注意，對於LinkedHashMap，為初始容量選擇過高的值的懲罰要比對HashMap輕，因為此類的迭代時間不受容量的影響。

6.並發

就像HashMap一樣， LinkedHashMap實現也不同步。因此，如果您要從多個線程訪問它，並且這些線程中的至少一個有可能在結構上進行更改，則必須在外部進行同步。

最好在創建時執行此操作：

Map m = Collections.synchronizedMap(new LinkedHashMap());

HashMap的區別在於需要進行結構修改的地方。在訪問順序鏈接的哈希表中，僅調用get API會導致結構上的修改。除此之外，還有諸如put和remove之類的操作。

7.結論

在本文中，我們就使用Java LinkedHashMap類作為Map接口的最重要實現之一進行了探討。我們還從其超類HashMap的差異方面探討了其內部工作方式。

希望在閱讀了這篇文章之後，您可以就用例中採用的Map實現做出更明智，更有效的決策。

本文中使用的所有示例的完整源代碼都可以在GitHub項目中找到。