在 Java 8 中，對(duì)于 ConcurrentHashMap 這個(gè)常用的工具類進(jìn)行了很大的升級(jí)，對(duì)比之前 Java 7 版本在諸多方面都進(jìn)行了調(diào)整和變化。
Java 7 版本的 ConcurrentHashMap
Java 7 版本中的 ConcurrentHashMap 的結(jié)構(gòu)示意圖：
從圖中我們可以看出，在 ConcurrentHashMap 內(nèi)部進(jìn)行了 Segment 分段，Segment 繼承了 ReentrantLock，可以理解為一把鎖，各個(gè) Segment 之間都是相互獨(dú)立上鎖的，互不影響。相比于之前的 Hashtable 每次操作都需要把整個(gè)對(duì)象鎖住而言，大大提高了并發(fā)效率。因?yàn)樗逆i與鎖之間是獨(dú)立的，而不是整個(gè)對(duì)象只有一把鎖。
每個(gè) Segment 的底層數(shù)據(jù)結(jié)構(gòu)與 HashMap 類似，仍然是數(shù)組和鏈表組成的拉鏈法結(jié)構(gòu)。默認(rèn)有 0~15 共 16 個(gè) Segment，所以最多可以同時(shí)支持 16 個(gè)線程并發(fā)操作（操作分別分布在不同的 Segment 上）。16 這個(gè)默認(rèn)值可以在初始化的時(shí)候設(shè)置為其他值，但是一旦確認(rèn)初始化以后，是不可以擴(kuò)容的。
Java 8 版本的 ConcurrentHashMap
Java 8 版本中的 ConcurrentHashMap 的結(jié)構(gòu)示意圖：
圖中的節(jié)點(diǎn)有三種類型。
- 第一種是最簡(jiǎn)單的，空著的位置代表當(dāng)前還沒有元素來填充。
- 第二種就是和 HashMap 非常類似的拉鏈法結(jié)構(gòu)，在每一個(gè)槽中會(huì)首先填入第一個(gè)節(jié)點(diǎn)，但是后續(xù)如果計(jì)算出相同的 Hash 值，就用鏈表的形式往后進(jìn)行延伸。
- 第三種結(jié)構(gòu)就是紅黑樹結(jié)構(gòu)，這是 Java 7 的 ConcurrentHashMap 中所沒有的結(jié)構(gòu)
當(dāng)?shù)诙N情況的鏈表長(zhǎng)度大于某一個(gè)閾值（默認(rèn)為 8），且同時(shí)滿足一定的容量要求的時(shí)候，ConcurrentHashMap 便會(huì)把這個(gè)鏈表從鏈表的形式轉(zhuǎn)化為紅黑樹的形式，目的是進(jìn)一步提高它的查找性能。所以，Java 8 的一個(gè)重要變化就是引入了紅黑樹的設(shè)計(jì)，由于紅黑樹并不是一種常見的數(shù)據(jù)結(jié)構(gòu)，所以我們?cè)诖撕?jiǎn)要介紹一下紅黑樹的特點(diǎn)。
紅黑樹是每個(gè)節(jié)點(diǎn)都帶有顏色屬性的二叉查找樹，顏色為紅色或黑色，紅黑樹的本質(zhì)是對(duì)二叉查找樹 BST 的一種平衡策略，我們可以理解為是一種平衡二叉查找樹，查找效率高，會(huì)自動(dòng)平衡，防止極端不平衡從而影響查找效率的情況發(fā)生。
由于自平衡的特點(diǎn)，即左右子樹高度幾乎一致，所以其查找性能近似于二分查找，時(shí)間復(fù)雜度是 O(log(n)) 級(jí)別；反觀鏈表，它的時(shí)間復(fù)雜度就不一樣了，如果發(fā)生了最壞的情況，可能需要遍歷整個(gè)鏈表才能找到目標(biāo)元素，時(shí)間復(fù)雜度為 O(n)，遠(yuǎn)遠(yuǎn)大于紅黑樹的 O(log(n))，尤其是在節(jié)點(diǎn)越來越多的情況下，O(log(n)) 體現(xiàn)出的優(yōu)勢(shì)會(huì)更加明顯。
紅黑樹的一些其他特點(diǎn)：
- 每個(gè)節(jié)點(diǎn)要么是紅色，要么是黑色，但根節(jié)點(diǎn)永遠(yuǎn)是黑色的。
- 紅色節(jié)點(diǎn)不能連續(xù)，也就是說，紅色節(jié)點(diǎn)的子和父都不能是紅色的。
- 從任一節(jié)點(diǎn)到其每個(gè)葉子節(jié)點(diǎn)的路徑都包含相同數(shù)量的黑色節(jié)點(diǎn)。
正是由于這些規(guī)則和要求的限制，紅黑樹保證了較高的查找效率，所以現(xiàn)在就可以理解為什么 Java 8 的 ConcurrentHashMap 要引入紅黑樹了。好處就是避免在極端的情況下沖突鏈表變得很長(zhǎng)，在查詢的時(shí)候，效率會(huì)非常慢。而紅黑樹具有自平衡的特點(diǎn)，所以，即便是極端情況下，也可以保證查詢效率在 O(log(n))。
分析 Java 7 版本的 ConcurrentHashMap 的重要源碼
static final class Segment<K,V> extends ReentrantLock implements Serializable
ConcurrentHashMap 是由 Segment 數(shù)組結(jié)構(gòu)和 HashEntry 數(shù)組結(jié)構(gòu)組成。
Segment 是一種可重入鎖（ReentrantLock），在 ConcurrentHashMap 里扮演鎖的角色；HashEntry 則用于存儲(chǔ)鍵值對(duì)數(shù)據(jù)。一個(gè) ConcurrentHashMap 里包含一個(gè) Segment 數(shù)組。Segment 的結(jié)構(gòu)和 HashMap 類似，是一種數(shù)組和鏈表結(jié)構(gòu)。一個(gè) Segment 里包含一個(gè) HashEntry 數(shù)組，每個(gè) HashEntry 是一個(gè)鏈表結(jié)構(gòu)的元素， 每個(gè) Segment 守護(hù)著一個(gè) HashEntry 數(shù)組里的元素，當(dāng)對(duì) HashEntry 數(shù)組的數(shù)據(jù)進(jìn)行修改時(shí)，必須首先獲得與它對(duì)應(yīng)的 Segment 鎖。
構(gòu)造方法和初始化
public ConcurrentHashMap17(int initialCapacity,
float loadFactor, int concurrencyLevel)
ConcurrentHashMap 初始化方法是通過 initialCapacity、loadFactor 和 concurrencyLevel(參數(shù) concurrencyLevel 是用戶估計(jì)的并發(fā)級(jí)別，就是說你覺得最多有多少線程共同修改這個(gè) map，根據(jù)這個(gè)來確定 Segment 數(shù)組的大小 concurrencyLevel 默認(rèn)是 DEFAULT_CONCURRENCY_LEVEL = 16;)等幾個(gè)參數(shù)來初始化 segment 數(shù)組、段偏移量 segmentShift、段掩碼 segmentMask 和每個(gè) segment 里的 HashEntry 數(shù)組來實(shí)現(xiàn)的。
并發(fā)級(jí)別可以理解為程序運(yùn)行時(shí)能夠同時(shí)更新 ConccurentHashMap 且不產(chǎn)生鎖競(jìng)爭(zhēng)的最大線程數(shù)，實(shí)際上就是ConcurrentHashMap 中的分段鎖個(gè)數(shù)，即 Segment[]的數(shù)組長(zhǎng)度。ConcurrentHashMap 默認(rèn)的并發(fā)度為 16，但用戶也可以 在構(gòu)造函數(shù)中設(shè)置并發(fā)度。當(dāng)用戶設(shè)置并發(fā)度時(shí)，ConcurrentHashMap 會(huì)使用大于等于該值的最小 2 冪指數(shù)作為實(shí)際并發(fā)度（假如用戶設(shè)置并發(fā)度為 17，實(shí)際 并發(fā)度則為 32）。
如果并發(fā)度設(shè)置的過小，會(huì)帶來嚴(yán)重的鎖競(jìng)爭(zhēng)問題；如果并發(fā)度設(shè)置的過大， 原本位于同一個(gè) Segment 內(nèi)的訪問會(huì)擴(kuò)散到不同的 Segment 中，CPU cache 命中 率會(huì)下降，從而引起程序性能下降。（文檔的說法是根據(jù)你并發(fā)的線程數(shù)量決定， 太多會(huì)導(dǎo)性能降低）
segments 數(shù)組的長(zhǎng)度 ssize 是通過 concurrencyLevel 計(jì)算得出的。為了能通過按位與的散列算法來定位 segments 數(shù)組的索引，必須保證 segments 數(shù)組的長(zhǎng)度是 2 的 N 次方（power-of-two size），所以必須計(jì)算出一個(gè)大于或等于 concurrencyLevel 的最小的 2 的 N 次方值來作為 segments 數(shù)組的長(zhǎng)度。假如 concurrencyLevel 等于 14、15 或 16，ssize 都會(huì)等于 16，即容器里鎖的個(gè)數(shù)也是 16。
在默認(rèn)情況下， ssize = 16，initialCapacity = 16，loadFactor = 0.75f，那么 cap = 1，threshold = (int) cap * loadFactor = 0。
int cap = MIN_SEGMENT_TABLE_CAPACITY;
while (cap < c)
cap <<= 1;
// create segments and segments[0]
Segment<K,V> s0 =
new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
(HashEntry<K,V>[])new HashEntry[cap]);
Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
this.segments = ss;
輸入?yún)?shù) initialCapacity 是 ConcurrentHashMap 的初始化容量，loadFactor 是每個(gè) segment 的負(fù)載因子，在構(gòu)造方法里需要通過這兩個(gè)參數(shù)來初始化數(shù)組中的每個(gè) segment。上面代碼中的變量 cap 就是 segment 里 HashEntry 數(shù)組的長(zhǎng)度， 它等于 initialCapacity 除以 ssize 的倍數(shù) c，如果 c 大于 1，就會(huì)取大于等于 c 的 2 的 N 次方值，所以 segment 里 HashEntry 數(shù)組的長(zhǎng)度不是 1，就是 2 的 N 次方。
分析 Java 8 版本的 ConcurrentHashMap 的重要源碼
改進(jìn)
改進(jìn)一：取消 segments 字段，直接采用 transient volatile HashEntry<K,V>[] table 保存數(shù)據(jù)，采用 table 數(shù)組元素作為鎖，從而實(shí)現(xiàn)了對(duì)縮小鎖的粒度，進(jìn)一 步減少并發(fā)沖突的概率，并大量使用了采用了 CAS + synchronized 來保證并發(fā)安全性。
改進(jìn)二：將原先 table 數(shù)組＋單向鏈表的數(shù)據(jù)結(jié)構(gòu)，變更為 table 數(shù)組＋單向鏈表＋紅黑樹的結(jié)構(gòu)。對(duì)于 hash 表來說，最核心的能力在于將 key hash 之后 能均勻的分布在數(shù)組中。如果 hash 之后散列的很均勻，那么 table 數(shù)組中的每個(gè) 隊(duì)列長(zhǎng)度主要為 0 或者 1。但實(shí)際情況并非總是如此理想，雖然 ConcurrentHashMap 類默認(rèn)的加載因子為 0.75，但是在數(shù)據(jù)量過大或者運(yùn)氣不佳的情況下，還是會(huì)存在一些隊(duì)列長(zhǎng)度過長(zhǎng)的情況，如果還是采用單向列表方式， 那么查詢某個(gè)節(jié)點(diǎn)的時(shí)間復(fù)雜度為 O(n)；因此，對(duì)于個(gè)數(shù)超過 8(默認(rèn)值)的列表， jdk1.8 中采用了紅黑樹的結(jié)構(gòu)，那么查詢的時(shí)間復(fù)雜度可以降低到 O(logN)，可以改進(jìn)性能。
使用 Node（1.7 為 Entry） 作為鏈表的數(shù)據(jù)結(jié)點(diǎn)，仍然包含 key，value， hash 和 next 四個(gè)屬性。 紅黑樹的情況使用的是 TreeNode（extends Node）。
根據(jù)數(shù)組元素中，第一個(gè)結(jié)點(diǎn)數(shù)據(jù)類型是 Node 還是 TreeNode 可以判斷該位置下是鏈表還是紅黑樹。
用于判斷是否需要將鏈表轉(zhuǎn)換為紅黑樹的閾值
static final int TREEIFY_THRESHOLD = 8;
用于判斷是否需要將紅黑樹轉(zhuǎn)換為鏈表的閾值
static final int UNTREEIFY_THRESHOLD = 6;
Node 節(jié)點(diǎn)
Node 是最核心的內(nèi)部類，它包裝了 key-value 鍵值對(duì)。
我們先來看看最基礎(chǔ)的內(nèi)部存儲(chǔ)結(jié)構(gòu) Node，這就是一個(gè)一個(gè)的節(jié)點(diǎ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;
.....
}
定義基本和 1.7 中的 HashEntry 相同。而這個(gè) map 本身所持有的也是一個(gè) Node 型的數(shù)組transient volatile Node<K,V>[] table;
增加了一個(gè) find 方法來用以輔助 map.get()方法。其實(shí)就是遍歷鏈表，子類中會(huì)覆蓋這個(gè)方法。
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;
}
在 map 中還定義了 Segment 這個(gè)類，不過只是為了向前兼容而已，不做過多考慮。
可以看出，每個(gè) Node 里面是 key-value 的形式，并且把 value 用 volatile 修飾，以便保證可見性，同時(shí)內(nèi)部還有一個(gè)指向下一個(gè)節(jié)點(diǎn)的 next 指針，方便產(chǎn)生鏈表結(jié)構(gòu)。
TreeNode
樹節(jié)點(diǎn)類，另外一個(gè)核心的數(shù)據(jù)結(jié)構(gòu)。當(dāng)鏈表長(zhǎng)度過長(zhǎng)的時(shí)候，會(huì)轉(zhuǎn)換為TreeNode。
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;
......
與 1.8 中 HashMap 不同點(diǎn)：
1、它并不是直接轉(zhuǎn)換為紅黑樹，而是把這些結(jié)點(diǎn)放在 TreeBin 對(duì)象中，由 TreeBin 完成對(duì)紅黑樹的包裝。
2、TreeNode 在 ConcurrentHashMap 擴(kuò)展自 Node 類，而并非 HashMap 中的 擴(kuò)展自 LinkedHashMap.Entry<K,V>類，也就是說 TreeNode 帶有 next 指針。
TreeBin
負(fù)責(zé) TreeNode 節(jié)點(diǎn)。它代替了 TreeNode 的根節(jié)點(diǎn)，也就是說在實(shí)際的 ConcurrentHashMap“數(shù)組”中，存放的是 TreeBin 對(duì)象，而不是 TreeNode 對(duì)象。 另外這個(gè)類還帶有了讀寫鎖機(jī)制。
static final class TreeBin<K,V> extends Node<K,V> {
TreeNode<K,V> root;
volatile TreeNode<K,V> first;
volatile Thread waiter;
volatile int lockState;
// values for lockState
static final int WRITER = 1; // set while holding write lock
static final int WAITER = 2; // set when waiting for write lock
static final int READER = 4; // increment value for setting read lock
核心方法
/*
* 利用硬件級(jí)別的原子操作，獲得在 i 位置上的 Node 節(jié)點(diǎn)
* Unsafe.getObjectVolatile 可以直接獲取指定內(nèi)存的數(shù)據(jù)，
* 保證了每次拿到數(shù)據(jù)都是最新的
**/
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}
/*利用CAS操作設(shè)置 i 位置上的 Node 節(jié)點(diǎn)*/
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
Node<K,V> c, Node<K,V> v) {
return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}
/*
* 利用硬件級(jí)別的原子操作，設(shè)置在 i 位置上的Node節(jié)點(diǎn)
* Unsafe.putObjectVolatile 可以直接設(shè)定指定內(nèi)存的數(shù)據(jù)，
* 保證了其他線程訪問這個(gè)節(jié)點(diǎn)時(shí)一定可以看到最新的數(shù)據(jù)
**/
static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
}
下面我們看兩個(gè)最重要、最核心的方法。
put 方法源碼分析
put 方法的核心是 putVal 方法
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) {
throw new NullPointerException();
}
//計(jì)算 hash 值
int hash = spread(key.hashCode());
int binCount = 0;
/*死循環(huán) 何時(shí)插入成功 何時(shí)跳出*/
for (Node<K, V>[] tab = table; ; ) {
Node<K, V> f;
int n, i, fh;
//如果數(shù)組是空的，就進(jìn)行初始化
if (tab == null || (n = tab.length) == 0) {
tab = initTable();/*如果table為空的話，初始化table*/
}
// 找該 hash 值對(duì)應(yīng)的數(shù)組下標(biāo)
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
//如果該位置是空的，就用 CAS 的方式放入新值
/*Node數(shù)組中的元素，這個(gè)位置沒有值 ，使用CAS操作放進(jìn)去*/
if (casTabAt(tab, i, null,
new Node<K, V>(hash, key, value, null))) {
break;
}
}
//hash值等于 MOVED 代表在擴(kuò)容
else if ((fh = f.hash) == MOVED) {
/*正在進(jìn)行擴(kuò)容，當(dāng)前線程幫忙擴(kuò)容*/
tab = helpTransfer(tab, f);
}
//槽點(diǎn)上是有值的情況
else {
V oldVal = null;
//用 synchronized 鎖住當(dāng)前槽點(diǎn)，保證并發(fā)安全
/*鎖Node數(shù)組中的元素，這個(gè)位置是Hash沖突組成鏈表的頭結(jié)點(diǎn)
* 或者是紅黑樹的根節(jié)點(diǎn)*/
synchronized (f) {
if (tabAt(tab, i) == f) {
//如果是鏈表的形式
/*fh>0 說明這個(gè)節(jié)點(diǎn)是一個(gè)鏈表的節(jié)點(diǎn) 不是樹的節(jié)點(diǎn)*/
if (fh >= 0) {
binCount = 1;
//遍歷鏈表
for (Node<K, V> e = f; ; ++binCount) {
K ek;
//如果發(fā)現(xiàn)該 key 已存在，就判斷是否需要進(jìn)行覆蓋，然后返回
/*put操作和putIfAbsent操作業(yè)務(wù)實(shí)現(xiàn)*/
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;
//到了鏈表的尾部也沒有發(fā)現(xiàn)該 key，說明之前不存在，就把新值添加到鏈表的最后
/*如果遍歷到了最后一個(gè)結(jié)點(diǎn)，使用尾插法,把它插入在鏈表尾部*/
if ((e = e.next) == null) {
pred.next = new Node<K, V>(hash, key,
value, null);
break;
}
}
}
//如果是紅黑樹的形式
/*按照樹的方式插入值*/
else if (f instanceof TreeBin) {
Node<K, V> p;
binCount = 2;
//調(diào)用 putTreeVal 方法往紅黑樹里增加數(shù)據(jù)
if ((p = ((TreeBin<K, V>) f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent) {
p.val = value;
}
}
}
}
}
if (binCount != 0) {
//檢查是否滿足條件并把鏈表轉(zhuǎn)換為紅黑樹的形式，默認(rèn)的 TREEIFY_THRESHOLD 閾值是 8
/*達(dá)到臨界值8 就需要把鏈表轉(zhuǎn)換為樹結(jié)構(gòu)*/
if (binCount >= TREEIFY_THRESHOLD) {
treeifyBin(tab, i);
}
//putVal 的返回是添加前的舊值，所以返回 oldVal
if (oldVal != null) {
return oldVal;
}
break;
}
}
}
/*Map的元素?cái)?shù)量+1，并檢查是否需要擴(kuò)容*/
addCount(1L, binCount);
return null;
}
通過以上的源碼分析，我們對(duì)于 putVal 方法有了詳細(xì)的認(rèn)識(shí)，可以看出，方法中會(huì)逐步根據(jù)當(dāng)前槽點(diǎn)是未初始化、空、擴(kuò)容、鏈表、紅黑樹等不同情況做出不同的處理。
總結(jié)來說，put 方法就是，沿用 HashMap 的 put 方法的思想，根據(jù) hash 值 計(jì)算這個(gè)新插入的點(diǎn)在 table 中的位置 i，如果 i 位置是空的，直接放進(jìn)去，否則 進(jìn)行判斷，如果 i 位置是樹節(jié)點(diǎn)，按照樹的方式插入新的節(jié)點(diǎn)，否則把 i 插入到 鏈表的末尾。
整體流程上，就是首先定義不允許 key 或 value 為 null 的情況放入，對(duì)于每一個(gè)放入的值，首先利用 spread 方法對(duì) key 的 hashcode 進(jìn)行一次 hash 計(jì)算，由 此來確定這個(gè)值在 table 中的位置。
如果這個(gè)位置是空的，那么直接放入，而且不需要加鎖操作。
如果這個(gè)位置存在結(jié)點(diǎn)，說明發(fā)生了 hash 碰撞，首先判斷這個(gè)節(jié)點(diǎn)的類型。 如果是鏈表節(jié)點(diǎn)，則得到的結(jié)點(diǎn)就是 hash 值相同的節(jié)點(diǎn)組成的鏈表的頭節(jié)點(diǎn)。需要依次向后遍歷確定這個(gè)新加入的值所在位置。如果遇到 hash 值與 key 值都與 新加入節(jié)點(diǎn)是一致的情況，則只需要更新 value 值即可。否則依次向后遍歷，直 到鏈表尾插入這個(gè)結(jié)點(diǎn)。如果加入這個(gè)節(jié)點(diǎn)以后鏈表長(zhǎng)度大于 8，就把這個(gè)鏈表 轉(zhuǎn)換成紅黑樹。如果這個(gè)節(jié)點(diǎn)的類型已經(jīng)是樹節(jié)點(diǎn)的話，直接調(diào)用樹節(jié)點(diǎn)的插入 方法進(jìn)行插入新的值。
get 方法源碼分析
get 方法比較簡(jiǎn)單，給定一個(gè) key 來確定 value 的時(shí)候，必須滿足兩個(gè)條件 key 相同 hash 值相同，對(duì)于節(jié)點(diǎn)可能在鏈表或樹上的情況，需要分別去查找。
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
//計(jì)算 hash 值
int h = spread(key.hashCode());
//如果整個(gè)數(shù)組是空的，或者當(dāng)前槽點(diǎn)的數(shù)據(jù)是空的，說明 key 對(duì)應(yīng)的 value 不存在，直接返回 null
/*根據(jù)hash值確定節(jié)點(diǎn)位置*/
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
//判斷頭結(jié)點(diǎn)是否就是我們需要的節(jié)點(diǎn)，如果是則直接返回
/*Node數(shù)組中的節(jié)點(diǎn)就是要找的節(jié)點(diǎn)*/
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
//如果頭結(jié)點(diǎn) hash 值小于 0，說明是紅黑樹或者正在擴(kuò)容，就用對(duì)應(yīng)的 find 方法來查找
/*eh<0 說明這個(gè)節(jié)點(diǎn)在樹上 調(diào)用樹的find方法尋找*/
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
//遍歷鏈表來查找
/*到這一步說明是個(gè)鏈表，遍歷鏈表找到對(duì)應(yīng)的值并返回*/
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
總結(jié)一下 get 的過程：
- 計(jì)算 Hash 值，并由此值找到對(duì)應(yīng)的槽點(diǎn)；
- 如果數(shù)組是空的或者該位置為 null，那么直接返回 null 就可以了；
- 如果該位置處的節(jié)點(diǎn)剛好就是我們需要的，直接返回該節(jié)點(diǎn)的值；
- 如果該位置節(jié)點(diǎn)是紅黑樹或者正在擴(kuò)容，就用 find 方法繼續(xù)查找；
- 否則那就是鏈表，就進(jìn)行遍歷鏈表查找。
對(duì)比Java7 和Java8 的異同和優(yōu)缺點(diǎn)
數(shù)據(jù)結(jié)構(gòu)
，Java 7 采用 Segment 分段鎖來實(shí)現(xiàn)，而 Java 8 中的 ConcurrentHashMap 使用數(shù)組 + 鏈表 + 紅黑樹，在這一點(diǎn)上它們的差別非常大。
并發(fā)度
Java 7 中，每個(gè) Segment 獨(dú)立加鎖，最大并發(fā)個(gè)數(shù)就是 Segment 的個(gè)數(shù)，默認(rèn)是 16。
但是到了 Java 8 中，鎖粒度更細(xì)，理想情況下 table 數(shù)組元素的個(gè)數(shù)（也就是數(shù)組長(zhǎng)度）就是其支持并發(fā)的最大個(gè)數(shù)，并發(fā)度比之前有提高。
保證并發(fā)安全的原理
Java 7 采用 Segment 分段鎖來保證安全，而 Segment 是繼承自 ReentrantLock。
Java 8 中放棄了 Segment 的設(shè)計(jì)，采用 Node + CAS + synchronized 保證線程安全。
遇到 Hash 碰撞
Java 7 在 Hash 沖突時(shí)，會(huì)使用拉鏈法，也就是鏈表的形式。
Java 8 先使用拉鏈法，在鏈表長(zhǎng)度超過一定閾值時(shí)，將鏈表轉(zhuǎn)換為紅黑樹，來提高查找效率。
查詢時(shí)間復(fù)雜度
Java 7 遍歷鏈表的時(shí)間復(fù)雜度是 O(n)，n 為鏈表長(zhǎng)度。
Java 8 如果變成遍歷紅黑樹，那么時(shí)間復(fù)雜度降低為 O(log(n))，n 為樹的節(jié)點(diǎn)個(gè)數(shù)。
HashTable
HashTable 容器使用 synchronized 來保證線程安全，但在線程競(jìng)爭(zhēng)激烈的情況下 HashTable 的效率非常低下。因?yàn)楫?dāng)一個(gè)線程訪問 HashTable 的同步方法， 其他線程也訪問 HashTable 的同步方法時(shí)，會(huì)進(jìn)入阻塞或輪詢狀態(tài)。如線程 1 使 用 put 進(jìn)行元素添加，線程 2 不但不能使用 put 方法添加元素，也不能使用 get 方法來獲取元素，所以競(jìng)爭(zhēng)越激烈效率越低。
并發(fā)下的 Map 常見問題匯總
Q：HashMap 和 HashTable 有什么區(qū)別？
A：
①、HashMap 是線程不安全的，HashTable 是線程安全的；
②、由于線程安全，所以 HashTable 的效率比不上 HashMap；
③、HashMap 最多只允許一條記錄的鍵為 null，允許多條記錄的值為 null， 而 HashTable 不允許；
④、HashMap 默認(rèn)初始化數(shù)組的大小為 16，HashTable 為 11，前者擴(kuò)容時(shí)， 擴(kuò)大兩倍，后者擴(kuò)大兩倍+1；
⑤、HashMap 需要重新計(jì)算 hash 值，而 HashTable 直接使用對(duì)象的 hashCode
Q：Java 中的另一個(gè)線程安全的與 HashMap 極其類似的類是什么？同樣是線程安全，它與 HashTable 在線程同步上有什么不同？
A：
ConcurrentHashMap 類（是 Java 并發(fā)包 java.util.concurrent 中提供的一 個(gè)線程安全且高效的 HashMap 實(shí)現(xiàn)）。
HashTable 是使用 synchronize 關(guān)鍵字加鎖的原理（就是對(duì)對(duì)象加鎖）；
而針對(duì) ConcurrentHashMap，在 JDK 1.7 中采用分段鎖的方式；JDK 1.8 中直接采用了 CAS（無鎖算法）+ synchronized，也采用分段鎖的方式并大大縮小了鎖的粒度。
HashMap & ConcurrentHashMap 的區(qū)別？
A：
除了加鎖，原理上無太大區(qū)別。 另外，HashMap 的鍵值對(duì)允許有 null，但是 ConCurrentHashMap 都不允許。
Q：為什么 ConcurrentHashMap 比 HashTable 效率要高？
A：
HashTable 使用一把鎖（鎖住整個(gè)鏈表結(jié)構(gòu)）處理并發(fā)問題，多個(gè)線程競(jìng)爭(zhēng)一把鎖，容易阻塞；
ConcurrentHashMap
JDK 1.7 中使用分段鎖（ReentrantLock + Segment + HashEntry），相當(dāng)于把一 個(gè) HashMap 分成多個(gè)段，每段分配一把鎖，這樣支持多線程訪問。鎖粒度：基 于 Segment，包含多個(gè) HashEntry。
JDK 1.8 中使用 CAS + synchronized + Node + 紅黑樹。鎖粒度：Node（首結(jié) 點(diǎn)）（實(shí)現(xiàn) Map.Entry<K,V>）。鎖粒度降低了。
Q：針對(duì) ConcurrentHashMap 鎖機(jī)制具體分析（JDK 1.7 VS JDK 1.8）？
A：
JDK 1.7 中，采用分段鎖的機(jī)制，實(shí)現(xiàn)并發(fā)的更新操作，底層采用數(shù)組+鏈表的存儲(chǔ)結(jié)構(gòu)，包括兩個(gè)核心靜態(tài)內(nèi)部類 Segment 和 HashEntry。
①、Segment 繼承 ReentrantLock（重入鎖） 用來充當(dāng)鎖的角色，每個(gè) Segment 對(duì)象守護(hù)每個(gè)散列映射表的若干個(gè)桶；
②、HashEntry 用來封裝映射表的鍵-值對(duì)；
③、每個(gè)桶是由若干個(gè) HashEntry 對(duì)象鏈接起來的鏈表。
JDK 1.8 中，采用 Node + CAS + Synchronized 來保證并發(fā)安全。取消類 Segment，直接用 table 數(shù)組存儲(chǔ)鍵值對(duì)；當(dāng) HashEntry 對(duì)象組成的鏈表長(zhǎng)度超 過 TREEIFY_THRESHOLD 時(shí)，鏈表轉(zhuǎn)換為紅黑樹，提升性能。底層變更為數(shù)組 + 鏈表 + 紅黑樹。
Q：ConcurrentHashMap 在 JDK 1.8 中，為什么要使用內(nèi)置鎖 synchronized 來代替重入鎖 ReentrantLock？
A：
1、JVM 開發(fā)團(tuán)隊(duì)在 1.8 中對(duì) synchronized 做了大量性能上的優(yōu)化，而且基于 JVM 的 synchronized 優(yōu)化空間更大，更加自然。
2、在大量的數(shù)據(jù)操作下，對(duì)于 JVM 的內(nèi)存壓力，基于 API 的 ReentrantLock 會(huì)開銷更多的內(nèi)存。
Q：ConcurrentHashMap 簡(jiǎn)單介紹？
A：
①、重要的常量：
private transient volatile int sizeCtl;
當(dāng)為負(fù)數(shù)時(shí)，-1 表示正在初始化，-N 表示 N - 1 個(gè)線程正在進(jìn)行擴(kuò)容； 當(dāng)為 0 時(shí)，表示 table 還沒有初始化； 當(dāng)為其他正數(shù)時(shí)，表示初始化或者下一次進(jìn)行擴(kuò)容的大小。
②、數(shù)據(jù)結(jié)構(gòu)：
Node 是存儲(chǔ)結(jié)構(gòu)的基本單元，繼承 HashMap 中的 Entry，用于存儲(chǔ)數(shù)據(jù)； TreeNode 繼承 Node，但是數(shù)據(jù)結(jié)構(gòu)換成了二叉樹結(jié)構(gòu)，是紅黑樹的存儲(chǔ)結(jié)構(gòu)，用于紅黑樹中存儲(chǔ)數(shù)據(jù)；
TreeBin 是封裝 TreeNode 的容器，提供轉(zhuǎn)換紅黑樹的一些條件和鎖的控制。
③、存儲(chǔ)對(duì)象時(shí)（put() 方法）：
- 如果沒有初始化，就調(diào)用 initTable() 方法來進(jìn)行初始化；
- 如果沒有 hash 沖突就直接 CAS 無鎖插入；
- 如果需要擴(kuò)容，就先進(jìn)行擴(kuò)容；
- 如果存在 hash 沖突，就加鎖來保證線程安全，兩種情況：一種是鏈表形式就直接遍歷到尾端插入，一種是紅黑樹就按照紅黑樹結(jié)構(gòu)插入；
- 如果該鏈表的數(shù)量大于閥值 8，就要先轉(zhuǎn)換成紅黑樹的結(jié)構(gòu)，break 再一次進(jìn)入循環(huán)
- 如果添加成功就調(diào)用 addCount() 方法統(tǒng)計(jì) size，并且檢查是否需要擴(kuò)容。
④、擴(kuò)容方法 transfer()：默認(rèn)容量為 16，擴(kuò)容時(shí)，容量變?yōu)樵瓉淼膬杀丁?helpTransfer()：調(diào)用多個(gè)工作線程一起幫助進(jìn)行擴(kuò)容，這樣的效率就會(huì)更高。
⑤、獲取對(duì)象時(shí)（get()方法）：
- 計(jì)算 hash 值，定位到該 table 索引位置，如果是首結(jié)點(diǎn)符合就返回；
- 如果遇到擴(kuò)容時(shí)，會(huì)調(diào)用標(biāo)記正在擴(kuò)容結(jié)點(diǎn) ForwardingNode.find()方法， 查找該結(jié)點(diǎn)，匹配就返回；
- 以上都不符合的話，就往下遍歷結(jié)點(diǎn)，匹配就返回，否則最后就返回 null。
Q：ConcurrentHashMap 的并發(fā)度是什么？
A：
1.7 中程序運(yùn)行時(shí)能夠同時(shí)更新 ConccurentHashMap 且不產(chǎn)生鎖競(jìng)爭(zhēng)的最大線程數(shù)。默認(rèn)為 16，且可以在構(gòu)造函數(shù)中設(shè)置。當(dāng)用戶設(shè)置并發(fā)度時(shí)， ConcurrentHashMap 會(huì)使用大于等于該值的最小 2 冪指數(shù)作為實(shí)際并發(fā)度（假如 用戶設(shè)置并發(fā)度為 17，實(shí)際并發(fā)度則為 32）。
1.8 中并發(fā)度則無太大的實(shí)際意義了，主要用處就是當(dāng)設(shè)置的初始容量小于并發(fā)度，將初始容量提升至并發(fā)度大小。
