一、引言
ConcurrentHashMap技術在網際網路技術使用如此廣泛,幾乎所有的後端技術面試官都要在ConcurrentHashMap技術的使用和原理方面對小夥伴們進行 360° 的刁難。
作為一個在網際網路公司面一次拿一次 Offer 的面霸,打敗了無數競争對手,每次都隻能看到無數落寞的身影失望的離開,略感愧疚(請允許我使用一下誇張的修辭手法)。
于是在一個寂寞難耐的夜晚,暖男我痛定思痛,決定開始寫 《吊打面試官》 系列,希望能幫助各位讀者以後面試勢如破竹,對面試官進行 360° 的反擊,吊打問你的面試官,讓一同面試的同僚瞠目結舌,瘋狂收割大廠 Offer!
雖然現在是網際網路寒冬,但乾坤未定,你我皆是黑馬
二、使用
我們經常線上程安全的場景下使用 ConcurrentHashMap,基本使用如下:
java複制代碼public class ConcurrentHashMapTest {
public static void main(String[] args) {
ConcurrentHashMap<String, String> map = new ConcurrentHashMap<>();
map.put("test1", "1");
map.put("test2", "2");
map.put("test3", "3");
map.remove("test1");
System.out.println(map.get("test1"));
System.out.println(map.get("test2"));
}
}
使用的話,我相信大部分的讀者應該都會的,這裡小黃也不多介紹了,我們直接進入正題
三、源碼
1、初始化
還是我們的老樣子,從初始化開始聊源碼
如果我們初始化時不攜帶入參的話,初始化方法如下:可以看到,基本沒有什麼東西
java複制代碼public ConcurrentHashMap() {}
如果你攜帶了入參的話,初始化方法如下:
java複制代碼public ConcurrentHashMap(int initialCapacity) {
// 假如哥們傳進來入參小于0
if (initialCapacity < 0)
// 直接抛出異常,說明哥們在搞笑
throw new IllegalArgumentException();
// 用傳進來的數值與 MAXIMUM_CAPACITY >>> 1 進行對比
// 若大于則使用MAXIMUM_CAPACITY
// 小于則使用距離initialCapacity最近的2次幂
int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
MAXIMUM_CAPACITY :
tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
this.sizeCtl = cap;
}
// 根據傳進的C的數值,找到其距離最近的2次幂
private static final int tableSizeFor(int c) {
int n = c - 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;
}
2、存儲操作
java複制代碼public V put(K key, V value) {
// 在調用put方法時,會調用putVal,第三個參數預設傳遞為false
// 在調用putIfAbsent時,會調用putVal方法,第三個參數傳遞的為true
// 如果傳遞為false,代表key一緻時,直接覆寫資料
// 如果傳遞為true,代表key一緻時,什麼都不做,key不存在,正常添加(Redis,setnx)
return putVal(key, value, false);
}
2.1 計算索引下标
java複制代碼final V putVal(K key, V value, boolean onlyIfAbsent) {
// 如果目前的key或者value是空的話,直接抛出異常
if (key == null || value == null){
throw new NullPointerException();
}
// 擷取其下标
int hash = spread(key.hashCode());
int binCount = 0;
}
// 作用:用高16位與低16位進行^運算,讓高位的數值可以進行計算
// 為什麼原來的高位沒有辦法計算呢?
// 我們後面的 (n - 1) & hash 的資料,&資料如下:
// 00000000 00000000 00000000 01010101
// 0000000 00000000 00000000 00011111
// 我們這裡看到,如果高16位不與低16位^運算的話,那麼基本我們的高位永遠也參加不了計算
// 為什麼需要&HASH_BITS:
// 保證最終的結果大于0,因為如果結果小于0的話,代表不同的意義:
// static final int MOVED = -1; // 代表目前hash位置的資料正在擴容!
// static final int TREEBIN = -2; // 代表目前hash位置下挂載的是一個紅黑樹
// static final int RESERVED = -3; // 預留目前索引位置……
static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;
}
2.2 初始化數組
java複制代碼// tab指向table,标準的Doug Lea寫法
for (Node<K,V>[] tab = table;;) {
Node<K,V> f;
int n, i, fh;
// 如果目前的數組為空或者他的數組長度為0
// 則進行初始化
if (tab == null || (n = tab.length) == 0){
tab = initTable();
}
}
// sizeCtl:是數組在初始化和擴容操作時的一個控制變量
// -1:代表目前數組正在初始化
// 小于-1:低16位代表目前數組正在擴容的線程個數(如果1個線程擴容,值為-2,如果2個線程擴容,值為-3)
// 0:代表數組還沒初始化
// 大于0:代表目前數組的擴容門檻值,或者是目前數組的初始化大小
private final Node<K,V>[] initTable() {
// 經典引用
Node<K,V>[] tab;
int sc;
// 目前的初始化沒有完成時,會一直進行該while循環
while ((tab = table) == null || tab.length == 0) {
// 如果小于0,代表目前數組正在擴容或者初始化
// 目前線程等待一下
if ((sc = sizeCtl) < 0)
Thread.yield();
// 嘗試将SIZECTL從SC更改為-1
// CAS修改,線程安全,保證隻有一個線程執行數組初始化
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
// 更改成功,再次判斷一下(參考DCL)
// 防止下面sizeCtl = sc剛指派完,正好有線程走到這一步,不做限制的話就會重新初始化了
if ((tab = table) == null || tab.length == 0) {
// 判斷目前的sc是否大于0(sc=SIZECTL)
// 大于0:n = sc
// 小于等于0:n = DEFAULT_CAPACITY
// 一般我們隻要不傳入入參,這裡基本走DEFAULT_CAPACITY的擴容
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
// 擴容即可
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
// table、tab指派
table = tab = nt;
// 這裡有點意思
// 将sc指派成(n - 1/4n) = 0.75N
// 這裡0.75是不是很熟悉,負載因子
sc = n - (n >>> 2);
}
} finally {
// 将上面的擴容門檻值賦予sizeCtl
sizeCtl = sc;
}
// 結束循環
break;
}
}
return tab;
}
2.3 将資料插入到數組
java複制代碼// 如果目前數組該下标沒有資料,直接插入即可
if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// CAS将目前的hash、key、value組裝成一個Node,插入目前數組i位置
// 插入成功結束即可
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))){
break;
}
}
// 基于我們上面說的(n - 1) & hash算出下标
// 傳回目前數組下該下标的資料
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);
}
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);
}
static class Node<K,V> implements Map.Entry<K,V> {
// 目前的hash值
final int hash;
// key
final K key;
// value
volatile V val;
// 下一個節點(用來連連結清單的)
volatile Node<K,V> next;
}
2.4 擴容(後面聊)
- 這部分後面聊
java複制代碼// 判斷目前位置資料是否正在擴容……
if ((fh = f.hash) == MOVED)
// 如果在擴容,則目前線程幫助其擴容
tab = helpTransfer(tab, f);
2.5 将資料插入到連結清單
java複制代碼else {
V oldVal = null;
// 鎖目前的數組下标i的數組塊
synchronized (f) {
// 看一下目前數組的i位置是不是等于f
// 相當于再次校驗一次(DCL)
if (tabAt(tab, i) == f) {
// static final int MOVED = -1; // 代表目前hash位置的資料正在擴容!
// static final int TREEBIN = -2; // 代表目前hash位置下挂載的是一個紅黑樹
// static final int RESERVED = -3; // 預留目前索引位置……
// fh = f.hash
// 判斷下目前的fh是否大于0,也就是不是上面三種情況
if (fh >= 0) {
// 記錄目前連結清單下面挂了幾個
binCount = 1;
// 擷取目前的數組節點,沒循環一次binCount加一
for (Node<K,V> e = f;; ++binCount) {
K ek;
// 如果目前數組下标的hash和我們入參的hash一樣,代表重複資料
if (e.hash == hash &&
// 如果目前的key也等于原始的key
// 或者是根據equals判斷出來的相等(因為有一些可能重寫了equals方法)
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
// 将目前老的資料指派給oldVal
oldVal = e.val;
// 這裡的onlyIfAbsent我們之前也聊過
// 如果傳遞為false,代表key一緻時,直接覆寫資料
// 如果傳遞為true,代表key一緻時,什麼都不做,key不存在,正常添加(Redis,setnx)
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;
}
}
}
}
2.6 将資料插入到紅黑樹
java複制代碼 // 如果上面不成立的話,也就是目前的數組下面是一個紅黑樹
// 需要将目前的資料放到紅黑樹裡面
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;
// 這裡的onlyIfAbsent我們之前也聊過
// 如果傳遞為false,代表key一緻時,直接覆寫資料
// 如果傳遞為true,代表key一緻時,什麼都不做,key不存在,正常添加(Redis,setnx)
if (!onlyIfAbsent)
// 覆寫資料
p.val = value;
}
}
2.7 連結清單轉紅黑樹
java複制代碼// 如果目前的連結清單上的資料不等于0
if (binCount != 0) {
// 目前清單下的資料長度大于8
// 這裡需要注意,大于8的話并不是立即轉成紅黑樹,還需要判斷目前數組的長度
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
static final int TREEIFY_THRESHOLD = 8;
static final int MIN_TREEIFY_CAPACITY = 64;
private final void treeifyBin(Node<K,V>[] tab, int index) {
Node<K,V> b; int n, sc;
// 如果目前的數組不為空
if (tab != null) {
// 如果目前的數組長度小于64,則沒必要轉成紅黑樹
// 直接擴容即可
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
tryPresize(n << 1);
// 後面的是轉成紅黑樹的代碼
// 我們下一章在分析
else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
synchronized (b) {
if (tabAt(tab, index) == b) {
TreeNode<K,V> hd = null, tl = null;
for (Node<K,V> e = b; e != null; e = e.next) {
TreeNode<K,V> p = new TreeNode<K,V>(e.hash, e.key, e.val, null, null);
if ((p.prev = tl) == null){
hd = p;
}
else{
tl.next = p;
}
tl = p;
}
setTabAt(tab, index, new TreeBin<K,V>(hd));
}
}
}
}
}
四、流程圖
1、初始化階段
2、存儲階段
五、總結
魯迅先生曾說:獨行難,衆行易,和志同道合的人一起進步。彼此毫無保留的分享經驗,才是對抗網際網路寒冬的最佳選擇。
其實很多時候,并不是我們不夠努力,很可能就是自己努力的方向不對,如果有一個人能稍微指點你一下,你真的可能會少走幾年彎路。