[[356772]]

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

阿粉今天就來談?wù)勥@個，這個問題在 1.7 版本和 1.8 版本中都有，阿粉分別來說說

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

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 運行到這里時被掛起 
               e = next;   
           }  
       }   
   }   

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

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

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

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

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

元素 15 就這么被覆蓋掉了

jdk 1.8

看完 1.7 之后，咱們再來看看 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)     // 如果沒有 hash 碰撞，則直接插入 
         tab[i] = newNode(hash, key, value, null); 
 } 

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

在多線程環(huán)境下，如果線程 1 檢查完了 hash 沒有碰撞，要進行插入時， CPU 時間片使用完畢，此時它被掛起，線程 2 開始跑，無巧不成書嘛，此時線程 2 經(jīng)過 hash 之后得到的值和線程 1 的 hash 值一樣，線程 2 將值插入進去，線程 1 恢復運行，因為前面檢查了 hash 碰撞，此時插入時不再做任何檢查，直接將值插入

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

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

修正一個問題

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

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 

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

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

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

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

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

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. 

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

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