1.1 加載因子

????????加載因子（Load Factor）是用來決定什么時候需要擴容的一個參數。具體來說，加載因子 = 當前元素數量 / 桶的數量，當某個桶的元素個數超過了 桶的數量 × 加載因子 時，就會觸發擴容。

????????我們都知道 ConcurrentHashMap 的默認大小是16，默認加載因子是：0.75。解析一下什么叫做加載因子，簡單的講就是觸發擴容機制的閾值。比如我的集合容量大小是 100，加載因子是：0.75，那么觸發擴容的閾值就是(100 x 0.75 = 75; 當數量達到75的時候觸發擴容機制。而不是在容量達到滿100的時候才觸發擴容機制)。通過設置加載因子的好處如下：

平衡性能與空間利用率	? ? ? ? 較低的加載因子（如 0.1）會使得哈希表在元素較少時擴容，從而減少哈希沖突，提高查找、插入和刪除操作的性能。 ? ? ? ? 較高的加載因子（如 0.9）會延遲擴容，節省內存空間，但可能會增加哈希沖突，降低性能。 ????????在?ConcurrentHashMap?中，默認的加載因子是 0.75。這是一個經驗值，能夠在大多數情況下提供較好的性能和空間利用率。
控制加載頻率	????????擴容是一個比較耗時的操作，因為它需要重新計算元素復制到新的桶里面。通過調整加載因子，在性能與內存之間達到一個平衡。

? ?

1.2 面試題：加載因子默認為什么是0.75，而不是9，或者5等等之類其他數字

????????所以這道題面試題問的就是加載因子的作用，從平衡性能和內存，以及控制加載頻率的角度去回答即可。

????????比如：如果設置的加載因子過高（例如 0.1?或 0.9），意味著 ConcurrentHashMap 會在桶中存儲更多的元素，減少擴容的次數，減少內存的開銷。但是這樣會也導致桶的元素過多，鏈表的長度過長。導致訪問元素時的查找效率下降，發生更多的哈希沖突（hash collision）幾率也逐漸增大。
????????較低的加載因子（0.1）意味著 ConcurrentHashMap 會在桶中存儲少量的元素，但擴容的次數上升，內存的開銷增多。頻繁的擴容處理會導致性能開銷增大。

? ? ? ? 所以取一個在性能與內存之間很好的折中植就是0.75。0.75 是一個經過大量測試驗證的值，適用于大多數常見場景。它在查找效率、內存使用和擴容操作之間取得了一個很好的折中。

? ? ? ? 當然，如果具體也可以根據需求調整
????????對于性能要求高的應用：

? ? ? 盡量減少哈希沖突，提高查找、插入和刪除操作的性能。降低加載因子（例如設置為 0.5 或更低）。

????????【原因】

? ? ? ? ? ? ? ? 較低的加載因子會使得哈希表在元素數量較少時觸發擴容，從而減少哈希沖突。

????????????????每個桶中的元素數量更少，查找、插入和刪除操作的時間復雜度更接近 O(1)。

????????【代價】

????????????????哈希表的容量會更大，占用更多的內存空間

????????????????擴容操作會更頻繁，可能會帶來一定的性能開銷

????????對于內存占用比較敏感的應用：

????????盡量減少內存占用，提高空間利用率。

????????【原因】

????????????????較高的加載因子會延遲擴容，使得哈希表在元素數量接近容量時才觸發擴容。

? ? ? ? ? ? ? ? 內存利用率更高，適合內存資源有限的場景。

? ? ? ? 【代價】

????????????????哈希沖突的概率會增加，尤其是在元素數量接近容量時，性能可能會下降。

????????????????查找、插入和刪除操作的時間復雜度可能會增加。

1.3 初始化功能 initTable()

首先，初始化功能在第一次put時會觸發。代碼分析如下
我們進一步觀察initTable() 方法

public V put(K key, V value) { return putVal(key, value, false); }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; K fk; V fv;// 當集合第一次添加元素時，觸發初始化if (tab == null || (n = tab.length) == 0) tab = initTable(); ...... // 忽略其他代碼

我們進一步觀察initTable() 方法

/** ConcurrentHashMap 的容器*/
transient volatile Node<K,V>[] table; 
/** sizeCtl的作用 sizeCtl (< 0) 負值時：sizeCtl = -1; 表示正在進行初始化其他負值（如 -2，-3 等）：表示正在進行擴容，并且數字的大小指示了當前有多少個線程正在進行擴容操作。例如，-2 表示有一個線程在進行擴容，-3 表示有兩個線程在進行擴容。sizeCtl = 0 時：當 sizeCtl == 0 時，表示表格的大小使用默認值。正值（用于表格大小的控制）：在表格初始化完成之后，sizeCtl 變成一個正值，表示下一個閾值，即表格的元素數量達到此值時，需要進行擴容。例如，如果 sizeCtl 設置為 16，則表示當表格的元素數量達到 16 時，應該觸發擴容操作。【總結】sizeCtl 控制表格的初始化、擴容，以及擴容過程中的線程同步。根據其值的不同，sizeCtl 在 ConcurrentHashMap 中承擔著不同的角色
*/
private transient volatile int sizeCtl;/** Unsafe 類，里面提供CPU相關的操作指令，比如CAS。CAS: compareAndSet 比較并交換，CAS 通過比較變量的當前值與預期值是否相同，如果兩值相同則將變量的值更新為新值，否則不做任何操作并且還支持跳過JVM內存管理相關操作
*/
private static final Unsafe U = Unsafe.getUnsafe();/** 通過 Unsafe 不安全類，繞過JVM的內存管理機制，直接訪問硬件的內存獲取 ConcurrentHashMap.class 類里面的 sizeCtl 的字段值
*/
private static final long SIZECTL= U.objectFieldOffset(ConcurrentHashMap.class, "sizeCtl");private final Node<K,V>[] initTable() {// 聲明兩個局部變量，而不直接使用全局的table, sizeCtl // 避免直接多次訪問全局的 table，提高代碼的效率。Node<K,V>[] tab; int sc;// 進入 while 循環時，首先檢查 table 是否為 null 或者是否為空（長度為 0）。// 如果是，表示 table 還沒有初始化while ((tab = table) == null || tab.length == 0) {// sizeCtl 負值集合處于初始化(-1)或者是擴容階段(-2,-3....)if ((sc = sizeCtl) < 0) Thread.yield(); // 所以當前線程禮讓出CPU資源（CPU時間分片）// U.compareAndSetInt 該方法就是int類型的CAS// 如果 sizeCtl 的當前值 不小于 0，我們嘗試通過 CAS（Compare-And-Set）操作 // 來將 sizeCtl 的值從 sc 修改為 -1，表示當前線程正在進行初始化操作。else if (U.compareAndSetInt(this, SIZECTL, sc, -1)) {try {// 再次檢查 table 是否已經初始化，如果沒有，則進行初始化。if ((tab = table) == null || tab.length == 0) { // 如果 sc(sizeCtl) 有正值，則表示當前容量大小，否則使用默認大小16int n = (sc > 0) ? sc : DEFAULT_CAPACITY;// 初始化：就是創建一個指定的大小數組賦值給table，并記錄sizeCtl的值。@SuppressWarnings("unchecked")Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];table = tab = nt;// 計算并更新 sc 的值。sc 記錄下一個閾值，即元素數量達到多少時需要擴容。// 此計算方法是基于表格大小的 75%（即 n - (n >>> 2)，// 實際上就是 n * 0.75）。當元素數量超過該閾值時，將會觸發擴容。sc = n - (n >>> 2); // 可以理解成這樣的 0.75 加載因子是寫固定的0.75。}} finally {sizeCtl = sc;}break;}}return tab;
}

public class Test {public static void main(String[] args) {ConcurrentHashMap<String, String> map = new ConcurrentHashMap<>();map.put("key1", "value1");System.out.println(map);}
}

?

1.4 總結

ConcurrentHashMap 的初始化，如果是第一次進行初始化，則容量大小為 16，加載因子(0.75)計算的閾值為12。ConcurrentHashMap 由于是線程安全的，在初始化的體現通過 Unsafe不安全類提供CAS操作來實現。通過CAS 判斷 sizeCtl 值。
sizeCtl 用于控制集合的擴容，初始化。比如 -1 表示正在初始化，其他的負數表示正在擴容 -2 一個線程擴容，-3 兩個線程，以此類推，
sizeCtl = 0 表示 初始化完成了。
sizeCtl > 0 表示觸發擴容的閾值。第一次為12 。

1.5 構造方法

    /** 最大值 */private static final int MAXIMUM_CAPACITY = 1 << 30;/** 默認容量大小 */private static final int DEFAULT_CAPACITY = 16;/** 默認加載因子大小 */private static final float LOAD_FACTOR = 0.75f;public ConcurrentHashMap() {}/*** @param initialCapacity 初始容量*/public ConcurrentHashMap(int initialCapacity) {this(initialCapacity, LOAD_FACTOR, 1);}/*** @param initialCapacity 初始容量* @param loadFactor 加載因子*/public ConcurrentHashMap(int initialCapacity, float loadFactor) {this(initialCapacity, loadFactor, 1);}/*** @param initialCapacity 初始容量* @param loadFactor 加載因子* @param concurrencyLevel 內部更新線程個數，估計將同時更新映射的線程數。* 此值用于幫助調整內部數據結構的大小，以減少線程間的競爭。*/public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) {if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)throw new IllegalArgumentException(); // 非法值，比如容量是負數之類// 如果初始容量小于并發級別，調整初始容量if (initialCapacity < concurrencyLevel) initialCapacity = concurrencyLevel;   // 確保桶的數量至少與并發線程數一樣多// 根據初始容量和負載因子計算內部表格的大小long size = (long)(1.0 + (long)initialCapacity / loadFactor);// 確保計算出的大小不超過最大容量int cap = (size >= (long) MAXIMUM_CAPACITY) ?MAXIMUM_CAPACITY : tableSizeFor((int)size);this.sizeCtl = cap;}/** 該方法支持傳入一個map */public ConcurrentHashMap(Map<? extends K, ? extends V> m) {this.sizeCtl = DEFAULT_CAPACITY; // 閾值大小為 16putAll(m);}

1.6 總結

????????ConcurrentHashMap 的構造方法，提供手動設置初始容量和加載因子以及內部線程個數。限制容量的范圍大小 0 到 MAXIMUM_CAPACITY（1 << 30 ）。
并且從里面也可以得知，在設置閾值大小的時候都是通過 sizeCtl (size Control ) 來接收。所以從這樣也可以知道初始化的時候，用它來進行一個參看和判斷。正數的就表示擴容閾值大小，等觸發擴容，或者是初始化時，將其sizeCtl 改為 負值。 -1 表示 初始值，-2 表示一個線程擴容，-3 表示兩個線程擴容，以此類推，畢竟ConcurrentHashMap支持線程安全。擴容完之后又將計算新的閾值大小賦值給 sizeCtl.
所以才說 sizeCtl 是掌管控制ConcurrentHashMap的初始化，擴容的一個重要變量。

1.7 新增功能

public V put(K key, V value) { return putVal(key, value, false); }

1.8 面試題：直接從上到下，添加一次就可以嗎？為什么要通過一個for 進行無限循環添加？

? ? ? ? 其實這并非是集合章節的知識點，這個是多線程章節的知識點。因為ConcurrentHashMap支持多線程并發，所以需要考慮到多線程的情況下。

????????作用：持續重試和處理并發操作
????????在并發數據結構中，許多操作（如插入、刪除、擴容等）都可能需要在多個線程同時訪問的環境下執行。使用無限循環可以確保：
????????重試操作：如果某個操作（如插入、更新或刪除）由于并發沖突（例如，另一個線程正在修改同一個桶或節點）而無法立即成功執行，程序可以在內部重新嘗試執行該操作。
????????保證條件滿足后繼續執行：在并發環境下，操作的執行結果通常依賴于其他線程的狀態，因此可能需要在條件不滿足時繼續嘗試直到成功。
????????處理擴容等需要重新計算大小的操作：
????????例如，在 ConcurrentHashMap 中，當插入元素導致負載過高時，可能需要擴容哈希表。擴容通常涉及以下步驟：
????????1 重新計算哈希表的大小
????????2 重新分配內存
????????3 重新散列所有現有元素
????????這些操作往往需要多次嘗試，直到哈希表的大小適合當前元素的數量。在此過程中，循環結構可以幫助處理這一過程，直到操作完成。

????????確保原子性操作
????????在高并發環境下，有時需要使用 CAS（比較并交換） 或類似的機制(JDK7 的線程安全是通過 分段鎖 Segment )來確保線程安全。例如，可能需要反復檢查某個條件（如節點是否已被更新），直到確認操作成功。

????????避免死鎖或競爭條件
????????使用無限循環可以防止由于競爭條件引起的操作失敗。通過在循環中不斷嘗試，確保操作的成功執行，同時避免因并發沖突或競爭條件導致程序永久卡住。

????????操作的延遲執行
????????有些操作可能會依賴某些狀態或條件，并且需要在特定的時機才執行。例如，在表格擴容時，可能需要等到某些條件滿足才繼續執行下一個步驟。無限循環允許在這些條件準備好時才繼續操作。

1.9下面看新增邏輯分析

final V putVal(K key, V value, boolean onlyIfAbsent) {// 這里可以說明 ConcurrentHashMap 不支持key,value為null// 這樣設計是為了避免二義性：何為二義性。/**在并發環境下，null 值可能會導致語義上的歧義，無法區分以下兩種情況：key 不存在：調用 get(key) 返回 null，可能表示該 key 不存在。key 存在，但 value 為 null：調用 get(key) 返回 null，也可能表示該 key 存在，但其對應的 value 是 null。這種二義性會導致程序邏輯難以處理，尤其是在并發場景下，可能會引發難以調試的問題。*/if (key == null || value == null) throw new NullPointerException();// 獲取鍵 key 的哈希值，用于確定元素的位置，spread()進一步優化并降低哈希沖突的概率int hash = spread(key.hashCode()); /** 記錄當前桶中的元素個數 */int binCount = 0;// 忽略添加邏輯addCount(1L, binCount); // 記錄當前桶的元素數量+1return null;}

????????補充一下ConcurrentHashMap 當中桶 (bin) 指的是什么，指定的就是 Node<K, V>[] table 。table[] 有多大，就有多少個桶，而我們知道 table 。是在初始化或者擴容的時候進行更新。所以這里的 binCount 就是指定當前桶的元素個數。而元素放在哪個桶的位置，是由計算的hash值來決定的。

? ? ? ? 新增邏輯大概考慮到五種情況

? ? ? ? 【情況一】：第一次新增觸發初始化

? ? ? ? 【情況二】： 矯正hash計算得出的索引沒有桶

? ? ? ? 【情況三】：新增遇到正在擴容處理，通過helpTransfer 來處理

? ? ? ? 【情況四】：處理key值相同，value不覆蓋(ConcurrentHashMap默認都是key相同，value覆蓋，有參數 onlyIfAbsent來決定，onlyIfAbsent 意思就是：是否只有值缺席的時候才添加。)

? ? ? ? 【情況五】：正常插入元素。（鏈表樹化成紅黑樹也在這里處理）

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; K fk; V fv;// 【情況一】：第一次新增觸發初始化if (tab == null || (n = tab.length) == 0)tab = initTable();/*** 【情況二】：如果計算得到索引所對應的桶為null: (f = null) == null*   當索引對應的桶為null,就通過CAS重新將元素添加到桶里面。并break;表示新增結束*  額外講解：避免了哈希值超過桶的范圍*     i 表示 索引，(n - 1) & hash 作用*     假如當桶大小只有32時，但是計算出的索引超過了32，比如 55。*     n = 32，n - 1 = 31（二進制 11111）。*	   如果 hash = 55，二進制表示為 110111。*     (55 & 31) 的結果是 55 & 11111 = 111，即索引為 7。*/else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))break;                   // no lock when adding to empty bin}/*** 【情況三】：如果桶的哈希值為 MOVED，表示該位置正在進行哈希表擴容操作。* 此時調用 helpTransfer() 來幫助完成擴容*/else if ((fh = f.hash) == MOVED)tab = helpTransfer(tab, f);/*** 【情況四】：* 如果 onlyIfAbsent 為 true* key 相同，value就不更新了。* 而put方法，put(K key, V value) { return putVal(key, value, false); }* 很顯然是key相同，value覆蓋更新 */else if (onlyIfAbsent // check first node without acquiring lock&& fh == hash&& ((fk = f.key) == key || (fk != null && key.equals(fk)))&& (fv = f.val) != null)return fv;// 【情況五】：正常的插入與更新else {V oldVal = null;synchronized (f) { //加鎖 synchronized (f)，確保線程安全。if (tabAt(tab, i) == f) {/** * 鏈表（fh >= 0）：遍歷當前桶中的鏈表，查找鍵是否存在。* 如果存在，更新值；如果不存在，將新節點添加到鏈表末尾。* 俗稱：key 相同時，key不變，value覆蓋*/if (fh >= 0) {binCount = 1;for (Node<K,V> e = f;; ++binCount) {K ek;// key 沖突，value覆蓋邏輯if (e.hash == hash &&((ek = e.key) == key ||(ek != null && key.equals(ek)))) {oldVal = e.val;if (!onlyIfAbsent)e.val = value;break;}// key 不沖突，直接添加key, value // (ConcurrentHashMap里面的元素都是以Node為基礎。)// 所以通過新增的put(key, value); 都會封裝成一個Node 元素。// 這個Node里面存儲的真正key和valueNode<K,V> pred = e;if ((e = e.next) == null) {pred.next = new Node<K,V>(hash, key, value);break;}}}// 如果當前桶已經是紅黑樹，則通過 putTreeVal() 方法處理。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;}}// 保留節點處理（f instanceof ReservationNode）：// 如果桶中是保留節點，則拋出異常else if (f instanceof ReservationNode)throw new IllegalStateException("Recursive update");}}// 鏈表樹化：桶中的元素數量大于等于 TREEIFY_THRESHOLD（默認 8），轉紅黑樹if (binCount != 0) {if (binCount >= TREEIFY_THRESHOLD)treeifyBin(tab, i);if (oldVal != null)return oldVal;break;}}}addCount(1L, binCount);return null;}

2.0 擴容機制 tryPresize

????????tryPresize 旨在根據給定的 size 計算新的容量，并嘗試擴容哈希表。它會根據表的當前狀態，所需容量和線程安全的操作來決定是否進行擴容。

在代碼內部我們可以看出，兩處需要進行擴容處理。一處是putAll()方法。一個是在新增時有一處是 鏈表樹化的擴容。

public void putAll(Map<? extends K, ? extends V> m) {tryPresize(m.size());for (Map.Entry<? extends K, ? extends V> e : m.entrySet())putVal(e.getKey(), e.getValue(), false);
}

    private final void treeifyBin(Node<K,V>[] tab, int index) {Node<K,V> b; int n;if (tab != null) {if ((n = tab.length) < MIN_TREEIFY_CAPACITY)tryPresize(n << 1);// ...... 忽略其他代碼

看擴容邏輯代碼

private final void tryPresize(int size) {/** * 擴容的大小 = c* 根據傳入的size大小來決定，如果size大于最大值MAXIMUM_CAPACITY，* 那么c就是最大值，調用 tableSizeFor 方法計算一個合適的容量。* tableSizeFor 的作用是返回大于等于給定值的最小 2 的冪次方*/int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :tableSizeFor(size + (size >>> 1) + 1);int sc;/** 這里我們都知道，1.3 初始化功能的時候提到過sizeCtl 有多重身份，sizeCtl < 0 時，表示正在處于初始化或者是擴容當中, -1 表示初始化， -2，-3表示擴容，-2是一條線程，-3是兩條線程擴容，依次類推sizeCtl = 0 時，初始化完成了，sizeCtl > 0 時，sizeCtl表示加載的閾值（有容量大小 X 加載因子得來的）*/while ((sc = sizeCtl) >= 0) {Node<K,V>[] tab = table; int n;// 處理初始化if (tab == null || (n = tab.length) == 0) {n = (sc > c) ? sc : c; // n = 本次最終擴容的大小if (U.compareAndSetInt(this, SIZECTL, sc, -1)) { // 通過CAS進行更新try {if (table == tab) {@SuppressWarnings("unchecked")Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];table = nt;// 重新計算 sizeCtl 新的閾值（n - (n >>> 2)，即 0.75 * n）// 這里是通過位運算來的。寫死了 0.75 加載因子sc = n - (n >>> 2);}} finally {sizeCtl = sc;}}}// 目標容量不在范圍內，不處理擴容了// 如果目標容量 c 小于等于當前閾值 sc，或者當前容量 n 已經達到最大容量 MAXIMUM_CAPACITYelse if (c <= sc || n >= MAXIMUM_CAPACITY)break;// 觸發擴容機制else if (tab == table) {int rs = resizeStamp(n);if (U.compareAndSetInt(this, SIZECTL, sc,(rs << RESIZE_STAMP_SHIFT) + 2))transfer(tab, null);}}
}

? ?