【轉(zhuǎn)載原文】莫那·魯?shù)繞掘金 講得很仔細(xì)雕擂，注解也很清楚
深入理解 hashcode 和 hash 算法
為什么使用 hashcode
那么我們就說(shuō)說(shuō)為什么使用 hashcode 量没，hashCode 存在的第一重要的原因就是在 HashMap(HashSet 其實(shí)就是HashMap) 中使用（其實(shí)Object 類(lèi)的 hashCode 方法注釋已經(jīng)說(shuō)明了 ），我知道，HashMap 之所以速度快，因?yàn)樗褂玫氖巧⒘斜恚鶕?jù) key 的 hashcode 值生成數(shù)組下標(biāo)（通過(guò)內(nèi)存地址直接查找召边，沒(méi)有任何判斷），時(shí)間復(fù)雜度完美情況下可以達(dá)到 n1（和數(shù)組相同裹驰，但是比數(shù)組用著爽多了隧熙，但是需要多出很多內(nèi)存，相當(dāng)于以空間換時(shí)間）幻林。
String 類(lèi)型的 hashcode 方法
在 JDK 中贞盯，Object 的 hashcode 方法是本地方法，也就是用 c 語(yǔ)言或 c++ 實(shí)現(xiàn)的沪饺，該方法直接返回對(duì)象的 內(nèi)存地址躏敢。這么做會(huì)有說(shuō)明問(wèn)題呢？我們用代碼看看：
class Test1{
String name;
public Test1(String name) {
this.name = name;
}
public static void main(String[] args) {
Map<Test1, String> map = new HashMap<>(4);
map.put(new Test1("hello"), "hello");
String hello = map.get(new Test1("hello"));
System.out.println(hello);
}
}
這段代碼打印出來(lái)的會(huì)是什么呢整葡？ 答： null件余。因?yàn)槲覀儧](méi)有重寫(xiě) hashCode 方法，所有遭居，HashMap 內(nèi)部使用的是該對(duì)象的內(nèi)存地址啼器，那么肯定不一樣。我們第一個(gè)對(duì)象根本就沒(méi)有存俱萍，因此镀首，返回就是 null。這里就可以看出來(lái)重寫(xiě) hashCode 的重要性鼠次。
JDK 中，我們經(jīng)常把 String 類(lèi)型作為 key，那么 String 類(lèi)型是如何重寫(xiě) hashCode 方法的呢腥寇？
我們看看代碼：
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
代碼非常簡(jiǎn)單成翩，就是使用 String 的 char 數(shù)組的數(shù)字每次乘以 31 再疊加最后返回，因此赦役，每個(gè)不同的字符串麻敌，返回的 hashCode 肯定不一樣。那么為什么使用 31 呢掂摔？
為什么大部分 hashcode 方法使用 31
如果有使用 eclipse 的同學(xué)肯定知道术羔，該工具默認(rèn)生成的 hashCode 方法實(shí)現(xiàn)也和 String 類(lèi)型差不多。都是使用的 31 乙漓，那么有沒(méi)有想過(guò)：為什么要使用 31 呢级历？
在名著 《Effective Java》第 42 頁(yè)就有對(duì) hashCode 為什么采用 31 做了說(shuō)明：
之所以使用 31， 是因?yàn)樗且粋€(gè)奇素?cái)?shù)叭披。如果乘數(shù)是偶數(shù)寥殖，并且乘法溢出的話，信息就會(huì)丟失涩蜘，因?yàn)榕c2相乘等價(jià)于移位運(yùn)算（低位補(bǔ)0）嚼贡。使用素?cái)?shù)的好處并不很明顯，但是習(xí)慣上使用素?cái)?shù)來(lái)計(jì)算散列結(jié)果同诫。 31 有個(gè)很好的性能粤策，即用移位和減法來(lái)代替乘法，可以得到更好的性能： 31 * i == (i << 5） - i误窖， 現(xiàn)代的 VM 可以自動(dòng)完成這種優(yōu)化叮盘。這個(gè)公式可以很簡(jiǎn)單的推導(dǎo)出來(lái)。
這個(gè)問(wèn)題在 SO 上也有討論： https://stackoverflow.com/questions/299304/why-does-javas-hashcode-in-string-use-31-as-a-multiplier%EF%BC%89
可以看到贩猎，使用 31 最主要的還是為了性能熊户。當(dāng)然用 63 也可以。但是 63 的溢出風(fēng)險(xiǎn)就更大了吭服。那么15 呢嚷堡？仔細(xì)想想也可以。
在《Effective Java》也說(shuō)道：編寫(xiě)這種散列函數(shù)是個(gè)研究課題艇棕，最好留給數(shù)學(xué)家和理論方面的計(jì)算機(jī)科學(xué)家來(lái)完成蝌戒。我們此次最重要的是知道了為什么使用31。
HashMap 的 hash 算法的實(shí)現(xiàn)原理（為什么右移 16 位沼琉，為什么要使用 ^ 位異或）
好了北苟，知道了 hashCode 的生成原理了，我們要看看今天的主角打瘪，hash 算法友鼻。
其實(shí)傻昙，這個(gè)也是數(shù)學(xué)的范疇，從我們的角度來(lái)講彩扔，只要知道這是為了更好的均勻散列表的下標(biāo)就好了妆档，但是，就是耐不住好奇心俺娴铩贾惦！ 能多知道一點(diǎn)就是一點(diǎn)，我們來(lái)看看 HashMap 的 hash 算法（JDK 8）.
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
乍看一下就是簡(jiǎn)單的異或運(yùn)算和右移運(yùn)算敦捧，但是為什么要異或呢须板？為什么要移位呢？而且移位16兢卵？
在分析這個(gè)問(wèn)題之前习瑰，我們需要先看看另一個(gè)事情，什么呢济蝉？就是 HashMap 如何根據(jù) hash 值找到數(shù)組種的對(duì)象杰刽，我們看看 get 方法的代碼：
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
// 我們需要關(guān)注下面這一行
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
我們看看代碼中注釋下方的一行代碼：first = tab[(n - 1) & hash])。
使用數(shù)組長(zhǎng)度減一 與運(yùn)算 hash 值王滤。這行代碼就是為什么要讓前面的 hash 方法移位并異或贺嫂。
我們分析一下：
首先，假設(shè)有一種情況雁乡，對(duì)象 A 的 hashCode 為 1000010001110001000001111000000第喳，對(duì)象 B 的 hashCode 為 0111011100111000101000010100000。
如果數(shù)組長(zhǎng)度是16踱稍，也就是 15 與運(yùn)算這兩個(gè)數(shù)泻帮， 你會(huì)發(fā)現(xiàn)結(jié)果都是0枣宫。這樣的散列結(jié)果太讓人失望了溅漾。很明顯不是一個(gè)好的散列算法哎甲。
但是如果我們將 hashCode 值右移 16 位，也就是取 int 類(lèi)型的一半啤挎，剛好將該二進(jìn)制數(shù)對(duì)半切開(kāi)驻谆。并且使用位異或運(yùn)算（如果兩個(gè)數(shù)對(duì)應(yīng)的位置相反，則結(jié)果為1庆聘，反之為0）胜臊，這樣的話，就能避免我們上面的情況的發(fā)生伙判。
總的來(lái)說(shuō)象对，使用位移 16 位和 異或 就是防止這種極端情況。但是宴抚，該方法在一些極端情況下還是有問(wèn)題勒魔，比如：10000000000000000000000000 和 1000000000100000000000000 這兩個(gè)數(shù)甫煞，如果數(shù)組長(zhǎng)度是16，那么即使右移16位沥邻，在異或危虱，hash 值還是會(huì)重復(fù)。但是為了性能唐全，對(duì)這種極端情況，JDK 的作者選擇了性能蕊玷。畢竟這是少數(shù)情況邮利，為了這種情況去增加 hash 時(shí)間，性?xún)r(jià)比不高垃帅。
HashMap 為什么使用 & 與運(yùn)算代替模運(yùn)算延届？
好了，知道了 hash 算法的實(shí)現(xiàn)原理還有他的一些取舍贸诚，我們?cè)倏纯磩倓傉f(shuō)的那個(gè)根據(jù)hash計(jì)算下標(biāo)的方法：
tab[(n - 1) & hash]方庭；
其中 n 是數(shù)組的長(zhǎng)度。其實(shí)該算法的結(jié)果和模運(yùn)算的結(jié)果是相同的酱固。但是械念，對(duì)于現(xiàn)代的處理器來(lái)說(shuō)，除法和求余數(shù)（模運(yùn)算）是最慢的動(dòng)作运悲。
上面情況下和模運(yùn)算相同呢龄减？
a % b == (b-1) & a ,當(dāng)b是2的指數(shù)時(shí)，等式成立班眯。
我們說(shuō) & 與運(yùn)算的定義：與運(yùn)算 第一個(gè)操作數(shù)的的第n位于第二個(gè)操作數(shù)的第n位如果都是1希停，那么結(jié)果的第n為也為1，否則為0署隘；
當(dāng) n 為 16 時(shí)宠能， 與運(yùn)算 101010100101001001101 時(shí)，也就是
1111 & 101010100101001001000 結(jié)果：1000 = 8
1111 & 101000101101001001001 結(jié)果：1001 = 9
1111 & 101010101101101001010 結(jié)果： 1010 = 10
1111 & 101100100111001101100 結(jié)果： 1100 = 12
可以看到磁餐，當(dāng) n 為 2 的冪次方的時(shí)候违崇，減一之后就會(huì)得到 1111* 的數(shù)字，這個(gè)數(shù)字正好可以掩碼崖媚。并且得到的結(jié)果取決于 hash 值亦歉。因?yàn)?hash 值是1，那么最終的結(jié)果也是1 畅哑，hash 值是0肴楷，最終的結(jié)果也是0。
HashMap 的容量為什么建議是 2的冪次方荠呐？
到這里赛蔫，我們提了一個(gè)關(guān)鍵的問(wèn)題： HashMap 的容量為什么建議是 2的冪次方砂客？正好可以和上面的話題接上。樓主就是這么設(shè)計(jì)的呵恢。
為什么要 2 的冪次方呢鞠值？
我們說(shuō)，hash 算法的目的是為了讓hash值均勻的分布在桶中（數(shù)組）渗钉，那么彤恶，如何做到呢？試想一下鳄橘，如果不使用 2 的冪次方作為數(shù)組的長(zhǎng)度會(huì)怎么樣声离？
假設(shè)我們的數(shù)組長(zhǎng)度是10，還是上面的公式：
1010 & 101010100101001001000 結(jié)果：1000 = 8
1010 & 101000101101001001001 結(jié)果：1000 = 8
1010 & 101010101101101001010 結(jié)果： 1010 = 10
1010 & 101100100111001101100 結(jié)果： 1000 = 8
看到結(jié)果我們驚呆了瘫怜，這種散列結(jié)果术徊，會(huì)導(dǎo)致這些不同的key值全部進(jìn)入到相同的插槽中，形成鏈表鲸湃，性能急劇下降赠涮。
所以說(shuō)，我們一定要保證 & 中的二進(jìn)制位全為 1暗挑，才能最大限度的利用 hash 值笋除，并更好的散列，只有全是1 窿祥，才能有更多的散列結(jié)果株憾。如果是 1010，有的散列結(jié)果是永遠(yuǎn)都不會(huì)出現(xiàn)的晒衩，比如 0111嗤瞎，0101，1111听系，1110.......贝奇，只要 & 之前的數(shù)有 0， 對(duì)應(yīng)的 1 肯定就不會(huì)出現(xiàn)（因?yàn)橹挥卸际?才會(huì)為1）靠胜。大大限制了散列的范圍掉瞳。
我們自定義 HashMap 容量最好是多少？
那我們?nèi)绾巫远x呢浪漠？自從有了阿里的規(guī)約插件陕习，每次樓主都要初始化容量，如果我們預(yù)計(jì)我們的散列表中有2個(gè)數(shù)據(jù)址愿，那么我就初始化容量為2嘛该镣？
絕對(duì)不行，如果大家看過(guò)源碼就會(huì)發(fā)現(xiàn)响谓，如果Map中已有數(shù)據(jù)的容量達(dá)到了初始容量的 75%损合，那么散列表就會(huì)擴(kuò)容省艳，而擴(kuò)容將會(huì)重新將所有的數(shù)據(jù)重新散列，性能損失嚴(yán)重嫁审，所以跋炕，我們可以必須要大于我們預(yù)計(jì)數(shù)據(jù)量的 1.34 倍，如果是2個(gè)數(shù)據(jù)的話律适，就需要初始化 2.68 個(gè)容量辐烂。當(dāng)然這是開(kāi)玩笑的，2.68 不可以擦耀，3 可不可以呢棉圈？肯定也是不可以的，我前面說(shuō)了眷蜓，如果不是2的冪次方，散列結(jié)果將會(huì)大大下降胎围。導(dǎo)致出現(xiàn)大量鏈表吁系。那么我可以將初始化容量設(shè)置為4。 當(dāng)然了白魂，如果你預(yù)計(jì)大概會(huì)插入 12 條數(shù)據(jù)的話汽纤，那么初始容量為16簡(jiǎn)直是完美，一點(diǎn)不浪費(fèi)福荸，而且也不會(huì)擴(kuò)容蕴坪。
總結(jié)
好了，分析完了 hashCode 和 hash 算法敬锐，讓我們對(duì) HashMap 又有了全新的認(rèn)識(shí)背传。當(dāng)然，HashMap 中還有很多有趣的東西值得挖掘台夺，樓主會(huì)繼續(xù)寫(xiě)下去径玖。爭(zhēng)取將 HashMap 的衣服扒光。
總的來(lái)說(shuō)颤介，通過(guò)今天的分析梳星，對(duì)我們今后使用 HashMap 有了更多的把握，也能夠排查一些問(wèn)題滚朵，比如鏈表數(shù)很多冤灾，肯定是數(shù)組初始化長(zhǎng)度不對(duì)，如果某個(gè)map很大辕近，注意韵吨，肯定是事先沒(méi)有定義好初始化長(zhǎng)度，假設(shè)亏推，某個(gè)Map存儲(chǔ)了10000個(gè)數(shù)據(jù)学赛，那么他會(huì)擴(kuò)容到 20000年堆，實(shí)際上，根本不用 20000盏浇，只需要 10000* 1.34= 13400 個(gè)变丧，然后向上找到一個(gè)2 的冪次方，也就是 16384 初始容量足夠绢掰。
深入理解 HashMap put 方法（JDK 8逐行剖析）
注意：我們今天所有的一切都是基于 JDK 8痒蓬，JDK 8 的實(shí)現(xiàn)和 JDK 7 有重大區(qū)別。
前面我們分析了 hashCode 和 hash 算法的原理滴劲，其實(shí)都是為我們解析 HashMap 做鋪墊攻晒，因?yàn)?HashMap 確實(shí)比較復(fù)雜（如果你每一行代碼都看的話，每個(gè)位移都糾結(jié)的話）班挖，雖然總的來(lái)說(shuō)鲁捏，HashMap 不過(guò)是 Node 數(shù)組加 鏈表和紅黑樹(shù)。但是里面的細(xì)節(jié)確是無(wú)比的優(yōu)雅和有趣萧芙。樓主為什么選擇 put 方法來(lái)講呢给梅？因?yàn)閺臉侵骺磥?lái)，HashMap 的精髓就在 put 方法中双揪。
HashMap 的解析從樓主來(lái)看动羽，主要可以分為幾個(gè)部分：
- hash 算法（這個(gè)我們之前說(shuō)過(guò)了，今天就不再贅述了）
- 初始化數(shù)組渔期。
- 通過(guò) hash 計(jì)算下標(biāo)并檢查 hash 是否沖突运吓，也就是對(duì)應(yīng)的下標(biāo)是否已存在元素。
- 通過(guò)判斷是否含有元素疯趟，決定是否創(chuàng)建還是追加鏈表或樹(shù)拘哨。
- 判斷已有元素的類(lèi)型，決定是追加樹(shù)還是追加鏈表迅办。
- 判斷是否超過(guò)閥值宅静，如果超過(guò)，則重新散列數(shù)組站欺。
- Java 8 重新散列時(shí)是如何優(yōu)化的姨夹。
開(kāi)始吧！７摺磷账！
初始化數(shù)組
首先我們來(lái)一個(gè)測(cè)試?yán)樱?/p>
public static void main(String[] args) {
HashMap<String, Integer> hashMap = new HashMap<>(2);
hashMap.put("one", 1);
Integer one = hashMap.get("one");
System.out.println(one);
}
一個(gè)簡(jiǎn)單的不能再簡(jiǎn)單的使用 HashMap 的例子，其中包含了對(duì)于 HashMap 來(lái)說(shuō)關(guān)鍵的 3 個(gè)步驟贾虽，初始化逃糟，put 元素，get 元素。
由于我們預(yù)計(jì)會(huì)放入一個(gè)元素绰咽，出于性能考慮菇肃，我們將容量設(shè)置為 2躺枕，既保證了性能惠况，也節(jié)約了空間（置于為什么，我們?cè)谥暗奈恼轮兄v過(guò)）魄懂。
那么我們就看看 new 操作的時(shí)候做了些什么事情：
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and the default load factor (0.75).
*
* @param initialCapacity the initial capacity.
* @throws IllegalArgumentException if the initial capacity is negative.
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//=================================================================================
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
上面是 HashMap 的兩個(gè)構(gòu)造方法玩敏，其中斗忌，我們?cè)O(shè)置了初始容量為 2， 而默認(rèn)的加載因子我們之前說(shuō)過(guò)：0.75旺聚，當(dāng)然也可以自己設(shè)置织阳，但 0.75 是最均衡的設(shè)置，沒(méi)有特殊要求不要修改該值砰粹，加載因子過(guò)小唧躲，理論上能減少 hash 沖突，加載因子過(guò)大可以節(jié)約空間碱璃，減少 HashMap 中最耗性能的操作：reHash惊窖。
從代碼中我可以看到，如果我們?cè)O(shè)置的初始化容量小于0厘贼，將會(huì)拋出異常，如果加載因子小于0也會(huì)拋出異常圣拄。同時(shí)嘴秸，如果初始容量大于最大容量，則重新設(shè)置為最大容量庇谆。
我們開(kāi)最后兩行代碼岳掐，首先，對(duì)負(fù)載因子進(jìn)行賦值饭耳，這個(gè)沒(méi)什么可說(shuō)的串述。
牛逼的是下面一行代碼：this.threshold = tableSizeFor(initialCapacity); 可以看的出來(lái)這個(gè)動(dòng)作是計(jì)算閥值，上面是閥值呢寞肖？閥值就是纲酗，如果容器中的元素大于閥值了，就需要進(jìn)行擴(kuò)容新蟆，那么這里的這行代碼觅赊，就是根據(jù)初始容量進(jìn)行閥值的計(jì)算。
我們進(jìn)入到該方法查看：
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
一通或運(yùn)算和無(wú)符號(hào)右移運(yùn)算琼稻，那么這個(gè)運(yùn)算的的最后結(jié)果是什么呢吮螺？這里其實(shí)就是如果用戶(hù)輸入的值不是2的冪次方（我們通過(guò)之前的分析，應(yīng)該直到初始容量如果不是2的冪次方會(huì)有多么不好的結(jié)果）。通過(guò)位移運(yùn)算和或運(yùn)算鸠补，最后得到一定是2的冪次方萝风，并且是那個(gè)離那個(gè)數(shù)最近的數(shù)字，我們仔細(xì)看看該方法：
| : 或運(yùn)算紫岩，第一個(gè)操作數(shù)的的第n位于第二個(gè)操作數(shù)的第n位 只要有一個(gè)是1规惰，那么結(jié)果的第n為也為1，否則為0
首先被因，將容量減1卿拴，我們后面就知道了。然后將該數(shù)字無(wú)符號(hào)右移1梨与，2堕花，4，8粥鞋，16缘挽，總共移了32位，剛好是一個(gè)int類(lèi)型的長(zhǎng)度呻粹。在移動(dòng)的過(guò)程中壕曼，還對(duì)該數(shù)字進(jìn)行或運(yùn)算，為了方便查看等浊，樓主寫(xiě)一下2進(jìn)制的運(yùn)算過(guò)程腮郊，假如我輸入的是10，明顯不是2的冪次方筹燕。我們看看會(huì)怎么樣：
10 = 1010轧飞；
n = 9;
1001 == 9；
1001 >>> 1 = 0100;
1001 或 0100 = 1101撒踪；
1101 >>> 2 = 0011;
110 或 0011 = 1111过咬；
1111 >>> 4 = 0000;
1111 或 0000 = 1111；
1111 >>> 8 = 0000;
1111 或 0000 = 1111制妄；
1111 >>> 16 = 0000掸绞；
1111 或 0000 = 1111；
最后耕捞，1111 也就是 15 衔掸，15 + 1 = 16，剛好就是距離10 最近的并且沒(méi)有變小的2的冪次方數(shù)砸脊【咂可以說(shuō)這個(gè)算法非常的牛逼。樓主五體投地凌埂。
但是如果是 16 呢驱显，并且沒(méi)有不減一，我們看看什么結(jié)果：
16 = 10000；
10000 >>> 1 = 01000;
10000 或 01000 = 11000埃疫；
11000 >>> 2 = 00110;
11000 或 00110 = 11110伏恐；
11110 >>> 4 = 00001;
11110 或 00001 = 11111；
11111 >>> 8 = 00000;
11111 或 00000 = 11111栓霜；
11111 >>> 16 = 00000翠桦；
11111 或 00000 = 11111；
最后的數(shù)字就是31 胳蛮，31+ 1 = 32销凑，同樣也是上升到了更大的2次冪的數(shù)字。但是這不是我想要的結(jié)果仅炊，所以斗幼，JDK 的作者在之前先減去了1. 防止出現(xiàn)這樣的問(wèn)題。
我們仔細(xì)觀察其算法的過(guò)程抚垄，可以說(shuō)蜕窿，任何一個(gè)int 數(shù)字，都能找到離他最近的 2 的冪次方數(shù)字（并且比他大）呆馁。
好了桐经。到這里就完成了初始化，不過(guò)請(qǐng)注意浙滤，這里設(shè)置的閥值并不是最終的閥值阴挣，最終的閥值我們會(huì)在后面詳細(xì)說(shuō)明。這里我們更加關(guān)注這個(gè)算法纺腊。真的牛逼啊屯吊。
通過(guò) hash 計(jì)算下標(biāo)并檢查 hash 是否沖突，也就是對(duì)應(yīng)的下標(biāo)是否已存在元素摹菠。
初始化好了 HashMap，我們接著就調(diào)用了 put 方法骗爆，該方法如下：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
其中調(diào)用 hash 方法次氨，該方法我們之前已經(jīng)深入討論過(guò)，今天就不贅述了摘投，如果有同學(xué)沒(méi)有看過(guò)煮寡，也不要緊，看完這篇 再去看 或者 看完那篇 再來(lái) 看這篇都可以犀呼。有點(diǎn)繞幸撕。好，然后調(diào)用了 puVal 方法外臂，我們看看該方法：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 當(dāng)前對(duì)象的數(shù)組是null 或者數(shù)組長(zhǎng)度時(shí)0時(shí)坐儿，則需要初始化數(shù)組
if ((tab = table) == null || (n = tab.length) == 0)
// 得到數(shù)組的長(zhǎng)度 16
n = (tab = resize()).length;
// 如果通過(guò)hash值計(jì)算出的下標(biāo)的地方?jīng)]有元素，則根據(jù)給定的key 和 value 創(chuàng)建一個(gè)元素
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else { // 如果hash沖突了
Node<K,V> e; K k;
// 如果給定的hash和沖突下標(biāo)中的 hash 值相等并且 （已有的key和給定的key相等（地址相同，或者equals相同））貌矿，說(shuō)明該key和已有的key相同
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 那么就將已存在的值賦給上面定義的e變量
e = p;
// 如果以存在的值是個(gè)樹(shù)類(lèi)型的炭菌，則將給定的鍵值對(duì)和該值關(guān)聯(lián)。
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 如果key不相同逛漫，只是hash沖突黑低，并且不是樹(shù)，則是鏈表
else {
// 循環(huán)酌毡，直到鏈表中的某個(gè)節(jié)點(diǎn)為null克握，或者某個(gè)節(jié)點(diǎn)hash值和給定的hash值一致且key也相同，則停止循環(huán)枷踏。
for (int binCount = 0; ; ++binCount) {
// 如果next屬性是空
if ((e = p.next) == null) {
// 那么創(chuàng)建新的節(jié)點(diǎn)賦值給已有的next 屬性
p.next = newNode(hash, key, value, null);
// 如果樹(shù)的閥值大于等于7菩暗，也就是，鏈表長(zhǎng)度達(dá)到了8（從0開(kāi)始）呕寝。
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 如果鏈表長(zhǎng)度達(dá)到了8勋眯，且數(shù)組長(zhǎng)度小于64，那么就重新散列下梢，如果大于64客蹋，則創(chuàng)建紅黑樹(shù)
treeifyBin(tab, hash);
// 結(jié)束循環(huán)
break;
}
// 如果hash值和next的hash值相同且（key也相同）
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 結(jié)束循環(huán)
break;
// 如果給定的hash值不同或者key不同。
// 將next 值賦給 p孽江，為下次循環(huán)做鋪墊
p = e;
}
}
// 通過(guò)上面的邏輯讶坯，如果e不是null，表示：該元素存在了(也就是他們呢key相等)
if (e != null) { // existing mapping for key
// 取出該元素的值
V oldValue = e.value;
// 如果 onlyIfAbsent 是 true岗屏，就不要改變已有的值辆琅，這里我們是false。
// 如果是false这刷，或者 value 是null
if (!onlyIfAbsent || oldValue == null)
// 將新的值替換老的值
e.value = value;
// HashMap 中什么都不做
afterNodeAccess(e);
// 返回之前的舊值
return oldValue;
}
}
// 如果e== null婉烟，需要增加 modeCount 變量，為迭代器服務(wù)暇屋。
++modCount;
// 如果數(shù)組長(zhǎng)度大于了閥值
if (++size > threshold)
// 重新散列
resize();
// HashMap 中什么都不做
afterNodeInsertion(evict);
// 返回null
return null;
}
該方法可以說(shuō)是 HashMap 的核心方法似袁，樓主已經(jīng)在該方法中寫(xiě)滿(mǎn)了注釋。樓主說(shuō)一下該方法的步驟：
判斷數(shù)組是否為空咐刨，如果是空昙衅，則創(chuàng)建默認(rèn)長(zhǎng)度位 16 的數(shù)組。
通過(guò)與運(yùn)算計(jì)算對(duì)應(yīng) hash 值的下標(biāo)定鸟，如果對(duì)應(yīng)下標(biāo)的位置沒(méi)有元素而涉，則直接創(chuàng)建一個(gè)。
-
如果有元素联予，說(shuō)明 hash 沖突了啼县，則再次進(jìn)行 3 種判斷材原。
- 判斷兩個(gè)沖突的key是否相等，equals 方法的價(jià)值在這里體現(xiàn)了谭羔。如果相等华糖，則將已經(jīng)存在的值賦給變量e。最后更新e的value瘟裸，也就是替換操作客叉。
- 如果key不相等，則判斷是否是紅黑樹(shù)類(lèi)型话告，如果是紅黑樹(shù)兼搏，則交給紅黑樹(shù)追加此元素。
- 如果key既不相等沙郭，也不是紅黑樹(shù)佛呻，則是鏈表，那么就遍歷鏈表中的每一個(gè)key和給定的key是否相等病线。如果吓著，鏈表的長(zhǎng)度大于等于8了，則將鏈表改為紅黑樹(shù)送挑，這是Java8 的一個(gè)新的優(yōu)化绑莺。
最后，如果這三個(gè)判斷返回的 e 不為null惕耕，則說(shuō)明key重復(fù)纺裁，則更新key對(duì)應(yīng)的value的值。
對(duì)維護(hù)著迭代器的modCount 變量加一司澎。
最后判斷欺缘，如果當(dāng)前數(shù)組的長(zhǎng)度已經(jīng)大于閥值了。則重新hash挤安。
通過(guò)判斷是否含有元素渊迁，決定是否創(chuàng)建還是追加鏈表或樹(shù)厌殉。
首先判斷是否含有元素鹃彻，通過(guò)什么判斷呢揭绑？
tab[i = (n - 1) & hash]秕衙；
這個(gè)算式根據(jù) hash 值獲取對(duì)應(yīng)的下標(biāo)蔓肯，具體是什么原理阀参，我們?cè)谏弦黄恼乱呀?jīng)說(shuō)了原因鸣皂。這里也不在贅述了摔踱。如果 hash 值沒(méi)有沖突虐先，則創(chuàng)建一個(gè) Node 對(duì)象，參數(shù)是hash值派敷，key蛹批，value撰洗，還有為null 的next 屬性。下面是構(gòu)造函數(shù)腐芍。
// 構(gòu)造函數(shù)
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
如果沒(méi)有沖突差导，后面緊接著就走 ++modCount，然后猪勇，判斷容量是否大于閥值（默認(rèn)是12）设褐。如果大于，則調(diào)用 resize 方法泣刹，重新散列助析。resize 方法我們后面詳細(xì)分析。
判斷已有元素的類(lèi)型椅您，決定是追加樹(shù)還是追加鏈表外冀。
如果 hash 沖突了怎么辦？我們剛剛說(shuō)會(huì)有3種判斷：
- 判斷兩個(gè)沖突的key是否相等掀泳，equals 方法的價(jià)值在這里體現(xiàn)了雪隧。如果相等，則將已經(jīng)存在的值賦給變量e员舵。最后更新e的value脑沿，也就是替換操作。
- 如果key不相等固灵，則判斷是否是紅黑樹(shù)類(lèi)型捅伤，如果是紅黑樹(shù)，則交給紅黑樹(shù)追加此元素巫玻。
- 如果key既不相等丛忆，也不是紅黑樹(shù)，則是鏈表仍秤，那么就遍歷鏈表中的每一個(gè)key和給定的key是否相等熄诡。如果，鏈表的長(zhǎng)度大于等于8了诗力，則將鏈表改為紅黑樹(shù)凰浮，這是Java8 的一個(gè)新的優(yōu)化。
注意：在鏈表的循環(huán)中苇本，有一個(gè)方法 treeifyBin袜茧，這個(gè)方法在鏈表長(zhǎng)度大于等于8 的時(shí)候會(huì)調(diào)用，那么該方法的內(nèi)容是什么呢瓣窄？
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 如果數(shù)組是null 或者數(shù)組的長(zhǎng)度小于 64
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
// 重新散列
resize();
// 如果給定的hash沖突了笛厦，則創(chuàng)建紅黑樹(shù)結(jié)構(gòu)
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
該方法雖然主要功能是替換鏈表結(jié)構(gòu)為紅黑樹(shù)，但是在替換前俺夕，會(huì)先判斷裳凸，如果數(shù)組是 null 或者數(shù)組的長(zhǎng)度小于 64贱鄙，則重新散列，因?yàn)橹匦律⒘袝?huì)拆分鏈表姨谷，使得鏈表的長(zhǎng)度變短逗宁。提高性能。如果長(zhǎng)度大于64了梦湘。就只能將鏈表變?yōu)榧t黑樹(shù)了瞎颗。
判斷是否超過(guò)閥值，如果超過(guò)践叠，則重新散列數(shù)組言缤。
最后，判斷是否閥值禁灼，如果超過(guò)則進(jìn)行散列管挟；
// 如果 e == null，需要增加 modeCount 變量弄捕，為迭代器服務(wù)僻孝。
++modCount;
// 如果數(shù)組長(zhǎng)度大于了閥值
if (++size > threshold)
// 重新散列
resize();
// HashMap 中什么都不做
afterNodeInsertion(evict);
// 返回null
return null;
我們知道，閥值默認(rèn)是16守谓，那么 resize 方法就是重新散列的核心方法穿铆，我們看看該方法實(shí)現(xiàn)：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 如果老的容量大于0
if (oldCap > 0) {
// 如果容量大于容器最大值
if (oldCap >= MAXIMUM_CAPACITY) {
// 閥值設(shè)為int最大值
threshold = Integer.MAX_VALUE;
// 返回老的數(shù)組，不再擴(kuò)充
return oldTab;
}// 如果老的容量*2 小于最大容量并且老的容量大于等于默認(rèn)容量
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 新的閥值也再老的閥值基礎(chǔ)上*2
newThr = oldThr << 1; // double threshold
}// 如果老的閥值大于0
else if (oldThr > 0) // initial capacity was placed in threshold
// 新容量等于老閥值
newCap = oldThr;
else { // 如果容量是0斋荞，閥值也是0荞雏，認(rèn)為這是一個(gè)新的數(shù)組，使用默認(rèn)的容量16和默認(rèn)的閥值12
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果新的閥值是0平酿，重新計(jì)算閥值
if (newThr == 0) {
// 使用新的容量 * 負(fù)載因子（0.75）
float ft = (float)newCap * loadFactor;
// 如果新的容量小于最大容量 且 閥值小于最大 則新閥值等于剛剛計(jì)算的閥值凤优，否則新閥值為 int 最大值
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 將新閥值賦值給當(dāng)前對(duì)象的閥值。
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// 創(chuàng)建一個(gè)Node 數(shù)組蜈彼，容量是新數(shù)組的容量（新容量要么是老的容量筑辨，要么是老容量*2，要么是16）
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
// 將新數(shù)組賦值給當(dāng)前對(duì)象的數(shù)組屬性
table = newTab;
// 如果老的數(shù)組不是null
if (oldTab != null) {
// 循環(huán)老數(shù)組
for (int j = 0; j < oldCap; ++j) {
// 定義一個(gè)節(jié)點(diǎn)
Node<K,V> e;
// 如果老數(shù)組對(duì)應(yīng)下標(biāo)的值不為空
if ((e = oldTab[j]) != null) {
// 設(shè)置為空
oldTab[j] = null;
// 如果老數(shù)組沒(méi)有鏈表
if (e.next == null)
// 將該值散列到新數(shù)組中
newTab[e.hash & (newCap - 1)] = e;
// 如果該節(jié)點(diǎn)是樹(shù)
else if (e instanceof TreeNode)
// 調(diào)用紅黑樹(shù) 的split 方法幸逆，傳入當(dāng)前對(duì)象棍辕，新數(shù)組，當(dāng)前下標(biāo)还绘，老數(shù)組的容量楚昭，目的是將樹(shù)的數(shù)據(jù)重新散列到數(shù)組中
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // 如果既不是樹(shù)，next 節(jié)點(diǎn)也不為空拍顷，則是鏈表抚太，注意，這里將優(yōu)化鏈表重新散列（java 8 的改進(jìn)）
// Java8 之前菇怀，這里曾是并發(fā)操作會(huì)出現(xiàn)環(huán)狀鏈表的情況凭舶，但是Java8 優(yōu)化了算法。此bug不再出現(xiàn)爱沟，但并發(fā)時(shí)仍然不建議HashMap
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 這里的判斷需要引出一些東西：oldCap 假如是16帅霜，那么二進(jìn)制為 10000，擴(kuò)容變成 100000呼伸，也就是32.
// 當(dāng)舊的hash值 與運(yùn)算 10000身冀，結(jié)果是0的話，那么hash值的右起第五位肯定也是0括享，那么該于元素的下標(biāo)位置也就不變搂根。
if ((e.hash & oldCap) == 0) {
// 第一次進(jìn)來(lái)時(shí)給鏈頭賦值
if (loTail == null)
loHead = e;
else
// 給鏈尾賦值
loTail.next = e;
// 重置該變量
loTail = e;
}
// 如果不是0，那么就是1铃辖，也就是說(shuō)剩愧，如果原始容量是16，那么該元素新的下標(biāo)就是：原下標(biāo) + 16（10000b）
else {
// 同上
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 理想情況下娇斩，可將原有的鏈表拆成2組仁卷，提高查詢(xún)性能。
if (loTail != null) {
// 銷(xiāo)毀實(shí)例犬第，等待GC回收
loTail.next = null;
// 置入bucket中
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
該方法可以說(shuō)還是比較復(fù)雜的锦积。初始的時(shí)候也是調(diào)用的這個(gè)方法，當(dāng)鏈表數(shù)超過(guò)8的時(shí)候同時(shí)數(shù)組長(zhǎng)度小于64的時(shí)候也是調(diào)用的這個(gè)方法歉嗓。該方法步驟如下：
- 判斷容量是否大于0丰介，如果大于0，并且容量已將大于最大值鉴分，則設(shè)置閥值為 int 最大值哮幢，并返回，如果老的容量乘以 2 小于最大容量冠场，且老的容量大于等于16家浇，則更新閥值。也就是乘以2.
- 如果老的閥值大于0碴裙，則新的容量等于老的閥值钢悲。注意：這里很重要。還記的我們之前使用new 操作符的時(shí)候舔株，會(huì)設(shè)置閥值為 2 的冪次方莺琳，那么這里就用上了那個(gè)計(jì)算出來(lái)的數(shù)字，也就是說(shuō)载慈，就算我們?cè)O(shè)置的不是2的冪次方惭等，HashMap 也會(huì)自動(dòng)將你的容量設(shè)置為2的冪次方。
- 如果老的閥值和容量都不大于0办铡，則認(rèn)為是一個(gè)新的數(shù)組辞做，默認(rèn)初始容量為16琳要，閥值為 16 * 0.75f，也就是 12秤茅。
- 如果稚补，新的閥值還是0，那么就使用我們剛剛設(shè)置的容量（HashMap 幫我們算的）框喳，通過(guò)乘以 0.75课幕，得到一個(gè)閥值，然后判斷算出的閥值是否合法：如果容量小于最大容量并且閥值小于最大容量五垮，那么則使用該閥值乍惊，否則使用 int 最大值。
- 將剛剛的閥值設(shè)置打當(dāng)前Map實(shí)例的閥值屬性中放仗。
- 將剛剛的數(shù)組設(shè)置到當(dāng)前Map實(shí)例的數(shù)組屬性中润绎。
- 如果老的數(shù)組不是null，則將老數(shù)組中的值重新散列到新數(shù)組中匙监。如果是null凡橱，直接返回新數(shù)組。
那么亭姥，將老數(shù)組重新散列的過(guò)程到底是怎么樣的呢稼钩？
Java 8 重新散列時(shí)是如何優(yōu)化的。
重新散列的代碼：
// 如果老的數(shù)組不是null
if (oldTab != null) {
// 循環(huán)老數(shù)組
for (int j = 0; j < oldCap; ++j) {
// 定義一個(gè)節(jié)點(diǎn)
Node<K,V> e;
// 如果老數(shù)組對(duì)應(yīng)下標(biāo)的值不為空
if ((e = oldTab[j]) != null) {
// 設(shè)置為空
oldTab[j] = null;
// 如果老數(shù)組沒(méi)有鏈表
if (e.next == null)
// 將該值散列到新數(shù)組中
newTab[e.hash & (newCap - 1)] = e;
// 如果該節(jié)點(diǎn)是樹(shù)
else if (e instanceof TreeNode)
// 調(diào)用紅黑樹(shù) 的split 方法达罗，傳入當(dāng)前對(duì)象坝撑，新數(shù)組，當(dāng)前下標(biāo)粮揉，老數(shù)組的容量巡李，目的是將樹(shù)的數(shù)據(jù)重新散列到數(shù)組中
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // 如果既不是樹(shù)，next 節(jié)點(diǎn)也不為空扶认，則是鏈表侨拦，注意，這里將優(yōu)化鏈表重新散列（java 8 的改進(jìn)）
// Java8 之前辐宾，這里曾是并發(fā)操作會(huì)出現(xiàn)環(huán)狀鏈表的情況狱从，但是Java8 優(yōu)化了算法。此bug不再出現(xiàn)叠纹，但并發(fā)時(shí)仍然不建議HashMap
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 這里的判斷需要引出一些東西：oldCap 假如是16季研，那么二進(jìn)制為 10000，擴(kuò)容變成 100000誉察，也就是32.
// 當(dāng)舊的hash值 與運(yùn)算 10000与涡，結(jié)果是0的話，那么hash值的右起第五位肯定也是0，那么該于元素的下標(biāo)位置也就不變驼卖。
if ((e.hash & oldCap) == 0) {
// 第一次進(jìn)來(lái)時(shí)給鏈頭賦值
if (loTail == null)
loHead = e;
else
// 給鏈尾賦值
loTail.next = e;
// 重置該變量
loTail = e;
}
// 如果不是0氨肌，那么就是1，也就是說(shuō)酌畜，如果原始容量是16埠戳，那么該元素新的下標(biāo)就是：原下標(biāo) + 16（10000b）
else {
// 同上
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 理想情況下蛮寂，可將原有的鏈表拆成2組，提高查詢(xún)性能象泵。
if (loTail != null) {
// 銷(xiāo)毀實(shí)例扒腕，等待GC回收
loTail.next = null;
// 置入bucket中
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
這里樓主重新貼了上面的代碼，因?yàn)檫@段代碼比較重要召廷。還是說(shuō)一下該部分代碼的步驟寺谤。
- 首先循環(huán)老數(shù)組。下標(biāo)從0開(kāi)始糜颠，如果對(duì)應(yīng)下標(biāo)的值不是null耗帕，則判斷該值有沒(méi)有next 節(jié)點(diǎn)，也就是判斷是否是鏈表品姓。
- 如果不是鏈表衬潦，則根據(jù)新的數(shù)組長(zhǎng)度重新hash該元素膘婶。
- 如果該節(jié)點(diǎn)是樹(shù)沾歪，則調(diào)用紅黑樹(shù)的 split 方法，傳入當(dāng)前對(duì)象和新數(shù)組還有下標(biāo)渺氧，該方法會(huì)重新計(jì)算紅黑樹(shù)中的每個(gè)hash值，如果重新計(jì)算后哎媚，樹(shù)中元素的hash值不同喇伯，則重新散列到不同的下標(biāo)中。達(dá)到拆分紅黑樹(shù)的目的拨与，提高性能稻据。具體如何拆分下面再說(shuō)。
- 之后的判斷就是鏈表买喧，在Java8中捻悯，該部分代碼不是簡(jiǎn)單的將舊鏈表中的數(shù)據(jù)拷貝到新數(shù)組中的鏈表就完了，而是會(huì)對(duì)舊的鏈表進(jìn)行重新 hash淤毛，如果 hash 得到的值和之前不同今缚，則會(huì)從舊的鏈表中拆出，放到另一個(gè)下標(biāo)中去低淡，提高性能姓言，剛剛的紅黑樹(shù)也是這么做的。
這里的重新hash 不是使用的 [e.hash & (newCap - 1)] 方法蔗蹋，而是使用更加效率的方法何荚，直接 hash 老的數(shù)組容量，就沒(méi)有了減一的操作猪杭，可見(jiàn) JDK 的作者為了性能可以說(shuō)是無(wú)所不用其極了餐塘。
其實(shí)我們的注釋已經(jīng)寫(xiě)了，但是樓主還是再解釋一遍吧：
仔細(xì)閱讀下面這段話：
oldCap 假如是16皂吮，那么二進(jìn)制為 10000戒傻，擴(kuò)容變成 100000，也就是32.當(dāng)舊的hash值 與運(yùn)算 10000蜂筹，結(jié)果是0的話需纳，那么hash值的右起第五位肯定也是0，那么該于元素的下標(biāo)位置也就不變艺挪。但如果不是0是1的話候齿，說(shuō)明該hash值變化了，那么就需要對(duì)這個(gè)元素重新散列放置闺属。那么應(yīng)該放哪里呢慌盯？如果是16，那么最左邊是1的話掂器，說(shuō)明hash值變大了16亚皂，那么只需要在原有的基礎(chǔ)上加上16便好了。
這段代碼還有一個(gè)需要注意的地方：在JDK 7 中国瓮，這里的的代碼是不同的灭必，在并發(fā)情況下會(huì)鏈表會(huì)變成環(huán)狀狞谱，形成死鎖。而JDK 8 已經(jīng)修復(fù)了該問(wèn)題禁漓，但是仍然不建議使用 HashMap 并發(fā)編程跟衅。
總結(jié)
截至到這里，我們的 HashMap 的 put 方法已經(jīng)剖析完了播歼，此次可以說(shuō)收獲不辛骢巍：
我們知道了，無(wú)論我們?nèi)绾卧O(shè)置初始容量秘狞，HashMap 都會(huì)將我們改成2的冪次方叭莫，也就是說(shuō)，HashMap 的容量百分之百是 2的冪次方烁试，因?yàn)镠ashMap 太依賴(lài)他了雇初。但是，請(qǐng)注意：如果我們預(yù)計(jì)插入7條數(shù)據(jù)减响，那么我們寫(xiě)入7靖诗，HashMap 會(huì)設(shè)置為 8，雖然是2的冪次方支示，但是刊橘，請(qǐng)注意，當(dāng)我們放入第7條數(shù)據(jù)的時(shí)候悼院，就會(huì)引起擴(kuò)容，造成性能損失咒循，所以据途，知曉了原理，我們以后在設(shè)置容量的時(shí)候還是自己算一下叙甸，比如放7條數(shù)據(jù)颖医，我們還是都是設(shè)置成16，這樣就不會(huì)擴(kuò)容了裆蒸。
HashMap 的默認(rèn)加載因子是 0.75熔萧，雖然可以修改，但是出于安全考慮僚祷，除非你經(jīng)過(guò)大量測(cè)試佛致，請(qǐng)不要修改此值，HashMap 使用此值基本是平衡了性能和空間的取舍辙谜。
HashMap 擴(kuò)容的時(shí)機(jī)是俺榆，容器中的元素?cái)?shù)量 > 負(fù)載因此 * 容量，如果負(fù)載因子是0.75装哆，容量是16罐脊，那么當(dāng)容器中數(shù)量達(dá)到13 的時(shí)候就會(huì)擴(kuò)容定嗓。還有，如果某個(gè)鏈表長(zhǎng)度達(dá)到了8萍桌，并且容量小于64宵溅，則也會(huì)用擴(kuò)容代替紅黑樹(shù)。
HashMap 在 JDK 7 中并發(fā)擴(kuò)容的時(shí)候是非常危險(xiǎn)的上炎，非常容易導(dǎo)致鏈表成環(huán)狀恃逻。但 JDK 8 中已經(jīng)修改了此bug。但還是不建議使用反症。強(qiáng)烈推薦并發(fā)容器 ConcurrentHashMap辛块。
HashMap 擴(kuò)容的時(shí)候，不管是鏈表還是紅黑樹(shù)铅碍，都會(huì)對(duì)這些數(shù)據(jù)進(jìn)行重新的散列計(jì)算润绵，然后縮短他們的長(zhǎng)度，優(yōu)化性能胞谈。在進(jìn)行散列計(jì)算的時(shí)候尘盼，會(huì)進(jìn)一步優(yōu)化性能，減少減一的操作烦绳，直接使用& 運(yùn)算卿捎。可謂神來(lái)之筆径密。
總之午阵，HashMap 中的優(yōu)秀的設(shè)計(jì)思想值得我們?nèi)W(xué)習(xí)，最讓樓主震驚的就是那個(gè)將任意一個(gè)數(shù)變成了2的冪次方的數(shù)享扔，并且該數(shù)字很合理底桂，說(shuō)實(shí)話，如果讓樓主寫(xiě)惧眠，樓主是寫(xiě)不出來(lái)的籽懦。
ConcurrentHashMap（JDK 1.8） putVal 源碼分析
我們之前分析了Hash的源碼，主要是 put 方法氛魁。同時(shí)暮顺，我們知道，HashMap 在并發(fā)的時(shí)候是不安全的秀存，為什么呢捶码？因?yàn)楫?dāng)多個(gè)線程對(duì) Map 進(jìn)行擴(kuò)容會(huì)導(dǎo)致鏈表成環(huán)。不單單是這個(gè)問(wèn)題或链，當(dāng)多個(gè)線程相同一個(gè)槽中插入數(shù)據(jù)宙项，也是不安全的。而在這之后株扛，我們學(xué)習(xí)了并發(fā)編程尤筐，而并發(fā)編程中有一個(gè)重要的東西汇荐，就是JDK 自帶的并發(fā)容器，提供了線程安全的特性且比同步容器性能好出很多盆繁。一個(gè)典型的代表就是 ConcurrentHashMap掀淘，對(duì)，又是 HashMap 油昂，但是這個(gè) Map 是線程安全的革娄，那么同樣的，我們今天就看看該類(lèi)的 put 方法是如何實(shí)現(xiàn)線程安全的冕碟。
源碼加注釋分析 putVal 方法
/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
// 死循環(huán)執(zhí)行
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
// 初始化
tab = initTable();
// 獲取對(duì)應(yīng)下標(biāo)節(jié)點(diǎn)拦惋，如果是kong，直接插入
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// CAS 進(jìn)行插入
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
// 如果 hash 沖突了安寺，且 hash 值為 -1厕妖，說(shuō)明是 ForwardingNode 對(duì)象（這是一個(gè)占位符對(duì)象，保存了擴(kuò)容后的容器）
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
// 如果 hash 沖突了挑庶，且 hash 值不為 -1
else {
V oldVal = null;
// 同步 f 節(jié)點(diǎn)言秸，防止增加鏈表的時(shí)候?qū)е骆湵沓森h(huán)
synchronized (f) {
// 如果對(duì)應(yīng)的下標(biāo)位置 的節(jié)點(diǎn)沒(méi)有改變
if (tabAt(tab, i) == f) {
// 并且 f 節(jié)點(diǎn)的hash 值 不是大于0
if (fh >= 0) {
// 鏈表初始長(zhǎng)度
binCount = 1;
// 死循環(huán)，直到將值添加到鏈表尾部迎捺，并計(jì)算鏈表的長(zhǎng)度
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
// 如果 f 節(jié)點(diǎn)的 hasj 小于0 并且f 是 樹(shù)類(lèi)型
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
// 鏈表長(zhǎng)度大于等于8時(shí)举畸，將該節(jié)點(diǎn)改成紅黑樹(shù)樹(shù)
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
// 判斷是否需要擴(kuò)容
addCount(1L, binCount);
return null;
}
樓主在代碼中寫(xiě)了很多注釋?zhuān)沁€是說(shuō)一下步驟（該方法和HashMap 的高度相似，但是多了很多同步操作）凳枝。
- 校驗(yàn)key value 值抄沮，都不能是null。這點(diǎn)和 HashMap 不同岖瑰。
- 得到 key 的 hash 值叛买。
- 死循環(huán)并更新 tab 變量的值。
- 如果容器沒(méi)有初始化锭环，則初始化聪全。調(diào)用 initTable 方法泊藕。該方法通過(guò)一個(gè)變量 + CAS 來(lái)控制并發(fā)辅辩。稍后我們分析源碼。
- 根據(jù) hash 值找到數(shù)組下標(biāo)娃圆，如果對(duì)應(yīng)的位置為空玫锋，就創(chuàng)建一個(gè) Node 對(duì)象用CAS方式添加到容器。并跳出循環(huán)讼呢。
- 如果 hash 沖突撩鹿，也就是對(duì)應(yīng)的位置不為 null，則判斷該槽是否被擴(kuò)容了（-1 表示被擴(kuò)容了）悦屏，如果被擴(kuò)容了节沦，返回新的數(shù)組键思。
- 如果 hash 沖突 且 hash 值不是 -1，表示沒(méi)有被擴(kuò)容甫贯。則進(jìn)行鏈表操作或者紅黑樹(shù)操作吼鳞，注意，這里的 f 頭節(jié)點(diǎn)被鎖住了叫搁，保證了同時(shí)只有一個(gè)線程修改鏈表赔桌。防止出現(xiàn)鏈表成環(huán)。
- 和 HashMap 一樣渴逻，如果鏈表樹(shù)超過(guò)8疾党，則修改鏈表為紅黑樹(shù)。
- 將數(shù)組加1（CAS方式）惨奕，如果需要擴(kuò)容雪位，則調(diào)用 transfer 方法（非常復(fù)雜，以后再詳解）進(jìn)行移動(dòng)和重新散列墓贿，該方法中茧泪，如果是槽中只有單個(gè)節(jié)點(diǎn)，則使用CAS直接插入聋袋，如果不是队伟，則使用 synchronized 進(jìn)行同步，防止并發(fā)成環(huán)幽勒。
這里說(shuō)一說(shuō) initTable 方法：
/**
* Initializes table, using the size recorded in sizeCtl.
*/
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
// 小于0說(shuō)明被其他線程改了
if ((sc = sizeCtl) < 0)
// 自旋等待
Thread.yield(); // lost initialization race; just spin
// CAS 修改 sizeCtl 的值為-1
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if ((tab = table) == null || tab.length == 0) {
// sc 在初始化的時(shí)候用戶(hù)可能會(huì)自定義嗜侮，如果沒(méi)有自定義，則是默認(rèn)的
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
// 創(chuàng)建數(shù)組
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
// sizeCtl 計(jì)算后作為擴(kuò)容的閥值
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}
該方法為了在并發(fā)環(huán)境下的安全啥容，加入了一個(gè) sizeCtl 變量來(lái)進(jìn)行判斷锈颗，只有當(dāng)一個(gè)線程通過(guò)CAS修改該變量成功后（默認(rèn)為0，改成 -1）咪惠，該線程才能初始化數(shù)組击吱。保證了初始化數(shù)組時(shí)的安全性。
總結(jié)
ConcurrentHashMap 是并發(fā)大師 Doug Lea 的杰作遥昧，可以說(shuō)鬼斧神工覆醇，總的來(lái)說(shuō)，使用了 CAS 加 synchronized 來(lái)保證了 put 操作并發(fā)時(shí)的危險(xiǎn)（特別是鏈表）炭臭，相比 同步容器 hashTable 來(lái)說(shuō)永脓，如果容器大小是16，并發(fā)的性能是他的16倍鞋仍，注意常摧，讀的時(shí)候是沒(méi)有鎖的，完全并發(fā)，而 HashTable 在 get 方法上直接加上了 synchronized 關(guān)鍵字落午，性能差距不言而喻谎懦。
當(dāng)然绵疲，樓主這篇文章可能之寫(xiě)到了 ConcurrentHashMap 的皮毛顽聂，關(guān)于如何擴(kuò)容震糖，樓主沒(méi)有詳細(xì)介紹埂材，而樓主在閱讀源碼的收獲也很多梨水，發(fā)現(xiàn)了很多有趣的東西俗批，比如 ThreadLocalRandom 類(lèi)在 addCount 方法中的應(yīng)用吃溅，大家可以看看該類(lèi)括丁，非常的實(shí)用在跳。
注意：這篇文章僅僅是 ConcurrentHashMap 的開(kāi)頭枪萄，關(guān)于 ConcurrentHashMap 里面的精華太多，值得我們好好學(xué)習(xí)猫妙。
ConcurrentHashMap size 方法原理分析
ConcurrentHashMap 博大精深瓷翻，從他的 50 多個(gè)內(nèi)部類(lèi)就能看出來(lái)，似乎 JDK 的并發(fā)精髓都在里面了割坠。但他依然擁有體驗(yàn)良好的 API 給我們使用齐帚，程序員根本感覺(jué)不到他內(nèi)部的復(fù)雜。但彼哼，他內(nèi)部的每一個(gè)方法都復(fù)雜無(wú)比对妄，就連 size 方法，都挺復(fù)雜的敢朱。
今天就一起來(lái)看看這個(gè) size 方法剪菱。
size 方法
代碼如下：
public int size() {
long n = sumCount();
return ((n < 0L) ? 0 : (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int)n);
}
最大返回 int 最大值，但是這個(gè) Map 的長(zhǎng)度是有可能超過(guò) int 最大值的拴签，所以 JDK 8 增了 mappingCount 方法孝常。代碼如下：
public long mappingCount() {
long n = sumCount();
return (n < 0L) ? 0L : n; // ignore transient negative values
}
相比較 size 方法，mappingCount 方法的返回值是 long 類(lèi)型蚓哩。所以不必限制最大值必須是 Integer.MAX_VALUE构灸。而 JDK 推薦使用這個(gè)方法。但這個(gè)返回值依然不一定絕對(duì)準(zhǔn)確岸梨。
從這兩個(gè)方法中可以看出喜颁，sumCount 方法是核心。
sumCount 方法實(shí)現(xiàn)
代碼如下：
final long sumCount() {
CounterCell[] as = counterCells; CounterCell a;
long sum = baseCount;
if (as != null) {
for (int i = 0; i < as.length; ++i) {
if ((a = as[i]) != null)
sum += a.value;
}
}
return sum;
}
上面的方法邏輯：當(dāng) counterCells 不是 null盛嘿，就遍歷元素洛巢，并和 baseCount 累加括袒。
兩個(gè)屬性 ： baseCount 和 counterCells次兆。
先看 baseCount。
/**
* Base counter value, used mainly when there is no contention,
* but also as a fallback during table initialization
* races. Updated via CAS.
* 當(dāng)沒(méi)有爭(zhēng)用時(shí)锹锰，使用這個(gè)變量計(jì)數(shù)芥炭。
*/
private transient volatile long baseCount;
一個(gè) volatile 的變量漓库，在 addCount 方法中會(huì)使用它，而 addCount 方法在 put 結(jié)束后會(huì)調(diào)用园蝠。在 addCount 方法中渺蒿，會(huì)對(duì)這個(gè)變量做 CAS 加法。
但是如果并發(fā)導(dǎo)致 CAS 失敗了彪薛，怎么辦呢茂装？使用 counterCells。
如果上面 CAS 失敗了善延，在 fullAddCount 方法中少态，會(huì)繼續(xù)死循環(huán)操作，直到成功易遣。
而這個(gè) CounterCell 類(lèi)又是上面鬼呢彼妻？
// 一種用于分配計(jì)數(shù)的填充單元。改編自LongAdder和Striped64豆茫。請(qǐng)查看他們的內(nèi)部文檔進(jìn)行解釋侨歉。
@sun.misc.Contended
static final class CounterCell {
volatile long value;
CounterCell(long x) { value = x; }
}
使用了 @sun.misc.Contended 標(biāo)記的類(lèi)，內(nèi)部一個(gè) volatile 變量揩魂。注釋說(shuō)幽邓，改編自LongAdder和Striped64,關(guān)于這兩個(gè)類(lèi)，請(qǐng)看 Java8 Striped64 和 LongAdder火脉。
而關(guān)于這個(gè)注解颊艳，有必要解釋一下。這個(gè)注解標(biāo)識(shí)著這個(gè)類(lèi)防止需要防止 "偽共享".
說(shuō)說(shuō)偽共享忘分。引用 一下別人的說(shuō)法：
避免偽共享(false sharing)棋枕。先引用個(gè)偽共享的解釋?zhuān)壕彺嫦到y(tǒng)中是以緩存行（cache line）為單位存儲(chǔ)的。緩存行是2的整數(shù)冪個(gè)連續(xù)字節(jié)妒峦，一般為32-256個(gè)字節(jié)重斑。最常見(jiàn)的緩存行大小是64個(gè)字節(jié)。當(dāng)多線程修改互相獨(dú)立的變量時(shí)肯骇，
如果這些變量共享同一個(gè)緩存行窥浪，就會(huì)無(wú)意中影響彼此的性能，這就是偽共享笛丙。
所以偽共享對(duì)性能危害極大漾脂。
JDK 8 版本之前沒(méi)有這個(gè)注解，Doug Lea 使用拼接來(lái)解決這個(gè)問(wèn)題胚鸯，把緩存行加滿(mǎn)骨稿，讓緩存之間的修改互不影響。
在我的機(jī)器上測(cè)試，加和不加這個(gè)注解的性能差距達(dá)到了 5 倍坦冠。
總結(jié)
好了形耗，關(guān)于 Size 方法就簡(jiǎn)單介紹到這里≌藁耄總結(jié)一下：
JDK 8 推薦使用mappingCount 方法激涤，因?yàn)檫@個(gè)方法的返回值是 long 類(lèi)型，不會(huì)因?yàn)?size 方法是 int 類(lèi)型限制最大值（size 方法是接口定義的判呕，不能修改）倦踢。
在沒(méi)有并發(fā)的情況下，使用一個(gè) baseCount volatile 變量就足夠了侠草，當(dāng)并發(fā)的時(shí)候硼一，CAS 修改 baseCount 失敗后，就會(huì)使用 CounterCell 類(lèi)了梦抢，會(huì)創(chuàng)建一個(gè)這個(gè)對(duì)象般贼，通常對(duì)象的 volatile value 屬性是 1。在計(jì)算 size 的時(shí)候奥吩，會(huì)將 baseCount 和 CounterCell 數(shù)組中的元素的 value 累加哼蛆，得到總的大小，但這個(gè)數(shù)字仍舊可能是不準(zhǔn)確的霞赫。
還有一個(gè)需要注意的地方就是腮介，這個(gè) CounterCell 類(lèi)使用了 @sun.misc.Contended 注解標(biāo)識(shí)，這個(gè)注解是防止偽共享的端衰。是 1.8 新增的叠洗。使用時(shí)，需要加上 -XX:-RestrictContended 參數(shù)旅东。
ConcurrentHashMap#helpTransfer() 分析
ConcurrentHashMap 鬼斧神工灭抑，并發(fā)添加元素時(shí)，如果 map 正在擴(kuò)容抵代，其他線程甚至于還會(huì)幫助擴(kuò)容腾节，也就是多線程擴(kuò)容。就這一點(diǎn)荤牍，就可以寫(xiě)一篇文章好好講講案腺。今天一起來(lái)看看。
源碼分析
為什么幫助擴(kuò)容康吵？
在 putVal 方法中劈榨，如果發(fā)現(xiàn)線程當(dāng)前 hash 沖突了，也就是當(dāng)前 hash 值對(duì)應(yīng)的槽位有值了晦嵌，且如果這個(gè)值是 -1 （MOVED）同辣，說(shuō)明 Map 正在擴(kuò)容拷姿。那么就幫助 Map 進(jìn)行擴(kuò)容。以加快速度邑闺。
具體代碼如下：
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
} // 如果對(duì)應(yīng)槽位不為空，且他的 hash 值是 -1棕兼，說(shuō)明正在擴(kuò)容陡舅，那么就幫助其擴(kuò)容。以加快速度
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
傳入的參數(shù)是：成員變量 table 和 對(duì)應(yīng)槽位的 f 變量伴挚。
怎么驗(yàn)證 hash 值是 MOVED 就是正在擴(kuò)容呢?
在 Cmap（ConcurrentHashMap 簡(jiǎn)稱(chēng)） 中靶衍，定義了一堆常量，其中：
static final int MOVED = -1; // hash for forwarding nodes
hash for forwarding nodes茎芋，說(shuō)明這個(gè)為了移動(dòng)節(jié)點(diǎn)而準(zhǔn)備的常量颅眶。
在 Node 的子類(lèi) ForwardingNode 的構(gòu)造方法中，可以看到這個(gè)變量作為 hash 值進(jìn)行了初始化田弥。
ForwardingNode(Node<K,V>[] tab) {
super(MOVED, null, null, null);
this.nextTable = tab;
}
而這個(gè)構(gòu)造方法只在一個(gè)地方調(diào)用了涛酗，即 transfer（擴(kuò)容） 方法。
點(diǎn)到為止偷厦。
關(guān)于擴(kuò)容后面再開(kāi)一篇商叹。
好了，如何幫助擴(kuò)容呢只泼？那要看看 helpTransfer 方法的實(shí)現(xiàn)剖笙。
/**
* Helps transfer if a resize is in progress.
*/
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
Node<K,V>[] nextTab; int sc;
// 如果 table 不是空 且 node 節(jié)點(diǎn)是轉(zhuǎn)移類(lèi)型，數(shù)據(jù)檢驗(yàn)
// 且 node 節(jié)點(diǎn)的 nextTable（新 table） 不是空请唱，同樣也是數(shù)據(jù)校驗(yàn)
// 嘗試幫助擴(kuò)容
if (tab != null && (f instanceof ForwardingNode) &&
(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
// 根據(jù) length 得到一個(gè)標(biāo)識(shí)符號(hào)
int rs = resizeStamp(tab.length);
// 如果 nextTab 沒(méi)有被并發(fā)修改 且 tab 也沒(méi)有被并發(fā)修改
// 且 sizeCtl < 0 （說(shuō)明還在擴(kuò)容）
while (nextTab == nextTable && table == tab &&
(sc = sizeCtl) < 0) {
// 如果 sizeCtl 無(wú)符號(hào)右移 16 不等于 rs （ sc前 16 位如果不等于標(biāo)識(shí)符弥咪，則標(biāo)識(shí)符變化了）
// 或者 sizeCtl == rs + 1 （擴(kuò)容結(jié)束了，不再有線程進(jìn)行擴(kuò)容）（默認(rèn)第一個(gè)線程設(shè)置 sc ==rs 左移 16 位 + 2十绑，當(dāng)?shù)谝粋€(gè)線程結(jié)束擴(kuò)容了聚至，就會(huì)將 sc 減一。這個(gè)時(shí)候本橙，sc 就等于 rs + 1）
// 或者 sizeCtl == rs + 65535 （如果達(dá)到最大幫助線程的數(shù)量晚岭，即 65535）
// 或者轉(zhuǎn)移下標(biāo)正在調(diào)整 （擴(kuò)容結(jié)束）
// 結(jié)束循環(huán)，返回 table
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || transferIndex <= 0)
break;
// 如果以上都不是, 將 sizeCtl + 1, （表示增加了一個(gè)線程幫助其擴(kuò)容）
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
// 進(jìn)行轉(zhuǎn)移
transfer(tab, nextTab);
// 結(jié)束循環(huán)
break;
}
}
return nextTab;
}
return table;
}
關(guān)于 sizeCtl 變量：
- -1 :代表table正在初始化,其他線程應(yīng)該交出CPU時(shí)間片
- -N: 表示正有N-1個(gè)線程執(zhí)行擴(kuò)容操作（高 16 位是 length 生成的標(biāo)識(shí)符勋功，低 16 位是擴(kuò)容的線程數(shù)）
- 大于 0: 如果table已經(jīng)初始化,代表table容量,默認(rèn)為table大小的0.75,如果還未初始化,代表需要初始化的大小
代碼步驟：
- 判 tab 空坦报，判斷是否是轉(zhuǎn)移節(jié)點(diǎn)。判斷 nextTable 是否更改了狂鞋。
- 更加 length 得到標(biāo)識(shí)符片择。
- 判斷是否并發(fā)修改了，判斷是否還在擴(kuò)容骚揍。
- 如果還在擴(kuò)容字管，判斷標(biāo)識(shí)符是否變化啰挪，判斷擴(kuò)容是否結(jié)束，判斷是否達(dá)到最大線程數(shù)嘲叔，判斷擴(kuò)容轉(zhuǎn)移下標(biāo)是否在調(diào)整（擴(kuò)容結(jié)束）亡呵，如果滿(mǎn)足任意條件，結(jié)束循環(huán)硫戈。
- 如果不滿(mǎn)足锰什，并發(fā)轉(zhuǎn)移。
這里有一個(gè)花費(fèi)了很長(zhǎng)時(shí)間糾結(jié)的地方：
sc == rs + 1
這個(gè)判斷可以在 addCount 方法中找到答案：默認(rèn)第一個(gè)線程設(shè)置 sc ==rs 左移 16 位 + 2丁逝，當(dāng)?shù)谝粋€(gè)線程結(jié)束擴(kuò)容了汁胆，就會(huì)將 sc 減一。這個(gè)時(shí)候霜幼，sc 就等于 rs + 1嫩码。
如果 sizeCtl == 標(biāo)識(shí)符 + 1 ，說(shuō)明庫(kù)容結(jié)束了罪既，沒(méi)有必要再擴(kuò)容了铸题。
總結(jié)一下：
當(dāng) Cmap put 元素的時(shí)候，如果發(fā)現(xiàn)這個(gè)節(jié)點(diǎn)的元素類(lèi)型是 forward 的話琢感，就幫助正在擴(kuò)容的線程一起擴(kuò)容回挽，提高速度。其中猩谊， sizeCtl 是關(guān)鍵千劈，該變量高 16 位保存 length 生成的標(biāo)識(shí)符，低 16 位保存并發(fā)擴(kuò)容的線程數(shù)牌捷，通過(guò)這連個(gè)數(shù)字墙牌，可以判斷出，是否結(jié)束擴(kuò)容了暗甥。
如下圖：
ConcurrentHashMap#transfer() 擴(kuò)容逐行分析
ConcurrentHashMap 是并發(fā)中的重中之重喜滨，也是最常用的數(shù)據(jù)結(jié)果，之前的文章中撤防，我們介紹了 putVal 方法虽风。并發(fā)編程之 ConcurrentHashMap（JDK 1.8） putVal 源碼分析。其中分析了 initTable 方法和 putVal 方法寄月，但也留下了一句話：
這篇文章僅僅是 ConcurrentHashMap 的開(kāi)頭辜膝，關(guān)于 ConcurrentHashMap 里面的精華太多，值得我們好好學(xué)習(xí)漾肮。
說(shuō)道精華厂抖，他的擴(kuò)容方法絕對(duì)是精華，要知道克懊，ConcurrentHashMap 擴(kuò)容是高度并發(fā)的忱辅。
今天來(lái)逐行分析源碼七蜘。
先說(shuō)結(jié)論
首先說(shuō)結(jié)論。源碼加注釋我會(huì)放在后面墙懂。該方法的執(zhí)行邏輯如下：
通過(guò)計(jì)算 CPU 核心數(shù)和 Map 數(shù)組的長(zhǎng)度得到每個(gè)線程（CPU）要幫助處理多少個(gè)桶橡卤，并且這里每個(gè)線程處理都是平均的。默認(rèn)每個(gè)線程處理 16 個(gè)桶损搬。因此碧库，如果長(zhǎng)度是 16 的時(shí)候，擴(kuò)容的時(shí)候只會(huì)有一個(gè)線程擴(kuò)容场躯。
初始化臨時(shí)變量 nextTable谈为。將其在原有基礎(chǔ)上擴(kuò)容兩倍旅挤。
-
死循環(huán)開(kāi)始轉(zhuǎn)移踢关。多線程并發(fā)轉(zhuǎn)移就是在這個(gè)死循環(huán)中，根據(jù)一個(gè) finishing 變量來(lái)判斷粘茄，該變量為 true 表示擴(kuò)容結(jié)束签舞，否則繼續(xù)擴(kuò)容。
- 進(jìn)入一個(gè) while 循環(huán)柒瓣，分配數(shù)組中一個(gè)桶的區(qū)間給線程儒搭，默認(rèn)是 16. 從大到小進(jìn)行分配。當(dāng)拿到分配值后芙贫，進(jìn)行 i-- 遞減搂鲫。這個(gè) i 就是數(shù)組下標(biāo)。（其中有一個(gè) bound 參數(shù)磺平，這個(gè)參數(shù)指的是該線程此次可以處理的區(qū)間的最小下標(biāo)魂仍，超過(guò)這個(gè)下標(biāo)，就需要重新領(lǐng)取區(qū)間或者結(jié)束擴(kuò)容拣挪，還有一個(gè) advance 參數(shù)擦酌，該參數(shù)指的是是否繼續(xù)遞減轉(zhuǎn)移下一個(gè)桶，如果為 true赶诊，表示可以繼續(xù)向后推進(jìn)笼平，反之，說(shuō)明還沒(méi)有處理好當(dāng)前桶舔痪，不能推進(jìn))
- 出 while 循環(huán)出吹，進(jìn) if 判斷，判斷擴(kuò)容是否結(jié)束辙喂，如果擴(kuò)容結(jié)束捶牢，清空臨死變量鸠珠，更新 table 變量，更新庫(kù)容閾值秋麸。如果沒(méi)完成渐排，但已經(jīng)無(wú)法領(lǐng)取區(qū)間（沒(méi)了），該線程退出該方法灸蟆，并將 sizeCtl 減一驯耻，表示擴(kuò)容的線程少一個(gè)了。如果減完這個(gè)數(shù)以后炒考，sizeCtl 回歸了初始狀態(tài)可缚，表示沒(méi)有線程再擴(kuò)容了，該方法所有的線程擴(kuò)容結(jié)束了斋枢。（這里主要是判斷擴(kuò)容任務(wù)是否結(jié)束帘靡，如果結(jié)束了就讓線程退出該方法芭梯，并更新相關(guān)變量）双霍。然后檢查所有的桶，防止遺漏夹界。
- 如果沒(méi)有完成任務(wù)戈次，且 i 對(duì)應(yīng)的槽位是空轩勘，嘗試 CAS 插入占位符，讓 putVal 方法的線程感知怯邪。
- 如果 i 對(duì)應(yīng)的槽位不是空绊寻，且有了占位符，那么該線程跳過(guò)這個(gè)槽位悬秉，處理下一個(gè)槽位澄步。
- 如果以上都是不是，說(shuō)明這個(gè)槽位有一個(gè)實(shí)際的值搂捧。開(kāi)始同步處理這個(gè)桶驮俗。
- 到這里，都還沒(méi)有對(duì)桶內(nèi)數(shù)據(jù)進(jìn)行轉(zhuǎn)移允跑，只是計(jì)算了下標(biāo)和處理區(qū)間王凑，然后一些完成狀態(tài)判斷。同時(shí)聋丝，如果對(duì)應(yīng)下標(biāo)內(nèi)沒(méi)有數(shù)據(jù)或已經(jīng)被占位了索烹，就跳過(guò)了。
-
處理每個(gè)桶的行為都是同步的弱睦。防止 putVal 的時(shí)候向鏈表插入數(shù)據(jù)百姓。
- 如果這個(gè)桶是鏈表，那么就將這個(gè)鏈表根據(jù) length 取于拆成兩份况木，取于結(jié)果是 0 的放在新表的低位垒拢，取于結(jié)果是 1 放在新表的高位旬迹。
- 如果這個(gè)桶是紅黑數(shù)，那么也拆成 2 份求类，方式和鏈表的方式一樣奔垦，然后，判斷拆分過(guò)的樹(shù)的節(jié)點(diǎn)數(shù)量尸疆，如果數(shù)量小于等于 6椿猎，改造成鏈表。反之寿弱，繼續(xù)使用紅黑樹(shù)結(jié)構(gòu)犯眠。
- 到這里，就完成了一個(gè)桶從舊表轉(zhuǎn)移到新表的過(guò)程症革。
好筐咧，以上，就是 transfer 方法的總體邏輯地沮。還是挺復(fù)雜的嗜浮。再進(jìn)行精簡(jiǎn)羡亩，分成 3 步驟：
- 計(jì)算每個(gè)線程可以處理的桶區(qū)間摩疑。默認(rèn) 16.
- 初始化臨時(shí)變量 nextTable，擴(kuò)容 2 倍畏铆。
- 死循環(huán)雷袋，計(jì)算下標(biāo)。完成總體判斷辞居。
- 如果桶內(nèi)有數(shù)據(jù)楷怒，同步轉(zhuǎn)移數(shù)據(jù)。通常會(huì)像鏈表拆成 2 份瓦灶。
大體就是上的的 3 個(gè)步驟鸠删。
再來(lái)看看源碼和注釋。
再看源碼分析
源碼加注釋?zhuān)?/p>
/**
* Moves and/or copies the nodes in each bin to new table. See
* above for explanation.
*
* transferIndex 表示轉(zhuǎn)移時(shí)的下標(biāo)贼陶，初始為擴(kuò)容前的 length刃泡。
*
* 我們假設(shè)長(zhǎng)度是 32
*/
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
// 將 length / 8 然后除以 CPU核心數(shù)。如果得到的結(jié)果小于 16碉怔，那么就使用 16烘贴。
// 這里的目的是讓每個(gè) CPU 處理的桶一樣多，避免出現(xiàn)轉(zhuǎn)移任務(wù)不均勻的現(xiàn)象撮胧，如果桶較少的話桨踪，默認(rèn)一個(gè) CPU（一個(gè)線程）處理 16 個(gè)桶
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range 細(xì)分范圍 stridea：TODO
// 新的 table 尚未初始化
if (nextTab == null) { // initiating
try {
// 擴(kuò)容 2 倍
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
// 更新
nextTab = nt;
} catch (Throwable ex) { // try to cope with OOME
// 擴(kuò)容失敗， sizeCtl 使用 int 最大值芹啥。
sizeCtl = Integer.MAX_VALUE;
return;// 結(jié)束
}
// 更新成員變量
nextTable = nextTab;
// 更新轉(zhuǎn)移下標(biāo)锻离，就是 老的 tab 的 length
transferIndex = n;
}
// 新 tab 的 length
int nextn = nextTab.length;
// 創(chuàng)建一個(gè) fwd 節(jié)點(diǎn)铺峭，用于占位。當(dāng)別的線程發(fā)現(xiàn)這個(gè)槽位中是 fwd 類(lèi)型的節(jié)點(diǎn)汽纠，則跳過(guò)這個(gè)節(jié)點(diǎn)逛薇。
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
// 首次推進(jìn)為 true，如果等于 true疏虫，說(shuō)明需要再次推進(jìn)一個(gè)下標(biāo)（i--）永罚，反之，如果是 false卧秘，那么就不能推進(jìn)下標(biāo)呢袱，需要將當(dāng)前的下標(biāo)處理完畢才能繼續(xù)推進(jìn)
boolean advance = true;
// 完成狀態(tài)，如果是 true翅敌，就結(jié)束此方法羞福。
boolean finishing = false; // to ensure sweep before committing nextTab
// 死循環(huán),i 表示下標(biāo)，bound 表示當(dāng)前線程可以處理的當(dāng)前桶區(qū)間最小下標(biāo)
for (int i = 0, bound = 0;;) {
Node<K,V> f; int fh;
// 如果當(dāng)前線程可以向后推進(jìn)蚯涮；這個(gè)循環(huán)就是控制 i 遞減治专。同時(shí)，每個(gè)線程都會(huì)進(jìn)入這里取得自己需要轉(zhuǎn)移的桶的區(qū)間
while (advance) {
int nextIndex, nextBound;
// 對(duì) i 減一遭顶，判斷是否大于等于 bound （正常情況下张峰，如果大于 bound 不成立，說(shuō)明該線程上次領(lǐng)取的任務(wù)已經(jīng)完成了棒旗。那么喘批，需要在下面繼續(xù)領(lǐng)取任務(wù)）
// 如果對(duì) i 減一大于等于 bound（還需要繼續(xù)做任務(wù)），或者完成了铣揉，修改推進(jìn)狀態(tài)為 false饶深，不能推進(jìn)了。任務(wù)成功后修改推進(jìn)狀態(tài)為 true逛拱。
// 通常敌厘，第一次進(jìn)入循環(huán)，i-- 這個(gè)判斷會(huì)無(wú)法通過(guò)朽合，從而走下面的 nextIndex 賦值操作（獲取最新的轉(zhuǎn)移下標(biāo)）俱两。其余情況都是：如果可以推進(jìn)，將 i 減一旁舰，然后修改成不可推進(jìn)锋华。如果 i 對(duì)應(yīng)的桶處理成功了，改成可以推進(jìn)箭窜。
if (--i >= bound || finishing)
advance = false;// 這里設(shè)置 false毯焕，是為了防止在沒(méi)有成功處理一個(gè)桶的情況下卻進(jìn)行了推進(jìn)
// 這里的目的是：1. 當(dāng)一個(gè)線程進(jìn)入時(shí)，會(huì)選取最新的轉(zhuǎn)移下標(biāo)。2. 當(dāng)一個(gè)線程處理完自己的區(qū)間時(shí)纳猫，如果還有剩余區(qū)間的沒(méi)有別的線程處理婆咸。再次獲取區(qū)間。
else if ((nextIndex = transferIndex) <= 0) {
// 如果小于等于0芜辕，說(shuō)明沒(méi)有區(qū)間了 尚骄，i 改成 -1，推進(jìn)狀態(tài)變成 false侵续，不再推進(jìn)倔丈，表示，擴(kuò)容結(jié)束了状蜗，當(dāng)前線程可以退出了
// 這個(gè) -1 會(huì)在下面的 if 塊里判斷需五，從而進(jìn)入完成狀態(tài)判斷
i = -1;
advance = false;// 這里設(shè)置 false，是為了防止在沒(méi)有成功處理一個(gè)桶的情況下卻進(jìn)行了推進(jìn)
}// CAS 修改 transferIndex轧坎，即 length - 區(qū)間值宏邮，留下剩余的區(qū)間值供后面的線程使用
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
bound = nextBound;// 這個(gè)值就是當(dāng)前線程可以處理的最小當(dāng)前區(qū)間最小下標(biāo)
i = nextIndex - 1; // 初次對(duì)i 賦值，這個(gè)就是當(dāng)前線程可以處理的當(dāng)前區(qū)間的最大下標(biāo)
advance = false; // 這里設(shè)置 false缸血，是為了防止在沒(méi)有成功處理一個(gè)桶的情況下卻進(jìn)行了推進(jìn)蜜氨，這樣對(duì)導(dǎo)致漏掉某個(gè)桶。下面的 if (tabAt(tab, i) == f) 判斷會(huì)出現(xiàn)這樣的情況捎泻。
}
}// 如果 i 小于0 （不在 tab 下標(biāo)內(nèi)飒炎，按照上面的判斷，領(lǐng)取最后一段區(qū)間的線程擴(kuò)容結(jié)束）
// 如果 i >= tab.length(不知道為什么這么判斷)
// 如果 i + tab.length >= nextTable.length （不知道為什么這么判斷）
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
if (finishing) { // 如果完成了擴(kuò)容
nextTable = null;// 刪除成員變量
table = nextTab;// 更新 table
sizeCtl = (n << 1) - (n >>> 1); // 更新閾值
return;// 結(jié)束方法族扰。
}// 如果沒(méi)完成
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {// 嘗試將 sc -1. 表示這個(gè)線程結(jié)束幫助擴(kuò)容了厌丑，將 sc 的低 16 位減一定欧。
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)// 如果 sc - 2 不等于標(biāo)識(shí)符左移 16 位渔呵。如果他們相等了，說(shuō)明沒(méi)有線程在幫助他們擴(kuò)容了砍鸠。也就是說(shuō)扩氢，擴(kuò)容結(jié)束了。
return;// 不相等爷辱，說(shuō)明沒(méi)結(jié)束录豺，當(dāng)前線程結(jié)束方法。
finishing = advance = true;// 如果相等饭弓，擴(kuò)容結(jié)束了双饥，更新 finising 變量
i = n; // 再次循環(huán)檢查一下整張表
}
}
else if ((f = tabAt(tab, i)) == null) // 獲取老 tab i 下標(biāo)位置的變量，如果是 null弟断，就使用 fwd 占位咏花。
advance = casTabAt(tab, i, null, fwd);// 如果成功寫(xiě)入 fwd 占位，再次推進(jìn)一個(gè)下標(biāo)
else if ((fh = f.hash) == MOVED)// 如果不是 null 且 hash 值是 MOVED。
advance = true; // already processed // 說(shuō)明別的線程已經(jīng)處理過(guò)了昏翰，再次推進(jìn)一個(gè)下標(biāo)
else {// 到這里苍匆，說(shuō)明這個(gè)位置有實(shí)際值了，且不是占位符棚菊。對(duì)這個(gè)節(jié)點(diǎn)上鎖浸踩。為什么上鎖，防止 putVal 的時(shí)候向鏈表插入數(shù)據(jù)
synchronized (f) {
// 判斷 i 下標(biāo)處的桶節(jié)點(diǎn)是否和 f 相同
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn;// low, height 高位桶统求，低位桶
// 如果 f 的 hash 值大于 0 检碗。TreeBin 的 hash 是 -2
if (fh >= 0) {
// 對(duì)老長(zhǎng)度進(jìn)行與運(yùn)算（第一個(gè)操作數(shù)的的第n位于第二個(gè)操作數(shù)的第n位如果都是1，那么結(jié)果的第n為也為1码邻，否則為0）
// 由于 Map 的長(zhǎng)度都是 2 的次方（000001000 這類(lèi)的數(shù)字）后裸，那么取于 length 只有 2 種結(jié)果，一種是 0冒滩，一種是1
// 如果是結(jié)果是0 微驶，Doug Lea 將其放在低位，反之放在高位开睡，目的是將鏈表重新 hash因苹，放到對(duì)應(yīng)的位置上，讓新的取于算法能夠擊中他篇恒。
int runBit = fh & n;
Node<K,V> lastRun = f; // 尾節(jié)點(diǎn)扶檐，且和頭節(jié)點(diǎn)的 hash 值取于不相等
// 遍歷這個(gè)桶
for (Node<K,V> p = f.next; p != null; p = p.next) {
// 取于桶中每個(gè)節(jié)點(diǎn)的 hash 值
int b = p.hash & n;
// 如果節(jié)點(diǎn)的 hash 值和首節(jié)點(diǎn)的 hash 值取于結(jié)果不同
if (b != runBit) {
runBit = b; // 更新 runBit，用于下面判斷 lastRun 該賦值給 ln 還是 hn胁艰。
lastRun = p; // 這個(gè) lastRun 保證后面的節(jié)點(diǎn)與自己的取于值相同款筑，避免后面沒(méi)有必要的循環(huán)
}
}
if (runBit == 0) {// 如果最后更新的 runBit 是 0 ，設(shè)置低位節(jié)點(diǎn)
ln = lastRun;
hn = null;
}
else {
hn = lastRun; // 如果最后更新的 runBit 是 1腾么， 設(shè)置高位節(jié)點(diǎn)
ln = null;
}// 再次循環(huán)奈梳，生成兩個(gè)鏈表，lastRun 作為停止條件解虱，這樣就是避免無(wú)謂的循環(huán)（lastRun 后面都是相同的取于結(jié)果）
for (Node<K,V> p = f; p != lastRun; p = p.next) {
int ph = p.hash; K pk = p.key; V pv = p.val;
// 如果與運(yùn)算結(jié)果是 0攘须，那么就還在低位
if ((ph & n) == 0) // 如果是0 ，那么創(chuàng)建低位節(jié)點(diǎn)
ln = new Node<K,V>(ph, pk, pv, ln);
else // 1 則創(chuàng)建高位
hn = new Node<K,V>(ph, pk, pv, hn);
}
// 其實(shí)這里類(lèi)似 hashMap
// 設(shè)置低位鏈表放在新鏈表的 i
setTabAt(nextTab, i, ln);
// 設(shè)置高位鏈表殴泰，在原有長(zhǎng)度上加 n
setTabAt(nextTab, i + n, hn);
// 將舊的鏈表設(shè)置成占位符
setTabAt(tab, i, fwd);
// 繼續(xù)向后推進(jìn)
advance = true;
}// 如果是紅黑樹(shù)
else if (f instanceof TreeBin) {
TreeBin<K,V> t = (TreeBin<K,V>)f;
TreeNode<K,V> lo = null, loTail = null;
TreeNode<K,V> hi = null, hiTail = null;
int lc = 0, hc = 0;
// 遍歷
for (Node<K,V> e = t.first; e != null; e = e.next) {
int h = e.hash;
TreeNode<K,V> p = new TreeNode<K,V>
(h, e.key, e.val, null, null);
// 和鏈表相同的判斷于宙，與運(yùn)算 == 0 的放在低位
if ((h & n) == 0) {
if ((p.prev = loTail) == null)
lo = p;
else
loTail.next = p;
loTail = p;
++lc;
} // 不是 0 的放在高位
else {
if ((p.prev = hiTail) == null)
hi = p;
else
hiTail.next = p;
hiTail = p;
++hc;
}
}
// 如果樹(shù)的節(jié)點(diǎn)數(shù)小于等于 6，那么轉(zhuǎn)成鏈表悍汛，反之捞魁，創(chuàng)建一個(gè)新的樹(shù)
ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
(hc != 0) ? new TreeBin<K,V>(lo) : t;
hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
(lc != 0) ? new TreeBin<K,V>(hi) : t;
// 低位樹(shù)
setTabAt(nextTab, i, ln);
// 高位數(shù)
setTabAt(nextTab, i + n, hn);
// 舊的設(shè)置成占位符
setTabAt(tab, i, fwd);
// 繼續(xù)向后推進(jìn)
advance = true;
}
}
}
}
}
}
代碼加注釋比較長(zhǎng)，有興趣可以逐行對(duì)照离咐，有 2 個(gè)判斷樓主看不懂為什么這么判斷谱俭，知道的同學(xué)可以提醒一下。
然后，說(shuō)說(shuō)精華的部分旺上。
- Cmap 支持并發(fā)擴(kuò)容瓶蚂，實(shí)現(xiàn)方式是，將表拆分宣吱，讓每個(gè)線程處理自己的區(qū)間窃这。如下圖：
假設(shè)總長(zhǎng)度是 64 ，每個(gè)線程可以分到 16 個(gè)桶征候，各自處理杭攻，不會(huì)互相影響。
-
而每個(gè)線程在處理自己桶中的數(shù)據(jù)的時(shí)候疤坝，是下圖這樣的：
擴(kuò)容前的狀態(tài)兆解。
當(dāng)對(duì) 4 號(hào)桶或者 10 號(hào)桶進(jìn)行轉(zhuǎn)移的時(shí)候，會(huì)將鏈表拆成兩份跑揉，規(guī)則是根據(jù)節(jié)點(diǎn)的 hash 值取于 length锅睛，如果結(jié)果是 0，放在低位历谍，否則放在高位现拒。
因此，10 號(hào)桶的數(shù)據(jù)望侈，黑色節(jié)點(diǎn)會(huì)放在新表的 10 號(hào)位置印蔬，白色節(jié)點(diǎn)會(huì)放在新桶的 26 號(hào)位置。
下圖是循環(huán)處理桶中數(shù)據(jù)的邏輯：
處理完之后脱衙，新桶的數(shù)據(jù)是這樣的：
總結(jié)
transfer 方法可以說(shuō)很牛逼侥猬，很精華，內(nèi)部多線程擴(kuò)容性能很高捐韩，
通過(guò)給每個(gè)線程分配桶區(qū)間退唠，避免線程間的爭(zhēng)用，通過(guò)為每個(gè)桶節(jié)點(diǎn)加鎖奥帘，避免 putVal 方法導(dǎo)致數(shù)據(jù)不一致铜邮。同時(shí)，在擴(kuò)容的時(shí)候寨蹋，也會(huì)將鏈表拆成兩份，這點(diǎn)和 HashMap 的 resize 方法類(lèi)似扔茅。
而如果有新的線程想 put 數(shù)據(jù)時(shí)已旧，也會(huì)幫助其擴(kuò)容。鬼斧神工召娜，令人贊嘆运褪。
ConcurrentHashMap#addCount() 分析
ConcurrentHashMap 精華代碼很多，前面分析了 helpTransfer 和 transfer 和 putVal 方法，今天來(lái)分析一下 addCount 方法秸讹，該方法會(huì)在 putVal 方法中調(diào)用檀咙。
該方法可以配合 size 方法一起查看，關(guān)于該方法璃诀，樓主也寫(xiě)了一篇文章分析過(guò)：并發(fā)編程 —— ConcurrentHashMap size 方法原理分析
具體代碼如下：
addCount(1L, binCount);
return null;
當(dāng)插入結(jié)束的時(shí)候弧可，會(huì)調(diào)用該方法，并傳入一個(gè) 1 和 binCount 參數(shù)劣欢。從方法名字上棕诵，該方法應(yīng)該是對(duì)哈希表的元素進(jìn)行計(jì)數(shù)的。
一起來(lái)看看 addCount 是如何操作的凿将。
源碼分析
源碼加注釋?zhuān)?/p>
// 從 putVal 傳入的參數(shù)是 1校套， binCount，binCount 默認(rèn)是0牧抵，只有 hash 沖突了才會(huì)大于 1.且他的大小是鏈表的長(zhǎng)度（如果不是紅黑數(shù)結(jié)構(gòu)的話）笛匙。
private final void addCount(long x, int check) {
CounterCell[] as; long b, s;
// 如果計(jì)數(shù)盒子不是空 或者
// 如果修改 baseCount 失敗
if ((as = counterCells) != null ||
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
CounterCell a; long v; int m;
boolean uncontended = true;
// 如果計(jì)數(shù)盒子是空（尚未出現(xiàn)并發(fā)）
// 如果隨機(jī)取余一個(gè)數(shù)組位置為空 或者
// 修改這個(gè)槽位的變量失敗（出現(xiàn)并發(fā)了）
// 執(zhí)行 fullAddCount 方法犀变。并結(jié)束
if (as == null || (m = as.length - 1) < 0 ||
(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
!(uncontended =
U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
fullAddCount(x, uncontended);
return;
}
if (check <= 1)
return;
s = sumCount();
}
// 如果需要檢查,檢查是否需要擴(kuò)容膳算，在 putVal 方法調(diào)用時(shí)，默認(rèn)就是要檢查的弛作。
if (check >= 0) {
Node<K,V>[] tab, nt; int n, sc;
// 如果map.size() 大于 sizeCtl（達(dá)到擴(kuò)容閾值需要擴(kuò)容） 且
// table 不是空涕蜂；且 table 的長(zhǎng)度小于 1 << 30。（可以擴(kuò)容）
while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
// 根據(jù) length 得到一個(gè)標(biāo)識(shí)
int rs = resizeStamp(n);
// 如果正在擴(kuò)容
if (sc < 0) {
// 如果 sc 的低 16 位不等于 標(biāo)識(shí)符（校驗(yàn)異常 sizeCtl 變化了）
// 如果 sc == 標(biāo)識(shí)符 + 1 （擴(kuò)容結(jié)束了映琳，不再有線程進(jìn)行擴(kuò)容）（默認(rèn)第一個(gè)線程設(shè)置 sc ==rs 左移 16 位 + 2机隙，當(dāng)?shù)谝粋€(gè)線程結(jié)束擴(kuò)容了，就會(huì)將 sc 減一萨西。這個(gè)時(shí)候有鹿，sc 就等于 rs + 1）
// 如果 sc == 標(biāo)識(shí)符 + 65535（幫助線程數(shù)已經(jīng)達(dá)到最大）
// 如果 nextTable == null（結(jié)束擴(kuò)容了）
// 如果 transferIndex <= 0 (轉(zhuǎn)移狀態(tài)變化了)
// 結(jié)束循環(huán)
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
// 如果可以幫助擴(kuò)容，那么將 sc 加 1. 表示多了一個(gè)線程在幫助擴(kuò)容
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
// 擴(kuò)容
transfer(tab, nt);
}
// 如果不在擴(kuò)容谎脯，將 sc 更新：標(biāo)識(shí)符左移 16 位 然后 + 2. 也就是變成一個(gè)負(fù)數(shù)葱跋。高 16 位是標(biāo)識(shí)符，低 16 位初始是 2.
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
// 更新 sizeCtl 為負(fù)數(shù)后源梭，開(kāi)始擴(kuò)容娱俺。
transfer(tab, null);
s = sumCount();
}
}
}
方法加了注釋以后，還是挺長(zhǎng)的废麻。
總結(jié)一下該方法的邏輯：
- x 參數(shù)表示的此次需要對(duì)表中元素的個(gè)數(shù)加幾荠卷。check 參數(shù)表示是否需要進(jìn)行擴(kuò)容檢查，大于等于0 需要進(jìn)行檢查烛愧，而我們的 putVal 方法的 binCount 參數(shù)最小也是 0 油宜，因此掂碱，每次添加元素都會(huì)進(jìn)行檢查。（除非是覆蓋操作）
- 判斷計(jì)數(shù)盒子屬性是否是空慎冤，如果是空疼燥，就嘗試修改 baseCount 變量，對(duì)該變量進(jìn)行加 X蚁堤。
- 如果計(jì)數(shù)盒子不是空醉者，或者修改 baseCount 變量失敗了，則放棄對(duì) baseCount 進(jìn)行操作违寿。
- 如果計(jì)數(shù)盒子是 null 或者計(jì)數(shù)盒子的 length 是 0湃交，或者隨機(jī)取一個(gè)位置取于數(shù)組長(zhǎng)度是 null，那么就對(duì)剛剛的元素進(jìn)行 CAS 賦值藤巢。
- 如果賦值失敗舞肆，或者滿(mǎn)足上面的條件葬项，則調(diào)用 fullAddCount 方法重新死循環(huán)插入啸如。
這里如果操作 baseCount 失敗了（或者計(jì)數(shù)盒子不是 Null）缘挑，且對(duì)計(jì)數(shù)盒子賦值成功，那么就檢查 check 變量绍刮，如果該變量小于等于 1. 直接結(jié)束温圆。否則，計(jì)算一下 count 變量孩革。 - 如果 check 大于等于 0 岁歉，說(shuō)明需要對(duì)是否擴(kuò)容進(jìn)行檢查。
- 如果 map 的 size 大于 sizeCtl（擴(kuò)容閾值）膝蜈，且 table 的長(zhǎng)度小于 1 << 30锅移，那么就進(jìn)行擴(kuò)容。
- 根據(jù) length 得到一個(gè)標(biāo)識(shí)符饱搏，然后非剃，判斷 sizeCtl 狀態(tài)，如果小于 0 推沸，說(shuō)明要么在初始化备绽，要么在擴(kuò)容。
- 如果正在擴(kuò)容鬓催，那么就校驗(yàn)一下數(shù)據(jù)是否變化了（具體可以看上面代碼的注釋?zhuān)┓嗡亍Ｈ绻麢z驗(yàn)數(shù)據(jù)不通過(guò)，break深浮。
- 如果校驗(yàn)數(shù)據(jù)通過(guò)了压怠，那么將 sizeCtl 加一，表示多了一個(gè)線程幫助擴(kuò)容飞苇。然后進(jìn)行擴(kuò)容菌瘫。
- 如果沒(méi)有在擴(kuò)容，但是需要擴(kuò)容布卡。那么就將 sizeCtl 更新雨让，賦值為標(biāo)識(shí)符左移 16 位 —— 一個(gè)負(fù)數(shù)。然后加 2忿等。 表示栖忠，已經(jīng)有一個(gè)線程開(kāi)始擴(kuò)容了。然后進(jìn)行擴(kuò)容贸街。然后再次更新 count庵寞，看看是否還需要擴(kuò)容。
總結(jié)一下
總結(jié)下來(lái)看薛匪，addCount 方法做了 2 件事情：
- 對(duì) table 的長(zhǎng)度加一捐川。無(wú)論是通過(guò)修改 baseCount，還是通過(guò)使用 CounterCell逸尖。當(dāng) CounterCell 被初始化了古沥，就優(yōu)先使用他，不再使用 baseCount娇跟。
- 檢查是否需要擴(kuò)容岩齿，或者是否正在擴(kuò)容。如果需要擴(kuò)容苞俘，就調(diào)用擴(kuò)容方法盹沈，如果正在擴(kuò)容，就幫助其擴(kuò)容吃谣。
有幾個(gè)要點(diǎn)注意：
- 第一次調(diào)用擴(kuò)容方法前乞封，sizeCtl 的低 16 位是加 2 的，不是加一基协。所以 sc == rs + 1 的判斷是表示是否完成任務(wù)了歌亲。因?yàn)橥瓿蓴U(kuò)容后，sizeCtl == rs + 1澜驮。
- 擴(kuò)容線程最大數(shù)量是 65535陷揪，是由于低 16 位的位數(shù)限制。
- 這里也是可以幫助擴(kuò)容的杂穷，類(lèi)似 helpTransfer 方法悍缠。
