Java中HashMap的put方法實現原理

一、數據結構介紹

HashMap是Java中常用的一種集合，是基於一定的hash算法實現的Key-value數據結構。HashMap類繼承於AbstractMap類，實現了Map接口。HashMap的底層實現是數組加鏈表或紅黑樹，通過key的hash值來找到其在數組中的位置，然後將其存儲在該位置的鏈表或紅黑樹中。

public class HashMap extends AbstractMap
    implements Map, Cloneable, Serializable {
        ...
    }

二、put方法

put方法是HashMap中最關鍵的方法之一，它負責將一個鍵值對存儲到Map中。put方法有兩個參數，第一個是key，第二個是value，該方法的返回值是被替換的value，如果之前沒有關聯的value則返回null。

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

可以看到，put方法的核心是putVal方法，該方法對外部不可見，它將key-value對插入到HashMap中，並且可以進行擴容和重新哈希處理。

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) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

三、put實現原理

put方法主要通過以下幾個步驟實現：

1. 如果table為null，或者table數組長度為0，執行resize方法進行初始化，否則直接用當前table數組存儲值。
2. 通過(key.hash) & (n-1)計算key的哈希值，並找到它在table中需要存儲的位置 i。
3. 檢查table[i]的這個位置是否已經有了值(e)，如果沒有，就把新的鍵值對放到table[i]的位置上。
4. 如果已經存在節點e，即table[i]位置已被佔用，則需要進一步判斷e和新插入元素的key是否相同，如果相同，則覆蓋原本的值，否則，需要判斷e所在節點的類型，如果是紅黑樹節點，則插入紅黑樹，否則在鏈表末尾追加節點。
5. 如果鏈表長度超過TREEIFY_THRESHOLD(默認值為8)時，則將鏈錶轉化成紅黑樹。TREEIFY_THRESHOLD是為了避免鏈表過長導致查詢時間複雜度增加。
6. 在插入節點後，判斷是否超過容量閾值(threshold)，如果超過，進行擴容操作，將table數組長度翻倍。

四、實戰應用

下面是一個簡單的HashMap使用示例，通過put方法向map中存儲數據。

HashMap map = new HashMap();
map.put(1, "one");
map.put(2, "two");
map.put(3, "three");
System.out.println(map.get(1)); //"one"
System.out.println(map.get(2)); //"two"
System.out.println(map.get(3)); //"three"

五、總結

本篇文章介紹了Java中HashMap的put方法實現原理，分別通過數據結構介紹、put方法、put實現原理和實戰應用等方面進行了詳細闡述。

為了保證HashMap的效率，需要在設計key的時候盡量避免哈希衝突，這樣可以減少鏈表的長度，提高HashMap的查詢效率。同時需要注意TREEIFY_THRESHOLD的值，這個值設置過小會導致鏈表膨脹成紅黑樹的過快，大大降低查詢性能。