來源轉(zhuǎn)行程序員
頂級程序員 | 公眾號 Topcoding

好久不見，最近我要復(fù)習(xí)了，隨時準(zhǔn)備面試，順便整理筆記，所以這又是一篇沒有感情的純物理輸出?。?！

哎！如果你也準(zhǔn)備面試就看看吧。

正文

這一看就是HashMap結(jié)構(gòu)不用說了吧

學(xué)會扒系統(tǒng)層源碼

HashMpa源碼分析

這里，我嘗試拋棄1.8之前都源碼分析，技術(shù)在進(jìn)步，從現(xiàn)在開始分析1.8之后的版本區(qū)別。

結(jié)構(gòu)：數(shù)組+鏈表位于java.util包中

public?class?HashMap<K,V>?extends?AbstractMap<K,V>
????implements?Map<K,V>,?Cloneable,?Serializable?

靜態(tài)內(nèi)部類實現(xiàn)了map的接口，允許使用null值，null鍵。

JDK 1.8采用的是Node鏈表

/**
?*?Basic?hash?bin?node,?used?for?most?entries.??(See?below?for
?*?TreeNode?subclass,?and?in?LinkedHashMap?for?its?Entry?subclass.)
?*/
static?class?Node<K,V>?implements?Map.Entry<K,V>?{
????final?int?hash;
????final?K?key;
????V?value;
????Node?next;

????Node(int?hash,?K?key,?V?value,?Node?next)?{
????????this.hash?=?hash;
????????this.key?=?key;
????????this.value?=?value;
????????this.next?=?next;
????}

????public?final?K?getKey()????????{?return?key;?}
????public?final?V?getValue()??????{?return?value;?}
????public?final?String?toString()?{?return?key?+?"="?+?value;?}

????public?final?int?hashCode()?{
????????return?Objects.hashCode(key)?^?Objects.hashCode(value);
????}

????public?final?V?setValue(V?newValue)?{
????????V?oldValue?=?value;
????????value?=?newValue;
????????return?oldValue;
????}

????public?final?boolean?equals(Object?o)?{
????????if?(o?==?this)
????????????return?true;
????????if?(o?instanceof?Map.Entry)?{
????????????Map.Entry?e?=?(Map.Entry)o;
????????????if?(Objects.equals(key,?e.getKey())?&&
????????????????Objects.equals(value,?e.getValue()))
????????????????return?true;
????????}
????????return?false;
????}
}

hashmap就是一個entry的數(shù)組，entry對象中包含了 key 和 value，其中 next 是為了解決 hash 沖突構(gòu)成的一個鏈表。

負(fù)載因子：0.75。

static?final?float?DEFAULT_LOAD_FACTOR?=?0.75f;

public?HashMap()?{
?????this.loadFactor?=?DEFAULT_LOAD_FACTOR;?//?all?other?fields?defaulted
}

HashMap中的數(shù)據(jù)量 / HashMap的總?cè)萘?initialCapacity),

當(dāng)loadFactor達(dá)到指定值或者0.75時候，HashMap的總?cè)萘孔詣訑U(kuò)展一倍，以此類推。

負(fù)載因子代表了hash表中元素的填滿程度。加載因子越大，填滿的元素越多，但是沖突的機(jī)會增大了，鏈表越來越長，查詢速度會降低。反之，如果加載因子過小，沖突的機(jī)會減小了，但是hash表過于稀疏。沖突越大，查找的成本就越高。

數(shù)組大小初始值

????/**
?????*?The?default?initial?capacity?-?MUST?be?a?power?of?two.
?????*/
static?final?int?DEFAULT_INITIAL_CAPACITY?=?1?<4;?//?aka?16

數(shù)組Node的初始化值是16，使用位與運(yùn)算速度更快。

HashMap最大容量

static?final?int?MAXIMUM_CAPACITY?=?1?<30;

必須是2的冪且小于2的30次方，傳入容量過大將被這個值替換）

當(dāng)看到 1<<30 時，對“<<” 有點模糊，當(dāng)了解“<<”的用法之后，又有一個問題；
int類型不是4個字節(jié)共32位嗎，為什么不是 1<<31呢？
首先介紹下等號右邊數(shù)字及字符的含義:
1、"<<"為左移運(yùn)算符，1表示十進(jìn)制中的“1”，30表示十進(jìn)制數(shù)字1轉(zhuǎn)化為二進(jìn)制后向左移動30位。在數(shù)值上等同于2的30次冪。
2、為什么是2的30次冪?
以一個字節(jié)為例：
1<<2 = 4
0000 0001(十進(jìn)制1)
向左移動兩位之后變成
0000 0100（十進(jìn)制4）
可見 1<<30 等同于十進(jìn)制中2的30次冪。
回到題目，為什么會是2的30次冪，而不是2的31次冪呢？
首先：JAVA規(guī)定了該static final 類型的靜態(tài)變量為int類型，至于為什么不是byte、long等類型，原因是由于考慮到HashMap的性能問題而作的折中處理！
由于int類型限制了該變量的長度為4個字節(jié)共32個二進(jìn)制位，按理說可以向左移動31位即2的31次冪。但是事實上由于二進(jìn)制數(shù)字中最高的一位也就是最左邊的一位是符號位，用來表示正負(fù)之分（0為正，1為負(fù)），所以只能向左移動30位，而不能移動到處在最高位的符號位！
此處參考原文鏈接：https://blog.csdn.net/qq_33666602/article/details/80139620

HashMap中的紅黑樹

由鏈表轉(zhuǎn)換成樹的閾值TREEIFY_THRESHOLD：8

解釋：一個桶中bin（箱子）的存儲方式由鏈表轉(zhuǎn)換成樹的閾值。即當(dāng)桶中bin的數(shù)量超過TREEIFY_THRESHOLD時使用樹來代替鏈表。默認(rèn)值是8。

static?final?int?TREEIFY_THRESHOLD?=?8;

由樹轉(zhuǎn)換成鏈表的閾值UNTREEIFY_THRESHOLD：6。當(dāng)執(zhí)行resize操作時，當(dāng)桶中bin的數(shù)量少于UNTREEIFY_THRESHOLD時使用鏈表來代替樹。默認(rèn)值是6

static?final?int?UNTREEIFY_THRESHOLD?=?6;

構(gòu)造方法

????/**
?????*?Constructs?an?empty?HashMap?with?the?specified?initial
?????*?capacity?and?load?factor.
?????*
?????*?@param??initialCapacity?the?initial?capacity
?????*?@param??loadFactor??????the?load?factor
?????*?@throws?IllegalArgumentException?if?the?initial?capacity?is?negative
?????*?????????or?the?load?factor?is?nonpositive
?????*/
????public?HashMap(int?initialCapacity,?float?loadFactor)?{
????????if?(initialCapacity?0)
????????????throw?new?IllegalArgumentException("Illegal?initial?capacity:?"?+
???????????????????????????????????????????????initialCapacity);
????????if?(initialCapacity?>?MAXIMUM_CAPACITY)
????????????initialCapacity?=?MAXIMUM_CAPACITY;
????????if?(loadFactor?<=?0?||?Float.isNaN(loadFactor))
????????????throw?new?IllegalArgumentException("Illegal?load?factor:?"?+
???????????????????????????????????????????????loadFactor);
????????this.loadFactor?=?loadFactor;
??????
??????
???????//這里的threshold按照定義應(yīng)該再乘一個加載因子。沒有乘的原因是沒有對table進(jìn)行初始化，在put里面會對其進(jìn)行初始化的。這里有一個問題，我在初始化加載因子的時候，貌似只能初始化大于1的數(shù)字，這個地方留著，有待商榷。
????????this.threshold?=?tableSizeFor(initialCapacity);

第一個參數(shù)有兩個的。這里首先保證了參數(shù)和合法性。當(dāng)參數(shù)合法的時候，將輸入的容量轉(zhuǎn)換為距離該樹最近的2的整數(shù)次冪。調(diào)用的tableSizeFor函數(shù)，分析如下：可以看到能夠得到距離該數(shù)最近的整數(shù)次冪了。

????/**
?????*?Returns?a?power?of?two?size?for?the?given?target?capacity.
?????*/
????static?final?int?tableSizeFor(int?cap)?{
????????int?n?=?cap?-?1;
????????n?|=?n?>>>?1;
????????n?|=?n?>>>?2;
????????n?|=?n?>>>?4;
????????n?|=?n?>>>?8;
????????n?|=?n?>>>?16;
????????return?(n?0)???1?:?(n?>=?MAXIMUM_CAPACITY)???MAXIMUM_CAPACITY?:?n?+?1;
????}

HashMap重寫equals方法做了什么

public?final?boolean?equals(Object?o)?{
????if?(o?==?this)
????????return?true;
????if?(o?instanceof?Map.Entry)?{
????????Map.Entry?e?=?(Map.Entry)o;
????????if?(Objects.equals(key,?e.getKey())?&&
????????????Objects.equals(value,?e.getValue()))
????????????return?true;
????}
????return?false;
}

相比Object方法equals多了一個if判斷，要判斷Entry數(shù)據(jù)里的key和value同時相等，因為hashcode可能key有碰撞，意思就是key相同，value不同，這個時候value在一個鏈表上，需要重寫equals方法，確保value相同。

思考：為什么要同時重寫 equals & hashcode？

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[]?tab;?Node?p;?int?n,?i;
??????
??????
???????//判斷了該hash表是否為空，如果為空，需要resize
????????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?e;?K?k;
???????????//else中即為hash出現(xiàn)了沖突(但是他們的key不一定沖突的，這里要注意)。
???????????//這個if的就是key相同而且hash還相同的，對于這種的，就需要直接修改這個節(jié)點的值，所以講p賦值于e，對e進(jìn)行稍后的處理。
????????????if?(p.hash?==?hash?&&
????????????????((k?=?p.key)?==?key?||?(key?!=?null?&&?key.equals(k))))
????????????????e?=?p;
????????????else?if?(p?instanceof?TreeNode)?//jdk1.8中引入了紅黑樹，如果鏈表的長度超過了8，就會把鏈表轉(zhuǎn)化為紅黑樹。這里就判斷p是否為紅黑樹的節(jié)點。
????????????????e?=?((TreeNode)p).putTreeVal(this,?tab,?hash,?key,?value);
????????????else?{??//這里的else說明，要么hashcode的值相同，但是key不同，那么就要開始遍歷當(dāng)前的鏈表，一直遍歷到鏈表末尾。如果出現(xiàn)了以下的情況：
????????????????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 ??//這里的TREEIFY_THRESHOLD為8，是當(dāng)鏈表長度超過8，就會將鏈表便轉(zhuǎn)化為紅黑樹。如果在長度以內(nèi)，便在鏈表末尾new一個節(jié)點，把數(shù)據(jù)存儲。
????????????????????????????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;
????}

調(diào)用的put方法中，可以看到會計算出這個key值的hashcode，然后將該hashcode，key，value作為參數(shù)調(diào)用putVal方法。

首先根據(jù)hash(key)&(n-1)取得hash值二進(jìn)制低m位找到index，這樣的散列算法使key比較均勻的分布在各個桶里，找到 index索引到Node節(jié)點，如果為空，直接put在此節(jié)點，否則判斷是否是紅黑樹，如果是則找到紅黑樹部分的節(jié)點直接put，否則查找鏈表中下一個Node節(jié)點的key值和hash等于插入的key和hash值的話直接更新Node節(jié)點的value值，否則找到Node節(jié)點為NULL的節(jié)點，
判斷鏈表個數(shù)是否超過閾值7，超過鏈表轉(zhuǎn)換為紅黑樹，不超過在鏈表new 新出的節(jié)點，然后判斷HashMap的節(jié)點數(shù)是否大于閾值（負(fù)載因子*table的長度），大于的話resize擴(kuò)容，否則不擴(kuò)容。

get方法源碼分析

public?V?get(Object?key)?{
????Node?e;
????return?(e?=?getNode(hash(key),?key))?==?null???null?:?e.value;
}

/**
?*?Implements?Map.get?and?related?methods
?*
?*?@param?hash?hash?for?key
?*?@param?key?the?key
?*?@return?the?node,?or?null?if?none
?*/
final?Node?getNode(int?hash,?Object?key)?{
????Node[]?tab;?
???Node?first,?e;?
???int?n;?
???K?k;
????if?((tab?=?table)?!=?null?&&?(n?=?tab.length)?>?0?&&
????????(first?=?tab[(n?-?1)?&?hash])?!=?null)?{
????????if?(first.hash?==?hash?&&?//?always?check?first?node
????????????((k?=?first.key)?==?key?||?(key?!=?null?&&?key.equals(k))))
????????????return?first;
????????if?((e?=?first.next)?!=?null)?{
????????????if?(first?instanceof?TreeNode)
????????????????return?((TreeNode)first).getTreeNode(hash,?key);
????????????do?{
??????????????//?遍歷紅黑樹，調(diào)用equals方法判斷key對應(yīng)的value
????????????????if?(e.hash?==?hash?&&
????????????????????((k?=?e.key)?==?key?||?(key?!=?null?&&?key.equals(k))))
????????????????????return?e;
????????????}?while?((e?=?e.next)?!=?null);
????????}
????}
????return?null;
}

vx搜：【轉(zhuǎn)行程序員】拉你進(jìn)群

擴(kuò)容函數(shù)resize源碼分析

final?Node[]?resize()?{
????????Node[]?oldTab?=?table;?//定義了一個臨時Node類型的數(shù)組
????????int?oldCap?=?(oldTab?==?null)???0?:?oldTab.length;?//判斷目前的table數(shù)組是否為空，記錄下當(dāng)前數(shù)組的大小
????????int?oldThr?=?threshold;?//記錄下原始的hashmap的大小的閾值
????????int?newCap,?newThr?=?0;?//新Cap的大小和閾值
????????if?(oldCap?>?0)?{//原table不為空
????????????if?(oldCap?>=?MAXIMUM_CAPACITY)?{//原數(shù)組的大小超過2^30
????????????????threshold?=?Integer.MAX_VALUE;
????????????????return?oldTab;
????????????}
????????????else?if?((newCap?=?oldCap?<1)??????????????????????oldCap?>=?DEFAULT_INITIAL_CAPACITY)
????????????????newThr?=?oldThr?<1;?//?double?threshold，擴(kuò)大原閾值兩倍，現(xiàn)容量擴(kuò)大為原兩倍
????????}
????????else?if?(oldThr?>?0)?
????????????newCap?=?oldThr;?//?用構(gòu)造器初始化了閾值，將閾值直接賦值給容量
????????else?{?//?原始的閾值和容量值都為0，使用默認(rèn)的閾值和容量值進(jìn)行初始化，這個在我們new HashMap就是這么處理的。
????????????newCap?=?DEFAULT_INITIAL_CAPACITY;
????????????newThr?=?(int)(DEFAULT_LOAD_FACTOR?*?DEFAULT_INITIAL_CAPACITY);
????????}
????????if?(newThr?==?0)?{//這里為0，說明進(jìn)入了else?if或者if，即為原table不為空，或者初始化的時候用構(gòu)造器人為設(shè)定的閾值
????????????float?ft?=?(float)newCap?*?loadFactor;
????????????newThr?=?(newCap?float)MAXIMUM_CAPACITY??
??????????????????????(int)ft?:?Integer.MAX_VALUE);
????????}
????????threshold?=?newThr;
????????@SuppressWarnings({"rawtypes","unchecked"})
????????Node[]?newTab?=?(Node[])new?Node[newCap];//初始化新的Node類型數(shù)組
????????table?=?newTab;
????????//當(dāng)原來的table不為空，需要將數(shù)據(jù)遷移到新的數(shù)組里面去
????????if?(oldTab?!=?null)?{
????????????for?(int?j?=?0;?j?//開始對原table進(jìn)行遍歷
????????????????Node?e;
????????????????if?((e?=?oldTab[j])?!=?null)?{//取出這個數(shù)組第一個不為空的元素
????????????????????oldTab[j]?=?null;//把空間釋放掉
????????????????????if?(e.next?==?null)//說明這個entry對應(yīng)的鏈表中只有一個節(jié)點，
????????????????????????newTab[e.hash?&?(newCap?-?1)]?=?e;計算相應(yīng)的hash值，把節(jié)點存儲到新table的對應(yīng)位置處
????????????????????else?if?(e?instanceof?TreeNode)//若e是紅黑樹的節(jié)點，要按照紅黑樹的節(jié)點移動
????????????????????????((TreeNode)e).split(this,?newTab,?j,?oldCap);
????????????????????else?{?//?preserve?order，說明此鏈表中不止一個節(jié)點，需要全部移到新的table中
????????????????????????Node?loHead?=?null,?loTail?=?null;
????????????????????????Node?hiHead?=?null,?hiTail?=?null;
????????????????????????Node?next;
????????????????????????//這里的循環(huán)是將鏈表按照(e.hash & oldCap)?==?0，把節(jié)點分成兩部分，進(jìn)行了一次rehash lo串的位置與原來相同，hi串的位置為原來位置+oldCap。
????????????????????????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;
????}

對于rehash這一段，還是有必要講解一下的。剛開始我是一點都不懂這是干什么玩意呢，后來理解了一下。

因為我們的閾值和容量都會變?yōu)樵瓉淼?倍。想想一下，如果hash值和原大小相與為0，說明啥？說明了即使閾值和容量變?yōu)樵瓉淼?倍，索引還是不會變。比較難懂，舉個例子：

cap：0000 1111
key1：0000 0000
key2；0000 0101

key1&cap = 0；key2&cap != 0

當(dāng)我cap變?yōu)樵瓉淼?倍時，

cap：0001 1111

key1&cap：0000 0000

key2&cap：0001 0101

發(fā)現(xiàn)擴(kuò)容后的key1的索引不變，key2的變了。那么有人會問，為毛key1&cap這個就是索引？其實這里的key是索引，即key.hashcode，那么我這個hashcode&cap=hashcode，這個是沒錯的。所以才有了以上的種種推斷。這個是設(shè)計思路，而上面是代碼實現(xiàn)。這個設(shè)計很巧妙，不用重新計算hashcode，省去了不少時間。