前言
List、Set、HashMap作為Java中常用的集合，需要深入認(rèn)識其原理和特性。
本篇博客介紹常見的關(guān)于Java中HashMap集合的面試問題，結(jié)合源碼分析題目背后的知識點。
關(guān)于List的博客文章如下：
- Java進(jìn)階（List）——面試時List常見問題解讀 & 結(jié)合源碼分析
關(guān)于的Set的博客文章如下：
- Java進(jìn)階（Set）——面試時Set常見問題解讀 & 結(jié)合源碼分析
其他關(guān)于HaseMap的文章如下：
- Java學(xué)數(shù)據(jù)結(jié)構(gòu)（3）——樹Tree & B樹 & 紅黑樹 & Java標(biāo)準(zhǔn)庫中的集合Set與映射Map & 使用多個映射Map的案例
- Java學(xué)數(shù)據(jù)結(jié)構(gòu)（4）——散列表Hash table & 散列函數(shù) & 哈希沖突
引出
1.jdk1.7 HashMap：數(shù)組+單向鏈表；
2.jdk1.8 HashMap：數(shù)組+鏈表（單向）+紅黑樹；
3.當(dāng)鏈表節(jié)點的數(shù)量達(dá)到8個時，通過treeify轉(zhuǎn)為紅黑樹；
4.首次添加元素，初始容量16，大于16時，雙倍擴(kuò)容；
5.HashMap設(shè)置長度，第一個2的冪次方的值；
6.紅黑樹元素的高位或者低位節(jié)點個數(shù)<6時，那么就調(diào)用untreeify方法來退回鏈表結(jié)構(gòu)；
7.jdk1.7采用的是頭插法，即新來元素在鏈表起始的位置，而jdk1.8采用尾插法，可以有效的避免在多線程操作中產(chǎn)生死循環(huán)；
8.ConcurrentHashMap高并發(fā)線程安全；
核心：鍵值對，KEY不可重復(fù)，VALUE可以重復(fù)
HashMap底層結(jié)構(gòu)是什么？
JDK 1.7和1.8 對比
jdk1.7 HashMap：數(shù)組+單向鏈表
jdk1.8 HashMap：數(shù)組+鏈表（單向）+紅黑樹
源碼Node類
源碼可以看到HashMap內(nèi)部定義了靜態(tài)Node類，Node類中成員有
Node<K,V> next;
同樣可以看到HashMap內(nèi)部定義了靜態(tài)TreeNode類，TreeNode類中成員有
TreeNode<K,V> left;
TreeNode<K,V> right;
可以看出存在紅黑樹
而TreeNode繼承了 LinkedHashMap.Entry，點進(jìn)查看，可以看到 Entry也繼承了 HashMap.Node。所以，TreeNode紅黑樹是從鏈表Node中轉(zhuǎn)換過來的
整體圖：
HashMap如何解決Hash碰撞問題？HashMap 何時從單鏈表，轉(zhuǎn)換為紅黑樹？
- 首先理解什么是hash碰撞問題，HashMap存放的元素的KEY需要經(jīng)過hash計算得到hash值，而這個hash值可以理解為就是此元素要存放的位置，即數(shù)組中的下標(biāo)；但是如果兩個不同元素經(jīng)過hash計算后，得到的hash值相同時，即兩個元素要存放的位置為同一個位置，產(chǎn)生沖突，這種現(xiàn)象就叫做hash碰撞。
- 要想了解HashMap是如何解決hash碰撞的，那我們就需要看看HashMap的put方法的源碼中的核心操作
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//添加第一個元素時，會進(jìn)入這個if結(jié)構(gòu)，table為null，則第一次初始化這個table數(shù)組的長度為16
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//判斷添加的元素的KEY經(jīng)過hash計算得到的下標(biāo)位置是否為null
if ((p = tab[i = (n - 1) & hash]) == null)
//如果是null，則直接添加元素
tab[i] = newNode(hash, key, value, null);
//不為null的情況
else {
Node<K,V> e; K k;
//如果key相同，則用新的元素添加到舊元素的位置，后續(xù)會將就元素返回
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//判斷是否為紅黑樹節(jié)點，如果是紅黑樹節(jié)點，則添加為紅黑樹
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//鏈表類型
else {
//通過for循環(huán)遍歷鏈表節(jié)點
for (int binCount = 0; ; ++binCount) {
//如果鏈表節(jié)點next節(jié)點為空
if ((e = p.next) == null) {
//則添加至鏈表的next節(jié)點屬性中
p.next = newNode(hash, key, value, null);
//如果鏈表節(jié)點 >= 7 說明鏈表存在8個已存的元素節(jié)點
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//轉(zhuǎn)為紅黑樹方法
treeifyBin(tab, hash);
break;
}
//如果KEY相同，匹配其他API 如 putIfAbsent()
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;
}
....
當(dāng)鏈表節(jié)點的數(shù)量達(dá)到8個時，通過treeify轉(zhuǎn)為紅黑樹
?
總結(jié)：HashMap是通過3層 if 結(jié)構(gòu)來判斷，數(shù)組下標(biāo)位置是否有元素和下標(biāo)位置的類型是鏈表還是紅黑樹，然后通過鏈表和紅黑樹來解決hash碰撞的問題，當(dāng)鏈表節(jié)點>=7時（當(dāng)鏈表節(jié)點的數(shù)量達(dá)到8個時），會通過treeify轉(zhuǎn)為紅黑樹。
HashMap的擴(kuò)容機(jī)制？HashMap的數(shù)組何時需要擴(kuò)容？
1.首次添加元素
HashMap在第一次添加元素時，會進(jìn)入第一個if結(jié)構(gòu)來初始化數(shù)組的長度
2.初始容量16
//添加第一個元素時，會進(jìn)入這個if結(jié)構(gòu)，table為null，則第一次初始化這個table數(shù)組的長度為16
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
3.大于16時，雙倍擴(kuò)容
此處resize方法就是擴(kuò)容方法，jdk8中，resize方法除了擴(kuò)容還增加了初始化的功能，進(jìn)入此方法我們可以看一下源碼
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) {
//如果當(dāng)前數(shù)組的長度>=最大值（2^30）時，將預(yù)值threshold設(shè)置為最大值
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//如果當(dāng)前數(shù)組的長度>=默認(rèn)的初始長度16，則雙倍擴(kuò)容
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
...
調(diào)用resize方法的地方
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
...
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
總結(jié)分析
- 從上面可以看出，HashMap在完成put元素存儲后，會判斷++size是否>了閾值，如果是就會去擴(kuò)容
- 下面這個方法是在，put元素為鏈表節(jié)點，并且要轉(zhuǎn)為紅黑樹時，會調(diào)用該方法，該方法會在一開始就判斷是否需要擴(kuò)容
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
- 判斷擴(kuò)容的核心就是threshold這個值
- 從resize方法中看到，HashMap在擴(kuò)容時，是之前的雙倍擴(kuò)容
HashMap設(shè)置長度為11，那么數(shù)組的容量為多少？
第一個2的冪次方的值
指定了長度初始化HashMap時，它會將數(shù)組的容量經(jīng)過一系列算法，設(shè)置為大于我們自定義值的第一個2的冪次方的值，
即 設(shè)置為11 ， 則為2^4=16
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 何時從紅黑樹轉(zhuǎn)換為 單鏈模式？
- HashMap在resize方法執(zhí)行時，會將元素從舊數(shù)組轉(zhuǎn)入新數(shù)組，此時如果轉(zhuǎn)移元素為紅黑樹結(jié)構(gòu)，那么就會調(diào)用split方法來分割紅黑樹方便轉(zhuǎn)移
- split方法內(nèi)部，在分割時，會生成高位樹與低位樹兩種，此時也會進(jìn)行判斷如果紅黑樹元素的高位或者低位節(jié)點個數(shù)<6時，那么就調(diào)用untreeify方法來退回鏈表結(jié)構(gòu)
split方法和untreeify方法
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
... //lowhead 低位樹
if (loHead != null) {
//在紅黑樹節(jié)點元素往新數(shù)組中添加時，會調(diào)用split方法來重組這個紅黑樹
//此時會判斷，紅黑樹的節(jié)點操作次數(shù)是否<6，即low樹（低位樹的節(jié)點數(shù)）< 6時，會通過untreeify方法來退化為鏈表
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
//此時會判斷，紅黑樹的節(jié)點操作次數(shù)是否<6，即high樹（高位樹的節(jié)點數(shù)）< 6時，會通過untreeify方法來退化為鏈表
//highhead 高位樹
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
HashMap 為什么在多線程并發(fā)使用過程中，容易造成死循環(huán)/死鎖？
圖示：
- 產(chǎn)生死循環(huán)的核心原因是因為，jdk1.7采用的是頭插法，即新來元素在鏈表起始的位置，而jdk1.8采用尾插法，可以有效的避免在多線程操作中產(chǎn)生以上死循環(huán)
- 但是HashMap不是線程安全的，所以在多線程的場景中，雖然不會出現(xiàn)死鎖/死循環(huán)，但是還是會出現(xiàn)節(jié)點丟失的情況，所以在并發(fā)的場景中推薦使用ConcurrentHashMap
如何得到一個線程安全的HashMap集合？
文章來源：http://www.zghlxwxcb.cn/news/detail-715422.html
ConcurrentHashMap concurrentHashMap = new ConcurrentHashMap<>();
總結(jié)
1.jdk1.7 HashMap：數(shù)組+單向鏈表；
2.jdk1.8 HashMap：數(shù)組+鏈表（單向）+紅黑樹；
3.當(dāng)鏈表節(jié)點的數(shù)量達(dá)到8個時，通過treeify轉(zhuǎn)為紅黑樹；
4.首次添加元素，初始容量16，大于16時，雙倍擴(kuò)容；
5.HashMap設(shè)置長度，第一個2的冪次方的值；
6.紅黑樹元素的高位或者低位節(jié)點個數(shù)<6時，那么就調(diào)用untreeify方法來退回鏈表結(jié)構(gòu)；
7.jdk1.7采用的是頭插法，即新來元素在鏈表起始的位置，而jdk1.8采用尾插法，可以有效的避免在多線程操作中產(chǎn)生死循環(huán)；
8.ConcurrentHashMap高并發(fā)線程安全；文章來源地址http://www.zghlxwxcb.cn/news/detail-715422.html
到了這里，關(guān)于Java進(jìn)階（HashMap）——面試時HashMap常見問題解讀 & 結(jié)合源碼分析的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
