Java提供的并發(fā)容器基本都在java.util.concurrent包中偶芍。比較常用的有ConcurrentHashMap、ConcurrentSkipListMap谅辣、CopyOnWriteArrayList凄吏、ConcurrentLinkedQueue铸敏、BlockingQueue等杈帐。
1体箕、線程安全的HashMap
HashMap是非線程安全的专钉，在并發(fā)環(huán)境中會(huì)帶來很多詭異的問題。
在多線程中使用線程安全的HashMap方式：
1）使用Collections.synchronizedMap()方法包裝HashMap
SynchronizedMap類實(shí)現(xiàn)了Map累铅，通過mutex對象實(shí)現(xiàn)對m互斥操作跃须。其他所有相關(guān)的操作都有用到mutex對象進(jìn)行同步，從而實(shí)現(xiàn)線程安全娃兽。這種方式在多線程環(huán)境中的性能并不好菇民，所有對Map的操作都需要獲取mutex對象鎖，導(dǎo)致操作出現(xiàn)等待現(xiàn)象投储。
2）使用ConcurrentHashMap第练，性能更高。
2玛荞、線程安全的List
Java中ArrayList和Vector都是使用數(shù)組作為內(nèi)部實(shí)現(xiàn)的复旬，Vector是線程安全的，ArrayList不是冲泥。LinkedList使用鏈表的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)了List，但它并非線程安全的壁涎，也可以通過Collections.synchronizedList()方式包裝List凡恍。
3、高效讀寫隊(duì)列ConcurrentLinkedQueue
JDK中提供了一個(gè)支持高并發(fā)的隊(duì)列ConcurrentLinkedQueue怔球，它使用鏈表結(jié)構(gòu)實(shí)現(xiàn)嚼酝。item表示目標(biāo)元素，next表示當(dāng)前Node的下一個(gè)元素竟坛。
對Node操作使用了CAS操作闽巩，casItem()方法表示設(shè)置當(dāng)前Node的item值，它有2個(gè)參數(shù)担汤，第一個(gè)表示期望值涎跨，第二個(gè)為設(shè)置目標(biāo)值。若當(dāng)前值等于期望值cmp時(shí)崭歧，就會(huì)將目標(biāo)設(shè)為val隅很。casNext()也類似，它用來設(shè)置next字段率碾。
head表示鏈表的頭部叔营，tail表示鏈表的尾部。head永遠(yuǎn)不會(huì)為null所宰，通過head和succ()方法能完整遍歷整個(gè)鏈表绒尊。
offer()方法中無任何鎖操作，線程安全由CAS和隊(duì)列算法來保證仔粥。方法的核心是for循環(huán)婴谱，此循環(huán)沒有出口，直到嘗試成功為止。
當(dāng)首次加入元素時(shí)勘究，由于隊(duì)列為空矮湘，因此p.next=null，然后將p的next節(jié)點(diǎn)賦值為newNode口糕，即將新的元素加入到隊(duì)列中缅阳。此時(shí)p==t，如果casNext()執(zhí)行成功景描，查詢直接返回true十办。如果失敗則再進(jìn)行一次循環(huán)，直到成功超棺。因此增加一個(gè)元素時(shí)向族，tail并不會(huì)被更新。
當(dāng)?shù)诙卧黾釉貢r(shí)棠绘，由于t還在head的位置上件相，p.next指向?qū)嶋H的第一個(gè)元素，因此q != null氧苍，表示q不是最后一個(gè)節(jié)點(diǎn)夜矗。由于往隊(duì)列中增加元素需要最后一個(gè)節(jié)點(diǎn)的位置，因此需要循環(huán)查找最后一個(gè)節(jié)點(diǎn)让虐。獲得最后一個(gè)節(jié)點(diǎn)后紊撕，p實(shí)際上指向鏈表的第一個(gè)元素，而它的next=null赡突，然后p更新自己的next对扶，讓它指向新加入的節(jié)點(diǎn)。如果成功則p != t惭缰，然后更新t所在位置浪南，將t移動(dòng)到鏈表最后。
如果p== q漱受，是由于遇到了哨兵（sentinel）節(jié)點(diǎn)導(dǎo)致的逞泄，哨兵節(jié)點(diǎn)就是next指向自己的節(jié)點(diǎn)，主要表示要?jiǎng)h除的節(jié)點(diǎn)或空節(jié)點(diǎn)拜效。當(dāng)遇到哨兵節(jié)點(diǎn)時(shí)喷众，無法通過next獲取后續(xù)節(jié)點(diǎn)，可能會(huì)直接返回head紧憾，并期望通過從鏈表頭部開始遍歷到千，再查找到鏈表末尾。
p = (t != (t =tail)) ? t :head;
在執(zhí)行?!=?時(shí)赴穗，線程會(huì)先取得t的值憔四，再執(zhí)行t = tail膀息，并取得新t的值，然后比較著兩個(gè)值是否相等了赵。在單線程下t !=?t?并不會(huì)成立潜支，但在并發(fā)下就有可能存在，如在獲得左邊的t值時(shí)柿汛，右邊的t值已被其他線程修改冗酿。如果在比較過程中，tail被其他線程修改络断，當(dāng)它再次賦值給t時(shí)裁替，會(huì)導(dǎo)致等式左右兩邊的t不同。如果兩個(gè)t不同貌笨，表示tail在中途被其他線程修改弱判。此時(shí)就可以用新的tail作為鏈表末尾，即等式右邊的t锥惋。如果tail沒有被修改昌腰，則返回head，要求從頭部開始重新查找尾部膀跌。
哨兵節(jié)點(diǎn)產(chǎn)生：當(dāng)隊(duì)列中只有一個(gè)節(jié)點(diǎn)時(shí)剥哑。
poll()方法用于彈出隊(duì)列內(nèi)的元素。
在updateHead()方法中淹父，將p作為新的鏈表頭部，原有的head被設(shè)置為哨兵（通過lazySetNext(h)方法實(shí)現(xiàn)）怎虫。由于原有的head和tail實(shí)際上是同一元素暑认，因此再次用offer()添加元素時(shí)，就會(huì)遇到這個(gè)哨兵tail大审。
4蘸际、高效讀取：CopyOnWriteArrayList
在大多數(shù)情況下徒扶，讀操作會(huì)遠(yuǎn)遠(yuǎn)大于寫操作粮彤，讀并不會(huì)修改原數(shù)據(jù)，因此并沒有必要加鎖姜骡，讀是線程安全的导坟。當(dāng)寫操作時(shí)讀必須等待，否則可能讀到不一致的數(shù)據(jù)圈澈，如果正在讀時(shí)也不能進(jìn)行寫入惫周。
CopyOnWriteArrayList類的讀是不加鎖的，寫入也不會(huì)阻塞讀操作康栈，只有在寫寫的時(shí)候才進(jìn)行同步等待递递。其實(shí)現(xiàn)原理是：當(dāng)List需要修改時(shí)并不是修改的原內(nèi)容喷橙，而是對原有的數(shù)據(jù)進(jìn)行一份復(fù)制，將修改的數(shù)據(jù)寫入副本登舞，寫完后再將修改后的副本替換原有的數(shù)據(jù)贰逾。
注意：讀操作代碼沒有任何同步控制和鎖操作，原因是內(nèi)部數(shù)組array不會(huì)發(fā)生修改菠秒，只會(huì)被另外array替換疙剑，可以保證數(shù)據(jù)安全。
寫操作使用了鎖稽煤，Arrays.copyOf(elements, len +1)對內(nèi)部元素進(jìn)行了完整復(fù)制核芽，生成一個(gè)新的數(shù)組newElements，然后將新的元素加入newElements中酵熙，setArray(newElements)使用新的數(shù)組替換原有數(shù)組轧简，修改就完成了。此過程不會(huì)影響讀操作匾二，修改完成后哮独，讀線程可以立刻知道這個(gè)修改（因?yàn)閍rray是volatile的）。
5察藐、數(shù)據(jù)共享通道：BlockingQueue
BlockingQueue是一個(gè)接口皮璧，它適合作為數(shù)據(jù)共享的通道，它有如下實(shí)現(xiàn)類：
ArrayBlockingQueue：
它的內(nèi)部元素都放在一個(gè)對象數(shù)組中：final Object[] items;
向隊(duì)列中壓入元素可以使用offer()和put()方法分飞。offer()：如果當(dāng)前隊(duì)列已滿悴务，會(huì)立即返回false。如果未滿譬猫，則執(zhí)行入隊(duì)操作讯檐。put()：也是將元素壓入到隊(duì)列末尾，如果隊(duì)列已滿染服，它會(huì)一直等待别洪，直到隊(duì)列中有空閑的位置。
從隊(duì)列中彈出元素可以使用poll()和take()方法柳刮，它們都是從隊(duì)列頭部獲取一個(gè)元素挖垛。區(qū)別是如果隊(duì)列為空時(shí)poll()會(huì)直接返回null，take()會(huì)等待秉颗，直到隊(duì)列內(nèi)有可用元素痢毒。
當(dāng)執(zhí)行put()時(shí)，如果隊(duì)列為空蚕甥，則讓當(dāng)前線程在notEmpty上等待闸准，新元素入隊(duì)時(shí)，則進(jìn)行一次notEmpty上的通知梢灭。當(dāng)隊(duì)列中有新元素時(shí)夷家，線程會(huì)得到一個(gè)通知蒸其。當(dāng)新元素進(jìn)入隊(duì)列后，需要通知等待在notEmpty上的線程库快，讓它們繼續(xù)工作摸袁。
對于put()操作也類似，當(dāng)隊(duì)列滿時(shí)需要讓壓入線程等待义屏，當(dāng)有元素從隊(duì)列中移走出現(xiàn)空位時(shí)靠汁，也需要通知等待入隊(duì)的線程。
6闽铐、隨機(jī)數(shù)據(jù)結(jié)構(gòu)：跳表SkipList
跳表是一種可以用來快速查找的數(shù)據(jù)結(jié)構(gòu)蝶怔，類似于平衡樹。區(qū)別是對于平衡樹的插入和輸出可能導(dǎo)致平衡樹進(jìn)行一次全局的調(diào)整兄墅，而跳表只需要對整個(gè)數(shù)據(jù)結(jié)構(gòu)的局部進(jìn)行操作踢星。好處是在高并發(fā)情況下，需要一個(gè)全局鎖來保證整個(gè)平衡樹的線程安全隙咸，對于跳表只需要部分鎖即可沐悦，性能更好。
跳表的查詢時(shí)間復(fù)雜度為O(log n)五督。它采用隨機(jī)算法藏否，本質(zhì)是同時(shí)維護(hù)了多個(gè)鏈表，并且鏈表是分層的充包。最底層的鏈表維護(hù)了跳表內(nèi)的所有元素副签，每上面一層鏈表都是下面一層的子集，一個(gè)元素插入哪些層是完全隨機(jī)的基矮。
跳表內(nèi)的所有元素都是排序的淆储，查找時(shí)，可以從頂級鏈表開始愈捅，一旦發(fā)現(xiàn)被查找的元素大于當(dāng)前鏈表中的取值，就會(huì)轉(zhuǎn)入下一層的鏈表繼續(xù)找慈鸠，在查找過程中搜索是跳躍式的蓝谨。跳表是一種使用空間換時(shí)間的算法。
使用跳表實(shí)現(xiàn)Map和使用哈希算法實(shí)現(xiàn)Map的不同之處是：哈希并不會(huì)保存元素的順序青团，而跳表內(nèi)所有元素都是排序的譬巫，在對跳表進(jìn)行遍歷時(shí)，將會(huì)得到一個(gè)有序的結(jié)果督笆。
ConcurrentSkipListMap是使用跳表數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的芦昔。
跳表的內(nèi)部數(shù)據(jù)結(jié)構(gòu)組成：Node和Index。
Node：一個(gè)Node表示一個(gè)節(jié)點(diǎn)娃肿，里面含有key咕缎、value珠十，每個(gè)Node還會(huì)指向下一個(gè)Node，即元素next凭豪。
casValue()方法用來設(shè)置value的值焙蹭，casNext()方法用來設(shè)置next字段。
Index：表示索引嫂伞，它內(nèi)部包裝了Node孔厉，同時(shí)增加了兩個(gè)向下的引用和向右的引用。整個(gè)跳表就是根據(jù)Index進(jìn)行全網(wǎng)組織的帖努。
對于每一層的表頭撰豺，還需要記錄當(dāng)前處于那一層，因此還需要一個(gè)HeadIndex的數(shù)據(jù)結(jié)構(gòu)拼余，表示鏈表頭部的第一個(gè)Index污桦，它繼承于Index。
總結(jié)：對跳表的所有操作姿搜，就是組織好這些Index之間的連接關(guān)系寡润。
--參考文獻(xiàn)《實(shí)戰(zhàn)Java高并發(fā)程序設(shè)計(jì)》
