ConcurrentHashMap 和 CopyOnWriteArrayList 提供線程安全性和已改進(jìn)的可伸縮性

1、eJava 理論與實(shí)踐: 并發(fā)集合類ConcurrentHashMap 和 CopyOnWriteArrayList 提供線程安全性和已改進(jìn)的可伸縮性級別: 初級Brian Goetz (brian), 首席顧問, Quiotix Corp2003 年 9 月 28 日DougLea的 util.concurrent 包除了包含許多其他有用的并發(fā)構(gòu)造塊之外，還包含了一些主要集合類型 List 和 Map 的高性能的、線程安全的實(shí)現(xiàn)。在本月的 Java理論與實(shí)踐中，BrianGoetz向您展示了用 ConcurrentHashMap 替換 Hashtable 或 synchronizedMap

2、，將有多少并發(fā)程序獲益。您可以在本文的 論壇中與作者以及其他讀者共享您的想法（您也可以點(diǎn)擊文章頂部或者底部的 討論進(jìn)入論壇）。 在Java類庫中出現(xiàn)的第一個(gè)關(guān)聯(lián)的集合類是 Hashtable ，它是JDK 1.0的一部分。 Hashtable 提供了一種易于使用的、線程安全的、關(guān)聯(lián)的map功能，這當(dāng)然也是方便的。然而，線程安全性是憑代價(jià)換來的 Hashtable 的所有方法都是同步的。此時(shí)，無競爭的同步會導(dǎo)致可觀的性能代價(jià)。 Hashtable 的后繼者 HashMap 是作為JDK1.2中的集合框架的一部分出現(xiàn)的，它通過提供一個(gè)不同步的基類和一個(gè)同步的包裝器 Collections.sync

3、hronizedMap ，解決了線程安全性問題。通過將基本的功能從線程安全性中分離開來， Collections.synchronizedMap 允許需要同步的用戶可以擁有同步，而不需要同步的用戶則不必為同步付出代價(jià)。 Hashtable 和 synchronizedMap 所采取的獲得同步的簡單方法（同步 Hashtable 中或者同步的 Map 包裝器對象中的每個(gè)方法）有兩個(gè)主要的不足。首先，這種方法對于可伸縮性是一種障礙，因?yàn)橐淮沃荒苡幸粋€(gè)線程可以訪問hash表。同時(shí)，這樣仍不足以提供真正的線程安全性，許多公用的混合操作仍然需要額外的同步。雖然諸如 get() 和 put() 之類的簡單

4、操作可以在不需要額外同步的情況下安全地完成，但還是有一些公用的操作序列，例如迭代或者put-if-absent（空則放入），需要外部的同步，以避免數(shù)據(jù)爭用。 有條件的線程安全性同步的集合包裝器 synchronizedMap 和 synchronizedList ，有時(shí)也被稱作 有條件地線程安全所有單個(gè)的操作都是線程安全的，但是多個(gè)操作組成的操作序列卻可能導(dǎo)致數(shù)據(jù)爭用，因?yàn)樵诓僮餍蛄兄锌刂屏魅Q于前面操作的結(jié)果。 清單1中第一片段展示了公用的put-if-absent語句塊如果一個(gè)條目不在 Map 中，那么添加這個(gè)條目。不幸的是，在 containsKey() 方法返回到 put() 方法被調(diào)

5、用這段時(shí)間內(nèi)，可能會有另一個(gè)線程也插入一個(gè)帶有相同鍵的值。如果您想確保只有一次插入，您需要用一個(gè)對 Map m 進(jìn)行同步的同步塊將這一對語句包裝起來。 清單1中其他的例子與迭代有關(guān)。在第一個(gè)例子中， List.size() 的結(jié)果在循環(huán)的執(zhí)行期間可能會變得無效，因?yàn)榱硪粋€(gè)線程可以從這個(gè)列表中刪除條目。如果時(shí)機(jī)不得當(dāng)，在剛好進(jìn)入循環(huán)的最后一次迭代之后有一個(gè)條目被另一個(gè)線程刪除了，則 List.get() 將返回 null ，而 doSomething() 則很可能會拋出一個(gè) NullPointerException 異常。那么，采取什么措施才能避免這種情況呢？如果當(dāng)您正在迭代一個(gè) List 時(shí)另

6、一個(gè)線程也可能正在訪問這個(gè) List ，那么在進(jìn)行迭代時(shí)您必須使用一個(gè) synchronized 塊將這個(gè) List 包裝起來，在 List 1 上同步，從而鎖住整個(gè) List 。這樣做雖然解決了數(shù)據(jù)爭用問題，但是在并發(fā)性方面付出了更多的代價(jià)，因?yàn)樵诘陂g鎖住整個(gè) List 會阻塞其他線程，使它們在很長一段時(shí)間內(nèi)不能訪問這個(gè)列表。 集合框架引入了迭代器，用于遍歷一個(gè)列表或者其他集合，從而優(yōu)化了對一個(gè)集合中的元素進(jìn)行迭代的過程。然而，在 java.util 集合類中實(shí)現(xiàn)的迭代器極易崩潰，也就是說，如果在一個(gè)線程正在通過一個(gè) Iterator 遍歷集合時(shí)，另一個(gè)線程也來修改這個(gè)集合，那么接下來的

7、 Iterator.hasNext() 或 Iterator.next() 調(diào)用將拋出 ConcurrentModificationException 異常。就拿剛才這個(gè)例子來講，如果想要防止出現(xiàn) ConcurrentModificationException 異常，那么當(dāng)您正在進(jìn)行迭代時(shí)，您必須使用一個(gè)在 List l 上同步的 synchronized 塊將該 List 包裝起來，從而鎖住整個(gè) List 。（或者，您也可以調(diào)用 List.toArray() ，在不同步的情況下對數(shù)組進(jìn)行迭代，但是如果列表比較大的話這樣做代價(jià)很高）。 清單 1. 同步的map中的公用競爭條件 Map m =

8、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 extern

9、al 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(); 信任的錯(cuò)覺synchronizedList 和 synchronizedMap 提供的有條件的線

10、程安全性也帶來了一個(gè)隱患 開發(fā)者會假設(shè)，因?yàn)檫@些集合都是同步的，所以它們都是線程安全的，這樣一來他們對于正確地同步混合操作這件事就會疏忽。其結(jié)果是盡管表面上這些程序在負(fù)載較輕的時(shí)候能夠正常工作，但是一旦負(fù)載較重，它們就會開始拋出 NullPointerException 或 ConcurrentModificationException 。 可伸縮性問題可伸縮性指的是一個(gè)應(yīng)用程序在工作負(fù)載和可用處理資源增加時(shí)其吞吐量的表現(xiàn)情況。一個(gè)可伸縮的程序能夠通過使用更多的處理器、內(nèi)存或者I/O帶寬來相應(yīng)地處理更大的工作負(fù)載。鎖住某個(gè)共享的資源以獲得獨(dú)占式的訪問這種做法會形成可伸縮性瓶頸它使其他線程不能訪

11、問那個(gè)資源，即使有空閑的處理器可以調(diào)用那些線程也無濟(jì)于事。為了取得可伸縮性，我們必須消除或者減少我們對獨(dú)占式資源鎖的依賴。同步的集合包裝器以及早期的 Hashtable 和 Vector 類帶來的更大的問題是，它們在單個(gè)的鎖上進(jìn)行同步。這意味著一次只有一個(gè)線程可以訪問集合，如果有一個(gè)線程正在讀一個(gè) Map ，那么所有其他想要讀或者寫這個(gè) Map 的線程就必須等待。最常見的 Map 操作， get() 和 put() ，可能比表面上要進(jìn)行更多的處理當(dāng)遍歷一個(gè)hash表的bucket以期找到某一特定的key時(shí)， get() 必須對大量的候選bucket調(diào)用 Object.equals() 。如果k

12、ey類所使用的 hashCode() 函數(shù)不能將value均勻地分布在整個(gè)hash表范圍內(nèi)，或者存在大量的hash沖突，那么某些bucket鏈就會比其他的鏈長很多，而遍歷一個(gè)長的hash鏈以及對該hash鏈上一定百分比的元素調(diào)用 equals() 是一件很慢的事情。在上述條件下，調(diào)用 get() 和 put() 的代價(jià)高的問題不僅僅是指訪問過程的緩慢，而且，當(dāng)有線程正在遍歷那個(gè)hash鏈時(shí)，所有其他線程都被鎖在外面，不能訪問這個(gè) Map 。 （哈希表根據(jù)一個(gè)叫做hash的數(shù)字關(guān)鍵字（key）將對象存儲在bucket中。hash value是從對象中的值計(jì)算得來的一個(gè)數(shù)字。每個(gè)不同的hash v

13、alue都會創(chuàng)建一個(gè)新的bucket。要查找一個(gè)對象，您只需要計(jì)算這個(gè)對象的hash value并搜索相應(yīng)的bucket就行了。通過快速地找到相應(yīng)的bucket，就可以減少您需要搜索的對象數(shù)量了。譯者注）get() 執(zhí)行起來可能會占用大量的時(shí)間，而在某些情況下，前面已經(jīng)作了討論的有條件的線程安全性問題會讓這個(gè)問題變得還要糟糕得多。 清單1 中演示的爭用條件常常使得對單個(gè)集合的鎖在單個(gè)操作執(zhí)行完畢之后還必須繼續(xù)保持一段較長的時(shí)間。如果您要在整個(gè)迭代期間都保持對集合的鎖，那么其他的線程就會在鎖外停留很長的一段時(shí)間，等待解鎖。 實(shí)例：一個(gè)簡單的cacheMap 在服務(wù)器應(yīng)用中最常見的應(yīng)用之一就是實(shí)現(xiàn)

14、一個(gè) cache。 服務(wù)器應(yīng)用可能需要緩存文件內(nèi)容、生成的頁面、數(shù)據(jù)庫查詢的結(jié)果、與經(jīng)過解析的XML文件相關(guān)的DOM樹，以及許多其他類型的數(shù)據(jù)。cache的主要用途是重用前一次處理得出的結(jié)果以減少服務(wù)時(shí)間和增加吞吐量。cache工作負(fù)載的一個(gè)典型的特征就是檢索大大多于更新，因此（理想情況下）cache能夠提供非常好的 get() 性能。不過，使用會妨礙性能的cache還不如完全不用cache。 如果使用 synchronizedMap 來實(shí)現(xiàn)一個(gè)cache，那么您就在您的應(yīng)用程序中引入了一個(gè)潛在的可伸縮性瓶頸。因?yàn)橐淮沃挥幸粋€(gè)線程可以訪問 Map ，這些線程包括那些要從 Map 中取出一個(gè)值的

15、線程以及那些要將一個(gè)新的 (key, value) 對插入到該map中的線程。 減小鎖粒度提高 HashMap 的并發(fā)性同時(shí)還提供線程安全性的一種方法是廢除對整個(gè)表使用一個(gè)鎖的方式，而采用對hash表的每個(gè)bucket都使用一個(gè)鎖的方式（或者，更常見的是，使用一個(gè)鎖池，每個(gè)鎖負(fù)責(zé)保護(hù)幾個(gè)bucket）。這意味著多個(gè)線程可以同時(shí)地訪問一個(gè) Map 的不同部分，而不必爭用單個(gè)的集合范圍的鎖。這種方法能夠直接提高插入、檢索以及移除操作的可伸縮性。不幸的是，這種并發(fā)性是以一定的代價(jià)換來的這使得對整個(gè)集合進(jìn)行操作的一些方法（例如 size() 或 isEmpty() ）的實(shí)現(xiàn)更加困難，因?yàn)檫@些方法要求一

16、次獲得許多的鎖，并且還存在返回不正確的結(jié)果的風(fēng)險(xiǎn)。然而，對于某些情況，例如實(shí)現(xiàn)cache，這樣做是一個(gè)很好的折衷因?yàn)闄z索和插入操作比較頻繁，而 size() 和 isEmpty() 操作則少得多。 回頁首ConcurrentHashMaputil.concurrent 包中的 ConcurrentHashMap 類（也將出現(xiàn)在JDK 1.5中的 java.util.concurrent 包中）是對 Map 的線程安全的實(shí)現(xiàn)，比起 synchronizedMap 來，它提供了好得多的并發(fā)性。多個(gè)讀操作幾乎總可以并發(fā)地執(zhí)行，同時(shí)進(jìn)行的讀和寫操作通常也能并發(fā)地執(zhí)行，而同時(shí)進(jìn)行的寫操作仍然可以不時(shí)地并

17、發(fā)進(jìn)行（相關(guān)的類也提供了類似的多個(gè)讀線程的并發(fā)性，但是，只允許有一個(gè)活動的寫線程） 。ConcurrentHashMap 被設(shè)計(jì)用來優(yōu)化檢索操作；實(shí)際上，成功的 get() 操作完成之后通常根本不會有鎖著的資源。要在不使用鎖的情況下取得線程安全性需要一定的技巧性，并且需要對Java內(nèi)存模型（Java Memory Model）的細(xì)節(jié)有深入的理解。 ConcurrentHashMap 實(shí)現(xiàn)，加上 util.concurrent 包的其他部分，已經(jīng)被研究正確性和線程安全性的并發(fā)專家所正視。在下個(gè)月的文章中，我們將看看 ConcurrentHashMap 的實(shí)現(xiàn)的細(xì)節(jié)。 ConcurrentHash

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

19、shMap 來替代 synchronizedMap 或 Hashtable 。 上述改進(jìn)使得 ConcurrentHashMap 能夠提供比 Hashtable 高得多的可伸縮性，而且，對于很多類型的公用案例（比如共享的cache）來說，還不用損失其效率。 好了多少？表 1對 Hashtable 和 ConcurrentHashMap 的可伸縮性進(jìn)行了粗略的比較。在每次運(yùn)行過程中， n 個(gè)線程并發(fā)地執(zhí)行一個(gè)死循環(huán)，在這個(gè)死循環(huán)中這些線程從一個(gè) Hashtable 或者 ConcurrentHashMap 中檢索隨機(jī)的key value，發(fā)現(xiàn)在執(zhí)行 put() 操作時(shí)有80%的檢索失敗率，在執(zhí)行

20、操作時(shí)有1%的檢索成功率。測試所在的平臺是一個(gè)雙處理器的Xeon系統(tǒng)，操作系統(tǒng)是Linux。數(shù)據(jù)顯示了10,000,000次迭代以毫秒計(jì)的運(yùn)行時(shí)間，這個(gè)數(shù)據(jù)是在將對 ConcurrentHashMap的 操作標(biāo)準(zhǔn)化為一個(gè)線程的情況下進(jìn)行統(tǒng)計(jì)的。您可以看到，當(dāng)線程增加到多個(gè)時(shí)， ConcurrentHashMap 的性能仍然保持上升趨勢，而 Hashtable 的性能則隨著爭用鎖的情況的出現(xiàn)而立即降了下來。 比起通常情況下的服務(wù)器應(yīng)用，這次測試中線程的數(shù)量看上去有點(diǎn)少。然而，因?yàn)槊總€(gè)線程都在不停地對表進(jìn)行操作，所以這與實(shí)際環(huán)境下使用這個(gè)表的更多數(shù)量的線程的爭用情況基本等同。表 1.Hashtab

21、le 與 ConcurrentHashMap在可伸縮性方面的比較線程數(shù) ConcurrentHashMap Hashtable 11.001.0322.5932.4045.5878.23813.21163.481627.58341.213257.27778.41CopyOnWriteArrayList在那些遍歷操作大大地多于插入或移除操作的并發(fā)應(yīng)用程序中，一般用 CopyOnWriteArrayList 類替代 ArrayList 。如果是用于存放一個(gè)偵聽器（listener）列表，例如在AWT或Swing應(yīng)用程序中，或者在常見的JavaBean中，那么這種情況很常見（相關(guān)的 CopyOnWr

22、iteArraySet 使用一個(gè) CopyOnWriteArrayList 來實(shí)現(xiàn) Set 接口）。 如果您正在使用一個(gè)普通的 ArrayList 來存放一個(gè)偵聽器列表，那么只要該列表是可變的，而且可能要被多個(gè)線程訪問，您就必須要么在對其進(jìn)行迭代操作期間，要么在迭代前進(jìn)行的克隆操作期間，鎖定整個(gè)列表，這兩種做法的開銷都很大。當(dāng)對列表執(zhí)行會引起列表發(fā)生變化的操作時(shí)， CopyOnWriteArrayList 并不是為列表創(chuàng)建一個(gè)全新的副本，它的迭代器肯定能夠返回在迭代器被創(chuàng)建時(shí)列表的狀態(tài)，而不會拋出 ConcurrentModificationException 。在對列表進(jìn)行迭代之前不必克隆列

23、表或者在迭代期間鎖定列表，因?yàn)榈魉吹降牧斜淼母北臼遣蛔兊?。換句話說， CopyOnWriteArrayList 含有對一個(gè)不可變數(shù)組的一個(gè)可變的引用，因此，只要保留好那個(gè)引用，您就可以獲得不可變的線程安全性的好處，而且不用鎖定列表。 結(jié)束語同步的集合類 Hashtable 和 Vector ，以及同步的包裝器類 Collections.synchronizedMap 和 Collections.synchronizedList ，為 Map 和 List 提供了基本的有條件的線程安全的實(shí)現(xiàn)。然而，某些因素使得它們并不適用于具有高度并發(fā)性的應(yīng)用程序中它們的集合范圍的單鎖特性對于可伸縮性來說

24、是一個(gè)障礙，而且，很多時(shí)候還必須在一段較長的時(shí)間內(nèi)鎖定一個(gè)集合，以防止出現(xiàn) ConcurrentModificationException s異常。 ConcurrentHashMap 和 CopyOnWriteArrayList 實(shí)現(xiàn)提供了更高的并發(fā)性，同時(shí)還保住了線程安全性，只不過在對其調(diào)用者的承諾上打了點(diǎn)折扣。 ConcurrentHashMap 和 CopyOnWriteArrayList 并不是在您使用 HashMap 或 ArrayList 的任何地方都一定有用，但是它們是設(shè)計(jì)用來優(yōu)化某些特定的公用解決方案的。許多并發(fā)應(yīng)用程序?qū)膶λ鼈兊氖褂弥蝎@得好處。 Java 理論與實(shí)踐: 并

25、發(fā)集合類ConcurrentHashMap 和 CopyOnWriteArrayList 提供線程安全性和已改進(jìn)的可伸縮性級別: 初級Brian Goetz (brian), 首席顧問, Quiotix Corp2003 年 9 月 28 日DougLea的 util.concurrent 包除了包含許多其他有用的并發(fā)構(gòu)造塊之外，還包含了一些主要集合類型 List 和 Map 的高性能的、線程安全的實(shí)現(xiàn)。在本月的 Java理論與實(shí)踐中，BrianGoetz向您展示了用 ConcurrentHashMap 替換 Hashtable 或 synchronizedMap ，將有多少并發(fā)程序獲益。您可

26、以在本文的 論壇中與作者以及其他讀者共享您的想法（您也可以點(diǎn)擊文章頂部或者底部的 討論進(jìn)入論壇）。 在Java類庫中出現(xiàn)的第一個(gè)關(guān)聯(lián)的集合類是 Hashtable ，它是JDK 1.0的一部分。 Hashtable 提供了一種易于使用的、線程安全的、關(guān)聯(lián)的map功能，這當(dāng)然也是方便的。然而，線程安全性是憑代價(jià)換來的 Hashtable 的所有方法都是同步的。此時(shí)，無競爭的同步會導(dǎo)致可觀的性能代價(jià)。 Hashtable 的后繼者 HashMap 是作為JDK1.2中的集合框架的一部分出現(xiàn)的，它通過提供一個(gè)不同步的基類和一個(gè)同步的包裝器 Collections.synchronizedMap ，解

27、決了線程安全性問題。通過將基本的功能從線程安全性中分離開來， Collections.synchronizedMap 允許需要同步的用戶可以擁有同步，而不需要同步的用戶則不必為同步付出代價(jià)。 Hashtable 和 synchronizedMap 所采取的獲得同步的簡單方法（同步 Hashtable 中或者同步的 Map 包裝器對象中的每個(gè)方法）有兩個(gè)主要的不足。首先，這種方法對于可伸縮性是一種障礙，因?yàn)橐淮沃荒苡幸粋€(gè)線程可以訪問hash表。同時(shí)，這樣仍不足以提供真正的線程安全性，許多公用的混合操作仍然需要額外的同步。雖然諸如 get() 和 put() 之類的簡單操作可以在不需要額外同步的情

28、況下安全地完成，但還是有一些公用的操作序列，例如迭代或者put-if-absent（空則放入），需要外部的同步，以避免數(shù)據(jù)爭用。 有條件的線程安全性同步的集合包裝器 synchronizedMap 和 synchronizedList ，有時(shí)也被稱作 有條件地線程安全所有單個(gè)的操作都是線程安全的，但是多個(gè)操作組成的操作序列卻可能導(dǎo)致數(shù)據(jù)爭用，因?yàn)樵诓僮餍蛄兄锌刂屏魅Q于前面操作的結(jié)果。 清單1中第一片段展示了公用的put-if-absent語句塊如果一個(gè)條目不在 Map 中，那么添加這個(gè)條目。不幸的是，在 containsKey() 方法返回到 put() 方法被調(diào)用這段時(shí)間內(nèi)，可能會有另一個(gè)

29、線程也插入一個(gè)帶有相同鍵的值。如果您想確保只有一次插入，您需要用一個(gè)對 Map m 進(jìn)行同步的同步塊將這一對語句包裝起來。 清單1中其他的例子與迭代有關(guān)。在第一個(gè)例子中， List.size() 的結(jié)果在循環(huán)的執(zhí)行期間可能會變得無效，因?yàn)榱硪粋€(gè)線程可以從這個(gè)列表中刪除條目。如果時(shí)機(jī)不得當(dāng)，在剛好進(jìn)入循環(huán)的最后一次迭代之后有一個(gè)條目被另一個(gè)線程刪除了，則 List.get() 將返回 null ，而 doSomething() 則很可能會拋出一個(gè) NullPointerException 異常。那么，采取什么措施才能避免這種情況呢？如果當(dāng)您正在迭代一個(gè) List 時(shí)另一個(gè)線程也可能正在訪問這個(gè)

30、List ，那么在進(jìn)行迭代時(shí)您必須使用一個(gè) synchronized 塊將這個(gè) List 包裝起來，在 List 1 上同步，從而鎖住整個(gè) List 。這樣做雖然解決了數(shù)據(jù)爭用問題，但是在并發(fā)性方面付出了更多的代價(jià)，因?yàn)樵诘陂g鎖住整個(gè) List 會阻塞其他線程，使它們在很長一段時(shí)間內(nèi)不能訪問這個(gè)列表。 集合框架引入了迭代器，用于遍歷一個(gè)列表或者其他集合，從而優(yōu)化了對一個(gè)集合中的元素進(jìn)行迭代的過程。然而，在 java.util 集合類中實(shí)現(xiàn)的迭代器極易崩潰，也就是說，如果在一個(gè)線程正在通過一個(gè) Iterator 遍歷集合時(shí)，另一個(gè)線程也來修改這個(gè)集合，那么接下來的 Iterator.hasN

31、ext() 或 Iterator.next() 調(diào)用將拋出 ConcurrentModificationException 異常。就拿剛才這個(gè)例子來講，如果想要防止出現(xiàn) ConcurrentModificationException 異常，那么當(dāng)您正在進(jìn)行迭代時(shí)，您必須使用一個(gè)在 List l 上同步的 synchronized 塊將該 List 包裝起來，從而鎖住整個(gè) List 。（或者，您也可以調(diào)用 List.toArray() ，在不同步的情況下對數(shù)組進(jìn)行迭代，但是如果列表比較大的話這樣做代價(jià)很高）。 清單 1. 同步的map中的公用競爭條件 Map m = Collections.sy

32、nchronizedMap(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 synchroniza

33、tion 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(); 信任的錯(cuò)覺synchronizedList 和 synchronizedMap 提供的有條件的線程安全性也帶來了一個(gè)隱患 開

34、發(fā)者會假設(shè)，因?yàn)檫@些集合都是同步的，所以它們都是線程安全的，這樣一來他們對于正確地同步混合操作這件事就會疏忽。其結(jié)果是盡管表面上這些程序在負(fù)載較輕的時(shí)候能夠正常工作，但是一旦負(fù)載較重，它們就會開始拋出 NullPointerException 或 ConcurrentModificationException 。 可伸縮性問題可伸縮性指的是一個(gè)應(yīng)用程序在工作負(fù)載和可用處理資源增加時(shí)其吞吐量的表現(xiàn)情況。一個(gè)可伸縮的程序能夠通過使用更多的處理器、內(nèi)存或者I/O帶寬來相應(yīng)地處理更大的工作負(fù)載。鎖住某個(gè)共享的資源以獲得獨(dú)占式的訪問這種做法會形成可伸縮性瓶頸它使其他線程不能訪問那個(gè)資源，即使有空閑的處理

35、器可以調(diào)用那些線程也無濟(jì)于事。為了取得可伸縮性，我們必須消除或者減少我們對獨(dú)占式資源鎖的依賴。同步的集合包裝器以及早期的 Hashtable 和 Vector 類帶來的更大的問題是，它們在單個(gè)的鎖上進(jìn)行同步。這意味著一次只有一個(gè)線程可以訪問集合，如果有一個(gè)線程正在讀一個(gè) Map ，那么所有其他想要讀或者寫這個(gè) Map 的線程就必須等待。最常見的 Map 操作， get() 和 put() ，可能比表面上要進(jìn)行更多的處理當(dāng)遍歷一個(gè)hash表的bucket以期找到某一特定的key時(shí)， get() 必須對大量的候選bucket調(diào)用 Object.equals() 。如果key類所使用的 hashCo

36、de() 函數(shù)不能將value均勻地分布在整個(gè)hash表范圍內(nèi)，或者存在大量的hash沖突，那么某些bucket鏈就會比其他的鏈長很多，而遍歷一個(gè)長的hash鏈以及對該hash鏈上一定百分比的元素調(diào)用 equals() 是一件很慢的事情。在上述條件下，調(diào)用 get() 和 put() 的代價(jià)高的問題不僅僅是指訪問過程的緩慢，而且，當(dāng)有線程正在遍歷那個(gè)hash鏈時(shí)，所有其他線程都被鎖在外面，不能訪問這個(gè) Map 。 （哈希表根據(jù)一個(gè)叫做hash的數(shù)字關(guān)鍵字（key）將對象存儲在bucket中。hash value是從對象中的值計(jì)算得來的一個(gè)數(shù)字。每個(gè)不同的hash value都會創(chuàng)建一個(gè)新的bu

37、cket。要查找一個(gè)對象，您只需要計(jì)算這個(gè)對象的hash value并搜索相應(yīng)的bucket就行了。通過快速地找到相應(yīng)的bucket，就可以減少您需要搜索的對象數(shù)量了。譯者注）get() 執(zhí)行起來可能會占用大量的時(shí)間，而在某些情況下，前面已經(jīng)作了討論的有條件的線程安全性問題會讓這個(gè)問題變得還要糟糕得多。 清單1 中演示的爭用條件常常使得對單個(gè)集合的鎖在單個(gè)操作執(zhí)行完畢之后還必須繼續(xù)保持一段較長的時(shí)間。如果您要在整個(gè)迭代期間都保持對集合的鎖，那么其他的線程就會在鎖外停留很長的一段時(shí)間，等待解鎖。 實(shí)例：一個(gè)簡單的cacheMap 在服務(wù)器應(yīng)用中最常見的應(yīng)用之一就是實(shí)現(xiàn)一個(gè) cache。 服務(wù)器應(yīng)

38、用可能需要緩存文件內(nèi)容、生成的頁面、數(shù)據(jù)庫查詢的結(jié)果、與經(jīng)過解析的XML文件相關(guān)的DOM樹，以及許多其他類型的數(shù)據(jù)。cache的主要用途是重用前一次處理得出的結(jié)果以減少服務(wù)時(shí)間和增加吞吐量。cache工作負(fù)載的一個(gè)典型的特征就是檢索大大多于更新，因此（理想情況下）cache能夠提供非常好的 get() 性能。不過，使用會妨礙性能的cache還不如完全不用cache。 如果使用 synchronizedMap 來實(shí)現(xiàn)一個(gè)cache，那么您就在您的應(yīng)用程序中引入了一個(gè)潛在的可伸縮性瓶頸。因?yàn)橐淮沃挥幸粋€(gè)線程可以訪問 Map ，這些線程包括那些要從 Map 中取出一個(gè)值的線程以及那些要將一個(gè)新的 (

39、key, value) 對插入到該map中的線程。 減小鎖粒度提高 HashMap 的并發(fā)性同時(shí)還提供線程安全性的一種方法是廢除對整個(gè)表使用一個(gè)鎖的方式，而采用對hash表的每個(gè)bucket都使用一個(gè)鎖的方式（或者，更常見的是，使用一個(gè)鎖池，每個(gè)鎖負(fù)責(zé)保護(hù)幾個(gè)bucket）。這意味著多個(gè)線程可以同時(shí)地訪問一個(gè) Map 的不同部分，而不必爭用單個(gè)的集合范圍的鎖。這種方法能夠直接提高插入、檢索以及移除操作的可伸縮性。不幸的是，這種并發(fā)性是以一定的代價(jià)換來的這使得對整個(gè)集合進(jìn)行操作的一些方法（例如 size() 或 isEmpty() ）的實(shí)現(xiàn)更加困難，因?yàn)檫@些方法要求一次獲得許多的鎖，并且還存在返

40、回不正確的結(jié)果的風(fēng)險(xiǎn)。然而，對于某些情況，例如實(shí)現(xiàn)cache，這樣做是一個(gè)很好的折衷因?yàn)闄z索和插入操作比較頻繁，而 size() 和 isEmpty() 操作則少得多。 ConcurrentHashMaputil.concurrent 包中的 ConcurrentHashMap 類（也將出現(xiàn)在JDK 1.5中的 java.util.concurrent 包中）是對 Map 的線程安全的實(shí)現(xiàn)，比起 synchronizedMap 來，它提供了好得多的并發(fā)性。多個(gè)讀操作幾乎總可以并發(fā)地執(zhí)行，同時(shí)進(jìn)行的讀和寫操作通常也能并發(fā)地執(zhí)行，而同時(shí)進(jìn)行的寫操作仍然可以不時(shí)地并發(fā)進(jìn)行（相關(guān)的類也提供了類似的多個(gè)

41、讀線程的并發(fā)性，但是，只允許有一個(gè)活動的寫線程） 。ConcurrentHashMap 被設(shè)計(jì)用來優(yōu)化檢索操作；實(shí)際上，成功的 get() 操作完成之后通常根本不會有鎖著的資源。要在不使用鎖的情況下取得線程安全性需要一定的技巧性，并且需要對Java內(nèi)存模型（Java Memory Model）的細(xì)節(jié)有深入的理解。 ConcurrentHashMap 實(shí)現(xiàn)，加上 util.concurrent 包的其他部分，已經(jīng)被研究正確性和線程安全性的并發(fā)專家所正視。在下個(gè)月的文章中，我們將看看 ConcurrentHashMap 的實(shí)現(xiàn)的細(xì)節(jié)。 ConcurrentHashMap 通過稍微地松弛它對調(diào)用者的

42、承諾而獲得了更高的并發(fā)性。檢索操作將可以返回由最近完成的插入操作所插入的值，也可以返回在步調(diào)上是并發(fā)的插入操作所添加的值（但是決不會返回一個(gè)沒有意義的結(jié)果）。由 ConcurrentHashMap.iterator() 返回的 Iterators 將每次最多返回一個(gè)元素，并且決不會拋出 ConcurrentModificationException 異常，但是可能會也可能不會反映在該迭代器被構(gòu)建之后發(fā)生的插入操作或者移除操作。在對集合進(jìn)行迭代時(shí)，不需要表范圍的鎖就能提供線程安全性。在任何不依賴于鎖整個(gè)表來防止更新的應(yīng)用程序中，可以使用 ConcurrentHashMap 來替代 synchro

43、nizedMap 或 Hashtable 。 上述改進(jìn)使得 ConcurrentHashMap 能夠提供比 Hashtable 高得多的可伸縮性，而且，對于很多類型的公用案例（比如共享的cache）來說，還不用損失其效率。 好了多少？表 1對 Hashtable 和 ConcurrentHashMap 的可伸縮性進(jìn)行了粗略的比較。在每次運(yùn)行過程中， n 個(gè)線程并發(fā)地執(zhí)行一個(gè)死循環(huán)，在這個(gè)死循環(huán)中這些線程從一個(gè) Hashtable 或者 ConcurrentHashMap 中檢索隨機(jī)的key value，發(fā)現(xiàn)在執(zhí)行 put() 操作時(shí)有80%的檢索失敗率，在執(zhí)行操作時(shí)有1%的檢索成功率。測試所在的平臺是一個(gè)雙處理器的Xeon系統(tǒng)，操作系統(tǒng)是Linux。數(shù)據(jù)顯示