資訊專欄INFORMATION COLUMN
摘要：當(dāng)鏈表長(zhǎng)度超過默認(rèn)是個(gè)時(shí)，會(huì)將鏈表轉(zhuǎn)換成紅黑樹以提升查找性能。
前言
系列文章目錄
上一篇我們討論了HashMap的擴(kuò)容操作, 提到擴(kuò)容操作發(fā)生在table的初始化或者table大小超過threshold后，而這兩個(gè)條件的觸發(fā)基本上就發(fā)生在put操作中。
本篇我們就來聊聊HashMap的put操作。
本文的源碼基于 jdk8 版本.
put方法HashMap 實(shí)現(xiàn)了Map接口, 因此必須要實(shí)現(xiàn)put方法:
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) */
}
可以看到, put方法是有返回值的, 這里調(diào)用了 putVal 方法, 這個(gè)方法很重要, 我們將通過代碼注釋的方式逐行說明.
在這之前我們先看該方法的參數(shù):
hash
由上面的調(diào)用可知, 該值為hash(key), 是key的hash值, 關(guān)于hash的概念之前已經(jīng)講過了, 這里不再贅述.
key, value
待存儲(chǔ)的鍵值對(duì)
onlyIfAbsent
這個(gè)參數(shù)用于決定待存儲(chǔ)的key已經(jīng)存在的情況下,要不要用新值覆蓋原有的value, 如果為true, 則保留原有值, false 則覆蓋原有值, 從上面的調(diào)用看, 該值為false, 說明當(dāng)key值已經(jīng)存在時(shí), 會(huì)直接覆蓋原有值。
evict
該參數(shù)用來區(qū)分當(dāng)前是否是構(gòu)造模式, 我們?cè)谥v解構(gòu)造函數(shù)的時(shí)候曾經(jīng)提到，HashMap的第四個(gè)構(gòu)造函數(shù)可以通過已經(jīng)存在的Map初始化一個(gè)HashMap, 如果為 false, 說明在構(gòu)造模式下, 這里我們是用在put函數(shù)而不是構(gòu)造函數(shù)里面, 所以為true。
參數(shù)解釋完了之后, 下面我們來逐行看代碼:
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node[] tab; Node p; int n, i;
// 首先判斷table是否是空的
// 我們知道, HashMap的三個(gè)構(gòu)造函數(shù)中, 都不會(huì)初始Table, 因此第一次put值時(shí), table一定是空的, 需要初始化
// table的初始化用到了resize函數(shù), 這個(gè)我們上一篇文章已經(jīng)講過了
// 由此可見table的初始化是延遲到put操作中的
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 這里利用 `(n-1) & hash` 方法計(jì)算 key 所對(duì)應(yīng)的下標(biāo)
// 如果key所對(duì)應(yīng)的桶里面沒有值, 我們就新建一個(gè)Node放入桶里面
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 到這里說明目標(biāo)位置桶里已經(jīng)有東西了
else {
Node e; K k;
// 這里先判斷當(dāng)前待存儲(chǔ)的key值和已經(jīng)存在的key值是否相等
// key值相等必須滿足兩個(gè)條件
// 1. hash值相同
// 2. 兩者 `==` 或者 `equals` 等
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p; // key已經(jīng)存在的情況下, e保存原有的鍵值對(duì)
// 到這里說明要保存的桶已經(jīng)被占用, 且被占用的位置存放的key與待存儲(chǔ)的key值不一致
// 前面已經(jīng)說過, 當(dāng)鏈表長(zhǎng)度超過8時(shí), 會(huì)用紅黑樹存儲(chǔ), 這里就是判斷存儲(chǔ)桶中放的是鏈表還是紅黑樹
else if (p instanceof TreeNode)
// 紅黑樹的部分以后有機(jī)會(huì)再說吧
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
//到這里說明是鏈表存儲(chǔ), 我們需要順序遍歷鏈表
else {
for (int binCount = 0; ; ++binCount) {
// 如果已經(jīng)找到了鏈表的尾節(jié)點(diǎn)了,還沒有找到目標(biāo)key, 則說明目標(biāo)key不存在，那我們就新建一個(gè)節(jié)點(diǎn), 把它接在尾節(jié)點(diǎn)的后面
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 如果鏈表的長(zhǎng)度達(dá)到了8個(gè), 就將鏈表轉(zhuǎn)換成紅黑數(shù)以提升查找性能
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果在鏈表中找到了目標(biāo)key則直接退出
// 退出時(shí)e保存的是目標(biāo)key的鍵值對(duì)
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 到這里說明要么待存儲(chǔ)的key存在, e保存已經(jīng)存在的值
// 要么待存儲(chǔ)的key不存在, 則已經(jīng)新建了Node將key值插入, e的值為Null
// 如果待存儲(chǔ)的key值已經(jīng)存在
if (e != null) { // existing mapping for key
V oldValue = e.value;
// 前面已經(jīng)解釋過, onlyIfAbsent的意思
// 這里是說舊值存在或者舊值為null的情況下, 用新值覆蓋舊值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); //這個(gè)函數(shù)只在LinkedHashMap中用到, 這里是空函數(shù)
// 返回舊值
return oldValue;
}
}
// 到這里說明table中不存在待存儲(chǔ)的key, 并且我們已經(jīng)將新的key插入進(jìn)數(shù)組了
++modCount; // 這個(gè)暫時(shí)用不到
// 因?yàn)橛植迦肓诵轮? 所以我們得把數(shù)組大小加1, 并判斷是否需要重新擴(kuò)容
if (++size > threshold)
resize();
afterNodeInsertion(evict); //這個(gè)函數(shù)只在LinkedHashMap中用到, 這里是空函數(shù)
return null;
}
總結(jié)
在put之前會(huì)檢查table是否為空，說明table真正的初始化并不是發(fā)生在構(gòu)造函數(shù)中， 而是發(fā)生在第一次put的時(shí)候。
查找當(dāng)前key是否存在的條件是p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))
如果插入的key值不存在，則值會(huì)插入到鏈表的末尾。
每次插入操作結(jié)束后，都會(huì)檢查當(dāng)前table節(jié)點(diǎn)數(shù)是否大于threshold, 若超過，則擴(kuò)容。
當(dāng)鏈表長(zhǎng)度超過TREEIFY_THRESHOLD（默認(rèn)是8）個(gè)時(shí)，會(huì)將鏈表轉(zhuǎn)換成紅黑樹以提升查找性能。
(完)
查看更多系列文章：系列文章目錄
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/76560.html
摘要：為了避免一篇文章的篇幅過長(zhǎng)，于是一些比較大的主題就都分成幾篇來講了，這篇文章是筆者所有文章的目錄，將會(huì)持續(xù)更新，以給大家一個(gè)查看系列文章的入口。 前言 大家好，筆者是今年才開始寫博客的，寫作的初衷主要是想記錄和分享自己的學(xué)習(xí)經(jīng)歷。因?yàn)閷懽鞯臅r(shí)候發(fā)現(xiàn)，為了弄懂一個(gè)知識(shí)，不得不先去了解另外一些知識(shí)，這樣以來，為了說明一個(gè)問題，就要把一系列知識(shí)都了解一遍，寫出來的文章就特別長(zhǎng)。 為了避免一篇...
摘要：為了避免一篇文章的篇幅過長(zhǎng)，于是一些比較大的主題就都分成幾篇來講了，這篇文章是筆者所有文章的目錄，將會(huì)持續(xù)更新，以給大家一個(gè)查看系列文章的入口。 前言 大家好，筆者是今年才開始寫博客的，寫作的初衷主要是想記錄和分享自己的學(xué)習(xí)經(jīng)歷。因?yàn)閷懽鞯臅r(shí)候發(fā)現(xiàn)，為了弄懂一個(gè)知識(shí)，不得不先去了解另外一些知識(shí)，這樣以來，為了說明一個(gè)問題，就要把一系列知識(shí)都了解一遍，寫出來的文章就特別長(zhǎng)。 為了避免一篇...
摘要：前言系列文章目錄上一篇我們說明了的構(gòu)造函數(shù)談到構(gòu)造函數(shù)中并不會(huì)初始化變量變量是在過程中初始化的本篇我們就來聊聊的擴(kuò)容本文的源碼基于版本用于以下兩種情況之一初始化在大小超過之后進(jìn)行擴(kuò)容下面我們直接來對(duì)照源碼分析原中已經(jīng)有值已經(jīng)超過最大限制不再 前言 系列文章目錄 上一篇我們說明了HashMap的構(gòu)造函數(shù), 談到構(gòu)造函數(shù)中并不會(huì)初始化table 變量, table 變量是在 resize過...
摘要：散列函數(shù)把消息或數(shù)據(jù)壓縮成摘要，使得數(shù)據(jù)量變小，將數(shù)據(jù)的格式固定下來。該函數(shù)將數(shù)據(jù)打亂混合，重新創(chuàng)建一個(gè)叫做散列值，，，或的指紋。 前言 系列文章目錄 前面我們討論了HashMap的結(jié)構(gòu), 接下來幾篇我們從源碼角度來看HashMap的實(shí)現(xiàn)細(xì)節(jié). 本篇我們就來聊聊HashMap的hash算法 本文的源碼基于 jdk8 版本. hash算法 上一篇文章我們提到, 為了利用數(shù)組索引進(jìn)行快速查...
摘要：前言系列文章目錄上一篇我們說明了的算法說到在構(gòu)造時(shí)會(huì)自動(dòng)將設(shè)為的整數(shù)次冪本篇我們就來聊聊的構(gòu)造函數(shù)本文的源碼基于版本構(gòu)造函數(shù)共有四個(gè)構(gòu)造函數(shù)默認(rèn)初始大小默認(rèn)負(fù)載因子沒有指定時(shí)使用默認(rèn)值即默認(rèn)初始大小默認(rèn)負(fù)載因子指定初始大小但使用默認(rèn)負(fù)載因子 前言 系列文章目錄 上一篇我們說明了HashMap的hash算法, 說到HashMap在構(gòu)造時(shí)會(huì)自動(dòng)將table設(shè)為2的整數(shù)次冪. 本篇我們就來聊...
閱讀 954·2021-10-13 09:48
閱讀 3974·2021-09-22 10:53
閱讀 3154·2021-08-30 09:41
閱讀 1979·2019-08-30 15:55
閱讀 2952·2019-08-30 15:55
閱讀 1874·2019-08-30 14:11
閱讀 2234·2019-08-29 13:44
閱讀 792·2019-08-26 12:23
