Java的HashMap多執行緒並發問題怎麼解決

並發問題的症狀

多執行緒put後可能導致get死循環

從前我們的Java程式碼因為一些原因使用了HashMap這個東西，但是當時的程式是單執行緒的，一切都沒有問題。後來，我們的程式效能有問題，所以需要變成多執行緒的，於是，變成多執行緒後到了線上，發現程式經常佔了100%的CPU，查看堆疊，你會發現程式都Hang在了HashMap .get()這個方法上了，重啟程式後問題消失。但是過段時間又會來。而且，這個問題在測試環境裡可能很難重現。

我們簡單的看一下我們自己的程式碼，我們就知道HashMap被多個執行緒操作。而Java的文檔說HashMap是非線程安全的，應該用ConcurrentHashMap。但是在這裡我們可以來研究一下原因。簡單程式碼如下：

package com.king.hashmap;
import java.util.HashMap;
public class TestLock {
     private HashMap map = new HashMap();
     public TestLock() {
         Thread t1 = new Thread() {
             public void run() {
                 for ( int i = 0 ; i < 50000 ; i++) {
                     map.put( new Integer(i), i);
                 }
                 System.out.println( "t1 over" );
             }
         };
         Thread t2 = new Thread() {
             public void run() {
                 for ( int i = 0 ; i < 50000 ; i++) {
                     map.put( new Integer(i), i);
                 }
                 System.out.println( "t2 over" );
             }
         };
         Thread t3 = new Thread() {
             public void run() {
                 for ( int i = 0 ; i < 50000 ; i++) {
                     map.put( new Integer(i), i);
                 }
                 System.out.println( "t3 over" );
             }
         };
         Thread t4 = new Thread() {
             public void run() {
                 for ( int i = 0 ; i < 50000 ; i++) {
                     map.put( new Integer(i), i);
                 }
                 System.out.println( "t4 over" );
             }
         };
         Thread t5 = new Thread() {
             public void run() {
                 for ( int i = 0 ; i < 50000 ; i++) {
                     map.put( new Integer(i), i);
                 }
                 System.out.println( "t5 over" );
             }
         };
         Thread t6 = new Thread() {
             public void run() {
                 for ( int i = 0 ; i < 50000 ; i++) {
                     map.get( new Integer(i));
                 }
                 System.out.println( "t6 over" );
             }
         };
         Thread t7 = new Thread() {
             public void run() {
                 for ( int i = 0 ; i < 50000 ; i++) {
                     map.get( new Integer(i));
                 }
                 System.out.println( "t7 over" );
             }
         };
         Thread t8 = new Thread() {
             public void run() {
                 for ( int i = 0 ; i < 50000 ; i++) {
                     map.get( new Integer(i));
                 }
                 System.out.println( "t8 over" );
             }
         };
         Thread t9 = new Thread() {
             public void run() {
                 for ( int i = 0 ; i < 50000 ; i++) {
                     map.get( new Integer(i));
                 }
                 System.out.println( "t9 over" );
             }
         };
         Thread t10 = new Thread() {
             public void run() {
                 for ( int i = 0 ; i < 50000 ; i++) {
                     map.get( new Integer(i));
                 }
                 System.out.println( "t10 over" );
             }
         };
         t1.start();
         t2.start();
         t3.start();
         t4.start();
         t5.start();
         t6.start();
         t7.start();
         t8.start();
         t9.start();
         t10.start();
     }
     public static void main(String[] args) {
         new TestLock();
     }
}

就是啟了10個線程，不斷的往一個非線程安全的HashMap中put內容/get內容，put的內容很簡單，key和value都是從0自增的整數（這個put的內容做的並不好，以致於後來幹擾了我分析問題的思路）。對HashMap做並發寫操作，我原以為只不過會產生髒數據的情況，但反复運行這個程序，會出現線程t1、t2被hang住的情況，多數情況下是一個線程被hang住另一個成功結束，偶爾會10個線程都被hang住。

產生這個死迴圈的根源在於對一個未保護的共享變數 — 一個”HashMap」資料結構的操作。當在所有操作的方法上加了”synchronized”後，一切恢復了正常。這算jvm的bug嗎？應該說不是的，這個現像很早以前就報告出來了。 Sun的工程師並不認為這是bug，而是建議在這樣的場景下應採用”ConcurrentHashMap”，

CPU利用率過高一般是因為出現了出現了死循環，導致部分線程一直運行，佔用cpu時間。問題原因是HashMap是非線程安全的，多個線程put的時候造成了某個key值Entry key List的死循環，問題就這樣產生了。

當另一個執行緒get 這個Entry List 死迴圈的key的時候，這個get也會一直執行。最後結果是越來越多的線程死循環，最後導致伺服器dang掉。我們一般認為HashMap重複插入某個值的時候，會覆寫之前的值，這個沒錯。但是對於多執行緒存取的時候，由於其內部實作機制(在多執行緒環境且未作同步的情況下，對同一個HashMap做put操作可能導致兩個或以上執行緒同時做rehash動作，就可能導致循環鍵表出現，一旦出現執行緒將無法終止，持續佔用CPU，導致CPU使用率居高不下)，就可能出現安全問題了。

使用jstack工具dump出問題的那台伺服器的堆疊資訊。死循環的話，先找RUNNABLE的線程，找到問題程式碼如下：

java.lang.Thread.State:RUNNABLE 
at java.util.HashMap.get(HashMap.java:303 ) 
at com.sohu.twap.service.logic.TransformTweeter.doTransformTweetT5(TransformTweeter.java:183) 
共出現了23次。
java.lang.Thread.State:RUNNABLE 
at java.util.HashMap.put(HashMap.java:374) 
at com.sohu.twap.service.logic.TransformTweeter.transformT5(TransformTweeter. java:816) 
共出現了3次。

注意：不合理使用HashMap導致出現的是死循環而不是死鎖。

多執行緒put的時候可能導致元素遺失

主要問題出在addEntry方法的new Entry (hash, key, value, e)，如果兩個執行緒都同時取得了e,則他們下一個元素都是e，然後賦值給table元素的時候有一個成功有一個遺失。

put非null元素後get出來的卻是null

在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 {
                 Entry next = e.next;
                 int i = indexFor(e.hash, newCapacity);
                 e.next = newTable[i];
                 newTable[i] = e;
                 e = next;
             } while (e != null );
         }
     }
}

在這個方法裡，將舊數組賦值給src，遍歷src，當src的元素非null時，就將src中的該元素置null，即將舊數組中的元素置null了，也就是這一句：

if (e != null ) {
         src[j] = null ;

此時若有get方法訪問這個key，它取得的還是舊數組，當然就取不到其對應的value了。

總結：HashMap未同步時在並發程式中會產生許多微妙的問題，難以從表層找到原因。所以使用HashMap出現了違反直覺的現象，那麼可能就是並發導致的了。

HashMap資料結構

我需要簡單地說一下HashMap這個經典的資料結構。

HashMap通常會用一個指標數組（假設為table[]）來做分散所有的key，當一個key被加入時，會透過Hash演算法透過key算出這個陣列的下標i，然後就把這個插到table[i]中，如果有兩個不同的key被算在了同一個i，那麼就叫衝突，又叫碰撞，這樣會在table[i]上形成一個鍊錶。

我們知道，如果table[]的尺寸很小，例如只有2個，如果要放進10個keys的話，那麼碰撞非常頻繁，於是一個O(1)的查找演算法，就變成了鍊錶遍歷，效能變成了O(n)，這是Hash表的缺陷。

所以，Hash表的尺寸和容量非常的重要。一般来说，Hash表这个容器当有数据要插入时，都会检查容量有没有超过设定的thredhold，如果超过，需要增大Hash表的尺寸，但是这样一来，整个Hash表里的元素都需要被重算一遍。这叫rehash，这个成本相当的大。

HashMap的rehash源代码

下面，我们来看一下Java的HashMap的源代码。Put一个Key,Value对到Hash表中：

public V put(K key, V value)
{
     ......
     //算Hash值
     int hash = hash(key.hashCode());
     int i = indexFor(hash, table.length);
     //如果该key已被插入，则替换掉旧的value （链接操作）
     for (Entry<K,V> 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++;
     //该key不存在，需要增加一个结点
     addEntry(hash, key, value, i);
     return null ;
}

检查容量是否超标：

void addEntry( int hash, K key, V value, int bucketIndex)
{
     Entry<K,V> e = table[bucketIndex];
     table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
     //查看当前的size是否超过了我们设定的阈值threshold，如果超过，需要resize
     if (size++ >= threshold)
         resize( 2 * table.length);
}

新建一个更大尺寸的hash表，然后把数据从老的Hash表中迁移到新的Hash表中。

void resize( int newCapacity)
{
     Entry[] oldTable = table;
     int oldCapacity = oldTable.length;
     ......
     //创建一个新的Hash Table
     Entry[] newTable = new Entry[newCapacity];
     //将Old Hash Table上的数据迁移到New Hash Table上
     transfer(newTable);
     table = newTable;
     threshold = ( int )(newCapacity * loadFactor);
}

迁移的源代码，注意高亮处：

void transfer(Entry[] newTable)
{
     Entry[] src = table;
     int newCapacity = newTable.length;
     //下面这段代码的意思是：
     //  从OldTable里摘一个元素出来，然后放到NewTable中
     for ( int j = 0 ; j < src.length; j++) {
         Entry<K,V> e = src[j];
         if (e != null ) {
             src[j] = null ;
             do {
                 Entry<K,V> next = e.next;
                 int i = indexFor(e.hash, newCapacity);
                 e.next = newTable[i];
                 newTable[i] = e;
                 e = next;
             } while (e != null );
         }
     }
}

好了，这个代码算是比较正常的。而且没有什么问题。

正常的ReHash过程

画了个图做了个演示。

1. 我假设了我们的hash算法就是简单的用key mod 一下表的大小（也就是数组的长度）。

2. 最上面的是old hash 表，其中的Hash表的size=2, 所以key = 3, 7, 5，在mod 2以后都冲突在table1这里了。

3. 接下来的三个步骤是Hash表 resize成4，然后所有的 重新rehash的过程。

并发的Rehash过程

（1）假设我们有两个线程。我用红色和浅蓝色标注了一下。我们再回头看一下我们的 transfer代码中的这个细节：

do {
     Entry<K,V> next = e.next; // <--假设线程一执行到这里就被调度挂起了
     int i = indexFor(e.hash, newCapacity);
     e.next = newTable[i];
     newTable[i] = e;
     e = next;
} while (e != null );

而我们的线程二执行完成了。于是我们有下面的这个样子。

注意：因为Thread1的 e 指向了key(3)，而next指向了key(7)，其在线程二rehash后，指向了线程二重组后的链表。我们可以看到链表的顺序被反转后。

（2）线程一被调度回来执行。

• 先是执行 newTalbe[i] = e。

• 然后是e = next，导致了e指向了key(7)。

• 而下一次循环的next = e.next导致了next指向了key(3)。

（3）一切安好。 线程一接着工作。把key(7)摘下来，放到newTable[i]的第一个，然后把e和next往下移。

（4）环形链接出现。 e.next = newTable[i] 导致 key(3).next 指向了 key(7)。注意：此时的key(7).next 已经指向了key(3)， 环形链表就这样出现了。

于是，当我们的线程一调用到，HashTable.get(11)时，悲剧就出现了——Infinite Loop。

三种解决方案

Hashtable替换HashMap

Hashtable 是同步的，但由迭代器返回的 Iterator 和由所有 Hashtable 的“collection 视图方法”返回的 Collection 的 listIterator 方法都是快速失败的：在创建 Iterator 之后，如果从结构上对 Hashtable 进行修改，除非通过 Iterator 自身的移除或添加方法，否则在任何时间以任何方式对其进行修改，Iterator 都将抛出 ConcurrentModificationException。因此，面对并发的修改，Iterator 很快就会完全失败，而不冒在将来某个不确定的时间发生任意不确定行为的风险。由 Hashtable 的键和值方法返回的 Enumeration 不是快速失败的。

注意，迭代器的快速失败行为无法得到保证，因为一般来说，不可能对是否出现不同步并发修改做出任何硬性保证。快速失败迭代器会尽最大努力抛出 ConcurrentModificationException。因此，为提高这类迭代器的正确性而编写一个依赖于此异常的程序是错误做法：迭代器的快速失败行为应该仅用于检测程序错误。

Collections.synchronizedMap将HashMap包装起来

返回由指定映射支持的同步（线程安全的）映射。为了保证按顺序访问，必须通过返回的映射完成对底层映射的所有访问。在返回的映射或其任意 collection 视图上进行迭代时，强制用户手工在返回的映射上进行同步：

Map m = Collections.synchronizedMap( new HashMap());
...
Set s = m.keySet();  // Needn't be in synchronized block
...
synchronized (m) {  // Synchronizing on m, not s!
Iterator i = s.iterator(); // Must be in synchronized block
     while (i.hasNext())
         foo(i.next());
}

不遵从此建议将导致无法确定的行为。如果指定映射是可序列化的，则返回的映射也将是可序列化的。

ConcurrentHashMap取代HashMap

支援檢索的完全並發和更新的所期望可調整並發的雜湊表。此類別遵守與 Hashtable 相同的功能規範，並且包括對應於 Hashtable 的每個方法的方法版本。不過，儘管所有操作都是線程安全的，但檢索操作不必鎖定，並且不支援以某種防止所有訪問的方式鎖定整個表。此類別可以透過程式完全與 Hashtable 進行互通，這取決於其線程安全，而與其同步細節無關。檢索操作（包括 get）通常不會受阻塞，因此，可能與更新操作交迭（包括 put 和 remove）。檢索會影響最近完成的更新操作的結果。對於一些聚合操作，例如 putAll 和 clear，並發檢索可能只會影響某些條目的插入和移除。類似地，在建立迭代器/枚舉時或自此之後，Iterators 和 Enumerations 會傳回在某一時間點上影響雜湊表狀態的元素。它們不會拋出 ConcurrentModificationException。不過，迭代器被設計成每次僅由一個執行緒使用。

以上是Java的HashMap多執行緒並發問題怎麼解決的詳細內容。更多資訊請關注PHP中文網其他相關文章！