Java的Hashtable在遍歷時的迭代器線程問題

這篇文章主要講什麼

• Hashtable及其內部類的部分源碼分析
• Hashtable在遍歷時的java.util.ConcurrentModificationException異常的來由和解決
• 單機在內存中緩存數據並定期清除過期緩存的簡單實現

事情的起因

工作中需要在某個業務類中設置一個將一些對象緩存在內存中的一個緩存機制（單機）。於是有了以下類似結構的實現：

 1 package org.cnblog.test;
 2 
 3 import java.util.Hashtable;
 4 import java.util.Iterator;
 5 
 6 /**
 7  * JAVA的Hashtable在遍歷時的迭代器線程問題
 8  * @author HY
 9  */
10 public class HashtableIteratorTest {
11 
12     //初始化緩存，並啟動刷新緩存的事件。
13     static {
14         Cache.cacheMap = new Hashtable<String, Long>();
15         new Cache().start();
16     }
17     
18     /**
19      * 執行Main方法
20      * @param args
21      */
22     public static void main(String[] args) {
23         
24         Thread t = new Thread(new Runnable() {
25             public void run() {
26                 while (true) {
27                     long time = System.currentTimeMillis();
28                     Cache.cacheMap.put(time + "", time);
29                     System.out.println("[" + Thread.currentThread().getName() + "]Cache中新增緩存>>" + time);
30                     try {
31                         // 每秒鐘增加一個緩存實例。
32                         Thread.sleep(1*1000);
33                     } catch (InterruptedException e) {
34                         e.printStackTrace();
35                     }
36                 }
37             }
38         });
39         t.start();
40     }
41     
42     private static class Cache extends Thread {
43         private static Hashtable<String, Long> cacheMap;
44         
45         /**
46          * 刷新緩存的方法，清除時間超過10秒的緩存。
47          */
48         private void refresh() {
49             synchronized (cacheMap) {
50                 String key;
51                 Iterator<String> i = cacheMap.keySet().iterator();
52                 while (i.hasNext()) {
53                     key = i.next();
54                     if (cacheMap.get(key) != null && System.currentTimeMillis() - cacheMap.get(key) > 10*1000) {
55                         cacheMap.remove(key);
56                         System.out.println("[" + Thread.currentThread().getName() + "]刪除的Key值<<" + key);
57                     }
58                 }
59             }
60         }
61         
62         public void run() {
63             while (true) {
64                 refresh();
65                 try {
66                     // 每過10秒鐘作一次緩存刷新
67                     Thread.sleep(10*1000);
68                 } catch (InterruptedException e) {
69                     e.printStackTrace();
70                 }
71             }
72         }
73     }
74 }

業務類HashtableIteratorTest中，使用靜態內部類Cache來存儲緩存，緩存的直接載體為內部類中的靜態成員cacheMap。

內部類Cache為線程類，線程的執行內容為每10秒鐘進行一次緩存刷新。（刷新結果是清除掉緩存時間超過10秒的內容）

業務類HashtableIteratorTest在初始化時，啟動內部類的線程，並實現一些存入緩存和讀取緩存的方法。

代碼中的main方法模擬每秒鐘增加一個緩存。

於是，代碼遇到了以下問題：

[Thread-1]Cache中新增緩存>>1418207644572
[Thread-1]Cache中新增緩存>>1418207645586
[Thread-1]Cache中新增緩存>>1418207646601
[Thread-1]Cache中新增緩存>>1418207647616
[Thread-1]Cache中新增緩存>>1418207648631
[Thread-1]Cache中新增緩存>>1418207649646
[Thread-1]Cache中新增緩存>>1418207650661
[Thread-1]Cache中新增緩存>>1418207651676
[Thread-1]Cache中新增緩存>>1418207652690
[Thread-1]Cache中新增緩存>>1418207653705
[Thread-0]刪除的Key值<<1418207644572
Exception in thread "Thread-0" java.util.ConcurrentModificationException
at java.util.Hashtable$Enumerator.next(Unknown Source)
at org.cnblog.test.HashtableIteratorTest$Cache.refresh(HashtableIteratorTest.java:53)
at org.cnblog.test.HashtableIteratorTest$Cache.run(HashtableIteratorTest.java:64)

上述代碼第53行，迭代緩存Map的時候拋出了java.util.ConcurrentModificationException異常。

解決過程

首先，ConcurrentModificationException在JDK中的描述為：

當方法檢測到對象的並發修改，但不允許這種修改時，拋出此異常。

很奇怪，我明明在refresh()中對cacheMap遍歷時，已經對cacheMap對象加鎖，可是在next的時候仍然拋出了這個異常。

於是查看JDK源碼，發現：

在cacheMap.keySet()時

public Set<K> keySet() {
  if (keySet == null)
    keySet = Collections.synchronizedSet(new KeySet(), this);
  return keySet;
}

KeySet是Set接口的一個子類，是Hashtable的內部類。返回的是將KeySet經過加鎖後的包裝類SynchronizedSet的對象。

SynchronizedSet類的部分源碼如下：

public <T> T[] toArray(T[] a) {
    synchronized(mutex) {return c.toArray(a);}
}
public Iterator<E> iterator() {
    return c.iterator(); // Must be manually synched by user!
}
public boolean add(E e) {
    synchronized(mutex) {return c.add(e);}
}
public boolean remove(Object o) {
    synchronized(mutex) {return c.remove(o);}
}

代碼中變量c為KeySet對象，mutex為調用keySet()方法的對象，即加鎖的對象為cacheMap。（Collections同步Set的原理）

注意代碼中iterator()方法中的注釋：用戶必須手動同步！

於是筆者仿佛找到了一些頭緒。

在獲取迭代器時，cacheMap.keySet().iterator()：

KeySet的iterator()方法最終返回的是Enumerator的對象，Enumerator是Hashtable的內部類。以下截取重要代碼：

 1     public T next() {
 2         if (modCount != expectedModCount)
 3         throw new ConcurrentModificationException();
 4         return nextElement();
 5     }
 6 
 7     public void remove() {
 8         if (!iterator)
 9         throw new UnsupportedOperationException();
10         if (lastReturned == null)
11         throw new IllegalStateException("Hashtable Enumerator");
12         if (modCount != expectedModCount)
13         throw new ConcurrentModificationException();
14 
15         synchronized(Hashtable.this) {
16         Entry[] tab = Hashtable.this.table;
17         int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;
18 
19         for (Entry<K,V> e = tab[index], prev = null; e != null;
20              prev = e, e = e.next) {
21             if (e == lastReturned) {
22             modCount++;
23             expectedModCount++;
24             if (prev == null)
25                 tab[index] = e.next;
26             else
27                 prev.next = e.next;
28             count--;
29             lastReturned = null;
30             return;
31             }
32         }
33         throw new ConcurrentModificationException();
34         }
35     }

可以看到，問題的發生源頭找到了，當modCount != expectedModCount時，就會拋出異常。

那麼，modCount和expectedModCount是做什麼的？

modCount和expectedModCount是int型

modCount字段在其外部類Hashtable中，注釋的大概意思是：這個數字記錄了，對hashtable內部結構產生變化的操作次數。如rehash()、put(K key, V value)中，都會有modCount++。

expectedModCount字段在Enumerator類中，並在Enumerator（迭代器）初始化時，賦予modCount的值。其注釋的主要內容為：用於檢測並發修改。

其值在迭代器的remove()方法中，與modCount一同自增（見上述代碼中remove()方法中第22、23行）。

於是真相浮於水面：在獲得迭代器時，expectedModCount與modCount值相等，但迭代的同時，第55行的cacheMap.remove(key)使modCount值自增1，導致modCount != expectedModCount，於是拋出ConcurrentModificationException異常。

結果

由上面的結論得出：

在Hashtable迭代的過程中，除迭代器中的操作外，凡對該map對象有產生結構變化的操作時，屬於並發修改。迭代器將不能正常工作。

這就是此類Hashtable在遍歷時，拋出ConcurrentModificationException異常的來由，用加鎖同步兩個操作不是問題所在。

本文問題解決方法很簡單：將55行的使用map調用刪除對象

55         cacheMap.remove(key);

改為在迭代器中刪除對象

55         i.remove();

即可。

也以此推斷出此類異常的解決方式：

要麼不要在迭代的時候進行rehash()、put(K key, V value)、remove(Object key)等會對map結構產生變化的操作；要麼就在迭代器中做可能的操作。