上一篇說(shuō)到空HashMap的put函數(shù)執(zhí)行過(guò)程，今天我們繼續(xù)看下非空HashMap的put函數(shù)執(zhí)行過(guò)程。上一篇鏈接我貼出來(lái)，供大家快速跳轉(zhuǎn)過(guò)去。
一起精讀源代碼系列(1) HashMap(一) put函數(shù)的執(zhí)行過(guò)程
那么當(dāng)HashMap中已經(jīng)存有元素的時(shí)候會(huì)發(fā)生什么呢？話不多說(shuō)，直接上putVal函數(shù)的前幾行代碼
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);
上篇分析的HashMap為空所以會(huì)進(jìn)這行if
(tab = table) == null || (n = tab.length) == 0
這次并不會(huì)進(jìn)，那下一行的if就需要判斷一下了，因?yàn)橛?jì)算出來(lái)的數(shù)組下標(biāo)對(duì)應(yīng)的節(jié)點(diǎn)p既可能為null，也可能不為null。打個(gè)比方
//代碼片段1
Map<Integer,String> map1 = new HashMap<>();
map1.put(1,"1");
map1.put(2,"2");
//代碼片段2
Map<Integer,String> map2 = new HashMap<>();
map2.put(1,"1");
map2.put(1,"2");
代碼片段1執(zhí)行的時(shí)候第二次put這里的p就是null，而代碼片段2執(zhí)行的時(shí)候第二次put這里的p就不是null。還是老規(guī)矩，分兩種情況一行行分析。
當(dāng)節(jié)點(diǎn)p為null的時(shí)候，我們可以看到這里會(huì)執(zhí)行newNode函數(shù)。也就是這么一個(gè)玩意：
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
return new Node<>(hash, key, value, next);
}
這個(gè)已經(jīng)分析過(guò)了，就是新建了一個(gè)Node節(jié)點(diǎn)。那么當(dāng)p不為null的時(shí)候繼續(xù)往下看。先來(lái)看第一個(gè)if會(huì)不會(huì)進(jìn)
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
按照從左到右依次執(zhí)行的順序，p.hash==hash這個(gè)肯定為true，因?yàn)閗ey是一樣的(從代碼片段1可以看到，都是1)，p.key==key這個(gè)也是true，所以這整個(gè)表達(dá)式一定是true，所以就會(huì)執(zhí)行e=p，把節(jié)點(diǎn)p賦值給e。這里暫時(shí)還看不出什么，我們繼續(xù)往后看。那進(jìn)了這個(gè)if，后面的else都直接跳過(guò)即可。來(lái)到最后
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
很明顯會(huì)進(jìn)到這里，e的value其實(shí)就是p的value，這時(shí)候會(huì)賦值給oldValue。下面又有一個(gè)if，其中的onlyIfAbsent這個(gè)參數(shù)傳進(jìn)來(lái)是false。參考putVal函數(shù)的注釋
* @param onlyIfAbsent if true, don't change existing value
這意思就是如果這個(gè)參數(shù)傳了true，則表示put同一個(gè)key的鍵值對(duì)進(jìn)HashMap的時(shí)候不替換原來(lái)的值。這個(gè)值默認(rèn)為false，所以if的條件是true，就會(huì)用新value替換原來(lái)的value了。同樣的，后面也執(zhí)行了一個(gè)空函數(shù)afterNodeAccess（這個(gè)函數(shù)在linkedHashMap有實(shí)現(xiàn)），并且這種情況下會(huì)把老的value返回。這樣我們就發(fā)現(xiàn)了，put函數(shù)其實(shí)是有返回值的。
好的，這下我們明白了同樣key不同value的替換過(guò)程。那接下來(lái)我們分析如果發(fā)生了所謂的hash沖突，HashMap會(huì)如何處理。什么是Hash沖突呢？上一篇我們聊到，HashMap會(huì)根據(jù)key計(jì)算出hash值，然后再與n-1按位與操作計(jì)算出在數(shù)組中的下標(biāo)，有了下標(biāo)，就往數(shù)組中添加一個(gè)Node。那如果不同的key得到的hash值相同的時(shí)候就會(huì)發(fā)生hash沖突。我寫(xiě)了一個(gè)簡(jiǎn)單的類來(lái)模擬hash沖突的過(guò)程。
import java.util.Objects;
public class User {
private String name;
public User(String name) {
this.name = name;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
@Override
public String toString() {
return "User{" +
"name='" + name + '\'' +
'}';
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
User user = (User) o;
return Objects.equals(name, user.name);
}
@Override
public int hashCode() {
if (name.equals("wang") || name.equals("WANG")) {
return 0x6666;
}
return super.hashCode();
}
}
hashcode函數(shù)的意思就是當(dāng)name為wang或者WANG的時(shí)候，hash值設(shè)置為同樣的0x6666。equals函數(shù)的意思就是當(dāng)兩個(gè)對(duì)象的name字段相等時(shí)就認(rèn)為兩個(gè)對(duì)象相等。
好，那接下來(lái)我們用這個(gè)類做一些事情。我們分別用wang和WANG作為HashMap的key，看看會(huì)發(fā)生什么。
User user1 = new User("wang");
User user2 = new User("WANG");
Map<User,String> map = new HashMap<>();
map.put(user1,"30");
map.put(user2,"32");
很顯然，這里的user1和user2用了wang和WANG作為key，根據(jù)我們上面的設(shè)定，兩個(gè)對(duì)象的hashCode值是一樣的。下面貼出這種情況下HashMap的執(zhí)行過(guò)程代碼
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;
}
代碼很少，但是并沒(méi)有那么好理解。首先是第一個(gè)if，p.next為null，也就是說(shuō)p是鏈表的尾結(jié)點(diǎn)，或者說(shuō)鏈表中的最后一個(gè)節(jié)點(diǎn)。這段代碼其實(shí)就是在循環(huán)查找鏈表直到鏈表的尾部。我們的代碼片段剛好符合這個(gè)邏輯，所以會(huì)進(jìn)到這個(gè)if。p.next=newNode，也就是說(shuō)往鏈表的尾部又插入了一個(gè)元素，然后break跳出for循環(huán)。因此我們可以得出第一個(gè)結(jié)論，當(dāng)HashMap中發(fā)生hash沖突的時(shí)候，會(huì)找到數(shù)組的下標(biāo)，然后往數(shù)組的下標(biāo)處對(duì)應(yīng)的鏈表尾部插入一個(gè)節(jié)點(diǎn)。
再往下一段代碼就是同樣key的一個(gè)value替換過(guò)程，之前也分析過(guò)，就不再多做分析了。
到了這里，大家應(yīng)該能理解數(shù)組和鏈表在HashMap中的應(yīng)用了。那么我們也會(huì)思考一個(gè)問(wèn)題，在某種場(chǎng)景下鏈表長(zhǎng)度可能會(huì)越來(lái)越大，是不是就有可能影響到HashMap的查詢效率呢？甚至，在極端情況下，HashMap的查詢時(shí)間復(fù)雜度可能會(huì)由O(1)退化到O(n)，這可是很嚴(yán)重的性能故障。為了解決這個(gè)問(wèn)題，JDK1.8引入了紅黑樹(shù)。紅黑樹(shù)是一種平衡的二叉查找樹(shù)，查詢、插入、刪除節(jié)點(diǎn)的時(shí)間復(fù)雜度均為O(logn)，是非常高效的一種數(shù)據(jù)結(jié)構(gòu)。putVal函數(shù)中涉及到紅黑樹(shù)的代碼如下：
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
也就是當(dāng)binCount這個(gè)值大于等于7或者鏈表長(zhǎng)度大于等于8的時(shí)候，會(huì)調(diào)用treeifyBin()把鏈表轉(zhuǎn)為紅黑樹(shù)。紅黑樹(shù)的代碼不太好寫(xiě)，還涉及到數(shù)據(jù)結(jié)構(gòu)和算法相關(guān)的知識(shí)，這不在本文的討論范圍，所以我不做太多的擴(kuò)展，有興趣的同學(xué)可以下去深入研究一下。
我們來(lái)總結(jié)一下整個(gè)put過(guò)程中數(shù)組、鏈表、紅黑樹(shù)之間的關(guān)系。首先數(shù)組的下標(biāo)是通過(guò)key值計(jì)算出來(lái)的，數(shù)組的value就是Node節(jié)點(diǎn)，當(dāng)沒(méi)有hash沖突的時(shí)候，Node節(jié)點(diǎn)的next是null，當(dāng)發(fā)生了hash沖突，Node節(jié)點(diǎn)的尾部會(huì)新增一個(gè)節(jié)點(diǎn)，鏈表長(zhǎng)度加1，而當(dāng)鏈表長(zhǎng)度大于等于7，會(huì)轉(zhuǎn)化為紅黑樹(shù)。
理解了這些之后，我們最后再來(lái)看一下put過(guò)程中另一個(gè)非常關(guān)鍵的點(diǎn)，HashMap擴(kuò)容。隨著我們不斷往HashMap中添加元素，hashMap的容量不足以容納我們放進(jìn)去的數(shù)據(jù)的時(shí)候，自然就需要擴(kuò)容了。相關(guān)代碼：
if (++size > threshold)
resize();
很顯然，當(dāng)hashMap的size大于閾值的時(shí)候，會(huì)執(zhí)行一次擴(kuò)容。上一篇我們說(shuō)到HashMap的默認(rèn)閾值為12，也就是在默認(rèn)情況下，當(dāng)hashMap的容量到達(dá)最大默認(rèn)容量16*0.75的時(shí)候，會(huì)進(jìn)行擴(kuò)容操作。0.75是指HashMap的負(fù)載因子。我先來(lái)解釋下這個(gè)負(fù)載因子的作用。在散列表這種數(shù)據(jù)結(jié)構(gòu)里面，有一個(gè)名詞叫做裝載因子，當(dāng)散列表中空閑位置不多的時(shí)候，散列沖突的概率就會(huì)大大提高。為了盡可能保證散列表的操作效率，一般情況下，我們會(huì)盡可能保證散列表中有一定比例的空閑槽位。我們用裝載因子（load factor）來(lái)表示空位的多少。裝載因子的計(jì)算公式如下:
散列表的裝載因子=填入表中的元素個(gè)數(shù)/散列表的長(zhǎng)度
在HashMap中，定義了一個(gè)默認(rèn)的裝載因子0.75f。為了計(jì)算方便，又定義了閾值threshold，初始值為默認(rèn)最大容量16乘以默認(rèn)裝載因子0.75得到12。當(dāng)HashMap中的容量第一次達(dá)到12以上的時(shí)候，就會(huì)執(zhí)行一次擴(kuò)容，我們就從第一次擴(kuò)容為入口往下看擴(kuò)容過(guò)程的代碼。直接來(lái)到resize函數(shù)的第681行到689行
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
}
可以看出，當(dāng)原來(lái)的容量大于0，會(huì)進(jìn)到這里。看第一個(gè)if，原容量大于等于最大容量MAXIMUM_CAPACITY，查看源碼可知，這個(gè)參數(shù)為23o，這個(gè)場(chǎng)景不涉及，所以不會(huì)進(jìn)。下面的else if，說(shuō)的是原容量擴(kuò)大一倍之后小于最大容量且原容量大于等于默認(rèn)初始容量16，假如我們?cè)萘繛?6，這個(gè)時(shí)候觸發(fā)擴(kuò)容，擴(kuò)大一倍是32，滿足這個(gè)else if的條件，所以得到newCap也就是新容量為32，newThr也就是新閾值為原閾值12擴(kuò)大一倍得到24。由此可得，經(jīng)過(guò)一次擴(kuò)容之后，容量和閾值都擴(kuò)大了一倍。進(jìn)了681行的if，所以后面的else都不會(huì)進(jìn)，直接跳到701行以后。由于這是一個(gè)for循環(huán)，沒(méi)辦法再縮短了，只能一起貼出來(lái)
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è)地方非常復(fù)雜，我會(huì)一行行解釋。首先是把新閾值賦值給了成員變量threshold，然后新建了一個(gè)容量是新容量大小的Node數(shù)組并且賦值給成員變量table。下面的過(guò)程就是把原數(shù)組搬遷到新數(shù)組的過(guò)程，我們都知道數(shù)組的搬遷其實(shí)性能很一般，那這里就可以看下HashMap的源碼是如何實(shí)現(xiàn)舊數(shù)組到新數(shù)組的數(shù)據(jù)搬遷的。
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
這里就不多說(shuō)了，就是一個(gè)數(shù)組的遍歷，只不過(guò)把舊數(shù)組中的值賦值給到e之后，就把這個(gè)值置為null了。
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
這里就是往新數(shù)組中插入數(shù)據(jù)的過(guò)程，如果e.next為null，意思就是這個(gè)地方的Node沒(méi)有引申鏈表，也就是說(shuō)沒(méi)有發(fā)生hash沖突。那e.hash&(newCap-1)計(jì)算出來(lái)的值會(huì)作為舊數(shù)據(jù)在新數(shù)組的下標(biāo)，上一篇我們分析了，由于newCap是2的x次方，所以這里的表達(dá)式其實(shí)就是e.hash對(duì)newCap進(jìn)行取模運(yùn)算。數(shù)據(jù)從舊表搬移到新表之后，即便下標(biāo)發(fā)生了變化，也不會(huì)影響到數(shù)據(jù)的查詢，因?yàn)樵贖ashMap的get函數(shù)里，擴(kuò)容之后，相應(yīng)的取下標(biāo)的計(jì)算也變了，這個(gè)我們后面會(huì)進(jìn)行分析。
接下去繼續(xù)，如果e.next不為null，這里我們先跳過(guò)紅黑樹(shù)直接進(jìn)入到鏈表層面的分析。用do while對(duì)鏈表進(jìn)行遍歷這里不多說(shuō)，重點(diǎn)在于一個(gè)表達(dá)式：(e.hash & oldCap) == 0，相信看過(guò)HashMap源碼的同學(xué)很多人都無(wú)法理解這個(gè)表達(dá)式的意義。下面我?guī)Т蠹疫M(jìn)行詳細(xì)的推導(dǎo)
- 我們已知容量肯定是2的整數(shù)次冪，所以oldCap轉(zhuǎn)為二進(jìn)制就是類似10000這樣的值；
- 如果按位與得到的值為0，則表示e.hash轉(zhuǎn)為二進(jìn)制之后在oldCap對(duì)應(yīng)的1的位置的值一定是0，其他位置可以隨意，例如01101這個(gè)hash值，又例如1101101這個(gè)hash值。只有在oldCap對(duì)應(yīng)1的位置的值是0的前提下，按位與得到的結(jié)果才會(huì)是0；
- 這種情況下，我們分別計(jì)算e.hash&(oldCap-1)和e.hash&(2*oldCap-1)，也就是在(e.hash & oldCap) == 0的前提下計(jì)算擴(kuò)容前后某個(gè)數(shù)據(jù)在數(shù)組中的下標(biāo)。當(dāng)2的x次方減1之后，轉(zhuǎn)為二進(jìn)制會(huì)得到低位全是1的數(shù)據(jù)，擴(kuò)容其實(shí)就是二進(jìn)制數(shù)據(jù)比擴(kuò)容前多了一個(gè)1，而根據(jù)第2點(diǎn)的分析，在多的這個(gè)1的位置上e.hash對(duì)應(yīng)的值是0，因此按位與操作擴(kuò)容前后得到的結(jié)果是一樣的，也就可以推導(dǎo)出4的結(jié)論;
- 在(e.hash & oldCap) == 0前提下，e在新舊數(shù)組的位置不變。
在這種情況下，把原數(shù)組搬移到新數(shù)組的時(shí)候，下標(biāo)都不需要改變。只需要取出當(dāng)前節(jié)點(diǎn)的頭節(jié)點(diǎn)賦值到新節(jié)點(diǎn)即可。
接下來(lái)我們分析(e.hash & oldCap) != 0的時(shí)候。推導(dǎo)過(guò)程如下
- 我們已知容量肯定是2的整數(shù)次冪，所以oldCap轉(zhuǎn)為二進(jìn)制就是類似10000這樣的值；
- 如果按位與得到的值不為0，則表示e.hash轉(zhuǎn)為二進(jìn)制之后在oldCap對(duì)應(yīng)的1的位置的值一定是1，其他位置可以隨意，例如11101這個(gè)hash值，又例如1111101這個(gè)hash值。只有在oldCap對(duì)應(yīng)1的位置的值是1的前提下，按位與得到的結(jié)果才不會(huì)是0；
- 這種情況下，我們分別計(jì)算e.hash&(oldCap-1)和e.hash&(2*oldCap-1)，也就是在(e.hash & oldCap) != 0的前提下計(jì)算擴(kuò)容前后某個(gè)數(shù)據(jù)在數(shù)組中的下標(biāo)。當(dāng)2的x次方減1之后，轉(zhuǎn)為二進(jìn)制會(huì)得到低位全是1的數(shù)據(jù)，擴(kuò)容其實(shí)就是二進(jìn)制數(shù)據(jù)比擴(kuò)容前多了一個(gè)1，而根據(jù)第2點(diǎn)的分析，在多的這個(gè)1的位置上e.hash對(duì)應(yīng)的值是1，因此按位與操作擴(kuò)容前后得到的結(jié)果就是高位上多了一位1。高位多了一個(gè)1也就意味著換算為10進(jìn)制多了2的x次方，也就是多了一個(gè)oldCap的值，可以推導(dǎo)出4的結(jié)論。
- 在(e.hash & oldCap) != 0前提下，e在新舊數(shù)組的位置等于原位置加oldCap。
那到此為止，整個(gè)擴(kuò)容過(guò)程就分析完畢，put函數(shù)也分析的差不多了。
下期預(yù)告，一起精讀源代碼系列(2) Android Handler系列源碼分析?；贏ndroid8.0。
