HashMap put過程

初始化

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

put()過程

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

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

// put源碼
public V put(K key, V value) {
        //如果table數(shù)組為空數(shù)組{}，進(jìn)行數(shù)組填充（為table分配實(shí)際內(nèi)存空間），入?yún)閠hreshold，
        //此時(shí)threshold為initialCapacity 默認(rèn)是1<<4(2^4=16)
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
       //如果key為null，存儲(chǔ)位置為table[0]或table[0]的沖突鏈上
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);//對(duì)key的hashcode進(jìn)一步計(jì)算，確保散列均勻
        int i = indexFor(hash, table.length);//獲取在table中的實(shí)際位置
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        //如果該對(duì)應(yīng)數(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ā)訪問時(shí)，若HashMap內(nèi)部結(jié)構(gòu)發(fā)生變化，快速響應(yīng)失敗
        addEntry(hash, key, value, i);//新增一個(gè)entry
        return null;
    }

inflateTable這個(gè)方法用于為主干數(shù)組table在內(nèi)存中分配存儲(chǔ)空間，通過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);//當(dāng)size超過臨界閾值threshold，并且即將發(fā)生哈希沖突時(shí)進(jìn)行擴(kuò)容
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
        createEntry(hash, key, value, bucketIndex);
    }

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

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

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

什么時(shí)候轉(zhuǎn)紅黑樹

因?yàn)楫?dāng)桶中元素到達(dá)8個(gè)的時(shí)候，概率已經(jīng)變得非常小，也就是說用0.75作為負(fù)載因子，每個(gè)碰撞位置的鏈表長(zhǎng)度超過8個(gè)是幾乎不可能的（概率極小）。（也就是超過8 可以轉(zhuǎn)化為紅黑樹）

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

在鏈表長(zhǎng)度大于 8 并且 表的長(zhǎng)度大于 64 的時(shí)候會(huì)轉(zhuǎn)化紅黑樹?。。?！

if ((e = p.next) == null) {
    p.next = newNode(hash, key, value, null);
    // 并且如果 鏈表的長(zhǎng)度 大于 8 會(huì)嘗試調(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;
        // 如果表的長(zhǎng)度小于 64 會(huì)先擴(kuò)容?。?！ 否則 擴(kuò)容
        // 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

我們平時(shí)在進(jìn)行方案設(shè)計(jì)時(shí)，必須考慮的兩個(gè)很重要的因素是：時(shí)間和空間。對(duì)于 HashMap 也是同樣的道理，簡(jiǎn)單來說，閾值為8是在時(shí)間和空間上權(quán)衡的結(jié)果。

科學(xué)解釋

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

那為什么紅黑樹轉(zhuǎn)回鏈表是6

因?yàn)橹虚g多個(gè)個(gè)7，不會(huì)使得紅黑樹和鏈表之間頻繁轉(zhuǎn)換，如果我們?cè)O(shè)置節(jié)點(diǎn)多于8個(gè)轉(zhuǎn)紅黑樹，少于8個(gè)就馬上轉(zhuǎn)鏈表，當(dāng)節(jié)點(diǎn)個(gè)數(shù)在8徘徊時(shí)，就會(huì)頻繁進(jìn)行紅黑樹和鏈表的轉(zhuǎn)換，造成性能的損耗

到此這篇關(guān)于Java中HashMap的put過程詳解的文章就介紹到這了,更多相關(guān)ashMap的put內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論