☆藍色夢想☆

Doug Lea的util.concurrent包除了包含許多其他有用的并發構造塊之外，還包含了一些主要集合類型List和Map的高性能的、線程安全的實現。Brian Goetz向您展示了用ConcurrentHashMap替換Hashtable或synchronizedMap，將有多少并發程序獲益。

在Java類庫中出現的第一個關聯的集合類是Hashtable，它是JDK 1.0的一部分。Hashtable提供了一種易于使用的、線程安全的、關聯的map功能，這當然也是方便的。然而，線程安全性是憑代價換來的——Hashtable的所有方法都是同步的。 此時，無競爭的同步會導致可觀的性能代價。Hashtable的后繼者HashMap是作為JDK1.2中的集合框架的一部分出現的，它通過提供一個不同步的基類和一個同步的包裝器Collections.synchronizedMap，解決了線程安全性問題。 通過將基本的功能從線程安全性中分離開來，Collections.synchronizedMap允許需要同步的用戶可以擁有同步，而不需要同步的用戶則不必為同步付出代價。

Hashtable 和 synchronizedMap所采取的獲得同步的簡單方法（同步Hashtable中或者同步的Map包裝器對象中的每個方法）有兩個主要的不足。首先，這種方法對于可伸縮性是一種障礙，因為一次只能有一個線程可以訪問hash表。 同時，這樣仍不足以提供真正的線程安全性，許多公用的混合操作仍然需要額外的同步。雖然諸如get() 和 put()之類的簡單操作可以在不需要額外同步的情況下安全地完成，但還是有一些公用的操作序列 ，例如迭代或者put-if-absent（空則放入），需要外部的同步，以避免數據爭用。

有條件的線程安全性
同步的集合包裝器 synchronizedMap 和 synchronizedList，有時也被稱作有條件地線程安全——所有 單個的操作都是線程安全的，但是多個操作組成的操作序列卻可能導致數據爭用，因為在操作序列中控制流取決于前面操作的結果。 清單1中第一片段展示了公用的put-if-absent語句塊——如果一個條目不在Map中，那么添加這個條目。不幸的是， 在containsKey()方法返回到put() 方法被調用這段時間內，可能會有另一個線程也插入一個帶有相同鍵的值。如果您想確保只有一次插入，您需要用一個對Map m進行同步的同步塊將這一對語句包裝起來。

清單1中其他的例子與迭代有關。在第一個例子中，List.size() 的結果在循環的執行期間可能會變得無效，因為另一個線程可以從這個列表中刪除條目。如果時機不得當，在剛好進入循環的最后一次迭代之后有一個條目被另一個線程刪除 了，則List.get()將返回null，而doSomething() 則很可能會拋出一個NullPointerException異常。那么，采取什么措施才能避免這種情況呢？如果當您正在迭代一個List 時另一個線程也 可能正在訪問這個 List，那么在進行迭代時您必須使用一個synchronized 塊將這個List 包裝起來， 在List 1 上同步，從而鎖住整個List。這樣做雖然解決了數據爭用問題，但是在并發性方面付出了更多的代價，因為在迭代期間鎖住整個List會阻塞其他線程，使它們在很長一段時間內不能訪問這個列表。

集合框架引入了迭代器，用于遍歷一個列表或者其他集合，從而優化了對一個集合中的元素進行迭代的過程。然而，在java.util 集合類中實現的迭代器極易崩潰，也就是說，如果在一個線程正在通過一個Iterator遍歷集合時，另一個線程也來修改這個 集合，那么接下來的Iterator.hasNext() 或 Iterator.next()調用將拋出ConcurrentModificationException異常。就拿 剛才這個例子來講，如果想要防止出現ConcurrentModificationException異常，那么當您正在進行迭代時，您必須 使用一個在 List l上同步的synchronized塊將該 List 包裝起來，從而鎖住整個 List。（或者，您也可以調用List.toArray()，在 不同步的情況下對數組進行迭代，但是如果列表比較大的話這樣做代價很高）。

												
    Map m = Collections.synchronizedMap(new HashMap());
    List l = Collections.synchronizedList(new ArrayList());

    // put-if-absent idiom -- contains a race condition
    // may require external synchronization
    if (!map.containsKey(key))
      map.put(key, value);

    // ad-hoc iteration -- contains race conditions
    // may require external synchronization
    for (int i=0; i<list.size(); i++) {
      doSomething(list.get(i));
    }

    // normal iteration -- can throw ConcurrentModificationException
    // may require external synchronization
    for (Iterator i=list.iterator(); i.hasNext(); ) {
      doSomething(i.next());
    }

										

信任的錯覺
synchronizedList 和 synchronizedMap提供的有條件的線程安全性也帶來了一個隱患——開發者會假設，因為這些集合都是同步的，所以它們都是線程安全的，這樣一來他們對于正確地同步混合操作這件事就會疏忽。其結果是盡管表面上這些程序在負載較輕的時候能夠正常工作，但是一旦負載較重，它們就會開始拋出NullPointerException 或 ConcurrentModificationException。

可伸縮性問題
可伸縮性指的是一個應用程序在工作負載和可用處理資源增加時其吞吐量的表現情況。一個可伸縮的程序能夠通過使用更多的處理器、內存或者I/O帶寬來相應地處理更大的工作負載。鎖住某個共享的資源以獲得獨占式的訪問這種做法會形成可伸縮性瓶頸——它使其他線程不能訪問那個資源，即使有空閑的處理器可以調用那些線程也無濟于事。為了取得可伸縮性，我們必須消除或者減少我們對獨占式資源鎖的依賴。

同步的集合包裝器以及早期的Hashtable 和 Vector類帶來的更大的問題是，它們在單個的鎖 上進行同步。這意味著一次只有一個線程可以訪問集合，如果有一個線程正在讀一個Map，那么所有其他想要讀或者寫這個Map的線程就必須等待。最常見的Map操作，get() 和 put()，可能比表面上要進行更多的處理——當遍歷一個hash表的bucket以期找到某一特定的key時，get()必須對大量的候選bucket調用Object.equals()。如果key類所使用的hashCode()函數不能將value均勻地分布在整個hash表范圍內，或者存在大量的hash沖突，那么某些bucket鏈就會比其他的鏈長很多，而遍歷一個長的hash鏈以及對該hash鏈上一定百分比的元素調用 equals()是一件很慢的事情。在上述條件下，調用 get() 和 put() 的代價高的問題不僅僅是指訪問過程的緩慢，而且，當有線程正在遍歷那個hash鏈時，所有其他線程都被鎖在外面，不能訪問這個Map。

（哈希表根據一個叫做hash的數字關鍵字（key）將對象存儲在bucket中。hash value是從對象中的值計算得來的一個數字。每個不同的hash value都會創建一個新的bucket。要查找一個對象，您只需要計算這個對象的hash value并搜索相應的bucket就行了。通過快速地找到相應的bucket，就可以減少您需要搜索的對象數量了。譯者注）

get()執行起來可能會占用大量的時間，而在某些情況下，前面已經作了討論的有條件的線程安全性問題會讓這個問題變得還要糟糕得多。清單1 中演示的爭用條件常常使得對單個集合的鎖在單個操作執行完畢之后還必須繼續保持一段較長的時間。如果您要在整個迭代期間都保持對集合的鎖，那么其他的線程就會在鎖外停留很長的一段時間，等待解鎖。

實例：一個簡單的cache
Map在服務器應用中最常見的應用之一就是實現一個cache。服務器應用可能需要緩存文件內容、生成的頁面、數據庫查詢的結果、與經過解析的XML文件相關的DOM樹，以及許多其他類型的數據。cache的主要用途是重用前一次處理得出的結果 以減少服務時間和增加吞吐量。cache工作負載的一個典型的特征就是檢索大大多于更新，因此（理想情況下）cache能夠提供非常好的get()性能。不過，使用會 妨礙性能的cache還不如完全不用cache。

如果使用 synchronizedMap 來實現一個cache，那么您就在您的應用程序中引入了一個潛在的可伸縮性瓶頸。因為一次只有一個線程可以訪問Map，這 些線程包括那些要從Map中取出一個值的線程以及那些要將一個新的(key, value)對插入到該map中的線程。

減小鎖粒度
提高HashMap的并發性同時還提供線程安全性的一種方法是廢除對整個表使用一個鎖的方式，而采用對hash表的每個bucket都使用一個鎖的方式（或者，更常見的是，使用一個鎖池，每個鎖負責保護幾個bucket） 。這意味著多個線程可以同時地訪問一個Map的不同部分，而不必爭用單個的集合范圍的鎖。這種方法能夠直接提高插入、檢索以及移除操作的可伸縮性。不幸的是，這種并發性是以一定的代價換來的——這使得對整個 集合進行操作的一些方法（例如 size() 或 isEmpty()）的實現更加困難，因為這些方法要求一次獲得許多的鎖，并且還存在返回不正確的結果的風險。然而，對于某些情況，例如實現cache，這樣做是一個很好的折衷——因為檢索和插入操作比較頻繁，而 size() 和 isEmpty()操作則少得多。

ConcurrentHashMap
util.concurrent 包中的ConcurrentHashMap類（也將出現在JDK 1.5中的java.util.concurrent包中）是對Map的線程安全的實現，比起synchronizedMap來，它提供了好得多的并發性。多個讀操作幾乎總可以并發地執行，同時進行的讀和寫操作通常也能并發地執行，而同時進行的寫操作仍然可以不時地并發進行（相關的類也提供了類似的多個讀線程的并發性，但是，只允許有一個活動的寫線程）。ConcurrentHashMap被設計用來優化檢索操作；實際上，成功的 get() 操作完成之后通常根本不會有鎖著的資源。要在不使用鎖的情況下取得線程安全性需要一定的技巧性，并且需要對Java內存模型（Java Memory Model）的細節有深入的理解。ConcurrentHashMap實現，加上util.concurrent包的其他部分，已經被研究正確性和線程安全性的并發專家所正視。在下個月的文章中，我們將看看ConcurrentHashMap的實現的細節。

ConcurrentHashMap 通過稍微地松弛它對調用者的承諾而獲得了更高的并發性。檢索操作將可以返回由最近完成的插入操作所插入的值，也可以返回在步調上是并發的插入操作所添加的值（但是決不會返回一個沒有意義的結果）。由ConcurrentHashMap.iterator()返回的Iterators將每次最多返回一個元素，并且決不會拋出ConcurrentModificationException異常，但是可能會也可能不會反映在該迭代器被構建之后發生的插入操作或者移除操作。在對 集合進行迭代時，不需要表范圍的鎖就能提供線程安全性。在任何不依賴于鎖整個表來防止更新的應用程序中，可以使用ConcurrentHashMap來替代synchronizedMap或Hashtable。

上述改進使得ConcurrentHashMap能夠提供比Hashtable高得多的可伸縮性，而且，對于很多類型的公用案例（比如共享的cache）來說，還不用損失其效率。

好了多少？
表 1對Hashtable 和 ConcurrentHashMap的可伸縮性進行了粗略的比較。在每次運行過程中，n 個線程并發地執行一個死循環，在這個死循環中這些線程從一個Hashtable 或者 ConcurrentHashMap中檢索隨機的key value，發現在執行put()操作時有80%的檢索失敗率，在執行操作時有1%的檢索成功率。測試所在的平臺是一個雙處理器的Xeon系統，操作系統是Linux。數據顯示了10,000,000次迭代以毫秒計的運行時間，這個數據是在將對ConcurrentHashMap的操作標準化為一個線程的情況下進行統計的。您可以看到，當線程增加到多個時，ConcurrentHashMap的性能仍然保持上升趨勢，而Hashtable的性能則隨著爭用鎖的情況的出現而立即降了下來。

比起通常情況下的服務器應用，這次測試中線程的數量看上去有點少。然而，因為每個線程都在不停地對表進行操作，所以這與實際環境下使用這個表的更多數量的線程的爭用情況基本等同。

表 1.Hashtable 與 ConcurrentHashMap在可伸縮性方面的比較

CopyOnWriteArrayList
在那些遍歷操作大大地多于插入或移除操作的并發應用程序中，一般用CopyOnWriteArrayList類替代ArrayList。如果是用于存放一個偵聽器（listener）列表，例如在AWT或Swing應用程序中，或者在常見的JavaBean中，那么這種情況很常見（相關的CopyOnWriteArraySet使用一個CopyOnWriteArrayList來實現Set接口） 。

如果您正在使用一個普通的ArrayList來存放一個偵聽器列表，那么只要該列表是可變的，而且可能要被多個線程訪問，您 就必須要么在對其進行迭代操作期間，要么在迭代前進行的克隆操作期間，鎖定整個列表，這兩種做法的開銷都很大。當對列表執行會引起列表發生變化的操作時，CopyOnWriteArrayList并不是為列表創建一個全新的副本，它的迭代器肯定能夠返回在迭代器被創建時列表的狀態，而不會拋出ConcurrentModificationException。在對列表進行迭代之前不必克隆列表或者在迭代期間鎖 定列表，因為迭代器所看到的列表的副本是不變的。換句話說，CopyOnWriteArrayList含有對一個不可變數組的一個可變的引用，因此，只要保留好那個引用，您就可以獲得不可變的線程安全性的好處，而且不用鎖 定列表。

結束語
同步的集合類Hashtable 和 Vector，以及同步的包裝器類 Collections.synchronizedMap 和 Collections.synchronizedList，為Map 和 List提供了基本的有條件的線程安全的實現。然而，某些因素使得它們并不適用于具有高度并發性的應用程序中——它們的 集合范圍的單鎖特性對于可伸縮性來說是一個障礙，而且，很多時候還必須在一段較長的時間內鎖定一個集合，以防止出現ConcurrentModificationExceptions異常。 ConcurrentHashMap 和 CopyOnWriteArrayList實現提供了更高的并發性，同時還保住了線程安全性，只不過在對其調用者的承諾上打了點折扣。ConcurrentHashMap 和 CopyOnWriteArrayList并不是在您使用HashMap 或 ArrayList的任何地方都一定有用，但是它們是設計用來優化某些特定的公用解決方案的。許多并發應用程序將從對它們的使用中獲得好處。