吖Pat
在平時開發中,我們經常採用HashMap來作為本地緩存的一種實現方式,將一些如系統變量等數據量比較少的參數保存在HashMap中,並將其作為單例類的一個屬性。在系統運行中,使用到這些緩存數據,都可以直接從該單例中獲取該屬性集合。但是,最近發現,HashMap並不是線程安全的,如果你的單例類沒有做代碼同步或對象鎖的控制,就可能出現異常。
首先看下在多線程的訪問下,非現場安全的HashMap的表現如何,在網上看了一些資料,自己也做了一下測試:
1public class MainClass {
2
3 public static final HashMap<string> firstHashMap=new HashMap<string>();/<string>/<string>
4
5 public static void main(String[] args) throws InterruptedException {
6
7 //線程一
8 Thread t1=new Thread(){
9 public void run() {
10 for(int i=0;i<25;i++){
11 firstHashMap.put(String.valueOf(i), String.valueOf(i));
12 }
13 }
14 };
15
16 //線程二
17 Thread t2=new Thread(){
18 public void run() {
19 for(int j=25;j<50;j++){
20 firstHashMap.put(String.valueOf(j), String.valueOf(j));
21 }
22 }
23 };
24
25 t1.start();
26 t2.start();
27
28 //主線程休眠1秒鐘,以便t1和t2兩個線程將firstHashMap填裝完畢。
29 Thread.currentThread().sleep(1000);
30
31 for(int l=0;l<50;l++){
32 //如果key和value不同,說明在兩個線程put的過程中出現異常。
33 if(!String.valueOf(l).equals(firstHashMap.get(String.valueOf(l)))){
34 System.err.println(String.valueOf(l)+":"+firstHashMap.get(String.valueOf(l)));
35 }
36 }
37
38 }
39
40}
上面的代碼在多次執行後,發現表現很不穩定,有時沒有異常文案打出,有時則有個異常出現:
為什麼會出現這種情況,主要看下HashMap的實現:
1public V put(K key, V value) {
2 if (key == null)
3 return putForNullKey(value);
4 int hash = hash(key.hashCode());
5 int i = indexFor(hash, table.length);
6 for (Entry
7 Object k;
8 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
9 V oldValue = e.value;
10 e.value = value;
11 e.recordAccess(this);
12 return oldValue;
13 }
14 }
15
16 modCount++;
17 addEntry(hash, key, value, i);
18 return null;
19 }
我覺得問題主要出現在方法addEntry,繼續看:
1void addEntry(int hash, K key, V value, int bucketIndex) {
2 Entry
3 table[bucketIndex] = new Entry
4 if (size++ >= threshold)
5 resize(2 * table.length);
6 }
從代碼中,可以看到,如果發現哈希表的大小超過閥值threshold,就會調用resize方法,擴大容量為原來的兩倍,而擴大容量的做法是新建一個Entry[]:
1void resize(int newCapacity) {
2 Entry[] oldTable = table;
3 int oldCapacity = oldTable.length;
4 if (oldCapacity == MAXIMUM_CAPACITY) {
5 threshold = Integer.MAX_VALUE;
6 return;
7 }
8
9 Entry[] newTable = new Entry[newCapacity];
10 transfer(newTable);
11 table = newTable;
12 threshold = (int)(newCapacity * loadFactor);
13 }
一般我們聲明HashMap時,使用的都是默認的構造方法:HashMap
當多個線程同時檢測到總數量超過門限值的時候就會同時調用resize操作,各自生成新的數組並rehash後賦給該map底層的數組table,結果最終只有最後一個線程生成的新數組被賦給table變量,其他線程的均會丟失。而且當某些線程已經完成賦值而其他線程剛開始的時候,就會用已經被賦值的table作為原始數組,這樣也會有問題。
JDK1.0引入了第一個關聯的集合類HashTable,它是線程安全的。HashTable的所有方法都是同步的。
JDK2.0引入了HashMap,它提供了一個不同步的基類和一個同步的包裝器synchronizedMap。synchronizedMap被稱為有條件的線程安全類。
JDK5.0util.concurrent包中引入對Map線程安全的實現ConcurrentHashMap,比起synchronizedMap,它提供了更高的靈活性。同時進行的讀和寫操作都可以併發地執行。
所以在開始的測試中,如果我們採用ConcurrentHashMap,它的表現就很穩定,所以以後如果使用Map實現本地緩存,為了提高併發時的穩定性,還是建議使用ConcurrentHashMap。
小紅的甜心
HashMap 擴容的源代碼如下:
resize 擴容方法中最重要的代碼如下:
resize 擴容步驟如下:
- 根據 newCapacity 生成一個數組。
- 遍歷舊的數組,然後對其中的每一個值進行hash,重新進行插入。
- 修改擴容的閥值:threshold 。
下面我們分別展示 在單線程和多線程的環境的擴容
我們定義的Map為 Map<integer>
單線程環境下的擴容
我們先定義有個簡單的hash, hash = key%length
默認hash表的長度為2,插入的元素為 5 9 11
5%2 = 1;
9%2 = 1;
11%2=1;
三個元素都碰撞在下標為1 的位置上。
下面我們擴容到4:
5%4 = 1;
9%4 = 1;
11%4=3;
擴容步驟如下:
併發環境下的擴容
首先線程1 和 線程2 同時擴容
線程1 和 線程2 的 e 為 5 。e.next = 9
但是此時,線程1 由於調度問題暫停執行。
線程2繼續執行,執行結束後如下:
這時,線程1被喚醒了。這時線程1的e為5,e.next = 9;
此時:
處理完5後,我們就要處理9。
此時
因為在線程2中9的下一個節點為5,所以還要繼續處理5,會把5放到線程1的table[1] 處,
這時就會循環生成一個循環列表。11這個元素時無法加入到線程1裡面了。