Java HashMaps 的工作原理——內部機制解析

HashMap 是 Java 中最常使用的数据结构之一，以其效率著称。在 HashMap 中的數據以鍵值對的形式儲存。

在這篇文章中，我將為你介紹 Java 中的 HashMap。我們將探索 HashMap 的常見操作，然後深入研究其內部運作原理。你將會了解散列函數以及索引計算是如何進行的。最後，我們將看看這些操作的時間複雜度，並討論在並發環境中的行為。

Java 中的 `HashMap` 是什麼？

HashMap 實現了 Java 集合框架中的 Map 介面。它是基於散列的概念。

散列是一種將任意大小的輸入轉換為固定大小輸出的技術，使用的是散列函數。在 Java 中，生成的輸出稱為散列碼，並以整數值表示。散列碼在 HashMap 中用於高效查找和存儲操作。

常見操作

像我們上面所討論的，HashMap 中的數據以鍵值對的形式儲存。鍵是一個唯一的標識符，每個鍵都與一個值相關聯。

以下是 HashMap 支持的一些常見操作。讓我們透過一些簡單的代碼示例來了解這些方法的作用：

插入

這個方法將新的鍵值對插入到 HashMap 中。
鍵值對的插入順序不會被保持。
在插入過程中，如果一個鍵已經存在，則會將現有的值替換為傳遞的新值。
您只能在 HashMap 中插入一個 null 鍵，但可以有多個 null 值。

以下是此操作的方法簽名，以及一個示例：

public V put(K key, V value)

Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);

在上述代碼中，我們有一個 HashMap 示例，我們在其中添加了一個 String 類型的鍵和一個 Integer 類型的值。

查詢：

抓取與給定鍵相關聯的值。
如果鍵在 HashMap 中不存在，則返回 null。

以下是此操作的方法簽名，以及一個示例：

public V get(Object key)

Integer value = map.get("apple"); // 返回 1

在上述代碼中，我們正在抓取與鍵 apple 相關聯的值。

其他常見操作包括：

remove：移除指定鍵的鍵值對。如果找不到該鍵，則返回null。
containsKey：檢查特定的鍵是否存在于HashMap中。
containsValue：檢查指定的值是否存在于HashMap中。

`HashMap`的內部結構

內部來說，HashMap使用一個桶（bins）的數組。每個桶是一個類型為Node的鏈表，用於表示HashMap的鍵值對。

static class Node<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K, V> next;

    Node(int hash, K key, V value, Node<K, V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

在上方，你可以看到用於存儲HashMap的鍵值對的Node類的結構。

Node類有以下字段：

hash：指的是鍵的hashCode。
key：指的是鍵值對的鍵。
value：指的是與鍵相關聯的值。
下一個: 作為指向下一節點的引用。

HashMap HashMap 根本上是基於哈希表實現的，其性能取決於兩個關鍵參數：初始容量和載荷因子。哈希表類的原始javadocs 將這兩個參數定義如下：

容積是哈希表中的桶數量，初始容量僅僅是創建哈希表時的容量。
載荷因子是衡量哈希表允許填充多滿之前其容量會自動增加的指標。

讓我們現在嘗試理解在 HashMap 中基本操作 put 和 get 是如何工作的。

哈希函數

在插入（put）一個鍵值對時，HashMap 首先會計算鍵的哈希碼。哈希函數隨後為該鍵計算一個整數。類可以使用 Object 類的 hashCode 方法，也可以覆寫這個方法並提供自己的實現。（關於哈希碼合約的詳細資訊在這裡）。然後將哈希碼與其高16位（h >>> 16）進行異或（XOR）操作，以達到更均勻的分布。

異或是比較兩個位的位操作，如果位不同則結果為1，如果位相同則結果為0。在這個背景下，對哈希碼及其高16位（使用無符號右移 >>> 操作符得到）進行位操作，有助於混合位，從而產生更均勻分布的哈希碼。

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

以上，你可以看到 HashMap 類的靜態哈希方法。

這樣的目的是為每個鍵產生唯一的哈希碼，但哈希函數可能會為不同的鍵產生相同的哈希碼。這會導致一種稱為碰撞的情況。我們將在下節看到如何處理碰撞。

索引計算

一旦為一個鍵產生了哈希碼，HashMap 就會計算一個在桶陣列中的索引，以確定鍵值對將被存儲的位置。這是通過使用位與操作來完成的，當陣列長度為二的冪次時，這是一種計算模數的有效方式。

int index = (n - 1) & hash;

在這裡，我們正在計算索引，其中 n 是桶陣列的長度。

一旦計算出索引，則將鍵存儲在桶陣列的該索引位置。然而，如果多個鍵最終具有相同的索引，則會引發碰撞。在這種情況下，HashMap 以以下兩種方式處理：

鏈接法：陣列中的每個桶都是一個節點的鏈接列表。如果一個鍵已經存在於特定索引位置，而另一個鍵被哈希到相同的索引位置，則它將附加到該列表中。
樹化：如果節點數量超過一定閾值，則將鏈接列表轉換為樹（這在Java 8中引入）。

static final int TREEIFY_THRESHOLD = 8;

這是確定樹化的閾值。

因此，擁有一個良好的哈希函數是至關重要的，它能夠在桶之間均勻分布鍵並最小化碰撞的機會。

檢索（get）和刪除（remove）操作的工作方式與插入（put）操作類似。以下是操作步驟：

檢索（get）：使用哈希函數計算哈希碼 -> 使用哈希碼計算索引 -> 遍歷鏈接列表或樹以找到具有匹配鍵的節點。
刪除（remove）：使用雜湊函數計算雜湊碼 -> 根據雜湊碼計算索引 -> 從鏈表或樹中移除節點。

時間複雜度

HashMap 的基本操作，如 put、get 和 remove，通常提供常數時間性能 O(1)，假設鍵是均勻分佈的。在鍵分佈不良且發生許多碰撞的情況下，這些操作可能會退化为線性時間複雜度 O(n)。

在樹化過程中，將長串的碰撞轉換為平衡樹，查詢操作可以提高到更有效的對數時間複雜度 O(log n)。

同步

HashMap 的實現不是同步的。如果多個線程同時訪問 HashMap 實例並遍歷地圖，且其中任一線程對地圖進行結構性修改（如添加或刪除鍵值映射），將導致 ConcurrentModificationException。

為防止這點，您可以使用 Collections.synchronizedMap 方法創建一個線程安全的實例。

結論

總結來說，了解 HashMap 的內部工作机制對开发者來說至關重要，以便他們能夠做出明智的決定。了解如何映射键值、碰撞是如何發生以及如何避免它們，將幫助您有效地使用 HashMap。

Java 中的 HashMap 是什麼？