0 文章結構
- HashMap 1.7 vs 1.8
- ConcurrentHashMap 1.7 vs 1.8
1 HashMap 1.7 1.8（陣列+鏈表OR紅黑樹）
HashMap 根據鍵的 hashCode 值存盤資料，大多數情況下可以直接定位到它的值，因而具有很快 的訪問速度，但遍歷順序卻是不確定的， HashMap 最多只允許一條記錄的鍵為 null，允許多條記 錄的值為 null，HashMap 非執行緒安全，即任一時刻可以有多個執行緒同時寫 HashMap，可能會導 致資料的不一致， 如果需要滿足執行緒安全， 可以用 Collections 的 synchronizedMap 方法使 HashMap 具有執行緒安全的能力， 或者使用 ConcurrentHashMap，
大方向上，HashMap 里面是一個陣列，然后陣列中每個元素是一個單向鏈表，上圖中，每個綠色 的物體是嵌套類 Entry 的實體，Entry 包含四個屬性：key, value, hash 值和用于單向鏈表的 next，
- capacity：當前陣列容量，始終保持 2^n，可以擴容，擴容后陣列大小為當前的 2 倍，
- loadFactor：負載因子，默認為 0.75，
- threshold：擴容的閾值，等于 capacity * loadFactor
Java8 對 HashMap 進行了一些修改，最大的不同就是利用了紅黑樹，所以其由 陣列+鏈表+紅黑 樹 組成，
根據 Java7 HashMap 的介紹，我們知道，查找的時候，根據 hash 值我們能夠快速定位到陣列的 具體下標，但是之后的話， 需要順著鏈表一個個比較下去才能找到我們需要的，時間復雜度取決 于鏈表的長度，為 O(n)，為了降低這部分的開銷，在 Java8 中，當鏈表中的元素超過了 8 個以后， 會將鏈表轉換為紅黑樹，在這些位置進行查找的時候可以降低時間復雜度為 O(logN)，
2 ConcurrentHashMap 1.7 1.8
1.7 Segment 段
ConcurrentHashMap 和 HashMap 思路是差不多的，但是因為它支持并發操作，所以要復雜一 些，整個 ConcurrentHashMap 由一個個 Segment 組成，Segment 代表”部分“或”一段“的 意思，所以很多地方都會將其描述為分段鎖，
1.7 執行緒安全（Segment 繼承 ReentrantLock 加鎖）
簡單理解就是，ConcurrentHashMap 是一個 Segment 陣列，Segment 通過繼承 ReentrantLock 來進行加鎖，所以每次需要加鎖的操作鎖住的是一個 segment，這樣只要保證每 個 Segment 是執行緒安全的，也就實作了全域的執行緒安全，
- concurrencyLevel：并行級別、并發數、Segment 數，默認是 16， 也就是說 ConcurrentHashMap 有 16 個 Segments，所以理論上，這個時候，最多可以同時支 持 16 個執行緒并發寫，只要它們的操作分別分布在不同的 Segment 上，
- 這個值可以在初始化的時 候設定為其他值，但是一旦初始化以后，它是不可以擴容的，
- 具體到每個 Segment 內部，其實 每個 Segment 很像之前介紹的 HashMap，不過它要保證執行緒安全，所以處理起來要麻煩些.
Java1.8 對 ConcurrentHashMap 進行了比較大的改動,Java8 也引入了紅黑樹，
3 ConcurrentHashMap 1.8 細節面試知識點1（總體變化？）
- ConcurrentHashMap：檢索操作(包括get)通常不會阻塞，因此可能與更新操作(包括put和remove)重疊，ConcurrentHashMap跟Hashtable類似但不同于HashMap，它不可以存放空值，key和value都不可以為null，
- ConcurrentHashMap從JDK1.5開始隨java.util.concurrent包一起引入JDK中，在JDK8以前，ConcurrentHashMap都是基于Segment分段鎖來實作的，在JDK8以后，就換成synchronized和CAS這套實作機制了，JDK1.8中的ConcurrentHashMap中仍然存在Segment這個類，而這個類的宣告則是為了兼容之前的版本序列化而存在的，
- JDK1.8中的ConcurrentHashMap不再使用Segment分段鎖，而是以table陣列的頭結點作為synchronized的鎖，和JDK1.8中的HashMap類似，對于hashCode相同的時候，在Node節點的數量少于8個時，這時的Node存盤結構是鏈表形式，時間復雜度為O(N)，當Node節點的個數超過8個時，則會轉換為紅黑樹，此時訪問的時間復雜度為O(long(N))，
4 ConcurrentHashMap 1.8 細節面試知識點2（可見性如何實作？）
- 使用volatile保證當Node中的值變化時對于其他執行緒是可見的
- 【Node中的val和next都被volatile關鍵字修飾，我們改動val的值或者next的值對于其他執行緒是可見的，因為volatile關鍵字，會在讀指令前插入讀屏障，可以讓高速快取中的資料失效，重新從主記憶體加載資料，】
- 【ConcurrentHashMap提供類似tabAt來讀取Table陣列中的元素，這里是以volatile讀的方式讀取table陣列中的元素，主要通過Unsafe這個類來實作的，保證其他執行緒改變了這個陣列中的值的情況下，在當前執行緒get的時候能拿到，】
- 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);
-
【而與之對應的，是setTabAt,這里是以volatile寫的方式往陣列寫入元素，這樣能保證修改后能對其他執行緒可見，】
-
static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);}
5 ConcurrentHashMap 1.8 細節面試知識點3（安全如何實作？）
- 使用table陣列的頭結點作為synchronized的鎖來保證寫操作的安全
- 【當頭結點不為null時，則使用該頭結點加鎖，這樣就能多執行緒去put hashCode相同的時候不會出現資料丟失的問題，synchronized是互斥鎖，有且只有一個執行緒能夠拿到這個鎖，從而保證了put操作是執行緒安全的，】
- 當頭結點為null時，使用CAS操作來保證資料能正確的寫入，
/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null, // cas insert head
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
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;
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;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
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);
}- 【所謂的CAS，即compareAndSwap，執行CAS操作的時候，將記憶體位置的值與預期原值比較，如果相匹配，那么處理器會自動將該位置值更新為新值，否則，處理器不做任何操作，】
- asTabAt同樣是通過呼叫Unsafe類來實作的，呼叫Unsafe的compareAndSwapObject來實作，其實如果仔細去追蹤這條線路，會發現其實最終呼叫的是cmpxchg這個CPU指令來實作的，這是一個CPU的原子指令，能保證資料的一致性問題，
-
6 ConcurrentHashMap 1.8 細節面試知識點4(為啥？快了？ 哪里快？)
- 舊版本的一個segment鎖，保護了多個hash桶，而jdk8版本的一個鎖只保護一個hash桶，由于鎖的粒度變小了，寫操作的并發性得到了極大的提升，
- 【更多的擴容執行緒】擴容時，需要鎖的保護，因此：舊版本最多可以同時擴容的執行緒數是segment鎖的個數，而jdk8的版本，理論上最多可以同時擴容的執行緒數是：hash桶的個數（table陣列的長度），但是為了防止擴容執行緒過多，ConcurrentHashMap規定了擴容執行緒每次最少遷移16個hash桶，因此jdk8的版本實際上最多可以同時擴容的執行緒數是：hash桶的個數/16
- 【擴容期間，依然保證較高的并發度】舊版本的segment鎖，鎖定范圍太大，導致擴容期間，寫并發度，嚴重下降，而新版本的采用更加細粒度的hash桶級別鎖，擴容期間，依然可以保證寫操作的并發度，
- 【ConcurrentHashMap的重要結構與方法】ConcurrentHashMap內部，和hashmap一樣，維護了一個table陣列，陣列元素是Node鏈表或者紅黑樹.
- 【關于table陣列，有3個重要方法】
-
以volatile讀的方式讀取table陣列中的元素 Node<K,V> tabAt(Node<K,V>[] tab, int i) U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE)
-
以volatile寫的方式，將元素插入table陣列 setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
-
以CAS的方式，將元素插入table陣列 casTabAt(Node<K,V>[] tab, int i,Node<K,V> c, Node<K,V> v) U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v)；
7 ConcurrentHashMap 1.8 細節面試知識點5(原始碼解讀)
- 我們看下ConcurrentHashMap的put方法是如何通過CAS確保執行緒安全的：假設此時有2個put執行緒,都發現此時桶為空，執行緒一執行casTabAt(tab,i,null,node1),此時tab[i]等于預期值null,因此會插入node1，隨后執行緒二執行casTabAt(tba,i,null,node2),此時tab[i]不等于預期值null，插入失敗，然后執行緒二會回到for回圈開始處，重新獲取tab[i]作為預期值，重復上述邏輯，
- get方法，get方法同樣利用了volatile特性，實作了無鎖讀，
查找value的程序如下：
1. 根據key定位hash桶，通過tabAt的volatile讀，獲取hash桶的頭結點，
2. 通過頭結點Node的volatile屬性next，遍歷Node鏈表
3. 找到目標node后，讀取Node的volatile屬性val
可見上述3個操作都是volatile讀，因此可以做到在不加鎖的情況下，保證value的記憶體可見性
-
put方法，由于鎖的粒度是hash桶，多個put執行緒只有在請求同一個hash桶時，才會被阻塞，請求不同hash桶的put執行緒，可以并發執行，put執行緒，請求的hash桶為空時，采用for回圈+CAS的方式無鎖插入，
-
remove方法，如圖所示：洗掉的node節點的next依然指著下一個元素，此時若有一個遍歷執行緒正在遍歷這個已經洗掉的節點，這個遍歷執行緒依然可以通過next屬性訪問下一個元素，從遍歷執行緒的角度看，他并沒有感知到此節點已經洗掉了，這說明了ConcurrentHashMap提供了弱一致性的迭代器，
7 Map 1.7 1.8 總結
- 執行緒安全和非安全的比較
- 安全方面：volatile cas synchronize 替換了 segment lock 方案，并發度有默認16 擴展為陣列節點數；
- 速度： 紅黑樹O(logN)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/260705.html
標籤：其他
上一篇：【動手擼深度學習】不吹不黑一份代碼即可進Kaggle排行榜！
下一篇：Protecting Poorly Chosen Secrets from Guessing Attacks論文筆記