首頁 > 軟體

你可知HashMap為什麼是執行緒不安全的

2022-10-14 14:00:54

 

 

HashMap 的執行緒不安全

HashMap 的執行緒不安全主要體現在下面兩個方面

  • 在 jdk 1.7 中,當並行執行擴容操作時會造成環形鏈和資料丟失的情況
  • 在 jdk 1.8 中,在並行執行 put 操作時會發生資料覆蓋的情況

對於 jdk 1.7 中 HashMap 的執行緒不安全,暫且不談了,我們主要看看 jdk 1.8 中的

HashMap 中的 put() 方法

該 put() 方法是 jdk 1.8 中的

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<K,V>[] tab; Node<K,V> p; int n, i;
    // 判斷 table[] 是否為空,如果是空的就建立一個 table[],並獲取他的長度n
    if ((tab = table) == null || (n = tab.length) == 0)
    	n = (tab = resize()).length;	
    // 如果單連結串列節點 Node<K,V> p == tab[i = (n - 1) & hash]) == null,
    // 就直接 put 進單連結串列中,說明此時並沒有發生 Hash 衝突
    if ((p = tab[i = (n - 1) & hash]) == null)
    	tab[i] = newNode(hash, key, value, null);
    else {
		// 說明索引位置已經放入過資料了,已經在單連結串列處產生了Hash衝突
        Node<K,V> e; K k;
		// 判斷 put 的資料和之前的資料是否重複
        if (p.hash == hash &&
            // 進行 key 的 hash 值和 key 的 equals() 和 == 比較,如果都相等,則初始化陣列 Node<K,V> e
            ((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 {
			// 如果不是紅黑樹,就遍歷每個節點,判斷單連結串列長度是否大於等於 7,
			// 如果單連結串列長度大於等於 7,陣列的長度小於 64 時,會優先選擇擴容
			// 如果單連結串列長度大於等於 7,陣列的長度大於 64 時,才會選擇單連結串列--->紅黑樹
            for (int binCount = 0; ; ++binCount) {
            	if ((e = p.next) == null) {
            		// 採用尾插法,在單連結串列中插入資料
                	p.next = newNode(hash, key, value, null);
                	// 如果 binCount >= 8 - 1
                    if (binCount >= TREEIFY_THRESHOLD - 1) 
                    	treeifyBin(tab, hash);
                        break;
                }
				// 判斷索引每個元素的key是否可要插入的key相同,如果相同就直接覆蓋
                if (e.hash == hash &&
					((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                 p = e;
			}
		}
		// 說明陣列或者單連結串列中有相同的key,因此只需要將value覆蓋,並將oldValue返回即可
        if (e != null) { 
        	V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
            	e.value = value;
                afterNodeAccess(e);
              	return oldValue;
        }
	}
	// 說明沒有key相同,因此要插入一個key-value,並記錄內部結構變化次數
    ++modCount;
    // 判斷是否擴容
    if (++size > threshold)
    	resize();
    afterNodeInsertion(evict);
    return null;
}

資料的覆蓋一

第 13 行程式碼是判斷是否出現 hash 衝突的,假設兩個執行緒 A、B 都在進行 put 操作,並且它們 put 資料的 key 的 hash 值是相同的,同時它們 keyA == keyB 為 true 或者 keyA.equals(keyB) 為 true,也就是說它們 put 資料的 value 是不相同的

當執行緒 A 執行完第 13 行程式碼後由於時間片耗盡導致被掛起,而執行緒 B 得到時間片後在該單連結串列處插入了元素,完成了正常的插入

然後執行緒 A 獲得時間片,由於之前已經進行了 hash 衝突的判斷,所有此時不會再進行判斷,而是直接進行插入覆蓋,這就導致了執行緒 B 插入的資料被執行緒 A 覆蓋了,從而發生了執行緒不安全

資料的覆蓋二

第 58 行處有個 ++size,我們這樣想,還是執行緒 A、B,這兩個執行緒同時進行 put 操作時,假設當前 HashMap 的 size 大小為 10

當執行緒 A 執行到第 58 行程式碼時,從主記憶體中獲得 size 的值為 10 後準備進行 +1 操作,但是由於時間片耗盡只好讓出 CPU

於是執行緒 B 得到 CPU 排程,還是從主記憶體中拿到 size 的值 10 進行 +1 操作,完成了 put 操作,並將 size = 11 寫回了主記憶體

然後執行緒 A 再次得到 CPU 排程,並繼續執行(此時 size 的值仍為10),當執行完 put 操作後,還是將 size = 11 寫了回記憶體。

此時,執行緒 A、B 都執行了一次 put 操作,但是 size 的值只增加了 1,所有說還是由於資料覆蓋又導致了執行緒不安全

// HashMap 中 size 變數
transient int size;

以上為個人經驗,希望能給大家一個參考,也希望大家多多支援it145.com。


IT145.com E-mail:sddin#qq.com