如有轉(zhuǎn)載請(qǐng)注明出處 http://www.itdecent.cn/p/f24fa4fa6b08
put(K key, V value)
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
通過(guò)put方法我們可以看到有三種情況：
- 當(dāng)數(shù)組為null
- 當(dāng)數(shù)組中的鏈表沒(méi)有節(jié)點(diǎn)
- 當(dāng)數(shù)組中的鏈表有節(jié)點(diǎn)
- 如果數(shù)組中的值為樹(shù)
- 如果數(shù)組中的值為鏈表
當(dāng)數(shù)組為null
當(dāng)數(shù)組為null的時(shí)候，他會(huì)調(diào)用resize方法，resize方法用來(lái)給HashMap擴(kuò)容，當(dāng)HashMap中的數(shù)據(jù)越來(lái)越多就會(huì)使key的碰撞概率越來(lái)越大，為了減少碰撞的概率，我們就需要給HashMap擴(kuò)容，擴(kuò)容之后HashMap需要將原來(lái)的數(shù)據(jù)重新計(jì)算位置放入新的數(shù)組中。
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) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
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"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
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;
if ((e.hash & oldCap) == 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;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
這個(gè)擴(kuò)容又有三種可能：
- 如果老的數(shù)組有值
- 老的數(shù)組的閾值大于0，并且老數(shù)組沒(méi)有值
這種情況解釋一下就是當(dāng)我們創(chuàng)建HashMap的時(shí)候可以傳入一個(gè)初始化大小，當(dāng)還沒(méi)有向HashMap中添加數(shù)據(jù)的時(shí)候，它就不滿足條件1，反而滿足條件2
- 當(dāng)數(shù)組為空，并且他的閾值也為0的時(shí)候
這種情況出現(xiàn)在創(chuàng)建HashMap的時(shí)候使用的是空參的構(gòu)造方法
擴(kuò)容-如果老的數(shù)組有值
- 如果老數(shù)組的長(zhǎng)度已經(jīng)到達(dá)最大長(zhǎng)度，那么他的閾值會(huì)設(shè)置為Integer的最大值，并且不會(huì)再去擴(kuò)容
- 如果擴(kuò)容兩倍之后沒(méi)有達(dá)到最大值那么就將閾值擴(kuò)大兩倍
擴(kuò)容-老的數(shù)組的閾值大于0，并且老數(shù)組沒(méi)有值
直接將老數(shù)組的閾值作為數(shù)組的長(zhǎng)度
擴(kuò)容-當(dāng)數(shù)組為空，并且他的閾值也為0的時(shí)候
初始化默認(rèn)數(shù)組長(zhǎng)度為16，閾值為數(shù)組長(zhǎng)度加載因子=160.75=12
做完以上操作我們就知道這個(gè)數(shù)組到底有多大了，接著去創(chuàng)建數(shù)組。接下來(lái)就是將老的數(shù)組中的數(shù)據(jù)存到新數(shù)組中對(duì)應(yīng)的位置。
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
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;
if ((e.hash & oldCap) == 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;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
這里遍歷了老的數(shù)組，將數(shù)組每一個(gè)位置的鏈表拿出來(lái)，又分成了三種情況
- 鏈表只有一個(gè)節(jié)點(diǎn)
將該鏈表重新計(jì)算位置放在新的數(shù)組中 - 樹(shù)結(jié)構(gòu)
本節(jié)我們暫時(shí)不細(xì)看，下一節(jié)細(xì)挖一下紅黑樹(shù)的查找和添加 - 鏈表有多個(gè)節(jié)點(diǎn)
(e.hash & oldCap) == 0 表示該節(jié)點(diǎn)還在原來(lái)數(shù)組中的位置(表示hash值的高位為0，也就是不超過(guò)原數(shù)組長(zhǎng)度的大小)，直接放入新數(shù)組的對(duì)應(yīng)位置就好，否則就重新計(jì)算放入新數(shù)組的位置
舉個(gè)例子理解一下為什么放在j+oldCap位置
數(shù)組長(zhǎng)度為16，二進(jìn)制為10000
有一個(gè)hash值二進(jìn)制為 10001，
他在原數(shù)組中位置是1，但是當(dāng)數(shù)組擴(kuò)容以后長(zhǎng)度變成了32，二進(jìn)制為100000
那他在新數(shù)組中的位置就是 32-1(11111)&10001=10001,十進(jìn)制就是17
就相當(dāng)于1+16(原數(shù)組的長(zhǎng)度)
當(dāng)數(shù)組中的鏈表沒(méi)有節(jié)點(diǎn)
此時(shí)直接創(chuàng)建一個(gè)節(jié)點(diǎn)放入數(shù)組中
當(dāng)數(shù)組中的鏈表有節(jié)點(diǎn)
- 數(shù)組中的鏈表已經(jīng)轉(zhuǎn)換成了紅黑樹(shù)
這個(gè)我們下一篇再細(xì)挖 - 數(shù)組中還是存放的鏈表
判斷鏈表的長(zhǎng)度是不是超過(guò)8，如果超過(guò)8就需要轉(zhuǎn)成紅黑樹(shù)，如果沒(méi)有超過(guò)8就創(chuàng)建一個(gè)節(jié)點(diǎn)放在后面，如果這個(gè)節(jié)點(diǎn)已經(jīng)存在就將原值返回。
