2019獨角獸企業重金招聘Python工程師標準>>>

? ? 注：分析JDK8的ConcurrentHashMap，JDK6/7上的實現和JDK8上的不一樣。

1.構造方法中的參數含義

? ? 構造方法中，有三個參數，如下，第三個參數才是一位數組的長度，第一個參數和第二個參數與Map的擴容有關

? ? List-1

public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel)

? ? 構造方法如下List-2

? ? List-2?initialCapacity的值不能小于concurrencyLevel，通過initialCapacity和loadFactor計算出值并賦值給sizeCtl

public ConcurrentHashMap(int initialCapacity,float loadFactor, int concurrencyLevel) {if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)throw new IllegalArgumentException();if (initialCapacity < concurrencyLevel) // Use at least as many binsinitialCapacity = concurrencyLevel; // as estimated threadslong size = (long)(1.0 + (long)initialCapacity / loadFactor);int cap = (size >= (long)MAXIMUM_CAPACITY) ?MAXIMUM_CAPACITY : tableSizeFor((int)size);this.sizeCtl = cap;}

? ? sizeCtl在哪用到了，如下圖1所示，如果sizeCtl的值大于0，說明我們指定了capacity，所以不會使用默認的DEFAULT_CAPACITY。注意sizeCtl的值是容量，不是當前Map中元素的個數。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 圖1 初始化表

2.并發度，一維數組

? ? 一維數組存儲在這個中，長度默認是16，即默認的ConcurrenyLevel。

? ? List-2

transient volatile Node<K,V>[] table=(Node<K,V>[])new Node<?,?>[n];

? ? Node的類結構如下所示：

? ? List-3

static class Node<K,V> implements Map.Entry<K,V> {final int hash;final K key;volatile V val;volatile Node<K,V> next;Node(int hash, K key, V val, Node<K,V> next) {this.hash = hash;this.key = key;this.val = val;this.next = next;} ... }

? ? 來看張ConcurrentHashMap的數據結構圖，如下圖1所示：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 圖1 ConcurrentHashMap的數據結構

? ? 如圖1所示，當A對應的鏈表長度達到8后，就會轉換為紅黑樹。為什么是8：屬性TREEIFY_THRESHOLD上有注釋，不過沒怎么看懂。我個人覺得，如果鏈表長度小于8就轉換為紅黑樹，效率上可能不如鏈表，畢竟紅黑樹的調整是比鏈表復雜的，這時不如直接使用鏈表；如果鏈表長度超過8，那么使用鏈表，查詢效率會變低(最壞情況下遍歷整條鏈表)，此時用紅黑樹那么就能將查詢的復雜度由O(n)降低到LogN。

? ? 紅黑樹中的節點TreeNode：

? ? List-4

static final class TreeNode<K,V> extends Node<K,V> {TreeNode<K,V> parent; // red-black tree linksTreeNode<K,V> left;TreeNode<K,V> right;TreeNode<K,V> prev; // needed to unlink next upon deletionboolean red;TreeNode(int hash, K key, V val, Node<K,V> next,TreeNode<K,V> parent) {super(hash, key, val, next);this.parent = parent;} ... }

3.多線程進行put，如何保證線程安全

? ? 來看一張圖，如下圖2：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?圖2 putVal方法中

? ? 假設put(x)時，插入的bucket位置是圖1中A對應的鏈表，那么會對A進行synchronized，這樣就保證了同一時刻只有線程能訪問synchronized的代碼塊，這個代碼塊中，有插入Node的操作，這樣就保證了線程安全。

????ConcurrentHashMap的get()方法是不需要加上synchronize的，因為很多關鍵的屬性都有volatile修飾保證了可見性，所以get()方法上不加synchronize的情況下，也可以得到結果。

4.如何擴容的，什么時候擴容

? ? 問題1：每次進行put后，都會調用addCount方法，對Map中當前元素數量加1。之后會調用sumCount()方法獲取Map中當前有多少個元素，如果等于或者大于sizeCtl的值，就會觸發擴容。

? ? 如下這個方法中就是觸發擴容的入口。

addCount(long x, int check)

? ? 如下這個屬性與擴容有關。

private transient volatile Node<K,V>[] nextTable;

? ? 實現擴容的代碼在如下方法中，實現起來很復雜，可以參考這篇文章。

transfer(Node<K,V>[] tab, Node<K,V>[] nextTab)

????

5.怎么實現統計Map中元素個數的功能

? ? 與倆個屬性有關，如下:

/*** Base counter value, used mainly when there is no contention,* but also as a fallback during table initialization* races. Updated via CAS.*/private transient volatile long baseCount;/*** Table of counter cells. When non-null, size is a power of 2.*/private transient volatile CounterCell[] counterCells;

? ? 注：counterCells的長度與CPU個數有關。

? ? CounterCell類如下:

@sun.misc.Contended static final class CounterCell {volatile long value;CounterCell(long x) { value = x; }}

?????解說下這個baseCount和counterCells是如何工作的：

• 情況1： 假設只有一個線程進行put，Map中元素個數加1，會對baseCount進行CAS進行值加1，由于此時只有一個線程，所以CAS會成功，注意這里的是Unsafe的CAS，而不是AtomicInteger之類的CAS，所以如果失敗會馬上返回false。
• 情況2：假設有多個線程進行put，此時多個線程對baseCount進行CAS，此時若有些線程發生CAS失敗，說明對baseCount競爭失敗，注意這里使用的是Unsafe的CAS，而不是AtomicInteger之類的CAS，所以如果失敗會馬上返回false。此時從counterCells中隨機選取一個出來，對CounterCell的value做CAS進行加1，如果此時發生CAS失敗，說明碰到了競爭，怎么處理呢，看下圖，將counterCells的數組長度翻倍，之后拷貝元素組的值到新數組中對應的位置。

? ??調用size()時，會調用sumCount()，sumCount()方法實現如下：

final long sumCount() {CounterCell[] as = counterCells; CounterCell a;long sum = baseCount;if (as != null) {for (int i = 0; i < as.length; ++i) {if ((a = as[i]) != null)sum += a.value;}}return sum;}

? ? 首先獲得baseCount的值，之后遍歷每個counterCells中的value，就是Map中的元素的值，當然，得到的這個值不一定準確、不是實時的。

? ? JDK8的ConcurrentHashMap中計算Map中元素個數的方法與LongAddr、DoubleAdder很類似。

? ? JDK8中獲取size的實現，比JDK6/7中的要好很多了，如果你看過JDK6/7中ConcurrentHashMap的實現，應該會有所感受的

轉載于:https://my.oschina.net/u/2518341/blog/1841714

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的JDK之ConcurrentHashMap的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。