在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() ，在不同步的情況下對數組進行迭代，但是如果列表比 較大的話這樣做代價很高）。
清單 1. 同步的map中的公用競爭條件
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在可伸縮性方面的比較
線程數 ConcurrentHashMap Hashtable 1 1.00 1.03 2 2.59 32.40 4 5.58 78.23 8 13.21 163.48 16 27.58 341.21 32 57.27 778.41
CopyOnWriteArrayList
在那些遍歷操作大大地多於插入或移除操作的並發應用程序中，一般用 CopyOnWriteArrayList 類替代 ArrayList 。如果是用於存放一個偵聽器 （listener）列表，例如在AWT或Swing應用程序中，或者在常見的JavaBean中， 那麼這種情況很常見（相關的 CopyOnWriteArraySet 使用一個 CopyOnWriteArrayList 來實現 Set 接口）。
如果您正在使用一個普通的 ArrayList 來存放一個偵聽器列表，那麼只要該 列表是可變的，而且可能要被多個線程訪問，您就必須要麼在對其進行迭代操作 期間，要麼在迭代前進行的克隆操作期間，鎖定整個列表，這兩種做法的開銷都 很大。當對列表執行會引起列表發生變化的操作時， CopyOnWriteArrayList 並 不是為列表創建一個全新的副本，它的迭代器肯定能夠返回在迭代器被創建時列 表的狀態，而不會拋出 ConcurrentModificationException 。在對列表進行迭 代之前不必克隆列表或者在迭代期間鎖定列表，因為迭代器所看到的列表的副本 是不變的。換句話說， CopyOnWriteArrayList 含有對一個不可變數組的一個可 變的引用，因此，只要保留好那個引用，您就可以獲得不可變的線程安全性的好 處，而且不用鎖定列表。
結束語
同步的集合類 Hashtable 和 Vector ，以及同步的包裝器類 Collections.synchronizedMap 和 Collections.synchronizedList ，為 Map 和 List 提供了基本的有條件的線程安全的實現。然而，某些因素使得它們並不 適用於具有高度並發性的應用程序中――它們的集合范圍的單鎖特性對於可伸縮 性來說是一個障礙，而且，很多時候還必須在一段較長的時間內鎖定一個集合， 以防止出現 ConcurrentModificationException s異常。 ConcurrentHashMap 和 CopyOnWriteArrayList 實現提供了更高的並發性，同時還保住了線程安全性 ，只不過在對其調用者的承諾上打了點折扣。 ConcurrentHashMap 和 CopyOnWriteArrayList 並不是在您使用 HashMap 或 ArrayList 的任何地方都 一定有用，但是它們是設計用來優化某些特定的公用解決方案的。許多並發應用 程序將從對它們的使用中獲得好處。
