歡迎訪問我的博客：http://wangnan.tech
參考：
- http://blog.csdn.net/qq_27093465/article/details/52279473
- http://blog.csdn.net/u010723709/article/details/48007881
- https://yq.aliyun.com/articles/36781
先說說HashMap HashTable
HashMap
- 線程不安全葱轩，并發(fā)情況下不能使用
HashTable:
- 線程安全凝果，但是效率低下
- HashTable容器使用synchronized來保證線程安全释牺，但在線程競爭激烈的情況下HashTable的效率非常低下髓削。因為當一個線程訪問HashTable的同步方法時，其他線程訪問HashTable的同步方法時葡兑，可能會進入阻塞或輪詢狀態(tài)。
- 線程1使用put方法時赞草，線程2不但不能使用put方法讹堤，也不能使用get方法
ConcurrentHashMap(jdk1.8之前)
簡介
- 假如容器里有多把鎖，每一把鎖用于鎖容器其中一部分數(shù)據(jù)厨疙，那么當多線程訪問容器里不同數(shù)據(jù)段的數(shù)據(jù)時洲守，線程間就不會存在鎖競爭，從而可以有效的提高并發(fā)訪問效率沾凄，這就是ConcurrentHashMap所使用的鎖分段技術梗醇，首先將數(shù)據(jù)分成一段一段的存儲，然后給每一段數(shù)據(jù)配一把鎖撒蟀，當一個線程占用鎖訪問其中一個段數(shù)據(jù)的時候叙谨，其他段的數(shù)據(jù)也能被其他線程訪問。
- ConcurrentHashMap是由Segment數(shù)組結構和HashEntry數(shù)組結構組成保屯。Segment是一種可重入鎖ReentrantLock手负，HashEntry則用于存儲鍵值對數(shù)據(jù)。一個ConcurrentHashMap里包含多個Segment數(shù)組姑尺，Segment的結構和HashMap類似竟终，是一種數(shù)組和鏈表結構，一個Segment里包含多個HashEntry數(shù)組切蟋，每個HashEntry是一個鏈表結構的元素统捶，,當對HashEntry數(shù)組的數(shù)據(jù)進行修改時，必須首先獲得它對應的Segment鎖柄粹。
ConcurrentHashMap(jdk1.8)
簡介
- 與JDK6的版本有很大的差異喘鸟。實現(xiàn)線程安全的思想也已經(jīng)完全變了，它摒棄了Segment（鎖段）的概念镰惦，而是啟用了一種全新的方式實現(xiàn),利用CAS算法迷守。它沿用了與它同時期的HashMap版本的思想，底層依然由“數(shù)組”+鏈表+紅黑樹的方式思想旺入，但是為了做到并發(fā)兑凿，又增加了很多輔助的類凯力，例如TreeBin，Traverser等對象內(nèi)部類礼华。
重要屬性
sizeCtl
可以說它是ConcurrentHashMap中出鏡率很高的一個屬性咐鹤，因為它是一個控制標識符，在不同的地方有不同用途圣絮，而且它的取值不同祈惶，也代表不同的含義。
- 負數(shù)代表正在進行初始化或擴容操作
- -1代表正在初始化
- -N 表示有N-1個線程正在進行擴容操作
- 正數(shù)或0代表hash表還沒有被初始化扮匠，這個數(shù)值表示初始化或下一次進行擴容的大小捧请，這一點類似于擴容閾值的概念。還后面可以看到棒搜，它的值始終是當前ConcurrentHashMap容量的0.75倍疹蛉，這與loadfactor是對應的。實際容量>=sizeCtl力麸，則擴容
concurrencyLevel
concurrencyLevel可款，能夠同時更新ConccurentHashMap且不產(chǎn)生鎖競爭的最大線程數(shù)，在Java8之前實際上就是ConcurrentHashMap中的分段鎖個數(shù)克蚂，即Segment[]的數(shù)組長度闺鲸。正確地估計很重要，當?shù)凸腊０龋瑪?shù)據(jù)結構將根據(jù)額外的競爭摸恍，從而導致線程試圖寫入當前鎖定的段時阻塞；相反游盲，如果高估了并發(fā)級別误墓，你遇到過大的膨脹，由于段的不必要的數(shù)量; 這種膨脹可能會導致性能下降益缎，由于高數(shù)緩存未命中谜慌。在Java8里，僅僅是為了兼容舊版本而保留莺奔。唯一的作用就是保證構造map時初始容量不小于concurrencyLevel欣范。
重要內(nèi)部類
Node
Node是最核心的內(nèi)部類，它包裝了key-value鍵值對令哟，所有插入ConcurrentHashMap的數(shù)據(jù)都包裝在這里面恼琼。它與HashMap中的定義很相似，但是有一些差別它對value和next屬性設置了volatile同步鎖屏富，它不允許調(diào)用setValue方法直接改變Node的value域晴竞，它增加了find方法輔助map.get()方法。
TreeNode
- 鏈表>8狠半，才可能轉(zhuǎn)為TreeNode.
- HashMap的TreeNode繼承至LinkedHashMap.Entry噩死；而這里繼承至自己實現(xiàn)的Node颤难，將帶有next指針，便于treebin訪問已维。
- 樹節(jié)點類行嗤，另外一個核心的數(shù)據(jù)結構。當鏈表長度過長的時候垛耳，會轉(zhuǎn)換為TreeNode栅屏。但是與HashMap不相同的是，它并不是直接轉(zhuǎn)換為紅黑樹堂鲜，而是把這些結點包裝成TreeNode放在TreeBin對象中栈雳，由TreeBin完成對紅黑樹的包裝。而且TreeNode在ConcurrentHashMap集成自Node類缔莲，而并非HashMap中的集成自LinkedHashMap.Entry<K,V>類甫恩，也就是說TreeNode帶有next指針，這樣做的目的是方便基于TreeBin的訪問酌予。
TreeBin
- TreeBin用于封裝維護TreeNode，包含putTreeVal奖慌、lookRoot抛虫、UNlookRoot、remove简僧、balanceInsetion建椰、balanceDeletion等方法
- 這個類并不負責包裝用戶的key、value信息岛马，而是包裝的很多TreeNode節(jié)點棉姐。它代替了TreeNode的根節(jié)點，也就是說在實際的ConcurrentHashMap“數(shù)組”中啦逆，存放的是TreeBin對象伞矩，而不是TreeNode對象，這是與HashMap的區(qū)別夏志。另外這個類還帶有了讀寫鎖乃坤。
Unsafe與CAS
在ConcurrentHashMap中，隨處可以看到U, 大量使用了U.compareAndSwapXXX的方法沟蔑，這個方法是利用一個CAS算法實現(xiàn)無鎖化的修改值的操作湿诊，他可以大大降低鎖代理的性能消耗。這個算法的基本思想就是不斷地去比較當前內(nèi)存中的變量值與你指定的一個變量值是否相等瘦材，如果相等厅须，則接受你指定的修改的值，否則拒絕你的操作食棕。因為當前線程中的值已經(jīng)不是最新的值朗和，你的修改很可能會覆蓋掉其他線程修改的結果错沽。這一點與樂觀鎖，SVN的思想是比較類似的例隆。
3個原子操作
- tabAt // 獲取索引i處Node
- casTabAt // 利用CAS算法設置i位置上的Node節(jié)點（將c和table[i]比較甥捺，相同則插入v）。
- setTabAt // 設置節(jié)點位置的值镀层，僅在上鎖區(qū)被調(diào)用
put相關
這個put方法依然沿用HashMap的put方法的思想镰禾，根據(jù)hash值計算這個新插入的點在table中的位置i，如果i位置是空的唱逢，直接放進去吴侦，否則進行判斷，如果i位置是樹節(jié)點坞古，按照樹的方式插入新的節(jié)點备韧，否則把i插入到鏈表的末尾。ConcurrentHashMap中依然沿用這個思想痪枫，有一個最重要的不同點就是ConcurrentHashMap不允許key或value為null值织堂。另外由于涉及到多線程，put方法就要復雜一點奶陈。在多線程中可能有以下兩個情況
- 如果一個或多個線程正在對ConcurrentHashMap進行擴容操作易阳，當前線程也要進入擴容的操作中。這個擴容的操作之所以能被檢測到吃粒，是因為transfer方法中在空結點上插入forward節(jié)點潦俺，如果檢測到需要插入的位置被forward節(jié)點占有，就幫助進行擴容
- 如果檢測到要插入的節(jié)點是非空且不是forward節(jié)點徐勃，就對這個節(jié)點加鎖事示，這樣就保證了線程安全。盡管這個有一些影響效率僻肖，但是還是會比hashTable的synchronized要好得多
流程：
- 判空：null直接拋空指針異常
- hash：計算哈希值
- 遍歷table
- 若table為空肖爵，則初始化，僅設置相關參數(shù)臀脏；
- 計算當前key存放位置遏匆，即table的下標i=(n - 1) & hash；
- 若待存放位置為null谁榜，casTabAt無鎖插入幅聘；
- 若是forwarding nodes（檢測到正在擴容），則helpTransfer（幫助其擴容）窃植；
- else（待插入位置非空且不是forward節(jié)點帝蒿，即碰撞了），將頭節(jié)點上鎖（保證了線程安全）：區(qū)分鏈表節(jié)點和樹節(jié)點巷怜，分別插入（遇到hash值與key值都與新節(jié)點一致的情況葛超，只需要更新value值即可暴氏。否則依次向后遍歷，直到鏈表尾插入這個結點）绣张；
- 若鏈表長度>8答渔，則treeifyBin轉(zhuǎn)樹（Note：若length<64,直接tryPresize,兩倍table.length;不轉(zhuǎn)樹）。
- addCount
resize相關
當ConcurrentHashMap容量不足的時候侥涵，需要對table進行擴容沼撕。這個方法的基本思想跟HashMap是很像的，但是由于它是支持并發(fā)擴容的芜飘，所以要復雜的多务豺。原因是它支持多線程進行擴容操作，而并沒有加鎖嗦明。我想這樣做的目的不僅僅是為了滿足concurrent的要求笼沥，而是希望利用并發(fā)處理去減少擴容帶來的時間影響。因為在擴容的時候娶牌，總是會涉及到從一個“數(shù)組”到另一個“數(shù)組”拷貝的操作奔浅，如果這個操作能夠并發(fā)進行，那真真是極好的了诗良。
整個擴容操作分為兩個部分:
- 第一部分是構建一個nextTable,它的容量是原來的兩倍乘凸，這個操作是單線程完成的。這個單線程的保證是通過RESIZE_STAMP_SHIFT這個常量經(jīng)過一次運算來保證的累榜，這個地方在后面會有提到；
- 第二個部分就是將原來table中的元素復制到nextTable中灵嫌，這里允許多線程進行操作壹罚。
多線程又是如何實現(xiàn)的呢？
遍歷到ForwardingNode節(jié)點((fh = f.hash) == MOVED)寿羞，說明此節(jié)點被處理過了猖凛，直接跳過。這是控制并發(fā)擴容的核心 绪穆。由于給節(jié)點上了鎖辨泳，只允許當前線程完成此節(jié)點的操作，處理完畢后玖院，將對應值設為ForwardingNode（fwd）菠红，其他線程看到forward，直接向后遍歷难菌。如此便完成了多線程的復制工作试溯，也解決了線程安全問題。
Size相關
由于ConcurrentHashMap在統(tǒng)計size時可能正被多個線程操作郊酒，而我們又不可能讓他停下來讓我們計算遇绞，所以只能計量一個估計值键袱。
