文章目錄
- ConcurrentHashMap
- 常量
-
- MAXIMUM_CAPACITY
- DEFAULT_CAPACITY
- MAX_ARRAY_SIZE
- DEFAULT_CONCURRENCY_LEVEL
- LOAD_FACTOR
- TREEIFY_THRESHOLD
- UNTREEIFY_THRESHOLD
- MIN_TREEIFY_CAPACITY
- MIN_TRANSFER_STRIDE
- RESIZE_STAMP_BITS
- RESIZE_STAMP_SHIFT
- MAX_RESIZERS
- HASHCODE
- NCPU
- sizeCtl
- table
- 方法
-
- initTable
- tableSizeFor
- put
- tryPresize
- addCount
- transfer
- helpTranfer
- get
ConcurrentHashMap
A hash table supporting full concurrency of retrievals and high expected concurrency for updates.
摘自
java.util.concurrent.ConcurrentHashMap
注釋的第一行,感覺很霸氣。
總結:
- 核心思想:CAS+Double Check+死循環
- 通過降低鎖粒度來處理不同資源的操作争奪同一個鎖引起的阻塞,擷取高性能。
- 一個桶一個鎖
- 并發擴容
- 多個消費者去消費一批資料
- sizeCtl掌控着ConcurrentHashMap
- 通過一個變量的符号位和掩碼位控制各種運作狀态
ConcurrentHashMap是一種并發安全的HashMap,核心思想是CAS+Double Check+死循環。
學習交流群:891193617
常量
MAXIMUM_CAPACITY
最大表容量
/**
* The largest possible table capacity. This value must be
* exactly 1<<30 to stay within Java array allocation and indexing
* bounds for power of two table sizes, and is further required
* because the top two bits of 32bit hash fields are used for
* control purposes.
*/
private static final int MAXIMUM_CAPACITY = 1 << 30;//tab.length <= 1073741824
DEFAULT_CAPACITY
預設表容量
/**
* The default initial table capacity. Must be a power of 2
* (i.e., at least 1) and at most MAXIMUM_CAPACITY.
*/
private static final int DEFAULT_CAPACITY = 16;
//預設初始化表的容量,必須是2的幂次方,并且最大是 MAXIMUM_CAPACITY。
MAX_ARRAY_SIZE
toArray()時最大數組長度
/**
* The largest possible (non-power of two) array size.
* Needed by toArray and related methods.
*/
static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//用于toArray與其相關方法的,轉為Collection視圖的最大數組長度
DEFAULT_CONCURRENCY_LEVEL
并發級别
/**
* The default concurrency level for this table. Unused but
* defined for compatibility with previous versions of this class.
*/
private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
//并發級别,沒啥用,為了相容舊版本而定義的
LOAD_FACTOR
加載因子
/**
* The load factor for this table. Overrides of this value in
* constructors affect only the initial table capacity. The
* actual floating point value isn't normally used -- it is
* simpler to use expressions such as {@code n - (n >>> 2)} for
* the associated resizing threshold.
*/
private static final float LOAD_FACTOR = 0.75f;
//加載因子,擴容門檻值 = 表容量 * 加載因子
TREEIFY_THRESHOLD
樹化門檻值
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2, and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8;
// 連結清單轉紅黑樹的門檻值,具體看注釋
UNTREEIFY_THRESHOLD
取消樹化門檻值
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;
//取消樹形的門檻值,僅在resize操作時會檢測節點數小于 UNTREEIFY_THRESHOLD 時會樹轉連結清單
MIN_TREEIFY_CAPACITY
樹化所需最低容量
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* The value should be at least 4 * TREEIFY_THRESHOLD to avoid
* conflicts between resizing and treeification thresholds.
*/
static final int MIN_TREEIFY_CAPACITY = 64;
// 連結清單轉樹要求的 最低表容量 參考 java.util.concurrent.ConcurrentHashMap#treeifyBin
MIN_TRANSFER_STRIDE
并發擴容時每一批資料的桶數量
/**
* Minimum number of rebinnings per transfer step. Ranges are
* subdivided to allow multiple resizer threads. This value
* serves as a lower bound to avoid resizers encountering
* excessive memory contention. The value should be at least
* DEFAULT_CAPACITY.
*/
private static final int MIN_TRANSFER_STRIDE = 16;
//簡單了解就是并發擴容時,将表拆成 (table.length / MIN_TRANSFER_STRIDE) 份,
//然後N個線程按份消費,具體參考 java.util.concurrent.ConcurrentHashMap#transfer
RESIZE_STAMP_BITS
sizeCtl 掩碼比特位數,也就是存儲表長度的比特位數
/**
* The number of bits used for generation stamp in sizeCtl.
* Must be at least 6 for 32bit arrays.
*/
private static final int RESIZE_STAMP_BITS = 16;
RESIZE_STAMP_SHIFT
sizeCtl存儲并發擴容線程數的有效位數
/**
* The bit shift for recording size stamp in sizeCtl.
*/
private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
MAX_RESIZERS
并發擴容線程數的最大值
/**
* The maximum number of threads that can help resize.
* Must fit in 32 - RESIZE_STAMP_BITS bits.
*/
private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
// 針對sizeCtl除了掩碼剩下的有效位數(16 = 32 - RESIZE_STAMP_BITS)
// 而16bit最多能表示65535個數字,并發擴容線程數最多是65535,但是代碼上寫的是2開始,是以并發擴容隻支援65534,因為1代表初始化
HASHCODE
/*
* Encodings for Node hash fields. See above for explanation.
*/
static final int MOVED = -1; // hash for forwarding nodes //正在轉移
static final int TREEBIN = -2; // hash for roots of trees //樹
static final int RESERVED = -3; // hash for transient reservations //保留字段
static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash //計算哈希值使用的值
//Node的特殊哈希值代表的意義
NCPU
/** Number of CPUS, to place bounds on some sizings */
static final int NCPU = Runtime.getRuntime().availableProcessors();
//CPU數,如:4核8線程,那麼NCPU=8
sizeCtl
/**
* Table initialization and resizing control. When negative, the
* table is being initialized or resized: -1 for initialization,
* else -(1 + the number of active resizing threads). Otherwise,
* when table is null, holds the initial table size to use upon
* creation, or 0 for default. After initialization, holds the
* next element count value upon which to resize the table.
*/
private transient volatile int sizeCtl;
//當sizeCtl>0時,sizeCtl初始化前是表的容量,初始化後是表擴容的門檻值
//當sizeCtl=-1時,代表表正在擴容
//當sizeCtl<-1時,此時sizeCtl的低16位-1代表并發擴容線程數,也就是最大并發擴容線程數=65535-1
table
約定table中每一個Node成員稱為桶,下标稱為索引
方法
initTable
Lazy模式初始化表
/**
* Initializes table, using the size recorded in sizeCtl.
*/
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {//死循環+CAS+DoubleCheck
if ((sc = sizeCtl) < 0)//有其他線程正在擴容或者初始化
Thread.yield(); // lost initialization race; just spin 釋放Cpu資源....
else if (U.compareAndSetInt(this, SIZECTL, sc, -1)) {//代表我在擴容
try {
if ((tab = table) == null || tab.length == 0) {//再次檢測表是否為空
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;//如果是空參構造 sc = 0
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
sc = n - (n >>> 2);//sc = n - n * 1/4 = 3/4 n = 0.75 n
//到處充滿了位運算...
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}
tableSizeFor
計算表容量的函數,通過任意一個正整數計算出距離最近的2的幂次方的數
/**
* Returns a power of two table size for the given desired capacity.
* See Hackers Delight, sec 3.2
*/
private static final int tableSizeFor(int c) {
int n = -1 >>> Integer.numberOfLeadingZeros(c - 1);
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
x = 2 ^ m //x是2的m次方
y = N &(x - 1)// N是一個整數, N 和(x - 1)位與 的結果是 y
=> y ∈ [0, x) (N ∈ Z) // y 的範圍是 [0, x), N是整數
// 相當于 N % x 的結果也是 y ∈ [0, x),也可以讓任意數字最後落在這個區間内
// 這種寫法經常出現在 有符号數轉無符号數
//例如:
byte b = -20;
short s = b & 255;
System.out.println(s);
> 236
表容量定義為 2的幂次方 的優點
-
快速計算桶的索引index=(table.length - 1) & hash
- 擴容時,隻需要左移1位,如此一來,節點轉移後的下标也可以快速推斷出來
- 桶在
的索引隻有2中可能nextTable
- 原位置(
)hash & table.length == 0
- 原位置 + table.length (
)hash & table.length != 0
- 原位置(
- 桶在
-
就可以儲存table.length5bits
- table.length永遠是2的幂次方,是以table.length的二進制中隻有一個1
- 定義
為index
的在二進制中索引,1
index ∈ [0, 31)
-
隻需要0-31
就可以存儲,這種思路類似壓縮稀疏數組5bits
- 在
中,java.util.concurrent.ConcurrentHashMap#resizeStamp
static final int resizeStamp(int n) { //Integer.numberOfLeadingZeros(n) 可以拿到二進制中1的索引 //(1 << (RESIZE_STAMP_BITS - 1)) return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1)); }
- 由于
的Java
有int
,表示32bits
需要index
,但是需要一個5bits
需要一個将其變成負數的符号位,是以sizeCtl
必須大于等于6RESIZE_STAMP_BITS
- 在
put
添加鍵值對,實際函數 java.util.concurrent.ConcurrentHashMap#putVal(K key, V value, boolean onlyIfAbsent)
- key:欲插入的鍵
- value:欲插入的值
- onlyIfAbsent:重複時不覆寫,預設是覆寫是以put函數調用時傳入的是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();//懶加載,如果第一次put就初始化表
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {//如果桶裡的資料是null
//i = (n - 1) & hash) 計算桶的索引
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
//如果沒有并發操作 或者 并發沒有對這個桶進行填充 那就添加結束
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)//正在轉移
tab = helpTransfer(tab, f);//幫助轉移
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;// 如果桶的資料不是null并且鍵與參數key相同就直接傳回
else {// 如果桶有資料 解決沖突
V oldVal = null;
synchronized (f) {//對桶上鎖
if (tabAt(tab, i) == f) { //校驗進入鎖之前是否有并發改變了桶的資料
if (fh >= 0) {//連結清單的頭節點
binCount = 1;//節點數量 因為桶裡資料不為null,是以至少為1
for (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;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {//周遊完了
pred.next = new Node<K,V>(hash, key, value);
break;
}
}
}
else if (f instanceof TreeBin) {//哈希值小于0時,判斷是否紅黑樹結構
Node<K,V> p;
binCount = 2;//紅黑樹至少2節點,第一個節點是紅黑樹的标志
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
else if (f instanceof ReservationNode)//保留節點,暫時用不到
throw new IllegalStateException("Recursive update");
}
}
if (binCount != 0) {//桶内節點數不為0
if (binCount >= TREEIFY_THRESHOLD)//桶内節點數到達 連結清單轉樹 的門檻值
treeifyBin(tab, i);//連結清單轉樹
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);//單獨分析
return null;
}
tryPresize
預判提前嘗試擴容
/**
* Tries to presize table to accommodate the given number of elements.
*
* @param size number of elements (doesn't need to be perfectly accurate)
*/
private final void tryPresize(int size) {
int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
tableSizeFor(size + (size >>> 1) + 1);
int sc;
while ((sc = sizeCtl) >= 0) {//不是在初始化或者擴容
Node<K,V>[] tab = table; int n;
if (tab == null || (n = tab.length) == 0) {//當第一次調用的是putAll函數
n = (sc > c) ? sc : c;
if (U.compareAndSetInt(this, SIZECTL, sc, -1)) {//将sizeCtl标志為正在初始化
try {
if (table == tab) {
//由于無鎖,是以double check [table]是否已經被其他線程初始化
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = nt;
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
}
}
else if (c <= sc || n >= MAXIMUM_CAPACITY)
//容量足夠或已是最大,你盡管插,暫時不需要擴容
break;
else if (tab == table) {
int rs = resizeStamp(n);//c超過門檻值了,需要擴容
if (U.compareAndSetInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))//第一條擴容線程
transfer(tab, null);
}
}
}
addCount
更新元素數量
- x:增加元素數量
- check:是否需要check擴容
/**
* Adds to count, and if table is too small and not already
* resizing, initiates transfer. If already resizing, helps
* perform transfer if work is available. Rechecks occupancy
* after a transfer to see if another resize is already needed
* because resizings are lagging additions.
*
* @param x the count to add
* @param check if <0, don't check resize, if <= 1 only check if uncontended
*/
private final void addCount(long x, int check) {
CounterCell[] cs; long b, s;
if ((cs = counterCells) != null ||
!U.compareAndSetLong(this, BASECOUNT, b = baseCount, s = b + x)) {
CounterCell c; long v; int m;
boolean uncontended = true;
if (cs == null || (m = cs.length - 1) < 0 ||
(c = cs[ThreadLocalRandom.getProbe() & m]) == null ||
!(uncontended =
U.compareAndSetLong(c, CELLVALUE, v = c.value, v + x))) {
fullAddCount(x, uncontended);
return;
}
if (check <= 1)
return;
s = sumCount();
}
//上面是對計數器的一些操作 不多說
//下面的對表擴容和sizeCtl變量的關鍵點,有一個國人發現了此處的BUG,2018年底才修複的
//https://bugs.java.com/bugdatabase/view_bug.do?bug_id=JDK-8214427
if (check >= 0) {
Node<K,V>[] tab, nt; int n, sc;
while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
// 元素數量到達擴容門檻值
int rs = resizeStamp(n) << RESIZE_STAMP_SHIFT;
// 将表容量二進制中`1`的索引存到rs
if (sc < 0) {
//由于`(tab = table) != null`成立,是以table不是null => sc<-1
//此時表正在擴容
if (sc == rs + MAX_RESIZERS || sc == rs + 1 ||
(nt = nextTable) == null || transferIndex <= 0)
// sc = rs + MAX_RESIZERS,代表sc的有效位數全部是1了代表并發擴容線程數到達上限
// sc == rs + 1 代表擴容任務已全部完成,本線程直接跳出
// 隻有全部線程完成任務才會sc = rs + 1,否則需要繼續領取任務繼續轉移。
// 由于擴容是倒序轉移的,當transferIndex <= 0 時,代表擴容結束了
// 當nextTable == null時,說明擴容結束了
// 以上可以從 transfer()函數分析得出
break;
if (U.compareAndSetInt(this, SIZECTL, sc, sc + 1))
//本線程加入并發擴容大家庭
transfer(tab, nt);//擴容開始
}
else if (U.compareAndSetInt(this, SIZECTL, sc, rs + 2))
// sc >= 0 第一條線程擴容 sizeCtl被指派為 rs + 2
// 從此行代碼可以看出 并發擴容的線程數 僅是sizeCtl的有效位數
// 這裡有效位數被定義為16,是以 => 低16位 - 1 = 并發擴容的線程數
transfer(tab, null);
s = sumCount();
}
}
}
transfer
并發擴容函數
/**
* Moves and/or copies the nodes in each bin to new table. See
* above for explanation.
*/
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
if (nextTab == null) { // initiating
try {
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
nextTab = nt;
} catch (Throwable ex) { // try to cope with OOME
sizeCtl = Integer.MAX_VALUE;
return;
}
nextTable = nextTab;
transferIndex = n;
}
int nextn = nextTab.length;
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
boolean advance = true;
boolean finishing = false; // to ensure sweep before committing nextTab
for (int i = 0, bound = 0;;) {
Node<K,V> f; int fh;
while (advance) {
int nextIndex, nextBound;
if (--i >= bound || finishing)
advance = false;
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
}
else if (U.compareAndSetInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
bound = nextBound;
i = nextIndex - 1;
advance = false;
}
}
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
if (finishing) {
nextTable = null;
table = nextTab;
sizeCtl = (n << 1) - (n >>> 1);
return;
}
if (U.compareAndSetInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
finishing = advance = true;
i = n; // recheck before commit
}
}
else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);
else if ((fh = f.hash) == MOVED)
advance = true; // already processed
else {
synchronized (f) {//對桶加鎖
if (tabAt(tab, i) == f) {//是否有并發沖突,其他線程把這個桶先轉移了
Node<K,V> ln, hn;
if (fh >= 0) {
int runBit = fh & n;//目前節點的标志位
//假設n = 16,那麼runBit就代表 fh二進制的第5位是否為1
Node<K,V> lastRun = f;
for (Node<K,V> p = f.next; p != null; p = p.next) {
int b = p.hash & n;
if (b != runBit) {
runBit = b;
lastRun = p;
}
}
//上面循環是為了循環最後一段 标志位不變的子連結清單
if (runBit == 0) {//标志位為0代表最後一段子連結清單不需要轉移
ln = lastRun;//ln代表轉移後位置不變的連結清單的頭節點
hn = null;//hn代表轉移後位置改變的連結清單的頭節點
}
else {
hn = lastRun;
ln = null;
}
for (Node<K,V> p = f; p != lastRun; p = p.next) {
int ph = p.hash; K pk = p.key; V pv = p.val;
if ((ph & n) == 0)
ln = new Node<K,V>(ph, pk, pv, ln);//巧妙構造連結清單...
else
hn = new Node<K,V>(ph, pk, pv, hn);
}
setTabAt(nextTab, i, ln);//位置不變的連結清單
setTabAt(nextTab, i + n, hn);//位置改變的連結清單
//由于表長度是2的幂次方,是以轉移後的位置隻有這2可能,證明很簡單..
setTabAt(tab, i, fwd);//對舊表标志這個桶已經轉移了
advance = true;
}
else if (f instanceof TreeBin) {//紅黑樹的轉移
TreeBin<K,V> t = (TreeBin<K,V>)f;
TreeNode<K,V> lo = null, loTail = null;
TreeNode<K,V> hi = null, hiTail = null;
int lc = 0, hc = 0;
for (Node<K,V> e = t.first; e != null; e = e.next) {
int h = e.hash;
TreeNode<K,V> p = new TreeNode<K,V>
(h, e.key, e.val, null, null);
if ((h & n) == 0) {
if ((p.prev = loTail) == null)
lo = p;
else
loTail.next = p;
loTail = p;
++lc;
}
else {
if ((p.prev = hiTail) == null)
hi = p;
else
hiTail.next = p;
hiTail = p;
++hc;
}
}
ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
(hc != 0) ? new TreeBin<K,V>(lo) : t;
//如果位置不變的的樹 的 節點數 ≤ 取消樹化的門檻值 就會将樹轉連結清單
hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
(lc != 0) ? new TreeBin<K,V>(hi) : t;
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);
advance = true;
}
else if (f instanceof ReservationNode)
throw new IllegalStateException("Recursive update");
}
}
}
}
}
helpTranfer
幫助轉移,簡直就是Mini版本addCount
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
Node<K,V>[] nextTab; int sc;
if (tab != null && (f instanceof ForwardingNode) &&
(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
int rs = resizeStamp(tab.length) << RESIZE_STAMP_SHIFT;
while (nextTab == nextTable && table == tab &&
(sc = sizeCtl) < 0) {
if (sc == rs + MAX_RESIZERS || sc == rs + 1 ||
transferIndex <= 0)
break;
if (U.compareAndSetInt(this, SIZECTL, sc, sc + 1)) {
transfer(tab, nextTab);
break;
}
}
return nextTab;
}
return table;
}
get
如果表中存在,就傳回此值,不存在就傳回null,key不能為null,否則抛出異常
/**
* Returns the value to which the specified key is mapped,
* or {@code null} if this map contains no mapping for the key.
*
* <p>More formally, if this map contains a mapping from a key
* {@code k} to a value {@code v} such that {@code key.equals(k)},
* then this method returns {@code v}; otherwise it returns
* {@code null}. (There can be at most one such mapping.)
*
* @throws NullPointerException if the specified key is null
*/
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());//計算哈希值
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {//如果表不為空,并且hash對應的桶不為空
if ((eh = e.hash) == h) { // 判斷桶内資料的哈希值等于參數的哈希值
if ((ek = e.key) == key || (ek != null && key.equals(ek)))//繼續判斷key
return e.val;
}
else if (eh < 0)//桶内是紅黑樹,通過頭節點搜尋指定鍵
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null) {//最後進行連結清單周遊查詢
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}