詳解Java中HashMap的put方法實現原理

一、HashMap概述

HashMap是Java中常用的一種數據結構，它是基於哈希表實現的一種Map接口。在HashMap中，通過把key映射到數組上來實現快速訪問。接下來，我們將針對HashMap的數據結構和put方法進行詳解。

二、HashMap的數據結構

在看put方法實現原理之前，首先需要了解HashMap的數據結構，HashMap採用的數據結構是Array+LinkedList，即鏈表散列。它的核心在於把對象的關鍵字（key）映射到一個整數上，這個整數將作為一個索引，指向存儲這個關鍵字的實際對象的位置。這個對象可以在數組的這個位置上或者在對應的鏈表中。

public class HashMap extends AbstractMap
    implements Map, Cloneable, Serializable {
    /** 存儲元素的數組 */
    transient Node[] table; 
    /** HashMap的大小 */
    transient int size; 
    /** HashMap被修改的次數 */
    transient int modCount; 
    /** 閾值 */
    int threshold; 
    /** 加載因子 */
    final float loadFactor;
}

HashMap中存儲元素的數組是Node類型，其中Node類型是一個雙向鏈表結構，它的結構如下：

static class Node implements Map.Entry {
    final int hash; // 哈希值
    final K key; // 鍵
    V value; // 值
    Node next; // 指向下一個節點的引用
    ...
}

當在HashMap中添加元素的時候，它會計算出每個鍵(key)對應的哈希值，然後用哈希值除以數組長度，取得餘數，把鍵(key)放入到相應的數組元素中。在同一個數組元素中，保留了一個鏈表結構，用來存儲有相同哈希值的元素。

三、put方法實現原理

put方法是向HashMap中添加元素的方法，在了解了HashMap的數據結構後，我們來看看put方法的實現原理。

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node[] tab; 
    Node p; 
    int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

HashMap的put方法通過哈希值計算和數組索引計算來存儲和定位元素。在執行put方法時，它首先計算出哈希值，然後找到對應的數組元素，如果該元素為null，則說明數組該位置沒有元素，直接把新元素插入到數組中。

接下來，如果該元素不為null，則需要看一下當前元素的哈希值是否與新元素相同，如果相同，則需要比較這兩個元素是否equals，如果equals返回true，則說明這個鍵已經存在於HashMap中，則把原來的value返回，否則，用新的value替換掉舊的value。

如果當前元素不為null，並且當前元素的哈希值與新元素的哈希值不同，則需要在當前元素的鏈表中往後查找，找到相同哈希值的元素，然後比較這兩個元素是否equals，如果equals返回true，則說明這個鍵已經存在於HashMap中，則把原來的value返回，否則，用新的value替換掉舊的value。

在查詢過程中，如果該元素為TreeNode類型，則說明該元素已經轉換為紅黑樹，此時，需要執行紅黑樹結構插入操作。

如果鏈表的長度達到閾值TREEIFY_THRESHOLD（默認值為8），則需要把鏈錶轉換為紅黑樹結構，從而提高查詢效率。

在把元素插入的過程中，如果HashMap中元素的個數達到了閾值，則需要擴大HashMap的容量，使得它可以容納更多的元素。在擴容過程中，較小容量的哈希表會複製到新表中，並且所有的元素都將會根據它們的哈希值重新分區到新表中。

四、小結

HashMap是Java中的一個重要數據結構，它是一個非常優秀的哈希表實現。在添加元素時，它採用哈希值計算和數組索引定位元素，還採用了鏈表散列和紅黑樹結構，使得它的查詢效率非常高。因此，在Java開發中，HashMap是一個常見的數據結構，尤其是存儲鍵值對的場景。而理解HashMap的實現原理，則是理解Java中哈希表實現的基礎。