ConcurrentHashMap的實現(xiàn)原理（JDK1.7和JDK1.8）
點擊上方藍色字體，選擇“標星公眾號”
優(yōu)質(zhì)文章，第一時間送達
JDK1.8之前
HashMap的底層是數(shù)組+鏈表結(jié)合在一起使用。
1、HashMap 通過 key 的hashCode 經(jīng)過哈希函數(shù)處理過后得到 hash 值；
2、然后通過 (n - 1) & hash 判斷當(dāng)前元素存放的位置（n 指的是數(shù)組的長度）；
3、如果當(dāng)前位置存在元素的話，就判斷該元素與要存入的元素的 hash值以及 key是否相同；
4、如果相同的話，直接覆蓋；
5、不相同就通過拉鏈法解決沖突。
JDK1.8之后
HashMap的底層數(shù)據(jù)結(jié)構(gòu)為數(shù)組+鏈表+紅黑樹實現(xiàn)
當(dāng)鏈表的長度大于閾值（默認為8）時，將鏈表轉(zhuǎn)化為紅黑樹，以減少搜索的時間。
將鏈表轉(zhuǎn)換成紅黑樹前會判斷，如果當(dāng)前數(shù)組的長度小于 64，那么會選擇先進行數(shù)組擴容，而不是轉(zhuǎn)換為紅黑樹。
ConcurrentHashMap
JDK5中添加了新的concurrent包，在線程安全的基礎(chǔ)上提供了更好的寫并發(fā)能力，但同時降低了對讀一致性的要求。
ConcurrentHashMap是java.util.concurrent下的類；
在并發(fā)編程中，ConcurrentHashMap是一個經(jīng)常被使用的數(shù)據(jù)結(jié)構(gòu)，它的實際與實現(xiàn)非常精巧，大量利用volatile，final，CAS等技術(shù)來減少鎖競爭對于性能的影響。
簡單的對比
HashTable 是一個線程安全的類，它使用synchronized來鎖住整張Hash表來實現(xiàn)線程安全，每次鎖住整張表讓線程獨占，相當(dāng)于所有線程進行讀寫時都去競爭同一把鎖，效率比較低
HashMap 不是一個線程安全的類
ConcurrentHashMap可以做到讀取數(shù)據(jù)不加鎖，并且其內(nèi)部的結(jié)構(gòu)可以讓其在進行寫操作的時候能夠?qū)㈡i的粒度保持地盡量地小，允許多個修改操作并發(fā)進行，其關(guān)鍵在于使用了鎖分離技術(shù)。它使用了多個鎖來控制對hash表的不同部分進行的修改。只要不爭奪同一把鎖，它們就可以并發(fā)進行。
JDK1.7
1、底層的數(shù)據(jù)結(jié)構(gòu)還是數(shù)組+鏈表。鏈表的結(jié)點是HashEntry
2、采用了segment分段鎖技術(shù)，在多線程并發(fā)更新操作時，對同一個segment進行同步加3 鎖，保證數(shù)據(jù)安全。
3、同步的實現(xiàn)方式使基于ReentrantLock（Segment繼承自ReentrantLock）
4、存在Hash沖突時，鏈表的查詢效率低
JDK1.8
ContcurrentHashMap基于JDK1.8的源碼剖析
底層的數(shù)據(jù)結(jié)構(gòu)與HashMap1.8版本一樣，都是基于數(shù)組+鏈表+紅黑樹
支持多線程的并發(fā)操作，實現(xiàn)的原理是CAS+synchronized保證并發(fā)更新
檢索操作不用加鎖，get方法是非阻塞的
put方法
public V put(K key, V value) {
//實際調(diào)用的是putVal(key,value,false)
//無論key在表中所對應(yīng)的值是否存在，都使用value進行更新
return putVal(key, value, false);
}
/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
//key和value的值必須是非null的
if (key == null || value == null) throw new NullPointerException();
//計算key的hash值用來定位元素的位置
int hash = spread(key.hashCode());
int binCount = 0;
//table 引用指向的是ConcurrentHashMap中 所有元素所存在的數(shù)組的引用 所以下面依次將遍歷
for (ConcurrentHashMap.Node<K,V>[] tab = table;;) {
ConcurrentHashMap.Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable();//table為空，則初始化table，首次初始化默認的數(shù)組長度為16
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// 判斷key對應(yīng)的數(shù)組位置上是否為null，若尚未發(fā)生hash碰撞，即進行CAS操作，new 一個 Node<K,V>存放到tab中，退出for循環(huán)；
if (casTabAt(tab, i, null,
new ConcurrentHashMap.Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
//判斷是否需要擴容
else if ((fh = f.hash) == MOVED) // MOVED = -1
tab = helpTransfer(tab, f);
else {
V oldVal = null;
synchronized (f) {//加鎖
if (tabAt(tab, i) == f) {
if (fh >= 0) {//當(dāng)作鏈表處理
binCount = 1;
for (ConcurrentHashMap.Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {// key 存在，更新
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
ConcurrentHashMap.Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new ConcurrentHashMap.Node<K,V>(hash, key,
value, null);//key 不存在，鏈表中追加新元素
break;
}
}
}
//按照紅黑樹的方式進行插入
else if (f instanceof ConcurrentHashMap.TreeBin) {
ConcurrentHashMap.Node<K,V> p;
binCount = 2;
//key不存在則putTreeVal方法直接添加新元素并返回null，key存在則返回對應(yīng)節(jié)點p并做val更新
if ((p = ((ConcurrentHashMap.TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
//當(dāng)插入鏈表后值大于8的時候要轉(zhuǎn)為紅黑樹
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
//size++
addCount(1L, binCount);
return null;
}
put方法流程圖
1.7和1.8版本都存在的特性
ConcurrentHashMap的key和value都不能為null
鍵值迭代器為弱一致性迭代器，創(chuàng)建迭代器后，可以對元素進行更新，對元素更新不會影響遍歷；
讀操作沒有加鎖，value是voliate修飾的，保證了可見性
讀寫分離提高效率：多線程對不同的Node/Segment 的插入和刪除是可以并發(fā)、并行執(zhí)行的，對同一個Node/Segment的寫操作是互斥的。讀操作都是無鎖的操作，可以并發(fā)、并行執(zhí)行。
HashMap，HashTable和ConcurrentHashMap的區(qū)別：
————————————————
版權(quán)聲明：本文為CSDN博主「小王～同學(xué)」的原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請附上原文出處鏈接及本聲明。
原文鏈接：
https://blog.csdn.net/qq_45754055/article/details/115592109
粉絲福利：Java從入門到入土學(xué)習(xí)路線圖
??????
??長按上方微信二維碼 2 秒
感謝點贊支持下哈 