Java HashMap原理解析

HashMap是Java中常用的一種數據結構，主要用於存儲鍵值對。它基於哈希表實現，其中鍵和值都可以為null。HashMap有著優秀的插入和查找效率，因此得到了廣泛的應用。本文將對Java HashMap的具體實現進行詳細闡述，包括哈希表的結構、擴容機制、實現原理以及在Java8中的優化。

一、哈希表的結構

HashMap底層是一個「鏈表散列」的結構，即數組和鏈表的結合體。具體而言，HashMap底層是一個數組(table數組)，數組中的每個元素稱為桶(bucket)，每個桶中又存放著鏈表。當鍵值對被put進Hashmap中時，通過hash函數計算出對應的hash值（即桶的index），然後將鍵值對加入到對應桶的鏈表中。

下面是一個簡單的HashMap示意圖：

             +----+    +----+
    table[0] |    | -> |    |
             +----+    +----+
    table[1] |    | -> |    |
             +----+    +----+
          ... 
             +----+    +----+             +----+
    table[n] |    | -> |    | -> ... -> |    |
             +----+    +----+             +----+

上圖中table數組長度為n，每個元素是一個鏈表的頭結點。每個鏈表頭節點代表桶，對應的鏈表中存儲了hash值相同的鍵值對。

二、擴容機制

當HashMap中存儲的鍵值對數量達到一定程度時（即超過了容量*負載因子），HashMap就需要對table數組進行擴容，以保證存儲空間的充足。

Java8之前的默認負載因子為0.75，意味著table數組的容量為n時，最多可存放n*0.75個鍵值對。當所存儲的鍵值對數量即將超過容量時，HashMap會將table數組的長度擴大為原來的兩倍，即將容量翻倍，然後將原來的鍵值對重新哈希到新數組中。

下圖是HashMap擴容前後的對比示意圖：

    // table長度為4，負載因子為0.75，最多存儲3個鍵值對
                    +--------------+
                    |              |
                    v              |
    +------+------+------+------+
    | node | node | null | null |
    +------+------+------+------+

    // 添加第4個鍵值對時，HashMap擴容，將table長度擴大為8
                           +------------------------+
                           |                        |
                           v                        |
    +------+------+------+------+------+------+------+------+ 
    | node | node | null | null | null | null | null | null | 
    +------+------+------+------+------+------+------+------+

擴容時，原來的鍵值對仍然存儲在原有的桶對應的鏈表中，而新添加的鍵值對則可能會散落到新的桶鏈表中。

三、實現原理

HashMap是一個典型的哈希表，它本質上是通過哈希函數將鍵映射到桶的位置，然後將鍵值對存儲在對應桶的鏈表中。HashMap中使用的哈希表具有以下特點：

哈希表桶數量不固定，動態擴容；
哈希函數計算儘可能地減少哈希衝突發生的概率；
鍵值對存儲方式為鏈表；
鏈表長度較長時，自動轉化為紅黑樹，以提高查找效率；
鍵和值均可為null。

根據Java8的源碼，HashMap的哈希函數實現如下：

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

可以看出，哈希函數主要由兩個步驟組成：獲取鍵的hashCode，然後通過位運算（異或運算和無符號右移操作）將高位的影響降低，使得得到的hash值更加亂序。

對於哈希衝突的處理方式，HashMap採用的是拉鏈法。即當出現哈希衝突時，將鍵值對添加至對應桶的鏈表中，之後根據鍵的equals方法找到對應的節點，即可獲取或修改對應的值。

在Java8中，為了提高HashMap的查找效率，引入了紅黑樹的優化。當桶的長度大於等於8時，將鏈錶轉化為平衡樹。通過紅黑樹的查找方式，可以將查找效率提高至O(log n)。

四、在Java8中的優化

在Java8中，HashMap進行了大量的優化，主要有以下幾點：

哈希表的長度不再以2的整數次冪為基礎，而是使用保持2的整數次冪的最小值的方法來分配桶的數量。
桶的數量很少，因為HashMap使用了紅黑樹，這樣鏈表很長的目標性從O(n)變成了O(log n)。
引入了TreeNode，當桶中鏈表的長度超過8時，鏈表會轉化為紅黑樹，以提高查找效率。
當鏈表的長度小於等於6時，會轉為鏈表，避免了因為節點太少轉換為樹而帶來的額外開銷。
在遍歷HashMap時，使用了迭代器，使得在遍歷時可以通過指向後一個元素的指針，快速進行下一輪迭代。

下面是Java8中紅黑樹的示意圖：

    +-------------+
    |             |
    v             |
  +------+     +------+
  | node |---->| node |--->...
  +------+     +------+
             |     |
             v     v
           +-----+-----+
           | 黑(bo) | 黑(bo) |
           +-----+-----+
             |     |
             v     v
           +------+------+
           | node | node |
           +------+------+
           |      |      |
           v      v      v
           .      .      .
           .      .      .
           .      .      .

五、代碼演示

以下代碼演示了如何創建HashMap，添加鍵值對和遍歷HashMap：

import java.util.*;

public class HashMapDemo {
    public static void main(String[] args) {
        // 創建HashMap並添加鍵值對
        Map map = new HashMap();
        map.put("apple", 1);
        map.put("banana", 2);
        map.put("orange", 3);

        // 遍歷HashMap
        for (Map.Entry entry : map.entrySet()) {
            System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
        }
    }
}

輸出：

Key: orange, Value: 3
Key: banana, Value: 2
Key: apple, Value: 1

六、總結

本文對Java HashMap進行了詳細的闡述，包括哈希表的結構、擴容機制、實現原理以及在Java8中的優化。HashMap是Java中非常重要的數據結構之一，在實際開發中經常用來存儲大量的鍵值對。熟悉HashMap的實現原理，有助於我們更好地理解其使用方法，避免出現一些隱晦的問題。

原創文章，作者：小藍，如若轉載，請註明出處：https://www.506064.com/zh-tw/n/199212.html