1 并發(fā)安全的哈希
為什么需要ConcurrentHashMap
HashMap在多線程環(huán)境下非線程安全竟闪，而HashTable通多對(duì)方法使用Synchronized加以修飾從而達(dá)到線程安全炼蛤，但是HashTable實(shí)現(xiàn)同步的方法比較暴力本刽，相當(dāng)于所有讀寫(xiě)線程均去讀取一把鎖，效率比較低下暗挑。另外一種同步Map的方法是使用Collections工具類(lèi)炸裆，例如：
Map<Integer,Integer>map=Collections.synchronizedMap(newHashMap<>());
該種方法與HashTable實(shí)現(xiàn)方式類(lèi)似鲜屏，也是通過(guò)鎖住整表來(lái)實(shí)現(xiàn)同步的。而ConcurrentHashMap則避免了上述兩種Map同步方式鎖住全表的問(wèn)題惯殊。在JDK1.7中也殖，通過(guò)引入分段鎖Segment(實(shí)現(xiàn)了ReentrantLock)忆嗜，保證了一定粒度的并行；在JDK1.8中則拋棄Segment的設(shè)計(jì)理念闪湾，將粒度完全降低到桶數(shù)量绩卤，基于CAS與Synchronized濒憋。
ConcurrentHashMap的基本設(shè)計(jì)思想
ConcurrentHashMap和HashMap實(shí)現(xiàn)上類(lèi)似，最主要的差別是ConcurrentHashMap 采用了分段鎖（Segment），每個(gè)分段鎖維護(hù)著幾個(gè)桶（HashEntry）律适，多個(gè)線程可以同時(shí)訪問(wèn)不同分段鎖上的桶，從而使其并發(fā)度更高（并發(fā)度就是Segment的個(gè)數(shù)）纠修。其中Segment繼承自ReentrantLock。默認(rèn)的并發(fā)級(jí)別為16了牛，也就是說(shuō)默認(rèn)創(chuàng)建16個(gè)Segment鹰祸。JDK1.7使用分段鎖機(jī)制來(lái)實(shí)現(xiàn)并發(fā)更新操作密浑，核心類(lèi)為Segment，它繼承自重入鎖ReentrantLock街图，并發(fā)度與Segment數(shù)量相等懒构。JDK1.8使用了CAS操作來(lái)支持更高的并發(fā)度胆剧，在CAS操作失敗時(shí)使用內(nèi)置鎖synchronized。并且 JDK 1.8 的實(shí)現(xiàn)也在鏈表過(guò)長(zhǎng)時(shí)會(huì)轉(zhuǎn)換為紅黑樹(shù)滚朵。
1.2 JDK7的ConcurrentHashMap
基本結(jié)構(gòu)
Segment
Segment是JDK1.7中ConcurrentHashMap的核心設(shè)計(jì)，通過(guò)引入分段達(dá)成提高并行處理度的效果欢伏。易于看出，Segment繼承了ReentrantLock并實(shí)現(xiàn)了序列化接口漏峰，說(shuō)明Segment的鎖是可重入的届榄。
staticfinalclassSegment<K,V>extendsReentrantLockimplementsSerializable{
transientvolatileintcount;// Segment中元素的數(shù)量，由volatile修飾靖苇，支持內(nèi)存可見(jiàn)性
transientintmodCount;// 對(duì)table的大小造成影響的操作的數(shù)量（比如put或者remove操作）
transientintthreshold;// 擴(kuò)容閾值
transientvolatileHashEntry<K,V>[]table;// 鏈表數(shù)組贤壁，數(shù)組中的每一個(gè)元素代表了一個(gè)鏈表的頭部
finalfloatloadFactor;// 負(fù)載因子
}
HashEntry
Segment中的元素是以HashEntry的形式存放在鏈表數(shù)組中的，其結(jié)構(gòu)與普通HashMap的HashEntry基本一致馒索，不同的是Segment的HashEntry绰上，其value由volatile修飾包帚，以支持內(nèi)存可見(jiàn)性，即寫(xiě)操作對(duì)其他讀線程即時(shí)可見(jiàn)疯趟。
staticfinalclassHashEntry<K,V>{
finalKkey;
finalinthash;
volatileVvalue;
finalHashEntry<K,V>next;
}
值得注意的是信峻，key瓮床，hash值與next域都是由final修飾的隘庄，無(wú)法修改其引用。
初始化過(guò)程
下面以一個(gè)ConcurrentHashMap構(gòu)造函數(shù)為例進(jìn)行分析：
publicConcurrentHashMap(intinitialCapacity,
floatloadFactor,intconcurrencyLevel) {
if(!(loadFactor>0)||initialCapacity<0||concurrencyLevel<=0)
thrownewIllegalArgumentException();
if(concurrencyLevel>MAX_SEGMENTS)
concurrencyLevel=MAX_SEGMENTS;
// 根據(jù)傳入的concurrencyLevel更新sshift與ssize
// 如concurrencyLevel=5 則天花板方向上離2^3=8最近获印，則sshift=3街州，ssize=8
intsshift=0;
intssize=1;
while(ssize<concurrencyLevel) {
++sshift;
ssize<<=1;
?? }
// segmentShift和segmentMask元素定位Segment下標(biāo)
segmentShift=32-sshift;// 計(jì)算Segment下標(biāo)時(shí)首先令hash值的位數(shù)
segmentMask=ssize-1;// 計(jì)算Segment下標(biāo)時(shí)隨后求余數(shù)的操作數(shù)
// 按照ssize的大小對(duì)segment數(shù)組進(jìn)行初始化
this.segments=Segment.newArray(ssize);
if(initialCapacity>MAXIMUM_CAPACITY)
initialCapacity=MAXIMUM_CAPACITY;
intc=initialCapacity/ssize;
// 若initialCapacity / ssize不整除唆缴，則將c=c+1
if(c*ssize<initialCapacity)
++c;
intcap=1;
// cap為每個(gè)segment的初始容量面徽，其值為離c天花板方向最近的2^n
// 例：c為5，cap則為2^3=8氮双；c為12，cap則為2^4=16
while(cap<c)
cap<<=1;
// 創(chuàng)建Segment
for(inti=0;i<this.segments.length;++i)
this.segments[i]=newSegment<K,V>(cap,loadFactor);
}
get方法
根據(jù)key獲取value時(shí)，由于1.7中需要兩次Hash過(guò)程造挽，第一次需要定位到Segment弄痹；第二次需要定位到Segment中的桶下標(biāo)。
publicVget(Objectkey) {
// 首先計(jì)算key的hash值
inthash=hash(key.hashCode());
// segmentFor(hash): 定位到key在哪個(gè)segment
// 調(diào)用segment的get(key, hash)獲取到指定key的value
returnsegmentFor(hash).get(key,hash);
}
finalSegment<K,V>segmentFor(inthash) {
returnsegments[(hash>>>segmentShift)&segmentMask];
}
Vget(Objectkey,inthash) {
if(count!=0) {// read-volatile
// 取得鏈表的頭部谐丢，就是第2次hash過(guò)程
HashEntry<K,V>e=getFirst(hash);
// 鏈表搜索乾忱，直到hash與key均相等時(shí)窄瘟，返回節(jié)點(diǎn)的value
while(e!=null) {
if(e.hash==hash&&key.equals(e.key)) {
Vv=e.value;
if(v!=null)
returnv;
returnreadValueUnderLock(e);// recheck
? ? ? ? ?? }
e=e.next;
? ? ?? }
?? }
returnnull;
}
HashEntry<K,V>getFirst(inthash) {
// 獲取Segment的數(shù)組結(jié)構(gòu)
HashEntry<K,V>[]tab=table;
// 第2次hash過(guò)程趟卸，確定key位于哪一個(gè)HashEntry
returntab[hash&(tab.length-1)];
}
在第二次查找具體元素時(shí)锄列，首先對(duì)count做了非零判斷，由于count是volatile修飾的竣况，put帕翻、remove等操作會(huì)更新count的值萝风，所以當(dāng)競(jìng)爭(zhēng)發(fā)生的時(shí)候，volatile的語(yǔ)義可以保證寫(xiě)操作在讀操作之前睬塌，也就保證了寫(xiě)操作對(duì)后續(xù)的讀操作都是可見(jiàn)的，這樣后面get的后續(xù)操作就可以拿到完整的元素內(nèi)容勋陪。
put方法
put操作也涉及2次hash定位過(guò)程诅愚，但是比get操作多了是否擴(kuò)容劫映、rehash等過(guò)程，2次哈希在此不做過(guò)多贅述雌桑。
Vput(Kkey,inthash,Vvalue,booleanonlyIfAbsent) {
// 先加鎖
lock();
try{
intc=count;
// 對(duì)c進(jìn)行+1操作校坑，獲取新的數(shù)組容量
// 如果新的數(shù)組容量高于閾值千诬，則先進(jìn)行擴(kuò)容操作
if(c++>threshold)// ensure capacity
rehash();
// 獲取Segment的數(shù)組table
HashEntry<K,V>[]tab=table;
// 2次hash過(guò)程確定桶下標(biāo)
intindex=hash&(tab.length-1);
// 獲取index位置的頭結(jié)點(diǎn)
HashEntry<K,V>first=tab[index];
HashEntry<K,V>e=first;
// 沿鏈表遍歷大渤，直到找到與元素key或者h(yuǎn)ash值相同的節(jié)點(diǎn)
while(e!=null&&(e.hash!=hash||!key.equals(e.key)))
e=e.next;
VoldValue;
// 若key或者h(yuǎn)ash值相同的節(jié)點(diǎn)存在，則進(jìn)行更新操作
if(e!=null) {
// value也是volatile修飾的耕捞，所以?xún)?nèi)存即時(shí)可見(jiàn)
oldValue=e.value;
if(!onlyIfAbsent)
e.value=value;
? ? ?? }
// 若key或者h(yuǎn)ash值相同的節(jié)點(diǎn)不存在俺抽，則新建節(jié)點(diǎn)较曼，追加到當(dāng)前鏈表的頭部(頭插法)
else{
oldValue=null;
// 更新modCount的值捷犹，記錄對(duì)table的大小造成影響的操作的數(shù)量
++modCount;
tab[index]=newHashEntry<K,V>(key,hash,first,value);
// 更新count的值，內(nèi)存即時(shí)可見(jiàn)
count=c;// write-volatile
? ? ?? }
// 返回舊值
returnoldValue;
}finally{
// 必須在finally中顯示釋放
unlock();
?? }
}
remove方法
Vremove(Objectkey,inthash,Objectvalue) {
// 加鎖侣颂，除了讀取操作枪孩，其他操作均需要加鎖
lock();
try{
// 計(jì)算新的Segment元素?cái)?shù)量
intc=count-1;
// 獲取Segment的數(shù)組table
HashEntry<K,V>[]tab=table;
// 第2次hash，確定在table的哪個(gè)位置
intindex=hash&(tab.length-1);
HashEntry<K,V>first=tab[index];
HashEntry<K,V>e=first;
// 沿鏈表遍歷拒担，直到找到與元素key或者h(yuǎn)ash值相同的節(jié)點(diǎn)
while(e!=null&&(e.hash!=hash||!key.equals(e.key)))
e=e.next;
VoldValue=null;
if(e!=null) {
Vv=e.value;
if(value==null||value.equals(v)) {
oldValue=v;
// 更新modCount值 ? ? ? ? ? ? ?
++modCount;
HashEntry<K,V>newFirst=e.next;
// 將待刪除元素的前面的元素全部復(fù)制一遍从撼，然后頭插到鏈表上去
for(HashEntry<K,V>p=first;p!=e;p=p.next)
newFirst=newHashEntry<K,V>(p.key,p.hash,
newFirst,p.value);
tab[index]=newFirst;
// 更新新的Segment元素?cái)?shù)量，內(nèi)存即時(shí)可見(jiàn)
count=c;// write-volatile
? ? ? ? ?? }
? ? ?? }
// 返回舊值
returnoldValue;
}finally{
// 釋放鎖
unlock();
?? }
}
由于呆馁，HashEntry中的next是final的，一經(jīng)賦值以后就不可修改阴挣，在定位到待刪除元素的位置以后，程序就將待刪除元素前面的那一些元素全部復(fù)制一遍茎芭，然后再一個(gè)一個(gè)重新接到鏈表上去梅桩。使用final保證其不變性從而易于并發(fā)讀取拜隧，但是當(dāng)修改時(shí)，其成本就顯得有些高了垦页。
1.3 JDK8的ConcurrentHashMap
基本結(jié)構(gòu)
http://ww1.sinaimg.cn/large/005L0VzSly1g7nehxnf22j30hy0fyab5.jpg在JDK1.8的ConcurrentHashMap中干奢，完全摒棄1.7中segment的概念忿峻，保持與1.8HashMap一致的設(shè)計(jì)，通過(guò)引入CAS與Synchronized來(lái)保證最大粒度的并行垄惧。
重要全局變量
staticfinalintMOVED=-1;// 表示正在轉(zhuǎn)移
staticfinalintTREEBIN=-2;// 表示已經(jīng)轉(zhuǎn)換成樹(shù)
staticfinalintRESERVED=-3;// hash for transient reservations
staticfinalintHASH_BITS=0x7fffffff;// usable bits of normal node hash
transientvolatileNode<K,V>[]table;//默認(rèn)沒(méi)初始化的數(shù)組赘艳，用來(lái)保存元素
privatetransientvolatileNode<K,V>[]nextTable;//轉(zhuǎn)移的時(shí)候用的數(shù)組
/**
* 用來(lái)控制表初始化和擴(kuò)容的，默認(rèn)值為0枷踏，當(dāng)在初始化的時(shí)候指定了大小，這會(huì)將這個(gè)大小保存在sizeCtl中旭蠕，大小為數(shù)組的0.75
* 當(dāng)為負(fù)的時(shí)候旷坦，說(shuō)明表正在初始化或擴(kuò)張秒梅，
* ? ? -1 表示初始化 ?
* ? ? -(1+n) n:表示活動(dòng)的擴(kuò)張線程
*/
privatetransientvolatileintsizeCtl;
Node內(nèi)部類(lèi)
staticclassNode<K,V>implementsMap.Entry<K,V>{
finalinthash;//key的hash值
finalKkey;//key
volatileVval;//value
volatileNode<K,V>next;//表示鏈表中的下一個(gè)節(jié)點(diǎn)
Node(inthash,Kkey,Vval,Node<K,V>next) {
this.hash=hash;
this.key=key;
this.val=val;
this.next=next;
?? }
publicfinalKgetKey() ? ? ? {returnkey; }
publicfinalVgetValue() ? ? {returnval; }
publicfinalinthashCode() ? {returnkey.hashCode()^val.hashCode(); }
}
TreeNode內(nèi)部類(lèi)
staticfinalclassTreeNode<K,V>extendsNode<K,V>{
TreeNode<K,V>parent;// red-black tree links
TreeNode<K,V>left;
TreeNode<K,V>right;
TreeNode<K,V>prev;// needed to unlink next upon deletion
booleanred;
TreeNode(inthash,Kkey,Vval,Node<K,V>next,
TreeNode<K,V>parent) {
super(hash,key,val,next);
this.parent=parent;
?? }
}
TreeBin內(nèi)部類(lèi)
staticfinalclassTreeBin<K,V>extendsNode<K,V>{
TreeNode<K,V>root;
volatileTreeNode<K,V>first;
volatileThreadwaiter;
volatileintlockState;
// values for lockState
staticfinalintWRITER=1;// set while holding write lock
staticfinalintWAITER=2;// set when waiting for write lock
staticfinalintREADER=4;// increment value for setting read lock
}
初始化方法
初始化方法均采用延遲初始化的形式捆蜀。
publicConcurrentHashMapDebug(intinitialCapacity) {
if(initialCapacity<0)
thrownewIllegalArgumentException();
intcap=((initialCapacity>=(MAXIMUM_CAPACITY>>>1))?
MAXIMUM_CAPACITY:
tableSizeFor(initialCapacity+(initialCapacity>>>1)+1));
this.sizeCtl=cap;
}
put方法
先判斷key與value是否為空辆它。與HashMap不同，ConcurrentHashMap不允許null作為key或value呢蔫，為什么這樣設(shè)計(jì)? 因?yàn)镃oncurrentHashmap是支持并發(fā)飒筑，這樣會(huì)有一個(gè)問(wèn)題协屡，當(dāng)你通過(guò)get(k)獲取對(duì)應(yīng)的value時(shí)，如果獲取到的是null時(shí)联予，你無(wú)法判斷材原，它是put（k,v）的時(shí)候value為null，還是這個(gè)key從來(lái)沒(méi)有做過(guò)映射卷胯。HashMap是非并發(fā)的窑睁，可以通過(guò)contains(key)來(lái)做這個(gè)判斷。而支持并發(fā)的Map在調(diào)用m.contains（key）和m.get(key)担钮，可能已經(jīng)不同了箫津；
計(jì)算hash值來(lái)確定放在數(shù)組的哪個(gè)位置
判斷當(dāng)前table是否為空，空的話初始化table
根據(jù)重哈希算出的值通過(guò)與運(yùn)算得到桶索引饼拍，利用Unsafe類(lèi)直接獲取內(nèi)存內(nèi)存中對(duì)應(yīng)位置上的節(jié)點(diǎn)师抄，若沒(méi)有碰撞即桶中無(wú)結(jié)點(diǎn)CAS直接添加
如果取出來(lái)的節(jié)點(diǎn)的hash值是MOVED(-1)的話教硫，則表示當(dāng)前正在對(duì)這個(gè)數(shù)組進(jìn)行擴(kuò)容栋豫，復(fù)制到新的數(shù)組谚殊，則當(dāng)前線程也去幫助復(fù)制
最后一種情況就是嫩絮，如果這個(gè)節(jié)點(diǎn)，不為空蜂怎，也不在擴(kuò)容杠步，則通過(guò)synchronized來(lái)加鎖榜轿，進(jìn)行添加操作
其他部分同HashMap中的操作
finalVputVal(Kkey,Vvalue,booleanonlyIfAbsent) {
if(key==null||value==null)thrownewNullPointerException();//K,V都不能為空谬盐，否則的話跑出異常
inthash=spread(key.hashCode());//取得key的hash值
intbinCount=0;//用來(lái)計(jì)算在這個(gè)節(jié)點(diǎn)總共有多少個(gè)元素，用來(lái)控制擴(kuò)容或者轉(zhuǎn)移為樹(shù)
for(Node<K,V>[]tab=table;;) {//
Node<K,V>f;intn,i,fh;
if(tab==null||(n=tab.length)==0)
tab=initTable();//第一次put的時(shí)候table沒(méi)有初始化皇型，則初始化table
elseif((f=tabAt(tab,i=(n-1)&hash))==null) {//通過(guò)哈希計(jì)算出一個(gè)表中的位置因?yàn)閚是數(shù)組的長(zhǎng)度，所以(n-1)&hash肯定不會(huì)出現(xiàn)數(shù)組越界
if(casTabAt(tab,i,null,//如果這個(gè)位置沒(méi)有元素的話绞吁，則通過(guò)cas的方式嘗試添加掀泳，注意這個(gè)時(shí)候是沒(méi)有加鎖的
newNode<K,V>(hash,key,value,null)))//創(chuàng)建一個(gè)Node添加到數(shù)組中區(qū)西轩，null表示的是下一個(gè)節(jié)點(diǎn)為空
break;// no lock when adding to empty bin
? ? ?? }
/*
* 如果檢測(cè)到某個(gè)節(jié)點(diǎn)的hash值是MOVED，則表示正在進(jìn)行數(shù)組擴(kuò)張的數(shù)據(jù)復(fù)制階段马僻，
* 則當(dāng)前線程也會(huì)參與去復(fù)制注服，通過(guò)允許多線程復(fù)制的功能，一次來(lái)減少數(shù)組的復(fù)制所帶來(lái)的性能損失
*/
elseif((fh=f.hash)==MOVED)
tab=helpTransfer(tab,f);
else{
/*
* 如果在這個(gè)位置有元素的話女淑，就采用synchronized的方式加鎖鸭你，
* ? ? 如果是鏈表的話(hash大于0)擒权，就對(duì)這個(gè)鏈表的所有元素進(jìn)行遍歷碳抄，
* ? ? ? ? 如果找到了key和key的hash值都一樣的節(jié)點(diǎn)剖效，則把它的值替換到
* ? ? ? ? 如果沒(méi)找到的話，則添加在鏈表的最后面
*? 否則劝贸，是樹(shù)的話映九，則調(diào)用putTreeVal方法添加到樹(shù)中去
* ?
*? 在添加完之后瞎颗，會(huì)對(duì)該節(jié)點(diǎn)上關(guān)聯(lián)的的數(shù)目進(jìn)行判斷捌议，
*? 如果在8個(gè)以上的話瓣颅，則會(huì)調(diào)用treeifyBin方法宫补，來(lái)嘗試轉(zhuǎn)化為樹(shù)粉怕，或者是擴(kuò)容
*/
VoldVal=null;
synchronized(f) {
if(tabAt(tab,i)==f) {//再次取出要存儲(chǔ)的位置的元素抒巢，跟前面取出來(lái)的比較
if(fh>=0) {//取出來(lái)的元素的hash值大于0蛉谜，當(dāng)轉(zhuǎn)換為樹(shù)之后，hash值為-2
binCount=1;
for(Node<K,V>e=f;;++binCount) {//遍歷這個(gè)鏈表
Kek;
if(e.hash==hash&&//要存的元素的hash客燕，key跟要存儲(chǔ)的位置的節(jié)點(diǎn)的相同的時(shí)候也搓，替換掉該節(jié)點(diǎn)的value即可
((ek=e.key)==key||
(ek!=null&&key.equals(ek)))) {
oldVal=e.val;
if(!onlyIfAbsent)//當(dāng)使用putIfAbsent的時(shí)候暮现，只有在這個(gè)key沒(méi)有設(shè)置值得時(shí)候才設(shè)置
e.val=value;
break;
? ? ? ? ? ? ? ? ? ? ? ? ?? }
Node<K,V>pred=e;
if((e=e.next)==null) {//如果不是同樣的hash栖袋，同樣的key的時(shí)候塘幅，則判斷該節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)是否為空电媳，
pred.next=newNode<K,V>(hash,key,//為空的話把這個(gè)要加入的節(jié)點(diǎn)設(shè)置為當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
value,null);
break;
? ? ? ? ? ? ? ? ? ? ? ? ?? }
? ? ? ? ? ? ? ? ? ? ?? }
? ? ? ? ? ? ? ? ?? }
elseif(finstanceofTreeBin) {//表示已經(jīng)轉(zhuǎn)化成紅黑樹(shù)類(lèi)型了
Node<K,V>p;
binCount=2;
if((p=((TreeBin<K,V>)f).putTreeVal(hash,key,//調(diào)用putTreeVal方法匾乓，將該元素添加到樹(shù)中去
value))!=null) {
oldVal=p.val;
if(!onlyIfAbsent)
p.val=value;
? ? ? ? ? ? ? ? ? ? ?? }
? ? ? ? ? ? ? ? ?? }
? ? ? ? ? ? ?? }
? ? ? ? ?? }
if(binCount!=0) {
if(binCount>=TREEIFY_THRESHOLD)//當(dāng)在同一個(gè)節(jié)點(diǎn)的數(shù)目達(dá)到8個(gè)的時(shí)候又谋，則擴(kuò)張數(shù)組或?qū)⒔o節(jié)點(diǎn)的數(shù)據(jù)轉(zhuǎn)為tree
treeifyBin(tab,i);
if(oldVal!=null)
returnoldVal;
break;
? ? ? ? ?? }
? ? ?? }
?? }
addCount(1L,binCount);//計(jì)數(shù)
returnnull;
}
關(guān)于put中對(duì)CAS和synchronized的使用：
CAS用于當(dāng)桶為空時(shí)，使用cas嘗試加入新的桶頭結(jié)點(diǎn)
synchronized用于桶不為空時(shí)衰齐，向鏈表或樹(shù)中put結(jié)點(diǎn)的情形
get方法
當(dāng)key為null的時(shí)候回拋出NullPointerException的異常
get操作通過(guò)首先計(jì)算key的hash值來(lái)確定該元素放在數(shù)組的哪個(gè)位置
判斷table是否為空且table長(zhǎng)度大于0且下標(biāo)不為空
然后遍歷該位置的所有節(jié)點(diǎn)
如果均無(wú)法定位到key則返回null
publicVget(Objectkey) {
Node<K,V>[]tab;Node<K,V>e,p;intn,eh;Kek;
inth=spread(key.hashCode());
if((tab=table)!=null&&(n=tab.length)>0&&
(e=tabAt(tab, (n-1)&h))!=null) {
if((eh=e.hash)==h) {
if((ek=e.key)==key||(ek!=null&&key.equals(ek)))
returne.val;
? ?? }
elseif(eh<0)
return(p=e.find(h,key))!=null?p.val:null;
while((e=e.next)!=null) {
if(e.hash==h&&
((ek=e.key)==key||(ek!=null&&key.equals(ek))))
returne.val;
? ?? }
? }
returnnull;
}
resize方法
當(dāng)需要擴(kuò)容的時(shí)候耻涛，調(diào)用的時(shí)候tryPresize方法抹缕。在tryPresize方法中芒帕，并沒(méi)有加鎖背蟆，允許多個(gè)線程進(jìn)入，如果數(shù)組正在擴(kuò)張志珍，則當(dāng)前線程也去幫助擴(kuò)容伦糯。值得注意的是嗽元，復(fù)制之后的新鏈表不是舊鏈表的絕對(duì)倒序剂癌；在擴(kuò)容的時(shí)候每個(gè)線程都有處理的步長(zhǎng)佩谷，最少為16谐檀，在這個(gè)步長(zhǎng)范圍內(nèi)的數(shù)組節(jié)點(diǎn)只有自己一個(gè)線程來(lái)處理抡谐。整個(gè)操作是在持有段鎖的情況下執(zhí)行。
privatefinalvoidtryPresize(intsize) {
intc=(size>=(MAXIMUM_CAPACITY>>>1))?MAXIMUM_CAPACITY:
tableSizeFor(size+(size>>>1)+1);
intsc;
while((sc=sizeCtl)>=0) {
Node<K,V>[]tab=table;intn;
/*
* 如果數(shù)組table還沒(méi)有被初始化桐猬，則初始化一個(gè)大小為sizeCtrl和剛剛算出來(lái)的c中較大的一個(gè)大小的數(shù)組
* 初始化的時(shí)候麦撵，設(shè)置sizeCtrl為-1，初始化完成之后把sizeCtrl設(shè)置為數(shù)組長(zhǎng)度的3/4
* 為什么要在擴(kuò)張的地方來(lái)初始化數(shù)組呢？這是因?yàn)槿绻谝淮蝡ut的時(shí)候不是put單個(gè)元素厦坛，
* 而是調(diào)用putAll方法直接put一個(gè)map的話五垮，在putALl方法中沒(méi)有調(diào)用initTable方法去初始化table，
* 而是直接調(diào)用了tryPresize方法杜秸，所以這里需要做一個(gè)是不是需要初始化table的判斷
*/
if(tab==null||(n=tab.length)==0) {
n=(sc>c)?sc:c;
if(U.compareAndSwapInt(this,SIZECTL,sc,-1)) {//初始化tab的時(shí)候撬碟，把sizeCtl設(shè)為-1
try{
if(table==tab) {
@SuppressWarnings("unchecked")
Node<K,V>[]nt=(Node<K,V>[])newNode<?,?>[n];
table=nt;
sc=n-(n>>>2);
? ? ? ? ? ? ? ? ?? }
}finally{
sizeCtl=sc;
? ? ? ? ? ? ?? }
? ? ? ? ?? }
? ? ?? }
/*
* 一直擴(kuò)容到的c小于等于sizeCtl或者數(shù)組長(zhǎng)度大于最大長(zhǎng)度的時(shí)候惶傻，則退出
* 所以在一次擴(kuò)容之后银室，不是原來(lái)長(zhǎng)度的兩倍蜈敢，而是2的n次方倍
*/
elseif(c<=sc||n>=MAXIMUM_CAPACITY) {
break;//退出擴(kuò)張
? ? ?? }
elseif(tab==table) {
intrs=resizeStamp(n);
/*
* 如果正在擴(kuò)容Table的話，則幫助擴(kuò)容
* 否則的話否过，開(kāi)始新的擴(kuò)容
* 在transfer操作苗桂，將第一個(gè)參數(shù)的table中的元素煤伟，移動(dòng)到第二個(gè)元素的table中去驼卖，
* 雖然此時(shí)第二個(gè)參數(shù)設(shè)置的是null酌畜，但是，在transfer方法中考婴，當(dāng)?shù)诙€(gè)參數(shù)為null的時(shí)候，
* 會(huì)創(chuàng)建一個(gè)兩倍大小的table
*/
if(sc<0) {
Node<K,V>[]nt;
if((sc>>>RESIZE_STAMP_SHIFT)!=rs||sc==rs+1||
sc==rs+MAX_RESIZERS||(nt=nextTable)==null||
transferIndex<=0)
break;
/*
* transfer的線程數(shù)加一,該線程將進(jìn)行transfer的幫忙
* 在transfer的時(shí)候考杉，sc表示在transfer工作的線程數(shù)
*/
if(U.compareAndSwapInt(this,SIZECTL,sc,sc+1))
transfer(tab,nt);
? ? ? ? ?? }
/*
* 沒(méi)有在初始化或擴(kuò)容崇棠，則開(kāi)始擴(kuò)容
*/
elseif(U.compareAndSwapInt(this,SIZECTL,sc,
(rs<<RESIZE_STAMP_SHIFT)+2)) {
transfer(tab,null);
? ? ? ? ?? }
? ? ?? }
?? }
}
復(fù)制之后的新鏈表不是舊鏈表的絕對(duì)倒序
在擴(kuò)容的時(shí)候每個(gè)線程都有處理的步長(zhǎng)，最少為16萎坷，在這個(gè)步長(zhǎng)范圍內(nèi)的數(shù)組節(jié)點(diǎn)只有自己一個(gè)線程來(lái)處理
remove方法
remove操作首先要確定需要?jiǎng)h除的元素的位置，不過(guò)刪除元素不是簡(jiǎn)單地把待刪除元素的前面的一個(gè)元素的next指向后面一個(gè)域這么簡(jiǎn)單僧鲁。由于HashEntry中的next是final的斟叼，一經(jīng)賦值以后就不可修改引用朗涩。因此，在定位到待刪除元素的位置以后厘线，程序就將待刪除元素前面的那一些元素全部復(fù)制一遍渡讼，然后再一個(gè)一個(gè)重新接到鏈表上去成箫。這其實(shí)是由entry的不變性來(lái)決定的混驰，除了value账胧，其他所有屬性都是用final來(lái)修飾的，這意味著在第一次設(shè)置了next域之后便不能再改變它居夹，取而代之的是將它之前的節(jié)點(diǎn)全都克隆一次准脂。至于entry為什么要設(shè)置為不變性，這跟不變性的訪問(wèn)不需要同步從而節(jié)省時(shí)間有關(guān)湾戳。
Vremove(Objectkey,inthash,Objectvalue) {
lock();
try{
intc=count-1;
HashEntry<K,V>[]tab=table;
intindex=hash&(tab.length-1);
HashEntry<K,V>first=tab[index];
HashEntry<K,V>e=first;
while(e!=null&&(e.hash!=hash||!key.equals(e.key)))
e=e.next;
VoldValue=null;
if(e!=null) {
Vv=e.value;
if(value==null||value.equals(v)) {
oldValue=v;
// All entries following removed node can stay
// in list, but all preceding ones need to be
// cloned.
++modCount;
HashEntry<K,V>newFirst=e.next;
for(HashEntry<K,V>p=first;p!=e;p=p.next)
newFirst=newHashEntry<K,V>(p.key,p.hash,
newFirst,p.value);
tab[index]=newFirst;
count=c;// write-volatile
? ? ? ? ?? }
? ? ?? }
returnoldValue;
}finally{
unlock();
?? }
}
size方法
計(jì)算ConcurrentHashMap的元素大小是一個(gè)有趣的問(wèn)題，因?yàn)槭遣l(fā)操作的韧衣，就是在你計(jì)算size的時(shí)候畅铭，他還在并發(fā)的插入數(shù)據(jù)，可能會(huì)導(dǎo)致你計(jì)算出來(lái)的size和你實(shí)際的size有相差（在你return size的時(shí)候榴徐，插入了多個(gè)數(shù)據(jù)）坑资，要解決這個(gè)問(wèn)題，JDK1.7版本用兩種方案：
第一種方案使用不加鎖的模式去嘗試多次計(jì)算ConcurrentHashMap的size攒巍，最多三次柒莉，比較前后兩次計(jì)算的結(jié)果，結(jié)果一致就認(rèn)為當(dāng)前沒(méi)有元素加入跨蟹，計(jì)算的結(jié)果是準(zhǔn)確的
第二種方案是如果第一種方案不符合窗轩，就會(huì)給每個(gè)Segment加上鎖，然后計(jì)算ConcurrentHashMap的size返回
1.4 其他
ConcurrentHashMap的工作原理以及版本差異
ConcurrentHashMap為了提高本身的并發(fā)能力腹备，在內(nèi)部采用了一個(gè)叫做Segment的結(jié)構(gòu)植酥，一個(gè)Segment其實(shí)就是一個(gè)類(lèi)HashTable的結(jié)構(gòu)，Segment內(nèi)部維護(hù)了一個(gè)鏈表數(shù)組卸留。ConcurrentHashMap定位一個(gè)元素的過(guò)程需要進(jìn)行兩次Hash操作旨指，第一次 Hash 定位到 Segment谆构，第二次Hash定位到元素所在的鏈表的頭部，因此熬尺，這一種結(jié)構(gòu)的帶來(lái)的副作用是Hash的過(guò)程要比普通的HashMap要長(zhǎng)，但是帶來(lái)的好處是寫(xiě)操作的時(shí)候可以只對(duì)元素所在的Segment進(jìn)行操作即可皂吮，不會(huì)影響到其他的Segment，這樣艺挪，在最理想的情況下麻裳，ConcurrentHashMap 可以最高同時(shí)支持 Segment 數(shù)量大小的寫(xiě)操作（剛好這些寫(xiě)操作都非常平均地分布在所有的 Segment上），所以疆瑰，通過(guò)這一種結(jié)構(gòu)穆役，ConcurrentHashMap的并發(fā)能力可以大大的提高。JAVA7之前ConcurrentHashMap主要采用鎖機(jī)制淹接，在對(duì)某個(gè)Segment進(jìn)行操作時(shí)塑悼，將該Segment鎖定，不允許對(duì)其進(jìn)行非查詢(xún)操作郭怪，而在JAVA8之后采用CAS無(wú)鎖算法，這種樂(lè)觀操作在完成前進(jìn)行判斷，如果符合預(yù)期結(jié)果才給予執(zhí)行败晴，對(duì)并發(fā)操作提供良好的優(yōu)化稳懒。而1.8中做了進(jìn)一步的優(yōu)化：
JDK1.8的實(shí)現(xiàn)降低鎖的粒度场梆，JDK1.7版本鎖的粒度是基于Segment的，包含多個(gè)HashEntry顶岸，而JDK1.8鎖的粒度就是HashEntry（首節(jié)點(diǎn)）
JDK1.8版本的數(shù)據(jù)結(jié)構(gòu)變得更加簡(jiǎn)單，使得操作也更加清晰流暢凌简，因?yàn)橐呀?jīng)使用synchronized來(lái)進(jìn)行同步雏搂，所以不需要分段鎖的概念裳食，也就不需要Segment這種數(shù)據(jù)結(jié)構(gòu)了，由于粒度的降低，實(shí)現(xiàn)的復(fù)雜度也增加了
JDK1.8使用紅黑樹(shù)來(lái)優(yōu)化鏈表歌憨，基于長(zhǎng)度很長(zhǎng)的鏈表的遍歷是一個(gè)很漫長(zhǎng)的過(guò)程甲抖，而紅黑樹(shù)的遍歷效率是很快的，代替一定閾值的鏈表氛魁，這樣形成一個(gè)最佳拍檔
JDK1.8為什么使用內(nèi)置鎖synchronized來(lái)代替重入鎖ReentrantLock，我覺(jué)得有以下幾點(diǎn)：因?yàn)榱６冉档土嘶蛄矗谙鄬?duì)而言的低粒度加鎖方式，synchronized并不比ReentrantLock差，在粗粒度加鎖中ReentrantLock可能通過(guò)Condition來(lái)控制各個(gè)低粒度的邊界筛婉，更加的靈活入蛆，而在低粒度中哨毁，Condition的優(yōu)勢(shì)就沒(méi)有了；在大量的數(shù)據(jù)操作下，對(duì)于JVM的內(nèi)存壓力凳枝，基于API的ReentrantLock會(huì)產(chǎn)生更多的內(nèi)存開(kāi)銷(xiāo)。
ConcurrentHashMap中變量使用final和volatile修飾的作用
final可實(shí)現(xiàn)不變模式（immutable），是多線程安全里最簡(jiǎn)單的一種保障方式刻伊。不變模式主要通過(guò)final關(guān)鍵字來(lái)限定的。在JMM中final關(guān)鍵字還有特殊的語(yǔ)義。Final域使得確保初始化安全性（initialization safety）成為可能晨川，初始化安全性讓不可變形對(duì)象不需要同步就能自由地被訪問(wèn)和共享
使用volatile來(lái)保證某個(gè)變量?jī)?nèi)存的改變對(duì)其他線程即時(shí)可見(jiàn)呀页，在配合CAS可以實(shí)現(xiàn)不加鎖對(duì)并發(fā)操作的支持remove執(zhí)行的開(kāi)始就將table賦給一個(gè)局部變量tab渴逻，將tab依次復(fù)制出來(lái)惨奕，最后直到該刪除位置香罐，將指針指向下一個(gè)變量
