from:http://yemengying.com/2016/05/07/threadsafe-hashmap/

這周真是發生了不少事，腦袋和心里一直都很亂，周二參加了一場面試，經歷了筆試+3輪面試，周五正式提交了離職申請。要開始新的征程了，意外的有些失落和不舍，畢竟是畢業后的第一份工作，畢竟在這認識了一群可愛的人，畢竟在這學到了很多東西,畢竟這有8000+的aeron chair!!!。可既然已經做了選擇就沒有退路了，勇敢往下走吧，希望接下來的三周可以把手頭上的工作做好交接善始善終，也希望以后不會后悔今天的選擇。

fighting！！！fighting！！！

進入正題，在周二面試時，一面的面試官有問到 HashMap 是否是線程安全的，如何在線程安全的前提下使用 HashMap,其實也就是 HashMap，Hashtable，ConcurrentHashMap 和 synchronized Map 的原理和區別。當時有些緊張只是簡單說了下HashMap不是線程安全的；Hashtable 線程安全，但效率低，因為是 Hashtable 是使用 synchronized 的，所有線程競爭同一把鎖；而 ConcurrentHashMap 不僅線程安全而且效率高，因為它包含一個 segment 數組，將數據分段存儲，給每一段數據配一把鎖，也就是所謂的鎖分段技術。當時忘記了 synchronized Map 和解釋一下 HashMap 為什么線程不安全。面試結束后問了下面試官哪里有些不足，面試官說上面這個問題的回答算過關，但可以在深入一些或者自己動手嘗試一下。so~~~雖然拿到了 offer，但還是再整理一下，不能得過且過啊。

為什么HashMap是線程不安全的

總說 HashMap 是線程不安全的，不安全的，不安全的，那么到底為什么它是線程不安全的呢？要回答這個問題就要先來簡單了解一下 HashMap 源碼中的使用的存儲結構(這里引用的是 Java 8 的源碼，與7是不一樣的)和它的擴容機制。

HashMap的內部存儲結構

下面是 HashMap 使用的存儲結構:

1
2
3
4
5
6
7
8
transient Node<K,V>[] table;
static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
}

可以看到 HashMap 內部存儲使用了一個 Node 數組(默認大小是16)，而 Node 類包含一個類型為 Node 的 next 的變量，也就是相當于一個鏈表，所有根據 hash 值計算的 bucket 一樣的 key 會存儲到同一個鏈表里(即產生了沖突)，大概就是下面圖的樣子(順便推薦個在線畫圖的網站Creately)。
HashMap內部存儲結果HashMap內部存儲結果

需要注意的是，在 Java 8 中如果 hash 值相同的 key 數量大于指定值(默認是8)時使用平衡樹來代替鏈表，這會將get()方法的性能從O(n)提高到O(logn)。具體的可以看我的另一篇博客Java 8中HashMap和LinkedHashMap如何解決沖突。

HashMap的自動擴容機制

HashMap 內部的 Node 數組默認的大小是16，假設有100萬個元素，那么最好的情況下每個 hash 桶里都有62500個元素??，這時get(),put(),remove()等方法效率都會降低。為了解決這個問題，HashMap 提供了自動擴容機制，當元素個數達到數組大小 loadFactor 后會擴大數組的大小，在默認情況下，數組大小為16，loadFactor 為0.75，也就是說當 HashMap 中的元素超過16\0.75=12時，會把數組大小擴展為2*16=32，并且重新計算每個元素在新數組中的位置。如下圖所示(圖片來源，權侵刪)。
自動擴容自動擴容
從圖中可以看到沒擴容前，獲取 EntryE 需要遍歷5個元素，擴容之后只需要2次。

為什么線程不安全

個人覺得 HashMap 在并發時可能出現的問題主要是兩方面,首先如果多個線程同時使用put方法添加元素，而且假設正好存在兩個 put 的 key 發生了碰撞(根據 hash 值計算的 bucket 一樣)，那么根據 HashMap 的實現，這兩個 key 會添加到數組的同一個位置，這樣最終就會發生其中一個線程的 put 的數據被覆蓋。第二就是如果多個線程同時檢測到元素個數超過數組大小* loadFactor ，這樣就會發生多個線程同時對 Node 數組進行擴容，都在重新計算元素位置以及復制數據，但是最終只有一個線程擴容后的數組會賦給 table，也就是說其他線程的都會丟失，并且各自線程 put 的數據也丟失。
關于 HashMap 線程不安全這一點，《Java并發編程的藝術》一書中是這樣說的：

HashMap 在并發執行 put 操作時會引起死循環，導致 CPU 利用率接近100%。因為多線程會導致 HashMap 的 Node 鏈表形成環形數據結構，一旦形成環形數據結構，Node 的 next 節點永遠不為空，就會在獲取 Node 時產生死循環。

哇塞，聽上去si不si好神奇，居然會產生死循環。。。。 google 了一下，才知道死循環并不是發生在 put 操作時，而是發生在擴容時。詳細的解釋可以看下面幾篇博客：

如何線程安全的使用HashMap

了解了 HashMap 為什么線程不安全，那現在看看如何線程安全的使用 HashMap。這個無非就是以下三種方式：

  • Hashtable
  • ConcurrentHashMap
  • Synchronized Map

例子：

1
2
3
4
5
6
7
8
//Hashtable
Map<String, String> hashtable = new Hashtable<>();
//synchronizedMap
Map<String, String> synchronizedHashMap = Collections.synchronizedMap(new HashMap<String, String>());
//ConcurrentHashMap
Map<String, String> concurrentHashMap = new ConcurrentHashMap<>();

依次來看看。

Hashtable

先稍微吐槽一下，為啥命名不是 HashTable 啊，看著好難受??，不管了就裝作它叫HashTable 吧。這貨已經不常用了，就簡單說說吧。HashTable 源碼中是使用 synchronized 來保證線程安全的，比如下面的 get 方法和 put 方法：

1
2
3
4
5
6
public synchronized V get(Object key) {
       // 省略實現
    }
public synchronized V put(K key, V value) {
	// 省略實現
    }

所以當一個線程訪問 HashTable 的同步方法時，其他線程如果也要訪問同步方法，會被阻塞住。舉個例子，當一個線程使用 put 方法時，另一個線程不但不可以使用 put 方法，連 get 方法都不可以，好霸道啊！！！so~~，效率很低，現在基本不會選擇它了。

ConcurrentHashMap

ConcurrentHashMap (以下簡稱CHM)是 JUC 包中的一個類，Spring 的源碼中有很多使用 CHM 的地方。之前已經翻譯過一篇關于 ConcurrentHashMap 的博客，如何在java中使用ConcurrentHashMap，里面介紹了 CHM 在 Java 中的實現，CHM 的一些重要特性和什么情況下應該使用 CHM。需要注意的是，上面博客是基于 Java 7 的，和8有區別,在8中 CHM 摒棄了 Segment（鎖段）的概念，而是啟用了一種全新的方式實現,利用 CAS 算法，有時間會重新總結一下。

SynchronizedMap

看了一下源碼，SynchronizedMap 的實現還是很簡單的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// synchronizedMap方法
public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
       return new SynchronizedMap<>(m);
   }
// SynchronizedMap類
private static class SynchronizedMap<K,V>
       implements Map<K,V>, Serializable {
       private static final long serialVersionUID = 1978198479659022715L;
       private final Map<K,V> m;     // Backing Map
       final Object      mutex;        // Object on which to synchronize
       SynchronizedMap(Map<K,V> m) {
           this.m = Objects.requireNonNull(m);
           mutex = this;
       }
       SynchronizedMap(Map<K,V> m, Object mutex) {
           this.m = m;
           this.mutex = mutex;
       }
       public int size() {
           synchronized (mutex) {return m.size();}
       }
       public boolean isEmpty() {
           synchronized (mutex) {return m.isEmpty();}
       }
       public boolean containsKey(Object key) {
           synchronized (mutex) {return m.containsKey(key);}
       }
       public boolean containsValue(Object value) {
           synchronized (mutex) {return m.containsValue(value);}
       }
       public V get(Object key) {
           synchronized (mutex) {return m.get(key);}
       }
       public V put(K key, V value) {
           synchronized (mutex) {return m.put(key, value);}
       }
       public V remove(Object key) {
           synchronized (mutex) {return m.remove(key);}
       }
       // 省略其他方法
   }

從源碼中可以看出調用 synchronizedMap() 方法后會返回一個 SynchronizedMap 類的對象，而在 SynchronizedMap 類中使用了 synchronized 同步關鍵字來保證對 Map 的操作是線程安全的。

性能對比

這是要靠數據說話的時代，所以不能只靠嘴說 CHM 快，它就快了。寫個測試用例，實際的比較一下這三種方式的效率(源碼來源)，下面的代碼分別通過三種方式創建 Map 對象，使用 ExecutorService 來并發運行5個線程，每個線程添加/獲取500K個元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
public class CrunchifyConcurrentHashMapVsSynchronizedMap {
    public final static int THREAD_POOL_SIZE = 5;
    public static Map<String, Integer> crunchifyHashTableObject = null;
    public static Map<String, Integer> crunchifySynchronizedMapObject = null;
    public static Map<String, Integer> crunchifyConcurrentHashMapObject = null;
    public static void main(String[] args) throws InterruptedException {
        // Test with Hashtable Object
        crunchifyHashTableObject = new Hashtable<>();
        crunchifyPerformTest(crunchifyHashTableObject);
        // Test with synchronizedMap Object
        crunchifySynchronizedMapObject = Collections.synchronizedMap(new HashMap<String, Integer>());
        crunchifyPerformTest(crunchifySynchronizedMapObject);
        // Test with ConcurrentHashMap Object
        crunchifyConcurrentHashMapObject = new ConcurrentHashMap<>();
        crunchifyPerformTest(crunchifyConcurrentHashMapObject);
    }
    public static void crunchifyPerformTest(final Map<String, Integer> crunchifyThreads) throws InterruptedException {
        System.out.println("Test started for: " + crunchifyThreads.getClass());
        long averageTime = 0;
        for (int i = 0; i < 5; i++) {
            long startTime = System.nanoTime();
            ExecutorService crunchifyExServer = Executors.newFixedThreadPool(THREAD_POOL_SIZE);
            for (int j = 0; j < THREAD_POOL_SIZE; j++) {
                crunchifyExServer.execute(new Runnable() {
                    @SuppressWarnings("unused")
                    @Override
                    public void run() {
                        for (int i = 0; i < 500000; i++) {
                            Integer crunchifyRandomNumber = (int) Math.ceil(Math.random() * 550000);
                            // Retrieve value. We are not using it anywhere
                            Integer crunchifyValue = crunchifyThreads.get(String.valueOf(crunchifyRandomNumber));
                            // Put value
                            crunchifyThreads.put(String.valueOf(crunchifyRandomNumber), crunchifyRandomNumber);
                        }
                    }
                });
            }
            // Make sure executor stops
            crunchifyExServer.shutdown();
            // Blocks until all tasks have completed execution after a shutdown request
            crunchifyExServer.awaitTermination(Long.MAX_VALUE, TimeUnit.DAYS);
            long entTime = System.nanoTime();
            long totalTime = (entTime - startTime) / 1000000L;
            averageTime += totalTime;
            System.out.println("2500K entried added/retrieved in " + totalTime + " ms");
        }
        System.out.println("For " + crunchifyThreads.getClass() + " the average time is " + averageTime / 5 + " ms\n");
    }
}

測試結果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Test started for: class java.util.Hashtable
2500K entried added/retrieved in 2018 ms
2500K entried added/retrieved in 1746 ms
2500K entried added/retrieved in 1806 ms
2500K entried added/retrieved in 1801 ms
2500K entried added/retrieved in 1804 ms
For class java.util.Hashtable the average time is 1835 ms
Test started for: class java.util.Collections$SynchronizedMap
2500K entried added/retrieved in 3041 ms
2500K entried added/retrieved in 1690 ms
2500K entried added/retrieved in 1740 ms
2500K entried added/retrieved in 1649 ms
2500K entried added/retrieved in 1696 ms
For class java.util.Collections$SynchronizedMap the average time is 1963 ms
Test started for: class java.util.concurrent.ConcurrentHashMap
2500K entried added/retrieved in 738 ms
2500K entried added/retrieved in 696 ms
2500K entried added/retrieved in 548 ms
2500K entried added/retrieved in 1447 ms
2500K entried added/retrieved in 531 ms
For class java.util.concurrent.ConcurrentHashMap the average time is 792 ms

這個就不用廢話了，CHM 性能是明顯優于 Hashtable 和 SynchronizedMap 的,CHM 花費的時間比前兩個的一半還少，哈哈，以后再有人問就可以甩數據了。

歡迎指正錯誤，歡迎一起討論。另外，針對提離職當天發生的一個小插曲，真真是給我上了一課，不是所有人都能接受實話的，只想引用歡樂頌里安迪的一句話:常與同好爭高下,不與傻瓜論短長。