一英支、同步容器
1. 實(shí)現(xiàn)原理
同步容器可以簡(jiǎn)單地理解為通過(guò) synchronized 來(lái)實(shí)現(xiàn)同步的容器前硫，如果有多個(gè)線程調(diào)用同步容器的方法锥咸，它們將會(huì)串行執(zhí)行输硝。
2. 分類
同步容器將它們的狀態(tài)封裝起來(lái)，并對(duì)每一個(gè)公有方法進(jìn)行同步党窜。主要包括：
- Vector
- Stack
- HashTable
- Collections 工具類中部分方法生成，例如：
Collectinons.synchronizedList()Collections.synchronizedSet()Collections.synchronizedMap()Collections.synchronizedSortedSet()Collections.synchronizedSortedMap()
其中 Vector（同步的ArrayList）和 Stack（繼承自Vector借宵，先進(jìn)后出）幌衣、HashTable（繼承自 Dictionary，實(shí)現(xiàn)了 Map 接口）是比較老的容器，Thinking in Java 中明確指出豁护，這些容器現(xiàn)在仍然存在于 JDK 中是為了向以前老版本的程序兼容哼凯，在新的程序中不應(yīng)該在使用。Collections的方法時(shí)將非同步的容器包裹生成對(duì)應(yīng)的同步容器楚里。
同步容器在單線程的環(huán)境下能夠保證線程安全断部，但是通過(guò) synchronized 同步方法將訪問(wèn)操作串行化，導(dǎo)致并發(fā)環(huán)境下效率低下班缎。而且同步容器在多線程環(huán)境下的復(fù)合操作（迭代蝴光、條件運(yùn)算如沒(méi)有則添加等）是非線程安全，需要客戶端代碼來(lái)實(shí)現(xiàn)加鎖达址。
3. 代碼示例
public static Object getLast(Vector list) {
int lastIndex = list.size() - 1;
return list.get(lastIndex);
}
public static void deleteLast(Vector list) {
int lastIndex = list.size() - 1;
list.remove(lastIndex);
}
上面的代碼取最后一個(gè)元素或者刪除最后一個(gè)元素蔑祟，使用了同步容器 Vector。如果有兩個(gè)線程 A 和 B 同時(shí)調(diào)用上面的兩個(gè)方法沉唠，假設(shè) list 的大小為 10疆虚，這里計(jì)算得到的 lastIndex 為 9，線程 B 首先執(zhí)行了刪除操作（多線程之間操作執(zhí)行的不確定性導(dǎo)致）满葛，而后線程 A 調(diào)用了 list.get 方法径簿，這時(shí)就會(huì)發(fā)生數(shù)組越界異常，導(dǎo)致問(wèn)題的原因就是上面的復(fù)合操作不是原子操作嘀韧，這里可以通過(guò)在方法內(nèi)部額外的使用 list 對(duì)象鎖來(lái)實(shí)現(xiàn)原子操作篇亭。
在多線程中使用同步容器，如果使用 Iterator 迭代容器或使用使用 for-each 遍歷容器乳蛾，在迭代過(guò)程中修改容器會(huì)拋出 ConcurrentModificationException 異常暗赶。想要避免出現(xiàn) ConcurrentModificationException，就必須在迭代過(guò)程持有容器的鎖肃叶。但是若容器較大蹂随，則迭代的時(shí)間也會(huì)較長(zhǎng)。那么需要訪問(wèn)該容器的其他線程將會(huì)長(zhǎng)時(shí)間等待因惭。從而會(huì)極大降低性能岳锁。
此外，隱式迭代的情況蹦魔，如 toString激率、hashCode、equals勿决、containsAll等限、removeAll、retainAll 等方法都會(huì)隱式的 Iterator 均牢，也可能拋出 ConcurrentModificationException涩禀。
二曹货、并發(fā)容器
1. 實(shí)現(xiàn)原理
同步容器并不能保證多線程安全，而并發(fā)容器是針對(duì)多個(gè)線程并發(fā)訪問(wèn)而設(shè)計(jì)的讳推。在 JDK 1.5 中引入了concurrent包顶籽，其中提供了很多并發(fā)容器，極大的提升同步容器類的性能银觅。
2. 分類
ConcurrentHashMap
- 對(duì)應(yīng)的非并發(fā)容器：HashMap
- 目標(biāo)：代替Hashtable礼饱、synchronizedMap，支持復(fù)合操作
- 原理：JDK 1.6 中采用一種更加細(xì)粒度的加鎖機(jī)制 Segment 分段鎖究驴，JDK 1.8 中采用 CAS 無(wú)鎖算法镊绪。
CopyOnWriteArrayList
- 對(duì)應(yīng)的非并發(fā)容器：ArrayList
- 目標(biāo)：代替Vector、synchronizedList
- 原理：利用高并發(fā)往往是讀多寫(xiě)少的特性纳胧，讀操作不加鎖镰吆；寫(xiě)操作先復(fù)制一份新的集合，在新的集合上面修改跑慕，然后將新集合賦值給舊的引用万皿，并通過(guò) volatile 保證其可見(jiàn)性，當(dāng)然寫(xiě)操作的鎖是必不可少的了核行。
CopyOnWriteArraySet
- 對(duì)應(yīng)的非并發(fā)容器：HashSet
- 目標(biāo)：代替 synchronizedSet
- 原理：基于 CopyOnWriteArrayList 實(shí)現(xiàn)牢硅，其唯一的不同是在 add 時(shí)調(diào)用的是 CopyOnWriteArrayList 的 addIfAbsent 方法，其遍歷當(dāng)前 Object 數(shù)組芝雪，如 Object 數(shù)組中已有了當(dāng)前元素减余，則直接返回；如果沒(méi)有則放入 Object 數(shù)組的尾部惩系，并返回位岔。
ConcurrentSkipListMap
- 對(duì)應(yīng)的非并發(fā)容器：TreeMap
- 目標(biāo)：代替 synchronizedSortedMap(TreeMap)
- 原理：Skip List（跳表）是一種可以代替平衡樹(shù)的數(shù)據(jù)結(jié)構(gòu)，默認(rèn)是按照 Key 值升序的堡牡。Skip List 讓已排序的數(shù)據(jù)分布在多層鏈表中抒抬，以 0 - 1 隨機(jī)數(shù)決定一個(gè)數(shù)據(jù)的向上攀升與否，通過(guò) 空間來(lái)?yè)Q取時(shí)間 的一個(gè)算法晤柄。ConcurrentSkipListMap 提供了一種線程安全的并發(fā)訪問(wèn)的排序映射表擦剑。內(nèi)部是 Skip List結(jié)構(gòu)實(shí)現(xiàn)，在理論上能夠在
O(log(n))時(shí)間內(nèi)完成查找芥颈、插入惠勒、刪除操作。
ConcurrentSkipListSet
- 對(duì)應(yīng)的非并發(fā)容器：TreeSet
- 目標(biāo)：代替 synchronizedSortedSet
- 原理：內(nèi)部基于 ConcurrentSkipListMap 實(shí)現(xiàn)
ConcurrentLinkedQueue
- 對(duì)應(yīng)的非并發(fā)容器：Queue
- 原理：不會(huì)阻塞的隊(duì)列爬坑，基于鏈表實(shí)現(xiàn)的 FIFO 隊(duì)列（LinkedList 的并發(fā)版本）
LinkedBlockingQueue纠屋、ArrayBlockingQueue、PriorityBlockingQueue
- 對(duì)應(yīng)的并發(fā)容器：Queue
- 特點(diǎn)：拓展了Queue盾计，增加了可阻塞的插入和獲取等操作
- 原理：通過(guò) ReentrantLock 實(shí)現(xiàn)線程安全巾遭，通過(guò) Condition 實(shí)現(xiàn)阻塞和喚醒
- LinkedBlockingQueue：基于鏈表實(shí)現(xiàn)的可阻塞的 FIFO 隊(duì)列
- ArrayBlockingQueue：基于數(shù)組實(shí)現(xiàn)的可阻塞的 FIFO 隊(duì)列
- PriorityBlockingQueue：按優(yōu)先級(jí)排序的隊(duì)列
