HashMap的put方法實現機制

一、HashMap簡介

HashMap是一個常用的數據結構，它實現了一個鍵值對映射的哈希表。它通過將鍵映射到bucket中，來實現快速的查找。HashMap中每個bucket會保存一個entry鏈表或是紅黑樹，如果鏈表的長度超過了一個預定的閥值，就會將鏈錶轉換為紅黑樹，這樣可以提高查找的效率。

二、HashMap的put方法實現

HashMap的put方法實現比較複雜，它會涉及到哈希值計算、尋找桶、查找以及對桶進行操作等操作。

1. 哈希值計算

在插入元素時，HashMap會根據元素的key來計算它的哈希值。這個哈希值是一個int類型的值，它的作用是用來確定該元素的桶位置。將哈希值對桶數組的長度取模，得到的餘數就是該元素所在桶的位置。具體的計算方式為：

/**
 * 計算key的哈希值
 */
final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

其中，key.hashCode()計算出的哈希值可能會產生衝突，為了減少衝突，Java使用了一種演算法將key.hashCode()的高16位與低16位進行異或運算，得到一個更加均勻分布的哈希值。

2. 尋找桶

在得到元素的哈希值後，需要根據哈希值來找到對應的桶，這個過程叫做尋找桶。HashMap使用一個數組來存儲桶，使用哈希值對數組長度取模可以得到對應的桶的位置。

/**
 * 根據哈希值獲取桶的位置
 */
final Node getNode(int hash, Object key) {
    Node[] tab; 
    Node first, e; 
    int n; 
    K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // ...
    }
    return null;
}

在這段代碼中，tab表示桶數組，如果桶數組不為空，那麼根據桶數組的長度和元素的哈希值得到的下標找到對應的桶first。該桶first是一個單向鏈表的頭節點，如果first不為空，就遍歷該鏈表，找到對應的元素。

3. 查找

在找到元素所在的桶後，需要在桶中查找該元素。由於HashMap中每個桶會存儲一個entry鏈表或是紅黑樹，所以需要根據鏈表或紅黑樹的數據結構不同，採用不同的方式進行查找。

對於entry鏈表，查找方式為遍歷鏈表。遍歷鏈表的過程是一個while循環，不斷將當前節點更新為下一個節點，直到找到對應的元素為止。

/**
 * 在桶中查找元素
 */
for (e = first; e != null; e = e.next) {
    if ((e.hash == hash) && ((k = e.key) == key || (key != null && key.equals(k)))) {
        oldValue = e.value;
        if (!onlyIfAbsent || oldValue == null)
            e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
}

對於紅黑樹，查找方式為紅黑樹的查找方式。紅黑樹是一種自平衡的二叉查找樹，它的查找操作的時間複雜度是O(log n)。

/**
 * 在紅黑樹中查找元素
 */
else if (p instanceof TreeNode)
    oldValue = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);

4. 對桶進行操作

在完成查找操作後，就可以根據查找的結果對桶進行相關操作。主要分為以下兩種情況：

1）在桶中未找到對應元素，需要將元素添加到桶中。

/**
 * 向桶中插入元素
 */
void addEntry(int hash, K key, V value, int bucketIndex) {
    // ...
    createEntry(hash, key, value, bucketIndex);
    if (size++ >= threshold)
        resize(2 * table.length);
    afterNodeInsertion(true);
}

在插入元素時，如果桶中未找到對應元素，那麼就需要將該元素添加到桶中。這時需要將元素插入到鏈表或紅黑樹的末尾。如果插入後鏈表長度超過了一定長度，就需要將鏈錶轉換為紅黑樹，以提高查找效率。除此之外，如果插入元素後HashMap的容量已經達到閥值，那麼就需要對桶數組進行擴容，以便存放更多的元素。

2）在桶中找到對應元素，需要更新該元素的值。

/**
 * 更新桶中的元素
 */
if (e != null) { 
    V oldValue = e.value;
    if (!onlyIfAbsent || oldValue == null)
        e.value = value;
    afterNodeAccess(e);
    return oldValue;
}

更新桶中元素的過程比較簡單，只需要將新的值賦給該元素即可。

三、總結

HashMap是一個重要的數據結構，在Java開發中被廣泛使用。它的put方法實現機制比較複雜，需要涉及到哈希值計算、尋找桶、查找以及對桶進行操作等多個步驟。掌握HashMap的put方法實現機制能夠幫助我們更好地理解和使用HashMap。