Java中HashMap的put過程詳解

更新時間：2023年07月25日 11:25:44 作者：「已注銷」

這篇文章主要介紹了Java中HashMap的put過程詳解,HashMap有4個構造器，其他構造器如果用戶沒有傳入initialCapacity?和loadFactor這兩個參數(shù)，會使用默認值一般如果new?HashMap()不傳值,需要的朋友可以參考下

HashMap put過程

初始化

HashMap有4個構造器，其他構造器如果用戶沒有傳入initialCapacity 和loadFactor這兩個參數(shù)，會使用默認值一般如果new HashMap() 不傳值，默認大小是16，負載因子是0.75， 如果自己傳入初始大小k，初始化大小為大于k的 2的整數(shù)次方，例如如果傳10，大小為16。

put()過程

判斷數(shù)組是否為空，為空進行初始化; 不為空，計算 key的 hash 值，通過(n - 1) & hash（記不住就直接說哈希算法）計算應當存放在數(shù)組中的下標 index;查看 table[index] 是否存在數(shù)據(jù)，沒有數(shù)據(jù)就構造一個Node節(jié)點存放在 table[index] 中；存在數(shù)據(jù)，說明發(fā)生了hash沖突(存在兩個節(jié)點key的hash值一樣), 繼續(xù)判斷key是否相等，相等，用新的value替換原數(shù)據(jù)(onlyIfAbsent為false)；如果不相等，判斷當前節(jié)點類型是不是樹型節(jié)點，如果是樹型節(jié)點，創(chuàng)造樹型節(jié)點插入紅黑樹中；(如果當前節(jié)點是樹型節(jié)點證明當前已經(jīng)是紅黑樹了) 如果不是樹型節(jié)點，創(chuàng)建普通Node加入鏈表中；判斷鏈表長度是否大于 8并且數(shù)組長度大于64，大于的話鏈表轉換為紅黑樹;

插入完成之后判斷當前節(jié)點數(shù)是否大于閾值，如果大于開始擴容為原數(shù)組的二倍。

// put源碼
public V put(K key, V value) {
        //如果table數(shù)組為空數(shù)組{}，進行數(shù)組填充（為table分配實際內(nèi)存空間），入?yún)閠hreshold，
        //此時threshold為initialCapacity 默認是1<<4(2^4=16)
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
       //如果key為null，存儲位置為table[0]或table[0]的沖突鏈上
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);//對key的hashcode進一步計算，確保散列均勻
        int i = indexFor(hash, table.length);//獲取在table中的實際位置
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        //如果該對應數(shù)據(jù)已存在，執(zhí)行覆蓋操作。用新value替換舊value，并返回舊value
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;//保證并發(fā)訪問時，若HashMap內(nèi)部結構發(fā)生變化，快速響應失敗
        addEntry(hash, key, value, i);//新增一個entry
        return null;
    }

inflateTable這個方法用于為主干數(shù)組table在內(nèi)存中分配存儲空間，通過roundUpToPowerOf2(toSize)可以確保capacity為大于或等于toSize的最接近toSize的二次冪，比如toSize=13,則capacity=16;to_size=16,capacity=16;to_size=17,capacity=32.

void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);//當size超過臨界閾值threshold，并且即將發(fā)生哈希沖突時進行擴容
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
        createEntry(hash, key, value, bucketIndex);
    }

通過以上代碼能夠得知，當發(fā)生哈希沖突并且size大于閾值(threshold)的時候，需要進行數(shù)組擴容，擴容時，需要新建一個長度為之前數(shù)組2倍的新的數(shù)組，然后將當前的Entry數(shù)組中的元素全部傳輸過去，擴容后的新數(shù)組長度為之前的2倍，所以擴容相對來說是個耗資源的操作。

為什么HashMap數(shù)組長度一定要是2的n次冪

計算索引位置的公式為：(n - 1) & hash，當 n 為 2 的 N 次方時，n - 1 為低位全是 1 的值，此時任何值跟 n - 1 進行 & 運算的結果為該值的低 N 位，達到了和取模同樣的效果，實現(xiàn)了均勻分布。實際上，這個設計就是基于公式：x mod 2^n = x & (2^n - 1)，因為 & 運算比 mod 具有更高的效率總的來說原因是2^n-1的低位是1，在進行與運算時更加高效，同時還可以降低hash沖突

什么時候轉紅黑樹

因為當桶中元素到達8個的時候，概率已經(jīng)變得非常小，也就是說用0.75作為負載因子，每個碰撞位置的鏈表長度超過8個是幾乎不可能的（概率極小）。（也就是超過8 可以轉化為紅黑樹）

并且如果鏈表的長度大于 8 會嘗試調(diào)用 treeifyBin 方法
再判斷表的長度是否大于64

在鏈表長度大于 8 并且表的長度大于 64 的時候會轉化紅黑樹?。。?！

if ((e = p.next) == null) {
    p.next = newNode(hash, key, value, null);
    // 并且如果 鏈表的長度 大于 8 會嘗試調(diào)用  treeifyBin 方法
    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
        treeifyBin(tab, hash);
    break;
}
// treeifyBin 方法
    final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        // 如果表的長度小于 64 會先擴容！??！ 否則 擴容
        // MIN_TREEIFY_CAPACITY = 64;
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

為什么鏈表閾值是8

我們平時在進行方案設計時，必須考慮的兩個很重要的因素是：時間和空間。對于 HashMap 也是同樣的道理，簡單來說，閾值為8是在時間和空間上權衡的結果。

科學解釋

理想情況下，使用隨機的哈希碼，節(jié)點分布在 hash 桶中的頻率遵循泊松分布，按照泊松分布的公式計算，鏈表中節(jié)點個數(shù)為8時的概率為 0.00000006（跟大樂透一等獎差不多，中大樂透？不存在的），這個概率足夠低了，并且到8個節(jié)點時，紅黑樹的性能優(yōu)勢也會開始展現(xiàn)出來，因此8是一個較合理的數(shù)字。