預(yù)備知識(shí)
位運(yùn)算知識(shí)
位運(yùn)算操作是由處理器支持的底層操作暇藏，底層硬件只支持01這樣的數(shù)字，因此位運(yùn)算運(yùn)行速度很快濒蒋。盡管現(xiàn)代計(jì)算機(jī)處理器擁有了更長(zhǎng)的指令流水線和更優(yōu)的架構(gòu)設(shè)計(jì)盐碱，使得加法和乘法運(yùn)算幾乎與位運(yùn)算一樣快，但是位運(yùn)算消耗更少的資源沪伙。常用的位運(yùn)算如下：
位與 &
(1&1=1 1&0=0 0&0=0)
位或 |
(1|1=1 1|0=1 0|0=0)
位非 ~
（ ~1=0 ~0=1）
位異或 ^
(1^1=0 1^0=1 0^0=0)
有符號(hào)右移 >>
在執(zhí)行右移操作時(shí)瓮顽，若參與運(yùn)算的數(shù)字為正數(shù)，則在高位補(bǔ)0围橡；若為負(fù)數(shù)暖混，則在高位補(bǔ)1。
無(wú)符號(hào)右移 >>>
無(wú)論參與運(yùn)算的數(shù)字為正數(shù)或?yàn)樨?fù)數(shù)翁授，在執(zhí)運(yùn)算時(shí)拣播，都會(huì)在高位補(bǔ)0善绎。
左移
對(duì)于左移是沒(méi)有正數(shù)跟負(fù)數(shù)這一說(shuō)的，因?yàn)樨?fù)數(shù)在CPU中是以補(bǔ)碼的形式存儲(chǔ)的诫尽，對(duì)于正數(shù)左移相當(dāng)于乘以2的N次冪禀酱。
敲重點(diǎn)：上面的重重都是簡(jiǎn)單的只是為了引出下面的結(jié)論：
a % (Math.pow(2,n)) 等價(jià)于 a&( Math.pow(2,n)-1)
比如a%16最終的結(jié)果一定是0～15之間的數(shù)字牧嫉，而a&1111正好把a(bǔ)除16后的余數(shù)有效的現(xiàn)實(shí)出來(lái)了因?yàn)槿绻? 1111這樣的話最前面一位其實(shí)代表的16剂跟，也就是說(shuō)二進(jìn)制從倒數(shù)第五位開(kāi)始只要出現(xiàn)了1那絕對(duì)代表的是16的倍數(shù)。 結(jié)論：位運(yùn)算比除法運(yùn)算在運(yùn)行效率上更高酣藻，對(duì)一個(gè)數(shù)取余盡量用a&二進(jìn)制數(shù)這樣可以更好的提速曹洽。
ArrayList
我們知道ArrayList是一個(gè)數(shù)組隊(duì)列，相當(dāng)于動(dòng)態(tài)數(shù)組辽剧。與Java中的基本數(shù)組相比送淆，它的容量能動(dòng)態(tài)增長(zhǎng)。它具有以下幾個(gè)重點(diǎn)怕轿。
ArrayList 實(shí)際上是通過(guò)一個(gè)數(shù)組去保存數(shù)據(jù)的偷崩。當(dāng)我們構(gòu)造ArrayList時(shí)；若使用默認(rèn)構(gòu)造函數(shù)撞羽，則ArrayList的默認(rèn)容量大小是10阐斜。
當(dāng)ArrayList容量不足以容納全部元素時(shí)，ArrayList會(huì)重新設(shè)置容量：原來(lái)容量的1.5倍诀紊。
ArrayList的克隆函數(shù)谒出，即是將全部元素克隆到一個(gè)數(shù)組中。
克隆的底層是System.arraycopy(0,oldsrc,0,newsrc,length);
ArrayList實(shí)現(xiàn)java.io.Serializable的方式邻奠。當(dāng)寫(xiě)入到輸出流時(shí)笤喳，先寫(xiě)入“容量”，再依次寫(xiě)入“每一個(gè)元素”碌宴；當(dāng)讀出輸入流時(shí)杀狡，先讀取“容量”，再依次讀取“每一個(gè)元素”唧喉。
優(yōu)點(diǎn)：
根據(jù)下標(biāo)遍歷元素效率較高捣卤。
根據(jù)下標(biāo)訪問(wèn)元素效率較高。
在數(shù)組的基礎(chǔ)上封裝了對(duì)元素操作的方法八孝。
這樣的動(dòng)態(tài)數(shù)組在內(nèi)地地址上是空間連續(xù)的董朝。
可以自動(dòng)擴(kuò)容。
缺點(diǎn)：
插入和刪除的效率比較低干跛。
根據(jù)內(nèi)容查找元素的效率較低子姜。
擴(kuò)容規(guī)則：每次擴(kuò)容現(xiàn)有容量的50%。
LinkedList
雙向鏈表每一個(gè)節(jié)點(diǎn)包含三部分(data,prev,next)楼入，它不要求空間是連續(xù)的哥捕。類(lèi)似于節(jié)點(diǎn)跟節(jié)點(diǎn)之間通過(guò)前后兩條線串聯(lián)起來(lái)的牧抽。
ArrayList和LinkedList總結(jié)：
ArrayList是實(shí)現(xiàn)了基于動(dòng)態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)，LinkedList是基于鏈表結(jié)構(gòu)遥赚。
對(duì)于隨機(jī)訪問(wèn)的get和set方法扬舒，ArrayList要優(yōu)于LinkedList，因?yàn)長(zhǎng)inkedList要移動(dòng)指針凫佛。
對(duì)于新增和刪除操作add和remove讲坎，LinkedList比較占優(yōu)勢(shì)，因?yàn)锳rrayList要移動(dòng)數(shù)據(jù)愧薛。
ArrayList使用在查詢(xún)比較多晨炕，但是插入和刪除比較少的情況，而LinkedList用在查詢(xún)比較少而插入刪除比較多的情況
RedBlackTree
首先你需要對(duì)二叉樹(shù)有個(gè)了解毫炉，知道這是什么樣子的一個(gè)數(shù)據(jù)組合方式瓮栗，然后知道二叉樹(shù)查找的時(shí)候缺點(diǎn)，可能發(fā)生數(shù)據(jù)傾斜瞄勾。因此引入了平衡二叉樹(shù)费奸，平衡二叉樹(shù)的左右節(jié)點(diǎn)深度之差不會(huì)超過(guò)1，查找方便構(gòu)建麻煩丰榴，因此又出現(xiàn)了紅黑樹(shù)货邓。紅黑樹(shù)是一種平衡的二叉查找樹(shù)秆撮，是一種計(jì)算機(jī)科學(xué)中常用的數(shù)據(jù)結(jié)構(gòu)四濒，最典型的應(yīng)用是實(shí)現(xiàn)數(shù)據(jù)的關(guān)聯(lián)，例如map等數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)职辨，紅黑樹(shù)重要特性是( 左節(jié)點(diǎn) < 根節(jié)點(diǎn) < 右節(jié)點(diǎn)) 紅黑樹(shù)有以下限制：
節(jié)點(diǎn)必須是紅色或者是黑色
根節(jié)點(diǎn)是黑色的
所有的葉子節(jié)點(diǎn)是黑色的盗蟆。
每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)是黑色的，也就是不能存在父子兩個(gè)節(jié)點(diǎn)全是紅色
從任意每個(gè)節(jié)點(diǎn)到其每個(gè)葉子節(jié)點(diǎn)的所有簡(jiǎn)單路徑上黑色節(jié)點(diǎn)的數(shù)量是相同的舒裤。
如果您對(duì)紅黑樹(shù)還不太了解推薦看下博主以前寫(xiě)的RBT
HashTable
Hash表是一種特殊的數(shù)據(jù)結(jié)構(gòu)喳资，它同數(shù)組、鏈表以及二叉排序樹(shù)等相比較有很明顯的區(qū)別腾供，它能夠快速定位到想要查找的記錄仆邓，而不是與表中存在的記錄的關(guān)鍵字進(jìn)行比較來(lái)進(jìn)行查找。這個(gè)源于Hash表設(shè)計(jì)的特殊性伴鳖，它采用了==函數(shù)映射==的思想將記錄的存儲(chǔ)位置與記錄的關(guān)鍵字關(guān)聯(lián)起來(lái)节值，從而能夠很快速地進(jìn)行查找。評(píng)價(jià)函數(shù)的性能關(guān)鍵在于==裝填因子==榜聂，以及如何合理的解決哈希沖突搞疗，具體的可看博主以前寫(xiě)的徹底搞定哈希表
HashMap源碼剖析
概述
通常具備前面一些知識(shí)點(diǎn)的鋪墊就可以很好的開(kāi)展HashMap的講解了，既然ArrayList须肆，LinkedList匿乃，Red Black Tree各有優(yōu)缺點(diǎn)桩皿，我們能不能集百家之長(zhǎng)實(shí)現(xiàn)一個(gè)綜合產(chǎn)物呢 === >HashMap，本文所以講解都是基于JDK8幢炸。
HashMap的組成部分：數(shù)組 + 鏈表 + 紅黑樹(shù)泄隔。HashMap的主干是一個(gè)Node數(shù)組。Node是HashMap的基本組成單元宛徊，每一個(gè)Node包含一個(gè)key-value鍵值對(duì)梅尤。HashMap的時(shí)間復(fù)雜度幾乎可以接近O(1)(如果出現(xiàn)了 哈希沖突可能會(huì)波動(dòng)下)，并且HashMap的空間利用率一般就是在40%左右岩调。HashMap的大致圖如下：
PS:其中幾個(gè)重要節(jié)點(diǎn)關(guān)系如下：
1.java.util.Map.Entry 這就是個(gè)interface定義了一些比較的接口函數(shù)巷燥。
2.java.util.HashMap.Node 就是我們HashMap中存儲(chǔ)的基本的KV。
3.java.util.LinkedHashMap.Enrty Enrty這個(gè)類(lèi)繼承自HashMap.Node這個(gè)類(lèi)号枕，Enrty是LIinkedHashMap的一個(gè)內(nèi)部類(lèi)缰揪，
4.java.util.HashMap.TreeNode TreeNode的構(gòu)造函數(shù)向上追溯繼承了LinkedHashMap.Entry，而后者又繼承了HashMap.Node葱淳。所以TreeNode既保有Node的屬性钝腺，同時(shí)由于添加了prev這個(gè)前驅(qū)指針使得==鏈表==變?yōu)榱?=雙向==。前三個(gè)節(jié)點(diǎn)跟第五個(gè)紅黑樹(shù)相關(guān)赞厕，第四個(gè)跟next跟雙向鏈表相關(guān)艳狐。
數(shù)據(jù)存儲(chǔ)的大致步驟有三步。
5.每個(gè)數(shù)據(jù)通過(guò)HashTable里的映射函數(shù)來(lái)決定將該數(shù)據(jù)放到數(shù)組的那個(gè)地方皿桑，數(shù)組初始化時(shí)候一定是2的次冪毫目，默認(rèn)16，初始化傳入的任何數(shù)字都會(huì)經(jīng)過(guò)tableSizeFor調(diào)整為2次冪诲侮。
6.如果同一個(gè)數(shù)組的地方被分配到太多數(shù)據(jù)就用鏈表法來(lái)解決哈希沖突镀虐。
7.如果同一個(gè)節(jié)點(diǎn)的鏈表數(shù)據(jù)節(jié)點(diǎn)個(gè)數(shù) > TREEIFY_THRESHOLD=8且數(shù)組長(zhǎng)度 >= MIN_TREEIFY_CAPACITY=64，則會(huì)將該鏈表進(jìn)化為RedBlackTree,如果RedBlackTree中節(jié)點(diǎn)個(gè)數(shù)小于UNTREEIFY_THRESHOLD=6會(huì)退化為鏈表沟绪。
特別提醒：讀HashMap源碼之前需要知道它大致特性如下：
1.HashMap的存取是沒(méi)有順序的
2.KV均允許為NULL
3.多線程情況下該類(lèi)安全刮便，可以考慮用HashTable。
4.JDk8底層是數(shù)組 + 鏈表 + 紅黑樹(shù)绽慈，JDK7底層是數(shù)組 + 鏈表恨旱。
5.初始容量和裝載因子是決定整個(gè)類(lèi)性能的關(guān)鍵點(diǎn),輕易不要?jiǎng)印?/p>
6.HashMap是懶漢式創(chuàng)建的，只有在你put數(shù)據(jù)時(shí)候才會(huì)build
7.單向鏈表轉(zhuǎn)換為紅黑樹(shù)的時(shí)候會(huì)先變化為雙向鏈表最終轉(zhuǎn)換為紅黑樹(shù)坝疼，雙向鏈表跟紅黑樹(shù)是共存的搜贤，切記。
8.對(duì)于傳入的兩個(gè)key裙士，會(huì)強(qiáng)制性的判別出個(gè)高低入客，判別高低主要是為了決定向左還是向右。
9.鏈表轉(zhuǎn)紅黑樹(shù)后會(huì)努力將紅黑樹(shù)的root節(jié)點(diǎn)和鏈表的頭節(jié)點(diǎn) 跟table[i]節(jié)點(diǎn)融合成一個(gè)。
10.在刪除的時(shí)候是先判斷刪除節(jié)點(diǎn)紅黑樹(shù)個(gè)數(shù)是否需要轉(zhuǎn)鏈表桌硫，不轉(zhuǎn)鏈表就跟RBT類(lèi)似夭咬，找個(gè)合適的節(jié)點(diǎn)來(lái)填充已刪除的節(jié)點(diǎn)。
11.紅黑樹(shù)的root節(jié)點(diǎn)不一定跟table[i]也就是鏈表的頭節(jié)點(diǎn)是同一個(gè)哦铆隘，三者同步是靠MoveRootToFront實(shí)現(xiàn)的哨苛。而HashIterator.remove()會(huì)在調(diào)用removeNode的時(shí)候movable=false慷荔。
在這里插入圖片描述
重要參數(shù)
靜態(tài)參數(shù)
- static final int DEFAULT_INITIAL_CAPACITY = 1 << 4
初始容量洲脂，默認(rèn)容量=16竹勉，箱子的個(gè)數(shù)不能太多或太少。如果太少肿嘲，很容易觸發(fā)擴(kuò)容融击，如果太多，遍歷哈希表會(huì)比較慢雳窟。
- static final int MAXIMUM_CAPACITY = 1 << 30
數(shù)組的最大容量尊浪，一般情況下只要內(nèi)存夠用，哈希表不會(huì)出現(xiàn)問(wèn)題
- static final float DEFAULT_LOAD_FACTOR = 0.75f
默認(rèn)的負(fù)載因子封救。因此初始情況下拇涤，當(dāng)存儲(chǔ)的所有節(jié)點(diǎn)數(shù) > (16 * 0.75 = 12 )時(shí)，就會(huì)觸發(fā)擴(kuò)容誉结。 默認(rèn)負(fù)載因子（0.75）在時(shí)間和空間成本上提供了很好的折衷鹅士。較高的值會(huì)降低空間開(kāi)銷(xiāo)，但提高查找成本（體現(xiàn)在大多數(shù)的HashMap類(lèi)的操作惩坑，包括get和put）掉盅。設(shè)置初始大小時(shí)，應(yīng)該考慮預(yù)計(jì)的entry數(shù)在map及其負(fù)載系數(shù)旭贬，并且盡量減少rehash操作的次數(shù)怔接。如果初始容量大于最大條目數(shù)除以負(fù)載因子，rehash操作將不會(huì)發(fā)生稀轨。
從上面的表中可以看到當(dāng)桶中元素到達(dá)8個(gè)的時(shí)候，概率已經(jīng)變得非常小岸军，也就是說(shuō)用0.75作為加載因子奋刽，每個(gè)碰撞位置的鏈表長(zhǎng)度超過(guò)８?jìng)€(gè)是幾乎不可能的。 4. static final int TREEIFY_THRESHOLD = 8
這個(gè)值表示當(dāng)某個(gè)箱子(數(shù)組的某個(gè)item)中艰赞，鏈表長(zhǎng)度 >= 8 時(shí)佣谐，有可能會(huì)轉(zhuǎn)化成樹(shù)。設(shè)置為8方妖，是系統(tǒng)根據(jù)泊松分布的數(shù)據(jù)分布圖來(lái)設(shè)定的狭魂。
- static final int UNTREEIFY_THRESHOLD = 6
在哈希表擴(kuò)容時(shí)，如果發(fā)現(xiàn)鏈表長(zhǎng)度 <= 6，則會(huì)由樹(shù)重新退化為鏈表雌澄。 設(shè)置為6猜測(cè)是因?yàn)闀r(shí)間和空間的權(quán)衡
當(dāng)鏈表長(zhǎng)度為6時(shí) 查詢(xún)的平均長(zhǎng)度為 n/2=3斋泄，紅黑樹(shù) log(6) = 2.6 為8時(shí) :鏈表 8/2=4， 紅黑樹(shù) log(8)=3
- static final int MIN_TREEIFY_CAPACITY = 64
鏈表轉(zhuǎn)變成樹(shù)之前镐牺，還會(huì)有一次判斷炫掐，只有數(shù)組長(zhǎng)度大于 64 才會(huì)發(fā)生轉(zhuǎn)換。這是為了避免在哈希表建立初期睬涧，多個(gè)鍵值對(duì)恰好被放入了同一個(gè)鏈表中而導(dǎo)致不必要的轉(zhuǎn)化募胃。
動(dòng)態(tài)參數(shù)
- transient Node<K,V>[] table
HashMap的鏈表數(shù)組。無(wú)論我們初始化時(shí)候是否傳參畦浓，它在自擴(kuò)容時(shí)總是2的次冪痹束。
- transient Set<Map.Entry<K,V>> entrySet
HashMap實(shí)例中的Entry的Set集合
- transient int size
HashMap表中存儲(chǔ)的實(shí)例KV個(gè)數(shù)。
- transient int modCount
凡是我們做的增刪改都會(huì)引發(fā)modCount值的變化讶请，跟版本控制功能類(lèi)似参袱，可以理解成version，在特定的操作下需要對(duì)version進(jìn)行檢查秽梅，適用于Fai-Fast機(jī)制抹蚀。
在java的集合類(lèi)中存在一種Fail-Fast的錯(cuò)誤檢測(cè)機(jī)制，當(dāng)多個(gè)線程對(duì)同一集合的內(nèi)容進(jìn)行操作時(shí)企垦，可能就會(huì)產(chǎn)生此類(lèi)異常环壤。 比如當(dāng)A通過(guò)iterator去遍歷某集合的過(guò)程中，其他線程修改了此集合钞诡，此時(shí)會(huì)拋出ConcurrentModificationException異常郑现。 此類(lèi)機(jī)制就是通過(guò)modCount實(shí)現(xiàn)的，在迭代器初始化時(shí)荧降，會(huì)賦值expectedModCount接箫，在迭代過(guò)程中判斷modCount和expectedModCount是否一致。
- int threshold
擴(kuò)容閾值 threshold = capacity * loadFactor
- final float loadFactor
可自定義的負(fù)載因子朵诫，不過(guò)一般都是用系統(tǒng)自帶的0.75辛友。
四種構(gòu)造方法
1.默認(rèn)構(gòu)造方法
2.傳入初始容量大小
3.傳入初始容量大小及負(fù)載因子
==tableSizeFor==:作用是返回大于輸入?yún)?shù)且最小的2的整數(shù)次冪的數(shù)。比如10剪返，則返回16废累。
詳解如下：
先來(lái)分析有關(guān)n位操作部分：先來(lái)假設(shè)n的二進(jìn)制為01xxx...xxx。接著 對(duì)n右移1位：001xx...xxx脱盲，再位或：011xx...xxx 對(duì)n右移2為：00011...xxx邑滨，再位或：01111...xxx 此時(shí)前面已經(jīng)有四個(gè)1了，再右移4位且位或可得8個(gè)1 同理钱反，有8個(gè)1掖看，右移8位肯定會(huì)讓后八位也為1匣距。
綜上可得，該算法讓最高位的1后面的位全變?yōu)?哎壳。最后再讓結(jié)果n+1毅待，即得到了2的整數(shù)次冪的值了。 現(xiàn)在回來(lái)看看第一條語(yǔ)句：
int n = cap - 1;
讓cap-1再賦值給n的目的是另找到的目標(biāo)值大于或等于原值耳峦。例如二進(jìn)制1000恩静，十進(jìn)制數(shù)值為8。如果不對(duì)它減1而直接操作蹲坷，將得到答案10000驶乾，即16。顯然不是結(jié)果循签。減1后二進(jìn)制為111级乐，再進(jìn)行操作則會(huì)得到原來(lái)的數(shù)值1000，這種二進(jìn)制方法的效率非常高县匠。
- 構(gòu)造函數(shù)傳入一個(gè)map 使用默認(rèn)的負(fù)載因子风科，然后根據(jù)當(dāng)前map的大小來(lái)反推需要的threshold，同時(shí)還可能會(huì)涉到resize乞旦，然后住個(gè)put到 容器中贼穆。
Hash值
無(wú)論我們put數(shù)據(jù)還是get數(shù)據(jù)都要先獲得該數(shù)據(jù)在這個(gè)哈希表中對(duì)應(yīng)的位置。比如put數(shù)據(jù)兰粉，它的流程分為2步故痊。
1.先獲得key對(duì)應(yīng)的hash值。 2. 將該數(shù)據(jù)的hash值A(chǔ)玖姑，跟將A右無(wú)符號(hào)移動(dòng)16位后再^得到最終值愕秫。這個(gè)操作叫擾動(dòng)，原因是怕低幾位出現(xiàn)想同的概率太大焰络，盡可能的將數(shù)據(jù)實(shí)現(xiàn)均勻分布戴甩。
同時(shí)JDK8跟JDK7的擾動(dòng)目的一樣，不過(guò)復(fù)雜程度不一樣闪彼。
1. get
相對(duì)來(lái)說(shuō)很簡(jiǎn)單,為方便理解先說(shuō)下代碼大致流程思路甜孤。
獲得key的hash然后根據(jù)hash和key按照插入時(shí)候的思路去查找get。
如果數(shù)組位置為NULL則直接返回 NULL备蚓。
如果數(shù)組位置不為NULL則先直接看數(shù)組位置是否符合课蔬。
如果數(shù)組位置有類(lèi)型說(shuō)紅黑樹(shù)類(lèi)型，則按照紅黑樹(shù)類(lèi)型查找返回郊尝。
如果數(shù)組有next，則按照遍歷鏈表的方式查找返回战惊。
1.1 getNode
宏觀查找函數(shù)細(xì)節(jié)：
1.3 getTreeNode
紅黑樹(shù)查找節(jié)點(diǎn)細(xì)節(jié)：
先獲得根節(jié)點(diǎn)流昏，左節(jié)點(diǎn)扎即，右節(jié)點(diǎn)。
根據(jù) 左節(jié)點(diǎn) < 根節(jié)點(diǎn) < 右節(jié)點(diǎn) 對(duì)對(duì)數(shù)據(jù)進(jìn)行逐步范圍的縮小查找况凉。
如果實(shí)現(xiàn)了Comparable方法則直接對(duì)比谚鄙。
否則如果根節(jié)點(diǎn)不符合則遞歸性的調(diào)用find查找函數(shù)。
1.4 ComparableClassFor:
查詢(xún)?cè)搆ey是否實(shí)現(xiàn)了Comparable接口刁绒。
1.5 compareComparables:
既然實(shí)現(xiàn)了Comparable接口就用該實(shí)現(xiàn)進(jìn)行對(duì)比判斷如何何去何從闷营。
2. put流程
跟隨源碼梳理下put操作的大致流程。
數(shù)據(jù)插入的時(shí)候大致流程如下：
- 對(duì)數(shù)據(jù)進(jìn)行Hash值計(jì)算知市。
- 將數(shù)據(jù)插入前先查看下當(dāng)前table的狀態(tài)傻盟，如果table是空需要調(diào)用resize來(lái)進(jìn)行初始化。
- 通過(guò)位運(yùn)算獲得key的目標(biāo)位置嫂丙。并判斷當(dāng)前位置情況娘赴。
- 如果當(dāng)前位置為空則直接進(jìn)行放置，如果跟當(dāng)前key一直則進(jìn)行覆蓋跟啤。
- 如果當(dāng)前有數(shù)據(jù)則看當(dāng)前數(shù)據(jù)類(lèi)型是否是紅黑樹(shù)诽表，是的話需要調(diào)用putTreeVal。
- 否則就認(rèn)為是個(gè)鏈表隅肥，然后循環(huán)的查找進(jìn)行尾部==插入==竿奏。同時(shí)還要考慮當(dāng)前鏈表轉(zhuǎn)紅黑樹(shù)。
在JDK8中尋找待插入點(diǎn) e是通過(guò)==尾插法==(類(lèi)似與排隊(duì)在最后面)腥放，而在JDK7中是==前插法==(類(lèi)似與加塞在最前面泛啸，之所以這樣做是HashMap發(fā)明者認(rèn)為后插入節(jié)被訪問(wèn)概率更大)，對(duì)應(yīng)代碼如下捉片。
- 對(duì)找到的舊節(jié)點(diǎn)e進(jìn)行判斷
oldValue對(duì)應(yīng)的舊值如果為NULL平痰，那么無(wú)論onlyIfAbsent是否決定替換。都將被替換伍纫。
oldValue對(duì)應(yīng)的舊值如果不為NULL宗雇，那么如果onlyIfAbsent是false就替換。
onlyIfAbsent:只有在缺席的情況下才替換莹规，不缺席不替換赔蒲。跟redis Setnx 同樣的功能。
- 數(shù)據(jù)最終添加完畢后要對(duì)對(duì)修改后的變量modCount加1良漱，同時(shí)看最新的總的節(jié)點(diǎn)數(shù)是否需要擴(kuò)容了舞虱，如果是就擴(kuò)容。
2 put
2.1 putTreeVal
- 先找到根節(jié)點(diǎn)母市，然后判斷是從左邊找還是右邊找key矾兜。
- 找到了則直接返回找到的節(jié)點(diǎn)。
- 沒(méi)找到則新建節(jié)點(diǎn)將該新建節(jié)點(diǎn)放到適當(dāng)?shù)奈恢没季茫瑫r(shí)考慮紅黑樹(shù)跟雙向鏈表的節(jié)點(diǎn)插入情況椅寺。
2.2 treeifyBin
主要功能是根據(jù)參數(shù)的閾值范圍絕對(duì)是否將鏈表轉(zhuǎn)化為紅黑樹(shù)浑槽，然后首先將單項(xiàng)鏈表轉(zhuǎn)化為雙向鏈表，再調(diào)用treeify以頭節(jié)點(diǎn)為根節(jié)點(diǎn)構(gòu)建紅黑樹(shù)返帕。
2.3 treeify
雙向鏈表跟紅黑樹(shù)創(chuàng)建桐玻，主要步驟分3步。
- 從該雙向鏈表中找第一個(gè)節(jié)點(diǎn)為root節(jié)點(diǎn)荆萤。
- 每一個(gè)雙向鏈表節(jié)點(diǎn)都在root節(jié)點(diǎn)為根都二叉樹(shù)中找位置然后將該數(shù)據(jù)插入到紅黑樹(shù)中镊靴，同時(shí)要注意balance。
- 最終要注意將根節(jié)點(diǎn)跟當(dāng)前table[i]對(duì)應(yīng)好链韭。
2.4 moveRootToFront
確保將root節(jié)點(diǎn)挪動(dòng)到table[first]上偏竟，如果紅黑樹(shù)構(gòu)建成功而沒(méi)成功執(zhí)行這個(gè)任務(wù)會(huì)導(dǎo)致tablle[first]對(duì)應(yīng)的節(jié)點(diǎn)不是紅黑樹(shù)的root節(jié)點(diǎn)。正常執(zhí)行的時(shí)候主要步驟分2步梧油。
- 找到跟節(jié)點(diǎn)然后將root節(jié)點(diǎn)放到跟節(jié)點(diǎn)苫耸，至此關(guān)于紅黑樹(shù)到操作搞定。
- 原來(lái)鏈表頭是first節(jié)點(diǎn)儡陨，現(xiàn)在將可能是中間節(jié)點(diǎn)的root節(jié)點(diǎn)挪到first節(jié)點(diǎn)前面褪子。 其中 checkInvariants函數(shù)的作用：校驗(yàn)TreeNode對(duì)象是否滿(mǎn)足紅黑樹(shù)和雙鏈表的特性。因?yàn)椴l(fā)情況下會(huì)發(fā)生很多異常骗村。
3 resize
獲得老table數(shù)據(jù)嫌褪，如果老table已經(jīng)足夠大則不再擴(kuò)容，只調(diào)節(jié)閾值胚股。
老table擴(kuò)容后的范圍也符合要求直接將容器大小跟閾值都擴(kuò)容 笼痛。
如果是帶參數(shù)構(gòu)造函數(shù)則需要將閾值復(fù)制給容器容量。
否則認(rèn)為該容器初始化時(shí)未傳參琅拌，需初始化缨伊。
如果老table有數(shù)據(jù)，新他變了大小設(shè)置好了但是閾值沒(méi)設(shè)置成功进宝。此時(shí)要設(shè)置新閾值刻坊。
創(chuàng)建新容器。
老table成功擴(kuò)容為新table党晋，涉及到數(shù)據(jù)的轉(zhuǎn)移谭胚。
數(shù)據(jù)不為空是單獨(dú)的節(jié)點(diǎn)則直接重新hash分配新位置。
數(shù)據(jù)不為空后面是一個(gè)鏈表未玻，則要把鏈表數(shù)據(jù)進(jìn)行區(qū)分看那些分到老地方那些分到新地方灾而。
如果該節(jié)點(diǎn)類(lèi)型是個(gè)紅黑樹(shù)則調(diào)用split.
鏈表形式的重新劃分解釋如下： 注意：不是(e.hash & (oldCap-1))而是(e.hash & oldCap), 后一個(gè)得到的是 元素的在數(shù)組中的位置是否需要移動(dòng),示例如下
示例1： e.hash= 10 0000 1010 oldCap=16 0001 0000 & =0 0000 0000 比較高位的第一位 0 結(jié)論：元素位置在擴(kuò)容后數(shù)組中的位置沒(méi)有發(fā)生改變 示例2： e.hash= 17 0001 0001 oldCap=16 0001 0000 & =1 0001 0000 比較高位的第一位 1 結(jié)論：元素位置在擴(kuò)容后數(shù)組中的位置發(fā)生了改變，新的下標(biāo)位置是原下標(biāo)位置+原數(shù)組長(zhǎng)度
3.1 split
擴(kuò)容后如何處理原來(lái)一個(gè)table[i]上的紅黑樹(shù)扳剿，代碼的整體思路跟處理鏈表的時(shí)候差不多旁趟，只要理解節(jié)點(diǎn)關(guān)系保存紅黑樹(shù)的時(shí)候也保存了雙向鏈表就OK了。
4. find
函數(shù)功能就是以指定的一個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)庇绽，根據(jù)指定的key跟value進(jìn)行查找轻庆。
通過(guò)hash值判斷 左邊找還是右邊找癣猾。
如果找到的很簡(jiǎn)單直接返回敛劝。
可能出現(xiàn)hash值相等可是key不一樣余爆，繼續(xù)查找分為三種情況。
左節(jié)點(diǎn)為空則找右節(jié)點(diǎn)
右節(jié)點(diǎn)為空則找左節(jié)點(diǎn)
左右節(jié)點(diǎn)都不會(huì)空夸盟，嘗試通Comparable對(duì)數(shù)據(jù)看向左還是向右蛾方。
無(wú)法通過(guò)comparable比較或者比較之后還是相等。
直接從右節(jié)點(diǎn)遞歸查找下上陕。
否則就從左邊查找桩砰。
4.1 tieBreakOrder
對(duì)兩個(gè)對(duì)象進(jìn)行比較，一定能比出個(gè)高低释簿。
a 跟 b 都是字符串則直接在if判斷里比拼完畢
a 跟 b 都是對(duì)象則直接查看對(duì)象在JVM中的hash地址亚隅，然后比較。
4. remove
函數(shù)入口而已：
4.1 removeNode
removeNode無(wú)非就是查看table[i]是否存在庶溶，然后是否在首節(jié)點(diǎn)上煮纵，是否在紅黑樹(shù)上，是否在鏈表上偏螺。這幾種情況行疏，找到了則直接刪除，同時(shí)注意平衡性套像。
4.2 removeTreeNode
該函數(shù)的 目的就是移除調(diào)用此方法的節(jié)點(diǎn)酿联，也就是該方法中的this節(jié)點(diǎn)。移除包括鏈表的處理和紅黑樹(shù)的處理夺巩≌耆茫可以看以前寫(xiě)過(guò)的RBT，刪除的時(shí)候思路大致是一樣的柳譬，這里大致分為3步驟喳张。
紅黑樹(shù)也是雙向鏈表，以鏈表的角度來(lái)刪除節(jié)點(diǎn)征绎，然后判斷是否需要退化為鏈表蹲姐。
根據(jù)當(dāng)前的p節(jié)點(diǎn)嘗試從pr找最小的或者從pl找最大的目標(biāo)節(jié)點(diǎn)s，將兩點(diǎn)兌換人柿。
找到要replacement來(lái)跟p進(jìn)行替換柴墩。
實(shí)施替換。
替換后為保持紅黑樹(shù)特性可能需要進(jìn)行balance凫岖。
4.3 untreeify
紅黑樹(shù)退化成鏈表
4.4 balanceDeletion
關(guān)于這個(gè)問(wèn)題可以直接看博主以前寫(xiě)的紅黑叔添加跟刪除RBT
JDK7死環(huán)問(wèn)題
JDK7對(duì)舊table數(shù)據(jù)重定位到新table的函數(shù)transfer如下江咳，其中重點(diǎn)關(guān)注部分以標(biāo)出。
1.頭插法正常情況下：
2.并發(fā)情況下 線程1只執(zhí)行了Entry<K,V> next = e.next就被掛起了哥放，而線程2正常執(zhí)行完畢歼指，結(jié)果圖如下：
線程1接著下面繼續(xù)執(zhí)行： 通過(guò)逐步分析跟繪圖可以知道 會(huì)有環(huán)產(chǎn)生爹土。
HashIterator 的 remove 方法
7vs8
7中找Hash用了4次，8中只用了1次踩身。
7 = 數(shù)組 + 鏈表胀茵，8 = 數(shù)組 + 鏈表 + 紅黑樹(shù)
7中是頭插法，多線程容易造成環(huán)挟阻，8中是尾插法琼娘。
7的擴(kuò)容是全部數(shù)據(jù)重新定位，8中是位置不變+ 移動(dòng)舊size大小來(lái)實(shí)現(xiàn)更好些附鸽。
7是先判斷是否要擴(kuò)容再插入脱拼，8中是先插入再看是否要擴(kuò)容。
HashMap不管78都是現(xiàn)場(chǎng)不安全的坷备，多線程情況下記得用ConcurrentHashmap熄浓。ConcurrentHashmap下篇文章說(shuō)。
常見(jiàn)問(wèn)題
隨機(jī)搜羅了一些常見(jiàn)HashMap問(wèn)題省撑，如果把上述代碼都看懂了應(yīng)付這些應(yīng)該沒(méi)問(wèn)題赌蔑。
HashMap原理，內(nèi)部數(shù)據(jù)結(jié)構(gòu)丁侄。
HashMap中的put,get,remove大致過(guò)程惯雳。
HashMap中 hash函數(shù)實(shí)現(xiàn)。
HashMap如何擴(kuò)容鸿摇。
HashMap幾個(gè)重要參數(shù)為什么這樣設(shè)定石景。
HashMap為什么線程不安全，如何替換拙吉。
HashMap在JDK7跟JDK8中的區(qū)別潮孽。
HashMap中鏈表跟紅黑樹(shù)切換思路。
