基于JDK1.8的HashMap部分源碼解讀哨啃。這里就解讀一下map的put方法截驮。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//定義一些變量
Node<K,V>[] tab; Node<K,V> p; int n, i;
//進(jìn)行一下判斷再愈，若符合判斷的，表示該map剛創(chuàng)建，還沒存放過元素
if ((tab = table) == null || (n = tab.length) == 0)
//進(jìn)行map的的一些參數(shù)設(shè)置弱左，里面會去設(shè)置容量，擴(kuò)容因子等炕淮。map的擴(kuò)容也是調(diào)的該方法
n = (tab = resize()).length;
// 判斷該索引位是否已經(jīng)存在元素
if ((p = tab[i = (n - 1) & hash]) == null)
//不存在元素拆火，則在該索引位創(chuàng)建一個Node元素對象
tab[i] = newNode(hash, key, value, null);
else {
//存在元素
Node<K,V> e; K k;
//判斷該存在的元素的key是否與要存入的元素一致，若一致，則將e的引用執(zhí)行該已存在的對象
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
//已存在的元素的key與傳入的key不同们镜，且該索引處的數(shù)據(jù)結(jié)構(gòu)是否已經(jīng)變成樹結(jié)構(gòu)币叹，則增加樹節(jié)點。其內(nèi)部設(shè)計到數(shù)結(jié)構(gòu)的一些算法操作模狭，左旋右旋之類的
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//已存在元素的下一個節(jié)點為空颈抚，將要存入的元素放在該處
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//TREEIFY_THRESHOLD=8，如果鏈表的長度大于等于8嚼鹉，則轉(zhuǎn)為樹結(jié)構(gòu)贩汉，其方法內(nèi)部有條件要求的，要node[]的長度大于MIN_TREEIFY_CAPACITY=64才會變成樹結(jié)構(gòu)锚赤，不然會進(jìn)行一次擴(kuò)容
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
//如果鏈表中的元素的key與要存入的key一致匹舞，則跳出循環(huán)
break;
//獲取鏈表的下一個元素，接著做上述操作
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
//若e對象不為null且onlyIfAbsent 為false线脚，則將傳入的value替換原有的value值赐稽，并返回原有值。（已存在的元素跟要存入的元素如果key不同浑侥，該操作沒啥特殊意義）
e.value = value;
//該方法里沒做什么姊舵，空實現(xiàn)而已
afterNodeAccess(e);
return oldValue;
}
}
//若有增加新的節(jié)點，則modCount+1
++modCount;
if (++size > threshold)
//如果添加完元素后锭吨，node[]滿足擴(kuò)容條件蠢莺，則進(jìn)行擴(kuò)容
resize();
//該方法里沒做什么，空實現(xiàn)而已
afterNodeInsertion(evict);
return null;
}
/**
* Replaces all linked nodes in bin at index for given hash unless
* table is too small, in which case resizes instead.
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//MIN_TREEIFY_CAPACITY的值為64
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
// 進(jìn)行node[]的擴(kuò)容
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
//對生成的數(shù)結(jié)構(gòu)進(jìn)行順序調(diào)整
hd.treeify(tab);
}
}
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
//若原數(shù)組長度已經(jīng)大于等于最多允許長度零如，則不再擴(kuò)容了
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//新生產(chǎn)的數(shù)組長度擴(kuò)大為原來的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//新生產(chǎn)的擴(kuò)容銀子也擴(kuò)大為原來的2倍
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
//創(chuàng)建新容量的數(shù)組
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
//遍歷舊node[]數(shù)組中的元素躏将，將其更新到新的數(shù)組中
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
//這里可以直接賦值，不用擔(dān)心這個索引位置已經(jīng)有元素存在考蕾，細(xì)品祸憋，這就是采用2的n次方擴(kuò)容的好處
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
//直接判斷新增的那一位與元素的hash值的結(jié)果。
//該處有疑問可以參考上《關(guān)于HashMap的源碼解讀一》
if ((e.hash & oldCap) == 0) {
//如果結(jié)果為0肖卧，表示其索引位置沒變
if (loTail == null)
//低位鏈表頭
loHead = e;
else
loTail.next = e;
//低位鏈表尾
loTail = e;
}
else {
if (hiTail == null)
//高位鏈表頭
hiHead = e;
else
hiTail.next = e;
//高位鏈表尾
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
//因為是擴(kuò)容一倍蚯窥，所以該高位索引位置只要加上原來的容量值即可
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
