前言
Map 這樣的 Key Value 在軟件開發(fā)中是非常經(jīng)典的結(jié)構(gòu)，常用于在內(nèi)存中存放數(shù)據(jù)瘫想。
本篇主要想討論 ConcurrentHashMap 這樣一個(gè)并發(fā)容器仗阅，在正式開始之前我覺得有必要談?wù)?HashMap，沒有它就不會(huì)有后面的 ConcurrentHashMap殿托。
HashMap
眾所周知 HashMap 底層是基于 數(shù)組 + 鏈表 組成的霹菊，不過在 jdk1.7 和 1.8 中具體實(shí)現(xiàn)稍有不同。
Base 1.7
1.7 中的數(shù)據(jù)結(jié)構(gòu)圖：
先來看看 1.7 中的實(shí)現(xiàn)支竹。
這是 HashMap 中比較核心的幾個(gè)成員變量旋廷；看看分別是什么意思？
- 初始化桶大小礼搁，因?yàn)榈讓邮菙?shù)組饶碘，所以這是數(shù)組默認(rèn)的大小。
- 桶最大值馒吴。
- 默認(rèn)的負(fù)載因子（0.75）
-
table真正存放數(shù)據(jù)的數(shù)組扎运。 -
Map存放數(shù)量的大小。 - 桶大小饮戳，可在初始化時(shí)顯式指定豪治。
- 負(fù)載因子，可在初始化時(shí)顯式指定扯罐。
重點(diǎn)解釋下負(fù)載因子：
由于給定的 HashMap 的容量大小是固定的负拟，比如默認(rèn)初始化：
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
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;
threshold = initialCapacity;
init();
}
給定的默認(rèn)容量為 16，負(fù)載因子為 0.75歹河。Map 在使用過程中不斷的往里面存放數(shù)據(jù)掩浙，當(dāng)數(shù)量達(dá)到了 16 * 0.75 = 12 就需要將當(dāng)前 16 的容量進(jìn)行擴(kuò)容，而擴(kuò)容這個(gè)過程涉及到 rehash秸歧、復(fù)制數(shù)據(jù)等操作厨姚，所以非常消耗性能。
因此通常建議能提前預(yù)估 HashMap 的大小最好键菱，盡量的減少擴(kuò)容帶來的性能損耗谬墙。
根據(jù)代碼可以看到其實(shí)真正存放數(shù)據(jù)的是
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
這個(gè)數(shù)組，那么它又是如何定義的呢？
Entry 是 HashMap 中的一個(gè)內(nèi)部類芭梯，從他的成員變量很容易看出：
- key 就是寫入時(shí)的鍵险耀。
- value 自然就是值。
- 開始的時(shí)候就提到 HashMap 是由數(shù)組和鏈表組成玖喘，所以這個(gè) next 就是用于實(shí)現(xiàn)鏈表結(jié)構(gòu)甩牺。
- hash 存放的是當(dāng)前 key 的 hashcode。
知曉了基本結(jié)構(gòu)累奈，那來看看其中重要的寫入贬派、獲取函數(shù)：
put 方法
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
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;
}
- 判斷當(dāng)前數(shù)組是否需要初始化。
- 如果 key 為空澎媒，則 put 一個(gè)空值進(jìn)去搞乏。
- 根據(jù) key 計(jì)算出 hashcode。
- 根據(jù)計(jì)算出的 hashcode 定位出所在桶戒努。
- 如果桶是一個(gè)鏈表則需要遍歷判斷里面的 hashcode请敦、key 是否和傳入 key 相等，如果相等則進(jìn)行覆蓋储玫，并返回原來的值侍筛。
- 如果桶是空的，說明當(dāng)前位置沒有數(shù)據(jù)存入撒穷；新增一個(gè) Entry 對(duì)象寫入當(dāng)前位置匣椰。
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
當(dāng)調(diào)用 addEntry 寫入 Entry 時(shí)需要判斷是否需要擴(kuò)容。
如果需要就進(jìn)行兩倍擴(kuò)充端礼，并將當(dāng)前的 key 重新 hash 并定位禽笑。
而在 createEntry 中會(huì)將當(dāng)前位置的桶傳入到新建的桶中，如果當(dāng)前桶有值就會(huì)在位置形成鏈表蛤奥。
get 方法
再來看看 get 函數(shù)：
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
- 首先也是根據(jù) key 計(jì)算出 hashcode佳镜，然后定位到具體的桶中。
- 判斷該位置是否為鏈表凡桥。
- 不是鏈表就根據(jù)
key蟀伸、key 的 hashcode是否相等來返回值。 - 為鏈表則需要遍歷直到 key 及 hashcode 相等時(shí)候就返回值唬血。
- 啥都沒取到就直接返回 null 望蜡。
Base 1.8
不知道 1.7 的實(shí)現(xiàn)大家看出需要優(yōu)化的點(diǎn)沒有唤崭？
其實(shí)一個(gè)很明顯的地方就是：
當(dāng) Hash 沖突嚴(yán)重時(shí)拷恨，在桶上形成的鏈表會(huì)變的越來越長(zhǎng)，這樣在查詢時(shí)的效率就會(huì)越來越低谢肾；時(shí)間復(fù)雜度為
O(N)腕侄。
因此 1.8 中重點(diǎn)優(yōu)化了這個(gè)查詢效率。
1.8 HashMap 結(jié)構(gòu)圖：
先來看看幾個(gè)核心的成員變量：
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int TREEIFY_THRESHOLD = 8;
transient Node<K,V>[] table;
/**
* Holds cached entrySet(). Note that AbstractMap fields are used
* for keySet() and values().
*/
transient Set<Map.Entry<K,V>> entrySet;
/**
* The number of key-value mappings contained in this map.
*/
transient int size;
和 1.7 大體上都差不多，還是有幾個(gè)重要的區(qū)別：
-
TREEIFY_THRESHOLD用于判斷是否需要將鏈表轉(zhuǎn)換為紅黑樹的閾值冕杠。 - HashEntry 修改為 Node微姊。
Node 的核心組成其實(shí)也是和 1.7 中的 HashEntry 一樣，存放的都是 key value hashcode next 等數(shù)據(jù)分预。
再來看看核心方法兢交。
put 方法
看似要比 1.7 的復(fù)雜，我們一步步拆解：
- 判斷當(dāng)前桶是否為空笼痹，空的就需要初始化（resize 中會(huì)判斷是否進(jìn)行初始化）配喳。
- 根據(jù)當(dāng)前 key 的 hashcode 定位到具體的桶中并判斷是否為空，為空表明沒有 Hash 沖突就直接在當(dāng)前位置創(chuàng)建一個(gè)新桶即可凳干。
- 如果當(dāng)前桶有值（ Hash 沖突）晴裹，那么就要比較當(dāng)前桶中的
key、key 的 hashcode與寫入的 key 是否相等救赐，相等就賦值給e,在第 8 步的時(shí)候會(huì)統(tǒng)一進(jìn)行賦值及返回涧团。 - 如果當(dāng)前桶為紅黑樹，那就要按照紅黑樹的方式寫入數(shù)據(jù)经磅。
- 如果是個(gè)鏈表泌绣，就需要將當(dāng)前的 key、value 封裝成一個(gè)新節(jié)點(diǎn)寫入到當(dāng)前桶的后面（形成鏈表）馋贤。
- 接著判斷當(dāng)前鏈表的大小是否大于預(yù)設(shè)的閾值赞别，大于時(shí)就要轉(zhuǎn)換為紅黑樹。
- 如果在遍歷過程中找到 key 相同時(shí)直接退出遍歷配乓。
- 如果
e != null就相當(dāng)于存在相同的 key,那就需要將值覆蓋仿滔。 - 最后判斷是否需要進(jìn)行擴(kuò)容。
get 方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
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 &&
(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;
}
get 方法看起來就要簡(jiǎn)單許多了犹芹。
- 首先將 key hash 之后取得所定位的桶崎页。
- 如果桶為空則直接返回 null 。
- 否則判斷桶的第一個(gè)位置(有可能是鏈表腰埂、紅黑樹)的 key 是否為查詢的 key飒焦，是就直接返回 value。
- 如果第一個(gè)不匹配屿笼，則判斷它的下一個(gè)是紅黑樹還是鏈表牺荠。
- 紅黑樹就按照樹的查找方式返回值。
- 不然就按照鏈表的方式遍歷匹配返回值驴一。
從這兩個(gè)核心方法（get/put）可以看出 1.8 中對(duì)大鏈表做了優(yōu)化休雌，修改為紅黑樹之后查詢效率直接提高到了 O(logn)。
但是 HashMap 原有的問題也都存在肝断，比如在并發(fā)場(chǎng)景下使用時(shí)容易出現(xiàn)死循環(huán)杈曲。
final HashMap<String, String> map = new HashMap<String, String>();
for (int i = 0; i < 1000; i++) {
new Thread(new Runnable() {
@Override
public void run() {
map.put(UUID.randomUUID().toString(), "");
}
}).start();
}
但是為什么呢驰凛？簡(jiǎn)單分析下。
看過上文的還記得在 HashMap 擴(kuò)容的時(shí)候會(huì)調(diào)用 resize() 方法担扑，就是這里的并發(fā)操作容易在一個(gè)桶上形成環(huán)形鏈表恰响；這樣當(dāng)獲取一個(gè)不存在的 key 時(shí)，計(jì)算出的 index 正好是環(huán)形鏈表的下標(biāo)就會(huì)出現(xiàn)死循環(huán)涌献。
如下圖：
遍歷方式
還有一個(gè)值得注意的是 HashMap 的遍歷方式胚宦，通常有以下幾種：
Iterator<Map.Entry<String, Integer>> entryIterator = map.entrySet().iterator();
while (entryIterator.hasNext()) {
Map.Entry<String, Integer> next = entryIterator.next();
System.out.println("key=" + next.getKey() + " value=" + next.getValue());
}
Iterator<String> iterator = map.keySet().iterator();
while (iterator.hasNext()){
String key = iterator.next();
System.out.println("key=" + key + " value=" + map.get(key));
}
強(qiáng)烈建議使用第一種 EntrySet 進(jìn)行遍歷。
第一種可以把 key value 同時(shí)取出燕垃，第二種還得需要通過 key 取一次 value间唉，效率較低。
簡(jiǎn)單總結(jié)下 HashMap：無論是 1.7 還是 1.8 其實(shí)都能看出 JDK 沒有對(duì)它做任何的同步操作利术，所以并發(fā)會(huì)出問題呈野，甚至出現(xiàn)死循環(huán)導(dǎo)致系統(tǒng)不可用。
因此 JDK 推出了專項(xiàng)專用的 ConcurrentHashMap 印叁，該類位于 java.util.concurrent 包下被冒，專門用于解決并發(fā)問題。
堅(jiān)持看到這里的朋友算是已經(jīng)把 ConcurrentHashMap 的基礎(chǔ)已經(jīng)打牢了轮蜕，下面正式開始分析昨悼。
ConcurrentHashMap
ConcurrentHashMap 同樣也分為 1.7 、1.8 版跃洛，兩者在實(shí)現(xiàn)上略有不同率触。
Base 1.7
先來看看 1.7 的實(shí)現(xiàn)，下面是他的結(jié)構(gòu)圖：
如圖所示汇竭，是由 Segment 數(shù)組葱蝗、HashEntry 組成，和 HashMap 一樣细燎，仍然是數(shù)組加鏈表两曼。
它的核心成員變量：
/**
* Segment 數(shù)組，存放數(shù)據(jù)時(shí)首先需要定位到具體的 Segment 中玻驻。
*/
final Segment<K,V>[] segments;
transient Set<K> keySet;
transient Set<Map.Entry<K,V>> entrySet;
Segment 是 ConcurrentHashMap 的一個(gè)內(nèi)部類悼凑，主要的組成如下：
static final class Segment<K,V> extends ReentrantLock implements Serializable {
private static final long serialVersionUID = 2249069246763182397L;
// 和 HashMap 中的 HashEntry 作用一樣，真正存放數(shù)據(jù)的桶
transient volatile HashEntry<K,V>[] table;
transient int count;
transient int modCount;
transient int threshold;
final float loadFactor;
}
看看其中 HashEntry 的組成：
和 HashMap 非常類似璧瞬，唯一的區(qū)別就是其中的核心數(shù)據(jù)如 value 户辫，以及鏈表都是 volatile 修飾的，保證了獲取時(shí)的可見性嗤锉。
原理上來說：ConcurrentHashMap 采用了分段鎖技術(shù)渔欢，其中 Segment 繼承于 ReentrantLock。不會(huì)像 HashTable 那樣不管是 put 還是 get 操作都需要做同步處理档冬，理論上 ConcurrentHashMap 支持 CurrencyLevel (Segment 數(shù)組數(shù)量)的線程并發(fā)膘茎。每當(dāng)一個(gè)線程占用鎖訪問一個(gè) Segment 時(shí)，不會(huì)影響到其他的 Segment酷誓。
下面也來看看核心的 put get 方法披坏。
put 方法
public V put(K key, V value) {
Segment<K,V> s;
if (value == null)
throw new NullPointerException();
int hash = hash(key);
int j = (hash >>> segmentShift) & segmentMask;
if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck
(segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
s = ensureSegment(j);
return s.put(key, hash, value, false);
}
首先是通過 key 定位到 Segment，之后在對(duì)應(yīng)的 Segment 中進(jìn)行具體的 put盐数。
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
HashEntry<K,V> node = tryLock() ? null :
scanAndLockForPut(key, hash, value);
V oldValue;
try {
HashEntry<K,V>[] tab = table;
int index = (tab.length - 1) & hash;
HashEntry<K,V> first = entryAt(tab, index);
for (HashEntry<K,V> e = first;;) {
if (e != null) {
K k;
if ((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
oldValue = e.value;
if (!onlyIfAbsent) {
e.value = value;
++modCount;
}
break;
}
e = e.next;
}
else {
if (node != null)
node.setNext(first);
else
node = new HashEntry<K,V>(hash, key, value, first);
int c = count + 1;
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node);
else
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
unlock();
}
return oldValue;
}
雖然 HashEntry 中的 value 是用 volatile 關(guān)鍵詞修飾的玫氢，但是并不能保證并發(fā)的原子性攻旦，所以 put 操作時(shí)仍然需要加鎖處理。
首先第一步的時(shí)候會(huì)嘗試獲取鎖烙无，如果獲取失敗肯定就有其他線程存在競(jìng)爭(zhēng)截酷，則利用 scanAndLockForPut() 自旋獲取鎖迂苛。
- 嘗試自旋獲取鎖。
- 如果重試的次數(shù)達(dá)到了
MAX_SCAN_RETRIES則改為阻塞鎖獲取，保證能獲取成功锁蠕。
再結(jié)合圖看看 put 的流程。
- 將當(dāng)前 Segment 中的 table 通過 key 的 hashcode 定位到 HashEntry舌仍。
- 遍歷該 HashEntry灌曙，如果不為空則判斷傳入的 key 和當(dāng)前遍歷的 key 是否相等在刺，相等則覆蓋舊的 value。
- 不為空則需要新建一個(gè) HashEntry 并加入到 Segment 中颖杏，同時(shí)會(huì)先判斷是否需要擴(kuò)容。
- 最后會(huì)解除在 1 中所獲取當(dāng)前 Segment 的鎖欲鹏。
get 方法
public V get(Object key) {
Segment<K,V> s; // manually integrate access methods to reduce overhead
HashEntry<K,V>[] tab;
int h = hash(key);
long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
(tab = s.table) != null) {
for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
e != null; e = e.next) {
K k;
if ((k = e.key) == key || (e.hash == h && key.equals(k)))
return e.value;
}
}
return null;
}
get 邏輯比較簡(jiǎn)單：
只需要將 Key 通過 Hash 之后定位到具體的 Segment ，再通過一次 Hash 定位到具體的元素上尤误。
由于 HashEntry 中的 value 屬性是用 volatile 關(guān)鍵詞修飾的，保證了內(nèi)存可見性，所以每次獲取時(shí)都是最新值最冰。
ConcurrentHashMap 的 get 方法是非常高效的暖哨，因?yàn)檎麄€(gè)過程都不需要加鎖沛慢。
Base 1.8
1.7 已經(jīng)解決了并發(fā)問題，并且能支持 N 個(gè) Segment 這么多次數(shù)的并發(fā)，但依然存在 HashMap 在 1.7 版本中的問題。
那就是查詢遍歷鏈表效率太低雕沉。
因此 1.8 做了一些數(shù)據(jù)結(jié)構(gòu)上的調(diào)整。
首先來看下底層的組成結(jié)構(gòu)：
看起來是不是和 1.8 HashMap 結(jié)構(gòu)類似？
其中拋棄了原有的 Segment 分段鎖丈攒，而采用了 CAS + synchronized 來保證并發(fā)安全性。
也將 1.7 中存放數(shù)據(jù)的 HashEntry 改為 Node孕豹，但作用都是相同的。
其中的 val next 都用了 volatile 修飾绞蹦，保證了可見性。
put 方法
重點(diǎn)來看看 put 函數(shù)：
- 根據(jù) key 計(jì)算出 hashcode 猿挚。
- 判斷是否需要進(jìn)行初始化。
-
f即為當(dāng)前 key 定位出的 Node，如果為空表示當(dāng)前位置可以寫入數(shù)據(jù)，利用 CAS 嘗試寫入降淮，失敗則自旋保證成功媒惕。 - 如果當(dāng)前位置的
hashcode == MOVED == -1,則需要進(jìn)行擴(kuò)容淑玫。 - 如果都不滿足，則利用 synchronized 鎖寫入數(shù)據(jù)。
- 如果數(shù)量大于
TREEIFY_THRESHOLD則要轉(zhuǎn)換為紅黑樹但壮。
get 方法
- 根據(jù)計(jì)算出來的 hashcode 尋址溯祸，如果就在桶上那么直接返回值博杖。
- 如果是紅黑樹那就按照樹的方式獲取值。
- 就不滿足那就按照鏈表的方式遍歷獲取值。
1.8 在 1.7 的數(shù)據(jù)結(jié)構(gòu)上做了大的改動(dòng)苗傅，采用紅黑樹之后可以保證查詢效率（
O(logn)）趣竣，甚至取消了 ReentrantLock 改為了 synchronized宵呛，這樣可以看出在新版的 JDK 中對(duì) synchronized 優(yōu)化是很到位的。
總結(jié)
看完了整個(gè) HashMap 和 ConcurrentHashMap 在 1.7 和 1.8 中不同的實(shí)現(xiàn)方式相信大家對(duì)他們的理解應(yīng)該會(huì)更加到位。
其實(shí)這塊也是面試的重點(diǎn)內(nèi)容，通常的套路是：
- 談?wù)勀憷斫獾?HashMap，講講其中的 get put 過程。
- 1.8 做了什么優(yōu)化狂男？
- 是線程安全的嘛？
- 不安全會(huì)導(dǎo)致哪些問題？
- 如何解決？有沒有線程安全的并發(fā)容器？
- ConcurrentHashMap 是如何實(shí)現(xiàn)的？ 1.7、1.8 實(shí)現(xiàn)有何不同？為什么這么做仁锯？
這一串問題相信大家仔細(xì)看完都能懟回面試官。
除了面試會(huì)問到之外平時(shí)的應(yīng)用其實(shí)也蠻多复罐，像之前談到的 Guava 中 Cache 的實(shí)現(xiàn)就是利用 ConcurrentHashMap 的思想乱投。
同時(shí)也能學(xué)習(xí) JDK 作者大牛們的優(yōu)化思路以及并發(fā)解決方案施掏。
其實(shí)寫這篇的前提是源于 GitHub 上的一個(gè) Issues，也希望大家能參與進(jìn)來蔑赘，共同維護(hù)好這個(gè)項(xiàng)目狸驳。
號(hào)外
最近在總結(jié)一些 Java 相關(guān)的知識(shí)點(diǎn)，感興趣的朋友可以一起維護(hù)缩赛。
歡迎關(guān)注公眾號(hào)一起交流：
