高頻考題：手寫(xiě)HashMap

JDK7、8擴(kuò)容源碼級(jí)詳解

JDK7、8HashMap的get()、put()流程詳解

JDK7 HashMap

JDK7HashMap在多線程環(huán)境下會(huì)出現(xiàn)死循環(huán)問(wèn)題。

假如此時(shí)A、B線程同時(shí)對(duì)一個(gè)HashMap進(jìn)行put操作，且HashMap剛號(hào)達(dá)到擴(kuò)容條件需要進(jìn)行擴(kuò)容

那么這兩個(gè)線程都會(huì)取對(duì)HahsMap進(jìn)行擴(kuò)容（JDK7HashMap擴(kuò)容調(diào)用 resize()方法，而resize()方法中需要調(diào)用transfer()方法將舊數(shù)組元素全部rehash到新數(shù)組中去==重點(diǎn)：這里在多線程環(huán)境下就會(huì)出現(xiàn)問(wèn)題==）

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }

    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}


void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    //對(duì)數(shù)組的每一條鏈表遍歷rehash
    for (Entry<K,V> e : table) {
        while(null != e) {
            //保留下一個(gè)節(jié)點(diǎn)
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            //得到對(duì)應(yīng)在新數(shù)組中的索引位置
            int i = indexFor(e.hash, newCapacity);
            
            //尾插法
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

我們假設(shè)現(xiàn)在有一個(gè)鏈表 C——>D,且C、D擴(kuò)容后計(jì)算的索引位置依然不變，那他么還在同一鏈表中

現(xiàn)在A線程進(jìn)入到transfer方法拿到C和它的下一個(gè)節(jié)點(diǎn)D(Entry<K,V> next = e.next;)后，A線程被掛起，此時(shí)B線程正常走流程將C、D rehash到新的數(shù)組中，那么根據(jù)頭插法在新的數(shù)組中是D——>C

B執(zhí)行完之后，A線程繼續(xù)去執(zhí)行

因?yàn)锳獲取到了 e = C,next = D,所以C可以進(jìn)行rehash，C進(jìn)行完后拿到D，發(fā)現(xiàn)D.next = C,所以D也可以進(jìn)行rehash，那么此時(shí)因?yàn)镈——>C,此時(shí)會(huì)再拿到C，發(fā)現(xiàn)C.next = null，但C不是null，所以C再進(jìn)行rehash，此時(shí)鏈表尾 C——> D ——>C,因?yàn)榇藭r(shí)e = NULL，所以退出循環(huán)，此時(shí)出現(xiàn)死循環(huán)。C——>D——>C。

==各位可以好好想想這些話或者自己在草稿紙上畫(huà)一畫(huà)再來(lái)看下面的圖！==

圖示演示：

在這里插入圖片描述

==B正常執(zhí)行完成==

在這里插入圖片描述

==A繼續(xù)執(zhí)行==

因?yàn)锳獲取到了 e = C,next = D,所以C可以進(jìn)行rehash

在這里插入圖片描述

C進(jìn)行完后拿到e = D，發(fā)現(xiàn)D.next = C,所以D也可以進(jìn)行rehash

在這里插入圖片描述

那么此時(shí)因?yàn)镈——>C,此時(shí)會(huì)再拿到C，發(fā)現(xiàn)C.next = null，但C不是null，所以C再進(jìn)行rehash

在這里插入圖片描述

此時(shí)e = NULL，所以退出循環(huán)，此時(shí)出現(xiàn)死循環(huán)。C——>D——>C。

JDK8 HashMap

JDK1.8會(huì)出現(xiàn)數(shù)據(jù)覆蓋的情況

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> 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<K,V> 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<K,V>)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;
}

• ==第6行代碼==：假設(shè)兩個(gè)線程A、B都在進(jìn)行put操作，并且根據(jù)key計(jì)算出的hash值相同，那么得到得索引下標(biāo)也相同，當(dāng)線程A執(zhí)行完第六行代碼后由于時(shí)間片耗盡導(dǎo)致被掛起，而線程B得到時(shí)間片后在該下標(biāo)處插入了元素，完成了正常的插入，然后線程A獲得時(shí)間片，由于之前已經(jīng)進(jìn)行了hash碰撞的判斷，所有此時(shí)不會(huì)再進(jìn)行判斷，而是直接進(jìn)行插入，這就導(dǎo)致了線程B插入的數(shù)據(jù)被線程A覆蓋了，從而線程不安全。

• ==第38行代碼==++size不安全，還是線程A、B，這兩個(gè)線程同時(shí)進(jìn)行put操作時(shí)，假設(shè)當(dāng)前HashMap的zise大小為10，當(dāng)線程A執(zhí)行到第38行代碼時(shí)，從主內(nèi)存中獲得size的值為10后準(zhǔn)備進(jìn)行+1操作，但是由于時(shí)間片耗盡只好讓出CPU，線程B快樂(lè)的拿到CPU還是從主內(nèi)存中拿到size的值10進(jìn)行+1操作，完成了put操作并將size=11寫(xiě)回主內(nèi)存，然后線程A再次拿到CPU并繼續(xù)執(zhí)行(此時(shí)size的值仍為10)，當(dāng)執(zhí)行完put操作后，還是將size=11寫(xiě)回內(nèi)存，此時(shí)，線程A、B都執(zhí)行了一次put操作，但是size的值只增加了1，所有說(shuō)還是由于數(shù)據(jù)覆蓋又導(dǎo)致了線程不安全。

最后

我是 Code皮皮蝦，一個(gè)熱愛(ài)分享知識(shí)的 皮皮蝦愛(ài)好者，未來(lái)的日子里會(huì)不斷更新出對(duì)大家有益的博文，期待大家的關(guān)注?。。?/strong>