[[356772]]

本文轉(zhuǎn)載自微信公眾號(hào)「Java極客技術(shù)」，作者鴨血粉絲 。轉(zhuǎn)載本文請(qǐng)聯(lián)系Java極客技術(shù)公眾號(hào)。  

阿粉今天就來(lái)談?wù)勥@個(gè)，這個(gè)問(wèn)題在 1.7 版本和 1.8 版本中都有，阿粉分別來(lái)說(shuō)說(shuō)

在說(shuō)之前，咱們先要達(dá)成一個(gè)共識(shí)：HashMap 發(fā)生數(shù)據(jù)覆蓋的問(wèn)題，是在多線程環(huán)境 & 擴(kuò)容下產(chǎn)生的，接下來(lái)咱們具體來(lái)看

jdk 1.7

void transfer(Entry[] newTable, boolean rehash) {   
       int newCapacity = newTable.length;   
       for (Entry<K,V> e : table) {   
  
           while(null != e) {   
               Entry<K,V> next = e.next;            
               if (rehash) {   
                   e.hash = null == e.key ? 0 : hash(e.key);   
               }   
               int i = indexFor(e.hash, newCapacity);    
               e.next = newTable[i];   
               newTable[i] = e;  // 線程 A 運(yùn)行到這里時(shí)被掛起 
               e = next;   
           }  
       }   
   }   

在擴(kuò)容時(shí)，發(fā)生數(shù)據(jù)覆蓋問(wèn)題主要核心就是上面的代碼，我們假設(shè)一下，剛開始時(shí)，結(jié)構(gòu)是這樣的：

現(xiàn)在有兩個(gè)線程 A 和 B ，它們都要進(jìn)行插入操作，首先 A 進(jìn)行插入操作，經(jīng)過(guò) Hash 之后就得到了要落到的桶的索引坐標(biāo)，運(yùn)行到 newTable[i] = e; 這行代碼時(shí)， CPU 時(shí)間片用完了，此時(shí)線程 A 就停止運(yùn)行被掛起，這個(gè)時(shí)候是這個(gè)樣子的：

線程 A 被掛起之后，線程 B 被調(diào)度得以運(yùn)行，巧的是，線程 B 經(jīng)過(guò) Hash 之后得到的要落到的桶索引坐標(biāo)和線程 A 一樣，此時(shí)線程 B 也進(jìn)行插入操作，線程 B 因?yàn)闀r(shí)間片足夠用，所以就成功的將記錄插入到了桶里面：

線程 B 插入成功之后，根據(jù) Java 內(nèi)存模型，此時(shí)主內(nèi)存中存放的值就是線程 B 運(yùn)行之后的結(jié)果

接下來(lái)線程 A 被喚醒，繼續(xù)執(zhí)行插入操作。對(duì)于 A 來(lái)說(shuō)，前面的步驟都已經(jīng)執(zhí)行過(guò)了，所以就不需要再次運(yùn)行，直接從 newTable[i] = e; 這行代碼開始往下繼續(xù)運(yùn)行即可，線程 A 保存的環(huán)境是 e = 12 next = 6 e.next = newTable[i]; 即 newTable[3] = null; ，那么接下來(lái)執(zhí)行 newTable[i] = e; & e = next 也就是 newTable[3] = 12 e = next = 6 執(zhí)行完畢之后，大概就是這樣：

元素 15 就這么被覆蓋掉了

jdk 1.8

看完 1.7 之后，咱們?cè)賮?lái)看看 1.8 版本。數(shù)據(jù)覆蓋主要發(fā)生在 put 操作中，下面是 1.8 源碼(阿粉在這里截取了一小部分)：

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)     // 如果沒(méi)有 hash 碰撞，則直接插入 
         tab[i] = newNode(hash, key, value, null); 
 } 

在上面的代碼中，我們能夠看到，源碼只是判斷了 hash 是否有碰撞，如果沒(méi)有就不再做別的檢查進(jìn)行插入操作

在多線程環(huán)境下，如果線程 1 檢查完了 hash 沒(méi)有碰撞，要進(jìn)行插入時(shí)， CPU 時(shí)間片使用完畢，此時(shí)它被掛起，線程 2 開始跑，無(wú)巧不成書嘛，此時(shí)線程 2 經(jīng)過(guò) hash 之后得到的值和線程 1 的 hash 值一樣，線程 2 將值插入進(jìn)去，線程 1 恢復(fù)運(yùn)行，因?yàn)榍懊鏅z查了 hash 碰撞，此時(shí)插入時(shí)不再做任何檢查，直接將值插入

那么線程 2 插入的值就被覆蓋掉了

HashMap 之所以發(fā)生數(shù)據(jù)覆蓋的問(wèn)題，最主要的原因在于它沒(méi)有加鎖，所以在多線程環(huán)境下會(huì)發(fā)生數(shù)據(jù)覆蓋問(wèn)題

修正一個(gè)問(wèn)題

在 面試官你能不能別問(wèn)我 HashMap 了? 這篇文章中，阿粉說(shuō)之所以是 8 轉(zhuǎn)為紅黑樹，和時(shí)間復(fù)雜度有關(guān)，后來(lái)經(jīng)過(guò)一位小伙伴留言才發(fā)現(xiàn)阿粉的思路錯(cuò)了，和泊松分布有關(guān)，這一點(diǎn)源碼中也有說(shuō)明：

Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution  
with a parameter of about 0.5 on average for the default resizing threshold of 0.75, although  
with a large variance because of resizing granularity. Ignoring variance, the expected  
occurrences of list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)).  
The first values are: 
      0:    0.60653066 
      1:    0.30326533 
      2:    0.07581633 
      3:    0.01263606 
      4:    0.00157952 
      5:    0.00015795 
      6:    0.00001316 
      7:    0.00000094 
      8:    0.00000006 
      more: less than 1 in ten million 

從源碼中可以看到，在負(fù)載因子 0.75 ( HashMap 默認(rèn))的情況下，單個(gè) hash 槽內(nèi)元素個(gè)數(shù)為 8 的概率為 0.00000006，是相當(dāng)小的一個(gè)值了，因此將 7 作為一個(gè)分水嶺，等于 7 時(shí)不做轉(zhuǎn)換，大于等于 8 才轉(zhuǎn)紅黑樹，小于等于 6 才轉(zhuǎn)鏈表。

哈希攪動(dòng)和高低 16 位有關(guān)系嗎?

有的小伙伴問(wèn)阿粉，哈希攪動(dòng)和高低 16 位有關(guān)系嗎?

阿粉不太清楚這個(gè)有關(guān)系是怎樣的一個(gè)有關(guān)系，但是 16 這個(gè)數(shù)字的選取，作者肯定也是經(jīng)過(guò)考慮之后再?zèng)Q定的

哈希攪動(dòng)主要發(fā)生在 resize() 這個(gè)方法中，我們可以看到源碼中的注釋：

Initializes or doubles table size.   
If null, allocates in  accord with initial capacity target held in field threshold.  
Otherwise, because we are using power-of-two expansion, the elements from each bin must either stay at same index, or move with a power of two offset in the new table. 

翻譯一下就是：在初始化或者增加表大小時(shí)，如果沒(méi)有指定，那么就按照初始容量來(lái)進(jìn)行分配。如果指定了，由于使用的是 2 的冪，所以每個(gè) bin 元素也必須保持相同的索引，或者在新表中以 2 的冪偏移

這樣看的話，好像和 16 位有點(diǎn)兒關(guān)系