Github issues:https://github.com/littlejoyo/Blog/issues/
個(gè)人博客：https://littlejoyo.github.io/
微信公眾號(hào)：Joyo說(shuō)
哈希表（hash table）也叫散列表，是一種非常重要的數(shù)據(jù)結(jié)構(gòu)，應(yīng)用場(chǎng)景及其豐富，許多緩存技術(shù)（比如memcached）的核心其實(shí)就是在內(nèi)存中維護(hù)一張大的哈希表。
一、什么是哈希表
在討論哈希表之前，我們先大概了解下其他數(shù)據(jù)結(jié)構(gòu)在新增，查找等基礎(chǔ)操作執(zhí)行性能
數(shù)組
采用一段連續(xù)的存儲(chǔ)單元來(lái)存儲(chǔ)數(shù)據(jù)。對(duì)于指定下標(biāo)的查找，時(shí)間復(fù)雜度為O(1)；
通過(guò)給定值進(jìn)行查找，需要遍歷數(shù)組，逐一比對(duì)給定關(guān)鍵字和數(shù)組元素，時(shí)間復(fù)雜度為O(n)，當(dāng)然，對(duì)于有序數(shù)組，則可采用二分查找，插值查找，斐波那契查找等方式，可將查找復(fù)雜度提高為O(logn)；
對(duì)于一般的插入刪除操作，涉及到數(shù)組元素的移動(dòng)，其平均復(fù)雜度也為O(n)線性鏈表
對(duì)于鏈表的新增，刪除等操作（在找到指定操作位置后），僅需處理結(jié)點(diǎn)間的引用即可，時(shí)間復(fù)雜度為O(1)，而查找操作需要遍歷鏈表逐一進(jìn)行比對(duì)，復(fù)雜度為O(n)二叉樹(shù)
對(duì)一棵相對(duì)平衡的有序二叉樹(shù)，對(duì)其進(jìn)行插入，查找，刪除等操作，平均復(fù)雜度均為O(logn)。哈希表
相比上述幾種數(shù)據(jù)結(jié)構(gòu)，在哈希表中進(jìn)行添加，刪除，查找等操作，性能十分之高，不考慮哈希沖突的情況下，僅需一次定位即可完成，時(shí)間復(fù)雜度為O(1).
哈希表上面的特性，哈希表的主干就是數(shù)組。
比如我們要新增或查找某個(gè)元素，我們通過(guò)把當(dāng)前元素的關(guān)鍵字 通過(guò)某個(gè)函數(shù)映射到數(shù)組中的某個(gè)位置，通過(guò)數(shù)組下標(biāo)一次定位就可完成操作。
存儲(chǔ)位置 = f(關(guān)鍵字)
其中，這個(gè)函數(shù)f一般稱為哈希函數(shù)，這個(gè)函數(shù)的設(shè)計(jì)好壞會(huì)直接影響到哈希表的優(yōu)劣。
查找操作同理，先通過(guò)哈希函數(shù)計(jì)算出實(shí)際存儲(chǔ)地址，然后從數(shù)組中對(duì)應(yīng)地址取出即可。
二、哈希沖突
通過(guò)哈希函數(shù)得出的實(shí)際存儲(chǔ)地址相同怎么辦？也就是說(shuō)，當(dāng)我們對(duì)某個(gè)元素進(jìn)行哈希運(yùn)算，得到一個(gè)存儲(chǔ)地址，然后要進(jìn)行插入的時(shí)候，發(fā)現(xiàn)已經(jīng)被其他元素占用了，其實(shí)這就是所謂的哈希沖突，也叫哈希碰撞。
哈希函數(shù)的設(shè)計(jì)至關(guān)重要，好的哈希函數(shù)會(huì)盡可能地保證 計(jì)算簡(jiǎn)單和散列地址分布均勻,但是不可能設(shè)計(jì)出一個(gè)絕對(duì)完美的哈希函數(shù)，我們需要清楚的是，數(shù)組是一塊連續(xù)的固定長(zhǎng)度的內(nèi)存空間，再好的哈希函數(shù)也不能保證得到的存儲(chǔ)地址絕對(duì)不發(fā)生沖突。
哈希沖突的解決方案有多種:開(kāi)放定址法（發(fā)生沖突，繼續(xù)尋找下一塊未被占用的存儲(chǔ)地址），再散列函數(shù)法，鏈地址法.
HashMap即是采用了鏈地址法.
- JDK7 使用了數(shù)組+鏈表的方式
- JDK8 使用了數(shù)組+鏈表+紅黑樹(shù)的方式
三、HashMap的實(shí)現(xiàn)原理
HashMap的主干是一個(gè)Entry數(shù)組。Entry是HashMap的基本組成單元，每一個(gè)Entry包含一個(gè)key-value鍵值對(duì)。
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
Entry是HashMap中的一個(gè)靜態(tài)內(nèi)部類(lèi)。
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;//存儲(chǔ)指向下一個(gè)Entry的引用，單鏈表結(jié)構(gòu)
int hash;//對(duì)key的hashcode值進(jìn)行hash運(yùn)算后得到的值，存儲(chǔ)在Entry，避免重復(fù)計(jì)算
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
HashMap的整體結(jié)構(gòu)如下:
解決沖突的鏈表的長(zhǎng)度影響到HashMap查詢的效率
簡(jiǎn)單來(lái)說(shuō)，HashMap由數(shù)組+鏈表組成的，數(shù)組是HashMap的主體，鏈表則是主要為了解決哈希沖突而存在的，如果定位到的數(shù)組位置不含鏈表（當(dāng)前entry的next指向null）,那么對(duì)于查找，添加等操作很快，僅需一次尋址即可；如果定位到的數(shù)組包含鏈表，對(duì)于添加操作，其時(shí)間復(fù)雜度為O(n)，首先遍歷鏈表，存在即覆蓋，否則新增；對(duì)于查找操作來(lái)講，仍需遍歷鏈表，然后通過(guò)key對(duì)象的equals方法逐一比對(duì)查找。所以，性能考慮，HashMap中的鏈表出現(xiàn)越少，性能才會(huì)越好。發(fā)生沖突關(guān)于entry節(jié)點(diǎn)插入鏈表還是鏈頭呢？
JDK7:插入鏈表的頭部，頭插法
JDK8:插入鏈表的尾部，尾插法
JDK7
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
閱讀源碼發(fā)現(xiàn)，如果遍歷鏈表都沒(méi)法發(fā)現(xiàn)相應(yīng)的key值的話，則會(huì)調(diào)用addEntry方法在鏈表添加一個(gè)Entry，重點(diǎn)就在與addEntry方法是如何插入鏈表的，addEntry方法源碼如下：
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}
這里構(gòu)造了一個(gè)新的Entry對(duì)象（構(gòu)造方法的最后一個(gè)參數(shù)傳入了當(dāng)前的Entry鏈表），然后直接用這個(gè)新的Entry對(duì)象取代了舊的Entry鏈表，看一下Entry的構(gòu)造方法可以知道是頭插法。
Entry( int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
從構(gòu)造方法中的next=n可以看出確實(shí)是把原本的鏈表直接鏈在了新建的Entry對(duì)象的后邊，可以斷定是插入頭部。
JDK8
還是繼續(xù)查看put方法的源碼查看插入節(jié)點(diǎn)的代碼：
//e是p的下一個(gè)節(jié)點(diǎn)
if ((e = p.next) == null) {
//插入鏈表的尾部
p.next = newNode(hash, key, value, null);
//如果插入后鏈表長(zhǎng)度大于8則轉(zhuǎn)化為紅黑樹(shù)
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
從這段代碼中可以很顯然地看出當(dāng)?shù)竭_(dá)鏈表尾部（即p是鏈表的最后一個(gè)節(jié)點(diǎn)）時(shí)，e被賦為null，會(huì)進(jìn)入這個(gè)分支代碼，然后會(huì)用newNode方法建立一個(gè)新的節(jié)點(diǎn)插入尾部。
四、HashMap的默認(rèn)參數(shù)理解
1.為什么HashMap的Entry數(shù)組長(zhǎng)度默認(rèn)為16呢?為什么數(shù)組長(zhǎng)度一定要是2的n次冪呢？
查看HashMap計(jì)算hashcode的方法獲取存儲(chǔ)的位置：
為了減少hash值的碰撞,需要實(shí)現(xiàn)一個(gè)盡量均勻分布的hash函數(shù),在HashMap中通過(guò)利用key的hashcode值,來(lái)進(jìn)行位運(yùn)算
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
return h & (length-1);
}
舉個(gè)例子
1.計(jì)算"book"的hashcode
十進(jìn)制 : 3029737
二進(jìn)制 : 101110001110101110 1001
2.HashMap長(zhǎng)度是默認(rèn)的16，length - 1的結(jié)果
十進(jìn)制 : 15
二進(jìn)制 : 1111
3.把以上兩個(gè)結(jié)果做與運(yùn)算
101110001110101110 1001 & 1111 = 1001
1001的十進(jìn)制 : 9,所以 index=9
結(jié)論：hash算法最終得到的index結(jié)果,取決于hashcode值的最后幾位
現(xiàn)在,我們假設(shè)HashMap的長(zhǎng)度是10,重復(fù)剛才的運(yùn)算步驟:
hashcode : 101110001110101110 1001
length - 1 : ??????????????????????????????????? 1001
index : ??????????????????????????????????????????1001
再換一個(gè)hashcode 101110001110101110 1111 試試:
hashcode : 101110001110101110 1111
length - 1 :????????????????????????????????????1001
index : ????????????????????????????????????????? 1001
從結(jié)果可以看出,雖然hashcode變化了,但是運(yùn)算的結(jié)果都是1001,也就是說(shuō),當(dāng)HashMap長(zhǎng)度為10的時(shí)候,有些index結(jié)果的出現(xiàn)幾率會(huì)更大而有些index結(jié)果永遠(yuǎn)不會(huì)出現(xiàn)(比如0111),這樣就不符合hash均勻分布的原則。
反觀長(zhǎng)度16或者其他2的冪,length - 1的值是所有二進(jìn)制位全為1,這種情況下,index的結(jié)果等同于hashcode后幾位的值，只要輸入的hashcode本身分布均勻,hash算法的結(jié)果就是均勻的。
結(jié)論：
- HashMap的默認(rèn)長(zhǎng)度為16和規(guī)定數(shù)組長(zhǎng)度為2的冪,是為了降低hash碰撞的幾率。
2.HashMap擴(kuò)容限制的負(fù)載因子為什么是0.75呢？為什么不能是0.1或者1呢？
由HashMap的put方法中實(shí)現(xiàn)中的addEntry的實(shí)現(xiàn)代碼可知當(dāng)數(shù)組長(zhǎng)度達(dá)到限制條件的閾值就要進(jìn)行數(shù)組的擴(kuò)容。
擴(kuò)容的方式是：
新建一個(gè)長(zhǎng)度為之前數(shù)組2倍的新的數(shù)組，然后將當(dāng)前的Entry數(shù)組中的元素全部傳輸過(guò)去，擴(kuò)容后的新數(shù)組長(zhǎng)度為之前的2倍，所以擴(kuò)容相對(duì)來(lái)說(shuō)是個(gè)耗資源的操作。
擴(kuò)容的觸發(fā)條件：
閾值 = 數(shù)組默認(rèn)的長(zhǎng)度 x 負(fù)載因子（閾值=16x0.75=12）
threshold = (int)(capacity * loadFactor);
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);//當(dāng)size超過(guò)臨界閾值threshold，并且即將發(fā)生哈希沖突時(shí)進(jìn)行擴(kuò)容
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
由上面的內(nèi)容可知，
- 如果負(fù)載因子為0.5甚至更低的可能的話，最后得到的臨時(shí)閾值明顯會(huì)很小，這樣的情況就會(huì)造成分配的內(nèi)存的浪費(fèi)，存在多余的沒(méi)用的內(nèi)存空間，也不滿足了哈希表均勻分布的情況。
- 如果負(fù)載因子達(dá)到了1的情況，也就是Entry數(shù)組存滿了才發(fā)生擴(kuò)容，這樣會(huì)出現(xiàn)大量的哈希沖突的情況，出現(xiàn)鏈表過(guò)長(zhǎng)，因此造成
get查詢數(shù)據(jù)的效率。 - 因此選擇了0.5~1的折中數(shù)也就是0.75，均衡解決了上面出現(xiàn)的情況。
五、JDK8下的HashMap的實(shí)現(xiàn)
區(qū)別：
- 使用一個(gè)Node數(shù)組取代了JDK7的Entry數(shù)組來(lái)存儲(chǔ)數(shù)據(jù)，這個(gè)Node可能是鏈表結(jié)構(gòu)，也可能是紅黑樹(shù)結(jié)構(gòu)；
- 如果插入的元素key的hashcode值相同，那么這些key也會(huì)被定位到Node數(shù)組的同一個(gè)格子里，如果不超過(guò)8個(gè)使用鏈表存儲(chǔ)；
-
超過(guò)8個(gè)，會(huì)調(diào)用treeifyBin函數(shù)，將鏈表轉(zhuǎn)換為紅黑樹(shù)。那么即使所有key的hashcode完全相同，由于紅黑樹(shù)的特點(diǎn)，查找某個(gè)特定元素，也只需要O（logn）的開(kāi)銷(xiāo)。
JDK8的HashMap
上圖是示意圖，主要是描述結(jié)構(gòu)，不會(huì)達(dá)到這個(gè)狀態(tài)的，因?yàn)檫@么多數(shù)據(jù)的時(shí)候早就擴(kuò)容了。
put
- 和 Java7 稍微有點(diǎn)不一樣的地方就是，Java7 是先擴(kuò)容后插入新值的，Java8 先插值再擴(kuò)容，不過(guò)這個(gè)不重要。
get
- 計(jì)算 key 的 hash 值，根據(jù) hash 值找到對(duì)應(yīng)數(shù)組下標(biāo): hash & (length-1)
- 判斷數(shù)組該位置處的元素是否剛好就是我們要找的，如果不是，走第三步
- 判斷該元素類(lèi)型是否是 TreeNode，如果是，用紅黑樹(shù)的方法取數(shù)據(jù)，如果不是，走第四步 遍歷鏈表，直到找到相等(==或equals)的 key
六、CurrentHashMap的原理
由于HashMap是線程不同步的，雖然處理數(shù)據(jù)的效率高，但是在多線程的情況下存在著安全問(wèn)題，因此設(shè)計(jì)了CurrentHashMap來(lái)解決多線程安全問(wèn)題。
HashMap在put的時(shí)候，插入的元素超過(guò)了容量（由負(fù)載因子決定）的范圍就會(huì)觸發(fā)擴(kuò)容操作，就是rehash，這個(gè)會(huì)重新將原數(shù)組的內(nèi)容重新hash到新的擴(kuò)容數(shù)組中，在多線程的環(huán)境下，存在同時(shí)其他的元素也在進(jìn)行put操作，如果hash值相同，可能出現(xiàn)同時(shí)在同一數(shù)組下用鏈表表示，造成閉環(huán)，導(dǎo)致在get時(shí)會(huì)出現(xiàn)死循環(huán)，所以HashMap是線程不安全的。
JDK7下的CurrentHashMap
在JDK1.7版本中，ConcurrentHashMap的數(shù)據(jù)結(jié)構(gòu)是由一個(gè)Segment數(shù)組和多個(gè)HashEntry組成，主要實(shí)現(xiàn)原理是實(shí)現(xiàn)了鎖分離的思路解決了多線程的安全問(wèn)題，如下圖所示：
Segment數(shù)組的意義就是將一個(gè)大的table分割成多個(gè)小的table來(lái)進(jìn)行加鎖，也就是上面的提到的鎖分離技術(shù)，而每一個(gè)Segment元素存儲(chǔ)的是HashEntry數(shù)組+鏈表，這個(gè)和HashMap的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)一樣。
ConcurrentHashMap 與HashMap和Hashtable 最大的不同在于：put和 get 兩次Hash到達(dá)指定的HashEntry，第一次hash到達(dá)Segment,第二次到達(dá)Segment里面的Entry,然后在遍歷entry鏈表.
初始化
ConcurrentHashMap的初始化是會(huì)通過(guò)位與運(yùn)算來(lái)初始化Segment的大小，用ssize來(lái)表示，源碼如下所示
private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// For serialization compatibility
// Emulate segment calculation from previous version of this class
int sshift = 0;
int ssize = 1;
while (ssize < DEFAULT_CONCURRENCY_LEVEL) {
++sshift;
ssize <<= 1;
}
int segmentShift = 32 - sshift;
int segmentMask = ssize - 1;
因?yàn)閟size用位于運(yùn)算來(lái)計(jì)算（ssize <<=1），所以Segment的大小取值都是以2的N次方，無(wú)關(guān)concurrencyLevel的取值，當(dāng)然concurrencyLevel最大只能用16位的二進(jìn)制來(lái)表示，即65536，換句話說(shuō)，Segment的大小最多65536個(gè)，沒(méi)有指定concurrencyLevel元素初始化，Segment的大小ssize默認(rèn)為 DEFAULT_CONCURRENCY_LEVEL =16
每一個(gè)Segment元素下的HashEntry的初始化也是按照位與運(yùn)算來(lái)計(jì)算，用cap來(lái)表示，如下：
int cap = 1;
while (cap < c)
cap <<= 1
上所示，HashEntry大小的計(jì)算也是2的N次方（cap <<=1）， cap的初始值為1，所以HashEntry最小的容量為2
put操作
static class Segment<K,V> extends ReentrantLock implements Serializable {
private static final long serialVersionUID = 2249069246763182397L;
final float loadFactor;
Segment(float lf) { this.loadFactor = lf; }
}
從上Segment的繼承體系可以看出，Segment實(shí)現(xiàn)了ReentrantLock,也就帶有鎖的功能，當(dāng)執(zhí)行put操作時(shí)，會(huì)進(jìn)行第一次key的hash來(lái)定位Segment的位置，如果該Segment還沒(méi)有初始化，即通過(guò)CAS操作進(jìn)行賦值，然后進(jìn)行第二次hash操作，找到相應(yīng)的HashEntry的位置，這里會(huì)利用繼承過(guò)來(lái)的鎖的特性，在將數(shù)據(jù)插入指定的HashEntry位置時(shí)（鏈表的尾端），會(huì)通過(guò)繼承ReentrantLock的tryLock（）方法嘗試去獲取鎖，如果獲取成功就直接插入相應(yīng)的位置，如果已經(jīng)有線程獲取該Segment的鎖，那當(dāng)前線程會(huì)以自旋的方式(如果不了解自旋鎖，請(qǐng)參考：自旋鎖原理及java自旋鎖)去繼續(xù)的調(diào)用tryLock（）方法去獲取鎖，超過(guò)指定次數(shù)就掛起，等待喚醒.
get
ConcurrentHashMap的get操作跟HashMap類(lèi)似，只是ConcurrentHashMap第一次需要經(jīng)過(guò)一次hash定位到Segment的位置，然后再hash定位到指定的HashEntry，遍歷該HashEntry下的鏈表進(jìn)行對(duì)比，成功就返回，不成功就返回null
size 返回ConcurrentHashMap元素大小
計(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版本用兩種方案
try {
for (;;) {
if (retries++ == RETRIES_BEFORE_LOCK) {
for (int j = 0; j < segments.length; ++j) ensureSegment(j).lock(); // force creation
}
sum = 0L;
size = 0;
overflow = false;
for (int j = 0; j < segments.length; ++j) {
Segment<K,V> seg = segmentAt(segments, j);
if (seg != null) { sum += seg.modCount; int c = seg.count; if (c < 0 || (size += c) < 0)
overflow = true;
} }
if (sum == last) break;
last = sum; } }
finally {
if (retries > RETRIES_BEFORE_LOCK) {
for (int j = 0; j < segments.length; ++j)
segmentAt(segments, j).unlock();
}
}
1、第一種方案他會(huì)使用不加鎖的模式去嘗試多次計(jì)算ConcurrentHashMap的size，最多三次，比較前后兩次計(jì)算的結(jié)果，結(jié)果一致就認(rèn)為當(dāng)前沒(méi)有元素加入，計(jì)算的結(jié)果是準(zhǔn)確的.
2、第二種方案是如果第一種方案不符合，他就會(huì)給每個(gè)Segment加上鎖，然后計(jì)算ConcurrentHashMap的size返回.
JDK8的ConcurrentHashMap
JDK1.8的實(shí)現(xiàn)已經(jīng)摒棄了Segment的概念，而是直接用Node數(shù)組+鏈表+紅黑樹(shù)的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)，并發(fā)控制使用Synchronized和CAS來(lái)操作，整個(gè)看起來(lái)就像是優(yōu)化過(guò)且線程安全的HashMap，雖然在JDK1.8中還能看到Segment的數(shù)據(jù)結(jié)構(gòu)，但是已經(jīng)簡(jiǎn)化了屬性，只是為了兼容舊版本.
在深入JDK1.8的put和get實(shí)現(xiàn)之前要知道一些常量設(shè)計(jì)和數(shù)據(jù)結(jié)構(gòu)，這些是構(gòu)成ConcurrentHashMap實(shí)現(xiàn)結(jié)構(gòu)的基礎(chǔ)，下面看一下基本屬性：
// node數(shù)組最大容量：2^30=1073741824
private static final int MAXIMUM_CAPACITY = 1 << 30;
// 默認(rèn)初始值，必須是2的幕數(shù)
private static final int DEFAULT_CAPACITY = 16
//數(shù)組可能最大值，需要與toArray（）相關(guān)方法關(guān)聯(lián)
static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//并發(fā)級(jí)別，遺留下來(lái)的，為兼容以前的版本
private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
// 負(fù)載因子
private static final float LOAD_FACTOR = 0.75f;
// 鏈表轉(zhuǎn)紅黑樹(shù)閥值,> 8 鏈表轉(zhuǎn)換為紅黑樹(shù)
static final int TREEIFY_THRESHOLD = 8;
//樹(shù)轉(zhuǎn)鏈表閥值，小于等于6（tranfer時(shí)，lc、hc=0兩個(gè)計(jì)數(shù)器分別++記錄原bin、新binTreeNode數(shù)量，<=UNTREEIFY_THRESHOLD 則untreeify(lo)）
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
private static final int MIN_TRANSFER_STRIDE = 16;
private static int RESIZE_STAMP_BITS = 16;
// 2^15-1，help resize的最大線程數(shù)
private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
// 32-16=16，sizeCtl中記錄size大小的偏移量
private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
// forwarding nodes的hash值
static final int MOVED = -1;
// 樹(shù)根節(jié)點(diǎn)的hash值
static final int TREEBIN = -2;
// ReservationNode的hash值
static final int RESERVED = -3;
// 可用處理器數(shù)量
static final int NCPU = Runtime.getRuntime().availableProcessors();
//存放node的數(shù)組
transient volatile Node<K,V>[] table;
/*控制標(biāo)識(shí)符，用來(lái)控制table的初始化和擴(kuò)容的操作，不同的值有不同的含義
*當(dāng)為負(fù)數(shù)時(shí)：-1代表正在初始化，-N代表有N-1個(gè)線程正在 進(jìn)行擴(kuò)容
*當(dāng)為0時(shí)：代表當(dāng)時(shí)的table還沒(méi)有被初始化
*當(dāng)為正數(shù)時(shí)：表示初始化或者下一次進(jìn)行擴(kuò)容的大小
private transient volatile int sizeCtl;
JDK8的Node
Node是ConcurrentHashMap存儲(chǔ)結(jié)構(gòu)的基本單元，繼承于HashMap中的Entry，用于存儲(chǔ)數(shù)據(jù)，Node數(shù)據(jù)結(jié)構(gòu)很簡(jiǎn)單，就是一個(gè)鏈表，但是只允許對(duì)數(shù)據(jù)進(jìn)行查找，不允許進(jìn)行修改
源代碼如下：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V val;
volatile Node<K,V> next;
Node(int hash, K key, V val, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.val = val;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return val; }
public final int hashCode() { return key.hashCode() ^ val.hashCode(); }
public final String toString(){ return key + "=" + val; }
public final V setValue(V value) {
throw new UnsupportedOperationException();
}
public final boolean equals(Object o) {
Object k, v, u; Map.Entry<?,?> e;
return ((o instanceof Map.Entry) &&
(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
(v = e.getValue()) != null &&
(k == key || k.equals(key)) &&
(v == (u = val) || v.equals(u)));
}
/**
* Virtualized support for map.get(); overridden in subclasses.
*/
Node<K,V> find(int h, Object k) {
Node<K,V> e = this;
if (k != null) {
do {
K ek;
if (e.hash == h &&
((ek = e.key) == k || (ek != null && k.equals(ek))))
return e;
} while ((e = e.next) != null);
}
return null;
}
}
TreeNode
TreeNode繼承于Node，但是數(shù)據(jù)結(jié)構(gòu)換成了二叉樹(shù)結(jié)構(gòu)，它是紅黑樹(shù)的數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，用于紅黑樹(shù)中存儲(chǔ)數(shù)據(jù)，當(dāng)鏈表的節(jié)點(diǎn)數(shù)大于8時(shí)會(huì)轉(zhuǎn)換成紅黑樹(shù)的結(jié)構(gòu)，他就是通過(guò)TreeNode作為存儲(chǔ)結(jié)構(gòu)代替Node來(lái)轉(zhuǎn)換成黑紅樹(shù)源代碼如下
static final class TreeNode<K,V> extends Node<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
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next,
TreeNode<K,V> parent) {
super(hash, key, val, next);
this.parent = parent;
}
Node<K,V> find(int h, Object k) {
return findTreeNode(h, k, null);
}
/**
* Returns the TreeNode (or null if not found) for the given key
* starting at given root.
*/
final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
if (k != null) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk; TreeNode<K,V> q;
TreeNode<K,V> pl = p.left, pr = p.right;
if ((ph = p.hash) > h)
p = pl;
else if (ph < h)
p = pr;
else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
return p;
else if (pl == null)
p = pr;
else if (pr == null)
p = pl;
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
else if ((q = pr.findTreeNode(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
}
return null;
}
}
TreeBin
TreeBin從字面含義中可以理解為存儲(chǔ)樹(shù)形結(jié)構(gòu)的容器，而樹(shù)形結(jié)構(gòu)就是指TreeNode，所以TreeBin就是封裝TreeNode的容器，它提供轉(zhuǎn)換黑紅樹(shù)的一些條件和鎖的控制.
總結(jié)和思考
其實(shí)可以看出JDK1.8版本的ConcurrentHashMap的數(shù)據(jù)結(jié)構(gòu)已經(jīng)接近HashMap，相對(duì)而言，ConcurrentHashMap只是增加了同步的操作來(lái)控制并發(fā)，從JDK1.7版本的ReentrantLock+Segment+HashEntry，到JDK1.8版本中synchronized+CAS+HashEntry+紅黑樹(shù),相對(duì)而言，總結(jié)如下思考
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)
1.因?yàn)榱６冉档土?，在相?duì)而言的低粒度加鎖方式，synchronized并不比ReentrantLock差，在粗粒度加鎖中ReentrantLock可能通過(guò)Condition來(lái)控制各個(gè)低粒度的邊界，更加的靈活，而在低粒度中，Condition的優(yōu)勢(shì)就沒(méi)有了
2.JVM的開(kāi)發(fā)團(tuán)隊(duì)從來(lái)都沒(méi)有放棄synchronized，而且基于JVM的synchronized優(yōu)化空間更大，使用內(nèi)嵌的關(guān)鍵字比使用API更加自然
3.在大量的數(shù)據(jù)操作下，對(duì)于JVM的內(nèi)存壓力，基于API的ReentrantLock會(huì)開(kāi)銷(xiāo)更多的內(nèi)存，雖然不是瓶頸，但是也是一個(gè)選擇依據(jù)
參考資料：
微信公眾號(hào)
掃一掃關(guān)注Joyo說(shuō)公眾號(hào)，共同學(xué)習(xí)和研究開(kāi)發(fā)技術(shù)。
