我們都知道，HashMap在并發(fā)環(huán)境下使用可能出現(xiàn)問題，但是具體表現(xiàn)，以及為什么出現(xiàn)并發(fā)問題，可能并不是所有人都了解

這篇文章記錄一下HashMap在多線程環(huán)境下可能出現(xiàn)的問題以及如何避免。

在分析HashMap的并發(fā)問題前，先簡單了解HashMap的put和get基本操作是如何實現(xiàn)的。

1.HashMap的put和get操作

大家知道HashMap內(nèi)部實現(xiàn)是通過拉鏈法解決哈希沖突的，也就是通過鏈表的結(jié)構(gòu)保存散列到同一數(shù)組位置的兩個值，

put操作主要是判空，對key的hashcode執(zhí)行一次HashMap自己的哈希函數(shù)，得到bucketindex位置，還有對重復(fù)key的覆蓋操作。

對照源碼分析一下具體的put操作是如何完成的：

public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        //得到key的hashcode，同時再做一次hash操作
        int hash = hash(key.hashCode());
        //對數(shù)組長度取余，決定下標(biāo)位置
        int i = indexFor(hash, table.length);
        /**
          * 首先找到數(shù)組下標(biāo)處的鏈表結(jié)點，
          * 判斷key對一個的hash值是否已經(jīng)存在，如果存在將其替換為新的value
          */
        for (Entry
    
      e = table[i]; e != 
     null; e = e.next) {
     
            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++;
     
        addEntry(hash, key, 
     value, i);
     
        
     return 
     null;
     
    }
     

    

涉及到的幾個方法：

static int hash(int h) {
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

static int indexFor(int h, int length) {
        return h & (length-1);
    }

數(shù)據(jù)put完成以后，就是如何get，我們看一下get函數(shù)中的操作：

public V get(Object key) {
        if (key == null)
            return getForNullKey();
        int hash = hash(key.hashCode());
        /**
          * 先定位到數(shù)組元素，再遍歷該元素處的鏈表
          * 判斷的條件是key的hash值相同，并且鏈表的存儲的key值和傳入的key值相同
          */
        for (Entry
    
      e = table[indexFor(hash, table.length)];e != 
     null;e = e.next) {
     
            Object k;
     
            
     if (e.hash == hash && ((k = e.key) == key || key.
     equals(k)))
     
                
     return e.
     value;
     
        }
     
        
     return 
     null;
     
}
     

    

看一下鏈表的結(jié)點數(shù)據(jù)結(jié)構(gòu)，保存了四個字段，包括key，value，key對應(yīng)的hash值以及鏈表的下一個節(jié)點：

static class Entry<K,V> implements Map.Entry<K,V> {
       final K key;//Key-value結(jié)構(gòu)的key
       V value;//存儲值
       Entry
    
      next;
     //指向下一個鏈表節(jié)點
     
       
     final 
     int hash;
     //哈希值
     
 }
     

    

2.Rehash/再散列擴展內(nèi)部數(shù)組長度

哈希表結(jié)構(gòu)是結(jié)合了數(shù)組和鏈表的優(yōu)點，在最好情況下，查找和插入都維持了一個較小的時間復(fù)雜度O(1)

不過結(jié)合HashMap的實現(xiàn)，考慮下面的情況，如果內(nèi)部Entry[] tablet的容量很小，或者直接極端化為table長度為1的場景，那么全部的數(shù)據(jù)元素都會產(chǎn)生碰撞

這時候的哈希表成為一條單鏈表，查找和添加的時間復(fù)雜度變?yōu)镺(N)，失去了哈希表的意義。

所以哈希表的操作中，內(nèi)部數(shù)組的大小非常重要，必須保持一個平衡的數(shù)字，使得哈希碰撞不會太頻繁，同時占用空間不會過大。

這就需要在哈希表使用的過程中不斷的對table容量進行調(diào)整，看一下put操作中的addEntry()方法：

void addEntry(int hash, K key, V value, int bucketIndex) {
   Entry
    
      e = table[bucketIndex];
     
       table[bucketIndex] = 
     new Entry
     
      (hash, key, 
      value, e);
      
       
      if (size++ >= threshold)
      
           resize(
      2 * table.length);
      
   }
      

     
    

這里面resize的過程，就是再散列調(diào)整table大小的過程，默認(rèn)是當(dāng)前table容量的兩倍。

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];
       //初始化一個大小為oldTable容量兩倍的新數(shù)組newTable
       transfer(newTable);
       table = newTable;
       threshold = (int)(newCapacity * loadFactor);
   }

關(guān)鍵的一步操作是transfer(newTable)，這個操作會把當(dāng)前Entry[] table數(shù)組的全部元素轉(zhuǎn)移到新的table中，這個transfer的過程在并發(fā)環(huán)境下會發(fā)生錯誤，導(dǎo)致數(shù)組鏈表中的鏈表形成循環(huán)鏈表，在后面的get操作時e = e.next操作無限循環(huán)，Infinite Loop出現(xiàn)。

下面具體分析HashMap的并發(fā)問題的表現(xiàn)以及如何出現(xiàn)的。

3.HashMap在多線程put后可能導(dǎo)致get無限循環(huán)

HashMap在并發(fā)環(huán)境下多線程put后可能導(dǎo)致get死循環(huán)，具體表現(xiàn)為CPU使用率100%，看一下transfer的過程：

void transfer(Entry[] newTable) {
        Entry[] src = table;
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) {
            Entry
    
      e = src[j];
     
            
     if (e != 
     null) {
     
                src[j] = 
     null;
     
                
     do {
     
        
     //假設(shè)第一個線程執(zhí)行到這里因為某種原因掛起
     
                    Entry
     
       next = e.next;
      
                    
      int i = indexFor(e.hash, newCapacity);
      
                    e.next = newTable[i];
      
                    newTable[i] = e;
      
                    e = next;
      
                } 
      while (e != 
      null);
      
            }
      
        }
      
    }
      

     
    

這里引用酷殼陳皓的博文：

http://coolshell.cn/articles/9606.html

并發(fā)下的Rehash

1）假設(shè)我們有兩個線程。我用紅色和淺藍(lán)色標(biāo)注了一下。

我們再回頭看一下我們的 transfer代碼中的這個細(xì)節(jié)：

do {
    Entry
    
      
     next = e.
     next;
     // <--假設(shè)線程一執(zhí)行到這里就被調(diào)度掛起了
     
    int i = indexFor(e.hash, newCapacity);
     
    e.
     next = newTable[i];
     
    newTable[i] = e;
     
    e = 
     next;
     
} 
     while (e != null);
     

    

而我們的線程二執(zhí)行完成了。于是我們有下面的這個樣子。

注意，因為Thread1的 e 指向了key(3)，而next指向了key(7)，其在線程二rehash后，指向了線程二重組后的鏈表。我們可以看到鏈表的順序被反轉(zhuǎn)后。

2）線程一被調(diào)度回來執(zhí)行。

• 先是執(zhí)行 newTalbe[i] = e;

• 然后是e = next，導(dǎo)致了e指向了key(7)

• 而下一次循環(huán)的next = e.next導(dǎo)致了next指向了key(3)

3）一切安好。

線程一接著工作。把key(7)摘下來，放到newTable[i]的第一個，然后把e和next往下移。

4）環(huán)形鏈接出現(xiàn)。

e.next = newTable[i] 導(dǎo)致 key(3).next 指向了 key(7)

注意：此時的key(7).next 已經(jīng)指向了key(3)， 環(huán)形鏈表就這樣出現(xiàn)了。

于是，當(dāng)我們的線程一調(diào)用到，HashTable.get(11)時，悲劇就出現(xiàn)了——Infinite Loop。

針對上面的分析模擬這個例子，

這里在run中執(zhí)行了一個自增操作，i++非原子操作，使用AtomicInteger避免可能出現(xiàn)的問題：

public class MapThread extends Thread{
        /**
         * 類的靜態(tài)變量是各個實例共享的，因此并發(fā)的執(zhí)行此線程一直在操作這兩個變量
         * 選擇AtomicInteger避免可能的int++并發(fā)問題
         */
         private static AtomicInteger ai = new AtomicInteger(0);
         //初始化一個table長度為1的哈希表
         private static HashMap
    
      map = 
     new HashMap
     
      (
      1);
      
         
      //如果使用ConcurrentHashMap，不會出現(xiàn)類似的問題
      

      //       private static ConcurrentHashMap
       
         map = new ConcurrentHashMap
        
         (1);
        
       
      

      
         
      public void run()
          {
      
              
      while (ai.
      get() < 
      100000)
      
              {  
      //不斷自增
      
                  map.put(ai.
      get(), ai.
      get());
      
                  ai.incrementAndGet();
      
               }
      

      
              System.
      out.println(Thread.currentThread().getName()+
      "線程即將結(jié)束");
      
          }
      
    }
      

     
    

測試一下：

public static void main(String[] args){
         MapThread t0 = new MapThread();
         MapThread t1 = new MapThread();
         MapThread t2 = new MapThread();
         MapThread t3 = new MapThread();
         MapThread t4 = new MapThread();
         MapThread t5 = new MapThread();
         MapThread t6 = new MapThread();
         MapThread t7 = new MapThread();
         MapThread t8 = new MapThread();
         MapThread t9 = new MapThread();

         t0.start();
         t1.start();
         t2.start();
         t3.start();
         t4.start();
         t5.start();
         t6.start();
         t7.start();
         t8.start();
         t9.start();

    }

注意并發(fā)問題并不是一定會產(chǎn)生，可以多執(zhí)行幾次，我試驗了上面的代碼很容易產(chǎn)生無限循環(huán)，控制臺不能終止，有線程始終在執(zhí)行中，這是其中一個死循環(huán)的控制臺截圖

可以看到六個線程順利完成了put工作后銷毀，還有四個線程沒有輸出，卡在了put階段，感興趣的可以斷點進去看一下：

上面的代碼，如果把注釋打開，換用ConcurrentHashMap就不會出現(xiàn)類似的問題。

4.多線程put的時候可能導(dǎo)致元素丟失

HashMap另外一個并發(fā)可能出現(xiàn)的問題是，可能產(chǎn)生元素丟失的現(xiàn)象。

考慮在多線程下put操作時，執(zhí)行addEntry(hash, key, value, i)，如果有產(chǎn)生哈希碰撞，導(dǎo)致兩個線程得到同樣的bucketIndex去存儲，就可能會出現(xiàn)覆蓋丟失的情況：

void addEntry(int hash, K key, V value, int bucketIndex) {
    //多個線程操作數(shù)組的同一個位置
    Entry
    
      e = table[bucketIndex];
     
        table[bucketIndex] = 
     new Entry
     
      (hash, key, 
      value, e);
      
        
      if (size++ >= threshold)
      
            resize(
      2 * table.length);
      
    }
      

     
    

5.使用線程安全的哈希表容器

那么如何使用線程安全的哈希表結(jié)構(gòu)呢，這里列出了幾條建議：

• 使用Hashtable 類，Hashtable 是線程安全的；

• 使用并發(fā)包下的java.util.concurrent.ConcurrentHashMap，ConcurrentHashMap實現(xiàn)了更高級的線程安全；

• 或者使用synchronizedMap() 同步方法包裝 HashMap object，得到線程安全的Map，并在此Map上進行操作。

參考

http://coolshell.cn/articles/9606.html

作者：邴越

https://www.cnblogs.com/binyue/p/3726403.html

特別推薦一個分享架構(gòu)+算法的優(yōu)質(zhì)內(nèi)容，還沒關(guān)注的小伙伴，可以長按關(guān)注一下：
長按訂閱更多精彩▼
如有收獲，點個在看，誠摯感謝