解析ConcurrentHashMap:成員屬性、內部類、構造方法
1、簡介
ConcurrentHashMap是HashMap的線程安全版本,內部也是使用(數組 + 鏈表 + 紅黑樹)的結構來存儲元素。相比於同樣線程安全的HashTable來說,效率等各方面都有極大地提高。
在學習ConcurrentHashMap源碼之前,這裡默認大傢已經讀過HashMap源碼,瞭解LongAdder原子類、紅黑樹。先簡單介紹下
ConcurrentHashMap的整體流程:
整體流程跟HashMap比較類似,大致是以下幾步:
(1)如果桶數組未初始化,則初始化;
(2)如果待插入的元素所在的桶為空,則嘗試把此元素直接插入到桶的第一個位置;
(3)如果正在擴容,則當前線程一起加入到擴容的過程中;
(4)如果待插入的元素所在的桶不為空且不在遷移元素,則鎖住這個桶(分段鎖);
(5)如果當前桶中元素以鏈表方式存儲,則在鏈表中尋找該元素或者插入元素;
(6)如果當前桶中元素以紅黑樹方式存儲,則在紅黑樹中尋找該元素或者插入元素;
(7)如果元素存在,則返回舊值;
(8)如果元素不存在,整個Map的元素個數加1,並檢查是否需要擴容;
添加元素操作中使用的鎖主要有(自旋鎖 + CAS + synchronized + 分段鎖)。
為什麼使用synchronized而不是ReentrantLock?
因為synchronized已經得到瞭極大地優化,在特定情況下並不比ReentrantLock差。
2、JDK1.8 ConcurrentHashMap結構圖
3、成員屬性
// 散列表數組最大容量值 private static final int MAXIMUM_CAPACITY = 1 << 30; // 散列表默認容量值16 private static final int DEFAULT_CAPACITY = 16; // 最大的數組大小(非2的冪) toArray和相關方法需要(並不是核心屬性) static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; // jdk1.7遺留下來的,用來表示並發級別的屬性 // jdk1.8隻有在初始化的時候用到,不再表示並發級別瞭~ 1.8以後並發級別由散列表長度決定 private static final int DEFAULT_CONCURRENCY_LEVEL = 16; // 負載因子:表示散列表的填滿程度~ 在ConcurrentHashMap中,該屬性是固定值0.75,不可修改~ private static final float LOAD_FACTOR = 0.75f; // 樹化閾值:散列表的一個桶中鏈表長度達到8時候,可能發生鏈表樹化 static final int TREEIFY_THRESHOLD = 8; // 反樹化閾值:散列表的一個桶中的紅黑樹元素個數小於6時候,將紅黑樹轉換回鏈表結構 static final int UNTREEIFY_THRESHOLD = 6; // 散列表長度達到64,且某個桶位中的鏈表長度達到8,才會發生樹化 static final int MIN_TREEIFY_CAPACITY = 64; // 控制線程遷移數據的最小步長(桶位的跨度~) private static final int MIN_TRANSFER_STRIDE = 16; // 固定值16,與擴容相關,計算擴容時會根據該屬性值生成一個擴容標識戳 private static int RESIZE_STAMP_BITS = 16; // (1 << (32 - RESIZE_STAMP_BITS)) - 1 = 65535:1 << 16 -1 // 表示並發擴容最多容納的線程數 private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1; // 也是擴容相關屬性,在擴容分析的時候會用到~ private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS; // 當node節點的hash值為-1:表示當前節點是FWD(forwarding)節點(已經被遷移的節點) static final int MOVED = -1; // 當node節點的hash值為-2:表示當前節點已經樹化,且當前節點為TreeBin對象~,TreeBin對象代理操作紅黑樹 static final int TREEBIN = -2; // 當node節點的hash值為-3: static final int RESERVED = -3; // 0x7fffffff 十六進制轉二進制值為:1111111111111111111111111111111(31個1) // 作用是將一個二進制負數與1111111111111111111111111111111 進行按位與(&)運算時,會得到一個正數,但不是取絕對值 static final int HASH_BITS = 0x7fffffff; // 當前系統的CPU數量 static final int NCPU = Runtime.getRuntime().availableProcessors(); // JDK1.8 序列化為瞭兼容 JDK1.7的ConcurrentHashMap用到的屬性 (非核心屬性) private static final ObjectStreamField[] serialPersistentFields = { new ObjectStreamField("segments", Segment[].class), new ObjectStreamField("segmentMask", Integer.TYPE), new ObjectStreamField("segmentShift", Integer.TYPE) }; // 散列表table transient volatile Node<K,V>[] table; // 新表的引用:擴容過程中,會將擴容中的新table賦值給nextTable,(保持引用),擴容結束之後,這裡就會被設置為NULL private transient volatile Node<K,V>[] nextTable; // 與LongAdder中的baseCount作用相同: 當未發生線程競爭或當前LongAdder處於加鎖狀態時,增量會被累加到baseCount private transient volatile long baseCount; // 表示散列表table的狀態: // sizeCtl<0時: // 情況一、sizeCtl=-1: 表示當前table正在進行初始化(即,有線程在創建table數組),當前線程需要自旋等待... // 情況二、表示當前table散列表正在進行擴容,高16位表示擴容的標識戳,低16位表示擴容線程數:(1 + nThread) 即,當前參與並發擴容的線程數量。 // sizeCtl=0時:表示創建table散列表時,使用默認初始容量DEFAULT_CAPACITY=16 // sizeCtl>0時: // 情況一、如果table未初始化,表示初始化大小 // 情況二、如果table已經初始化,表示下次擴容時,觸發條件(閾值) private transient volatile int sizeCtl; // 擴容過程中,記錄當前進度。所有的線程都需要從transferIndex中分配區間任務,並去執行自己的任務 private transient volatile int transferIndex; // LongAdder中,cellsBusy表示對象的加鎖狀態: // 0: 表示當前LongAdder對象處於無鎖狀態 // 1: 表示當前LongAdder對象處於加鎖狀態 private transient volatile int cellsBusy; // LongAdder中的cells數組,當baseCount發生線程競爭後,會創建cells數組, // 線程會通過計算hash值,去取到自己的cell,將增量累加到指定的cell中 // 總數 = sum(cells) + baseCount private transient volatile CounterCell[] counterCells;
4、靜態屬性
// Unsafe 類 private static final sun.misc.Unsafe U; // 表示sizeCtl屬性在ConcurrentHashMap中內存的偏移地址 private static final long SIZECTL; // 表示transferIndex屬性在ConcurrentHashMap中內存的偏移地址 private static final long TRANSFERINDEX; // 表示baseCount屬性在ConcurrentHashMap中內存的偏移地址 private static final long BASECOUNT; // 表示cellsBusy屬性在ConcurrentHashMap中內存的偏移地址 private static final long CELLSBUSY; // 表示cellsValue屬性在ConcurrentHashMap中內存的偏移地址 private static final long CELLVALUE; // 表示數組第一個元素的偏移地址 private static final long ABASE; // 該屬性用於數組尋址,請繼續往下閱讀 private static final int ASHIFT;
5、靜態代碼塊
static { try { U = sun.misc.Unsafe.getUnsafe(); Class<?> k = ConcurrentHashMap.class; SIZECTL = U.objectFieldOffset (k.getDeclaredField("sizeCtl")); TRANSFERINDEX = U.objectFieldOffset (k.getDeclaredField("transferIndex")); BASECOUNT = U.objectFieldOffset (k.getDeclaredField("baseCount")); CELLSBUSY = U.objectFieldOffset (k.getDeclaredField("cellsBusy")); Class<?> ck = CounterCell.class; CELLVALUE = U.objectFieldOffset (ck.getDeclaredField("value")); Class<?> ak = Node[].class; // 拿到數組第一個元素的偏移地址 ABASE = U.arrayBaseOffset(ak); // 表示數組中每一個單元所占用的空間大小,即scale表示Node[]數組中每一個單元所占用的空間 int scale = U.arrayIndexScale(ak); // (scale & (scale - 1)) != 0:判斷scale的數值是否是2的次冪數 // java語言規范中,要求數組中計算出的scale必須為2的次冪數 // 1 0000 % 0 1111 = 0 if ((scale & (scale - 1)) != 0) throw new Error("data type scale not a power of two"); // numberOfLeadingZeros(scale) 根據scale,返回當前數值轉換為二進制後,從高位到地位開始統計,統計有多少個0連續在一塊:eg, 8轉換二進制=>1000 則 numberOfLeadingZeros(8)的結果就是28,為什麼呢?因為Integer是32位,1000占4位,那麼前面就有32-4個0,即連續最長的0的個數為28個 // 4轉換二進制=>100 則 numberOfLeadingZeros(8)的結果就是29 // ASHIFT = 31 - Integer.numberOfLeadingZeros(4) = 2 那麼ASHIFT的作用是什麼呢?其實它有數組尋址的一個作用: // 拿到下標為5的Node[]數組元素的偏移地址(存儲地址):假設此時 根據scale計算得到的ASHIFT = 2 // ABASE + (5 << ASHIFT) == ABASE + (5 << 2) == ABASE + 5 * scale,就得到瞭下標為5的數組元素的偏移地址 ASHIFT = 31 - Integer.numberOfLeadingZeros(scale); } catch (Exception e) { throw new Error(e); } }
6、內部類
6.1 Node節點
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; Node(int hash, K key, V val, Node<K,V> next) { this.hash = hash; this.key = key; this.val = val; this.next = next; } public final K getKey() { return key; } public final V getValue() { return val; } public final int hashCode() { return key.hashCode() ^ val.hashCode(); public final String toString(){ return key + "=" + val; } public final V setValue(V value) { throw new UnsupportedOperationException(); } public final boolean equals(Object o) { Object k, v, u; Map.Entry<?,?> e; return ((o instanceof Map.Entry) && (k = (e = (Map.Entry<?,?>)o).getKey()) != null && (v = e.getValue()) != null && (k == key || k.equals(key)) && (v == (u = val) || v.equals(u))); } /** * Virtualized support for map.get(); overridden in subclasses. */ Node<K,V> find(int h, Object k) { Node<K,V> e = this; if (k != null) { do { K ek; if (e.hash == h && ((ek = e.key) == k || (ek != null && k.equals(ek)))) return e; } while ((e = e.next) != null); } return null; } }
6.2 ForwardingNode節點
這個內部類在之後分析擴容的文章中會再仔細去探究,這裡先熟悉一下~
// 如果是一個寫的線程(eg:並發擴容線程),則需要為創建新表貢獻一份力 // 如果是一個讀的線程,則調用該內部類的find(int h, Object k)方法 static final class ForwardingNode<K,V> extends Node<K,V> { // nextTable表示新散列表的引用 final Node<K,V>[] nextTable; ForwardingNode(Node<K,V>[] tab) { super(MOVED, null, null, null); this.nextTable = tab; } // 到新表上去讀數據 Node<K,V> find(int h, Object k) { // loop to avoid arbitrarily deep recursion on forwarding nodes outer: for (Node<K,V>[] tab = nextTable;;) { Node<K,V> e; int n; if (k == null || tab == null || (n = tab.length) == 0 || (e = tabAt(tab, (n - 1) & h)) == null) return null; for (;;) { int eh; K ek; if ((eh = e.hash) == h && ((ek = e.key) == k || (ek != null && k.equals(ek)))) return e; if (eh < 0) { if (e instanceof ForwardingNode) { tab = ((ForwardingNode<K,V>)e).nextTable; continue outer; } else return e.find(h, k); } if ((e = e.next) == null) return null; } } } }
6.3 TreeNode節點
TreeBin中需要用到該節點,之後會細說~
static final class TreeNode<K,V> extends Node<K,V> { // 父節點 TreeNode<K,V> parent; // red-black tree links // 左子節點 TreeNode<K,V> left; // 右節點 TreeNode<K,V> right; // 前驅節點 TreeNode<K,V> prev; // needed to unlink next upon deletion // 節點有紅、黑兩種顏色~ boolean red; TreeNode(int hash, K key, V val, Node<K,V> next, TreeNode<K,V> parent) { super(hash, key, val, next); this.parent = parent; } Node<K,V> find(int h, Object k) { return findTreeNode(h, k, null); } /** * Returns the TreeNode (or null if not found) for the given key * starting at given root. */ final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) { if (k != null) { TreeNode<K,V> p = this; do { int ph, dir; K pk; TreeNode<K,V> q; TreeNode<K,V> pl = p.left, pr = p.right; if ((ph = p.hash) > h) p = pl; else if (ph < h) p = pr; else if ((pk = p.key) == k || (pk != null && k.equals(pk))) return p; else if (pl == null) p = pr; else if (pr == null) p = pl; else if ((kc != null || (kc = comparableClassFor(k)) != null) && (dir = compareComparables(kc, k, pk)) != 0) p = (dir < 0) ? pl : pr; else if ((q = pr.findTreeNode(h, k, kc)) != null) return q; else p = pl; } while (p != null); } return null; } }
7、構造方法
public ConcurrentHashMap() { } public ConcurrentHashMap(int initialCapacity) { if (initialCapacity < 0) throw new IllegalArgumentException(); int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY : tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1)); this.sizeCtl = cap; } public ConcurrentHashMap(Map<? extends K, ? extends V> m) { this.sizeCtl = DEFAULT_CAPACITY; putAll(m); } public ConcurrentHashMap(int initialCapacity, float loadFactor) { this(initialCapacity, loadFactor, 1); } 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 bins initialCapacity = concurrencyLevel; // as estimated threads long size = (long)(1.0 + (long)initialCapacity / loadFactor); int cap = (size >= (long)MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : tableSizeFor((int)size); this.sizeCtl = cap; }
構造方法與HashMap對比可以發現,沒有瞭HashMap
中的threshold
和loadFactor
,而是改用瞭sizeCtl
來控制,而且隻存儲瞭容量在裡面,那麼它是怎麼用的呢?官方給出的解釋如下:
(1)-1
,表示有線程正在進行初始化操作。
(2)-(1 + nThreads),
表示有n個線程正在一起擴容。
(3)0
,默認值,後續在真正初始化的時候使用默認容量。
(4)> 0
,初始化或擴容完成後下一次的擴容門檻 。
8、總結
文章會不定時更新,有時候一天多更新幾篇,如果幫助您復習鞏固瞭知識點,後續會億點點的更新!希望大傢多多關註WalkonNet的其他內容!
推薦閱讀:
- 淺談Java源碼ConcurrentHashMap
- JDK1.8中的ConcurrentHashMap使用及場景分析
- Java源碼解析之ConcurrentHashMap
- 解析ConcurrentHashMap: 紅黑樹的代理類(TreeBin)
- 聊一聊concurrenthashmap的size方法原理