Java HashMap深度剖析

一、什麼是HashMap

HashMap是Java集合框架中的一個類，它實現了Map接口，用於存儲鍵值對，其中鍵和值均可以為null。HashMap提供了O(1)的時間複雜度來實現put()和get()方法的添加和查詢操作。具體實現方式是通過將鍵對象的hashCode值映射到存儲數組的索引位置來進行存儲。

二、HashMap的存儲結構

HashMap的基本存儲結構是一個Entry數組，Entry類就是HashMap中存儲每個鍵值對的容器。下面是Entry類的定義：

class Entry {
    final int hash;
    final K key;
    V value;

    Entry next;

    Entry(int h, K k, V v, Entry n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }
}

可以看到每個Entry對象都包含了一個int類型的hash值，表示當前鍵對象的hash值。通過hashCode()方法可以把鍵對象映射為一個int值，這個int值被稱為散列碼（hash code）。

Entry還包含了一個next屬性，用於指向桶中的下一個鍵值對，如果同一個桶中有多個鍵值對，就會形成一個鏈表。

三、Hash算法

在HashMap中，鍵值對是根據它們的hashCode()和equals()方法來存儲並獲取的。hashCode()方法生成了一個int範圍內的散列碼，這個散列碼會被用來計算出在Entry數組中存儲的索引位置。由於可能存在不同的鍵對象hash值相同的情況，因此同一個桶里可能存在多條鏈表，需要遍歷鏈表來查找真正的鍵值對。

在默認情況下，HashMap的hash算法如下：

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

首先，如果鍵對象為null，則直接返回0作為hash值。如果鍵對象不為null，則將hashCode()方法的返回值賦值為h。接着，將h右移16位並將h與其異或（^）後的結果返回為最終的hash值。

四、解決哈希衝突

哈希衝突是指不同的鍵對象在通過hash算法之後生成了相同的hash值，導致它們應該被存儲在同一個桶中，從而引發鏈表的形成。在存儲鍵值對時，當一個新的鍵值對需要存儲時，HashMap會通過計算key對象的hash值來得到存儲在數組中的位置，如果該位置已經有其他鍵值對存在，新的鍵值對就需要放在同一個桶中，否則將直接存儲在該位置上，此過程被稱為哈希衝突解決，具體實現方法有兩種：鏈表法和開放尋址法。

五、擴容

在 HashMap 的底層是基於數組和鏈表實現的，因此在存儲的鍵值對會越來越多的時候，HashMap 底層會進行擴容以保證查詢效率。當HashMap達到一定的負載因子時（默認為0.75），會觸發擴容操作。擴容的過程就是將原來的Entry數組擴大為原來的兩倍，同時將原來的鍵值對重新計算hash值，然後重新存儲在新的數組中。

六、應用場景

HashMap在Java中被廣泛應用，它適用於需要搜索、插入和刪除元素頻繁的場景。比如，在Web框架的緩存中，使用HashMap緩存數據能夠有效地提高查詢性能。在開發過程中，需要注意多線程並發訪問的問題，可以使用ConcurrentHashMap來替代HashMap。