面試造飛機(jī)系列：用心整理的HashMap面試題，以后都不用擔(dān)心了
來(lái)自：非科班的科班
本文思維導(dǎo)圖
HashMap簡(jiǎn)介
HashMap 是很常用的一種集合框架，其底層實(shí)現(xiàn)方式在 JDK 1.7和 JDK 1.8中卻有很大區(qū)別。
HashMap 是用來(lái)存儲(chǔ)數(shù)據(jù)的，它底層在JDK 1.7是數(shù)組+鏈表實(shí)現(xiàn)的，而JDK 1.8是使用數(shù)組+鏈表+紅黑樹(shù)實(shí)現(xiàn)，通過(guò)對(duì) key 進(jìn)行哈希計(jì)算等操作后得到數(shù)組下標(biāo)，把 value 等信息存放在鏈表或紅黑樹(shù)存在此位置。
如果兩個(gè)不同的 key 運(yùn)算后獲取的數(shù)組下標(biāo)一致，就出現(xiàn)了哈希沖突。數(shù)組默認(rèn)長(zhǎng)度是16，如果實(shí)際數(shù)組長(zhǎng)度超過(guò)一定的值，就會(huì)進(jìn)行擴(kuò)容。
HashMap的面試不管小廠還是大廠都是高頻問(wèn)點(diǎn)，特別是大廠一定會(huì)深究底層，采用持續(xù)的追問(wèn)，知道你懷疑人生，在Java7和Java8中對(duì)HashMap的數(shù)據(jù)結(jié)構(gòu)進(jìn)行了很大的優(yōu)化。
今天這篇文章就以HashMap的高頻問(wèn)點(diǎn)為主，層層的剖析HasMap的底層實(shí)現(xiàn)，話不多說(shuō)，直接進(jìn)入正題。
問(wèn)點(diǎn)一：你了解HashMap的底層數(shù)據(jù)結(jié)構(gòu)嗎？
對(duì)于HashMap的底層數(shù)據(jù)結(jié)構(gòu)在Java7和Java8中的實(shí)現(xiàn)是不同的，在Java7中是采用數(shù)組+鏈表的數(shù)據(jù)結(jié)構(gòu)進(jìn)行實(shí)現(xiàn)，而在Java8中是采用數(shù)組+鏈表+紅黑樹(shù)的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的。
說(shuō)時(shí)遲那時(shí)快，剛話說(shuō)完，從兜里拿出筆和紙，啪地一聲放在桌子上畫(huà)了起來(lái)，許久之后，出現(xiàn)了兩幅jdk7和jdk8的HashMap的內(nèi)部結(jié)構(gòu)圖：
上圖是
jdk7內(nèi)部結(jié)構(gòu)圖，以
Entry<K,V>[]數(shù)組作為
哈希桶，每個(gè)哈希桶的后面又可以連著一條
單向鏈表，在鏈表中以
k，v的形式存儲(chǔ)數(shù)據(jù)，并且每一個(gè)節(jié)點(diǎn)有指向下一節(jié)點(diǎn)的
指針。
上圖是
jdk8的
HashMap的內(nèi)部結(jié)構(gòu)圖，此時(shí)在源碼源碼中就不再使用
Entry<K,V>[]作為數(shù)組，而是使用
Node<K,V>[]數(shù)組作為
哈希桶，每個(gè)哈希桶的后面也可能連著一條
單向鏈表或者
紅黑樹(shù)。
當(dāng)單向鏈表的值>8的時(shí)候，鏈表就會(huì)轉(zhuǎn)換為紅黑樹(shù)進(jìn)行存儲(chǔ)數(shù)據(jù)，具體詳細(xì)的紅黑樹(shù)介紹之前已經(jīng)寫(xiě)過(guò)一篇，這里就不再贅述，未詳細(xì)了解的請(qǐng)移至這一篇[B樹(shù)、B-樹(shù)、B+樹(shù)、B*樹(shù)圖文詳解]。
在面試大廠的時(shí)候，其實(shí)答到這里，還是不完整的，為什么呢？因?yàn)槟阆肽阏f(shuō)的上面的實(shí)際由jdk7和jdk8轉(zhuǎn)變的一個(gè)結(jié)果，但是重要的為什么要這樣做？你還沒(méi)有回答。
如果你聰明點(diǎn)的話，就不會(huì)等著面試官拋出接下來(lái)的問(wèn)題？而是自己去回答這個(gè)為什么？不是等著面試官繼續(xù)拋出這個(gè)為什么？一個(gè)會(huì)聊天的人他會(huì)去猜測(cè)對(duì)方想知道什么？
問(wèn)點(diǎn)二：為什么JDK 7使用數(shù)組+鏈表？JDK8中為什么要使用紅黑樹(shù)？哈希沖突是怎么回事？HashMap又是怎么解決的？
在深入這些問(wèn)題之前，首先要了解一些概念，比如什么是hash函數(shù)，對(duì)于hash函數(shù)，之前已經(jīng)詳細(xì)的寫(xiě)過(guò)一篇，這里就不再贅述，詳細(xì)參考這一篇[大白話之哈希表和哈希算法]。
哈希沖突是怎么回事呢？當(dāng)<k,v>的數(shù)據(jù)將要存進(jìn)HashMap中的時(shí)候，會(huì)先，把k值經(jīng)過(guò)hash函數(shù)進(jìn)行計(jì)算得到hash值，再通過(guò)hash值進(jìn)行計(jì)算得到數(shù)據(jù)在數(shù)組的下標(biāo)，在jdk7中的源碼如下：
//key 進(jìn)行哈希計(jì)算
int hash = hash(key);
//獲取數(shù)組下標(biāo)
int i = indexFor(hash, table.length);
通過(guò)計(jì)算后的下標(biāo)，從而得到數(shù)組的對(duì)應(yīng)下標(biāo)的位置，最后把k，v值存進(jìn)去，同樣的當(dāng)再次第二次存值的時(shí)候，同樣把k，v傳進(jìn)來(lái)，當(dāng)k再次進(jìn)行計(jì)算出數(shù)組下標(biāo)index，有可能和第一次計(jì)算的index的值相同。
為什么有可能相同呢？這個(gè)是hash函數(shù)的原因，看完上面推薦的那篇hash函數(shù)詳細(xì)介紹你就懂了。當(dāng)兩次的計(jì)算index相同，這就是hash沖突。
但是，兩次的需要存進(jìn)去的value值是不同的，這就出現(xiàn)了同一個(gè)數(shù)組后面有一條鏈表，會(huì)比較鏈表上的每一個(gè)value值與當(dāng)前的value是否相同，若是不相同，通過(guò)頭插法，將數(shù)值插入鏈表中。如下圖所示：
接下來(lái)通通過(guò)源碼進(jìn)行分析，在jdk 7插入的put 方法源碼如下：
public V put(K key, V value) {
//數(shù)組為空就進(jìn)行初始化
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
//key 進(jìn)行哈希計(jì)算
int hash = hash(key);
//獲取數(shù)組下標(biāo)
int i = indexFor(hash, table.length);
//如果此下標(biāo)有值，遍歷鏈表上的元素，key 一致的話就替換 value 的值
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//新增一個(gè)key
addEntry(hash, key, value, i);
return null;
}
put方法中主要做了以下幾件事：
判斷
table數(shù)組是否為空，若為空進(jìn)行初始化table數(shù)組。判斷key值是否為
null，將null是作為key存進(jìn)去。若
key不為空，通過(guò)key計(jì)算出數(shù)組下標(biāo)，判斷table[i]是否為空。若是不為空通過(guò)鏈表循環(huán)，判斷在鏈表中是否存在與該
key相等，若是存在，直接將value替換成新的value。若是table[i]為空或者鏈表中不存在與之相同的key，就addEntry(hash, key, value, i)新增一個(gè)節(jié)點(diǎn)。
接下來(lái)看看addEntry(hash, key, value, i)新增節(jié)點(diǎn)的源碼如下：
void addEntry(int hash, K key, V value, int bucketIndex) {
//數(shù)組長(zhǎng)度大于閾值且存在哈希沖突（即當(dāng)前數(shù)組下標(biāo)有元素），就將數(shù)組擴(kuò)容至2倍
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
這個(gè)方法很簡(jiǎn)單，直接就是判斷當(dāng)前數(shù)組的大小是否>=threshold并且table[bucketIndex]是否為null。若成立擴(kuò)容，然后rehash，重新得到新數(shù)組的下標(biāo)值，最后 createEntry(hash, key, value, bucketIndex)創(chuàng)建新節(jié)點(diǎn)。
最后來(lái)看一下createEntry(hash, key, value, bucketIndex)創(chuàng)建新節(jié)點(diǎn)的源碼如下：
void createEntry(int hash, K key, V value, int bucketIndex) {
//此位置有元素，就在鏈表頭部插入新元素（頭插法）
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
該方法就是通過(guò)頭插法加入新節(jié)點(diǎn)，方法非常簡(jiǎn)單，相信都能看懂。經(jīng)過(guò)上面對(duì)put方法的源碼分析，在jdk 7 中put操作的原理圖如下所示：
在
JDK 7中，鏈表存儲(chǔ)有一個(gè)缺點(diǎn)，就是當(dāng)數(shù)據(jù)很多的時(shí)候，鏈表就會(huì)很長(zhǎng)，每次查詢都會(huì)遍歷很長(zhǎng)的鏈表。
因此在JDK 8中為了優(yōu)化HashMap的查詢效率，將內(nèi)部的結(jié)構(gòu)改為數(shù)組+鏈表+和紅黑樹(shù)，當(dāng)一個(gè)哈希桶后面的鏈表長(zhǎng)度>8的時(shí)候，就會(huì)將鏈表轉(zhuǎn)化為紅黑樹(shù)，紅黑樹(shù)是二分查找，提高了查詢的效率。接下來(lái)通過(guò)JDK 8的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) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//數(shù)組為空就初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//當(dāng)前下標(biāo)為空，就直接插入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//key 相同就覆蓋原來(lái)的值
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//樹(shù)節(jié)點(diǎn)插入數(shù)據(jù)
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
//鏈表，尾插法插入數(shù)據(jù)
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//鏈表長(zhǎng)度超過(guò)8，就把鏈表轉(zhuǎn)為紅黑樹(shù)
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//key相同就覆蓋原來(lái)的值
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;
//數(shù)組長(zhǎng)度大于閾值，就擴(kuò)容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
通過(guò)分析源碼，上面的方法主要做了以下幾件事：
判斷當(dāng)前桶是否為空，空的就需要初始化（
resize中會(huì)判斷是否進(jìn)行初始化）。根據(jù)當(dāng)前
key的hashcode定位到具體的桶中并判斷是否為空，為空表明沒(méi)有Hash沖突就直接在當(dāng)前位置創(chuàng)建一個(gè)新桶即可。如果當(dāng)前桶有值（ Hash 沖突），那么就要比較當(dāng)前桶中的
key、key的hashcode與寫(xiě)入的key是否相等，相等就賦值給 e。如果當(dāng)前桶為紅黑樹(shù)，那就要按照紅黑樹(shù)的方式寫(xiě)入數(shù)據(jù)。
如果是個(gè)鏈表，就需要將當(dāng)前的
key、value封裝成一個(gè)新節(jié)點(diǎn)寫(xiě)入到當(dāng)前桶的后面（形成鏈表）。接著判斷當(dāng)前鏈表的大小是否大于預(yù)設(shè)的閾值，大于時(shí)就要轉(zhuǎn)換為紅黑樹(shù)。
如果在遍歷過(guò)程中找到
key相同時(shí)直接退出遍歷。如果
e != null就相當(dāng)于存在相同的key,那就需要將值覆蓋。最后判斷是否需要進(jìn)行擴(kuò)容。
繼續(xù)看下 treeifyBin 的源碼：
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//鏈表轉(zhuǎn)為紅黑樹(shù)時(shí)，若此時(shí)數(shù)組長(zhǎng)度小于64，擴(kuò)容數(shù)組
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
//鏈表轉(zhuǎn)為樹(shù)結(jié)構(gòu)
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
由此可以看到1.8中，數(shù)組有兩種情況會(huì)發(fā)生擴(kuò)容：
一是超過(guò)閾值
二是鏈表轉(zhuǎn)為紅黑樹(shù)且數(shù)組元素小于64時(shí)
由此在jdk1.8中，默認(rèn)長(zhǎng)度為16情況下，要么元素一直放在同一下標(biāo)，鏈表轉(zhuǎn)為紅黑樹(shù)且數(shù)組元素小于64時(shí)就會(huì)擴(kuò)容，要么超過(guò)閾值12時(shí)才會(huì)擴(kuò)容。
依據(jù)上面的源碼分析，在JDK 1.8中put方法的執(zhí)行的原理圖如下：
通過(guò)上面的分析，我們可以看到
jdk1.7和
1.8情況下
hashmap實(shí)現(xiàn)方式區(qū)別是非常大的。在源碼的分析中，也可以找到下面問(wèn)題的答案。
問(wèn)點(diǎn)三：HashMap的擴(kuò)容機(jī)制是怎么樣的？JDK7與JDK8有什么不同嗎？
JDK 1.7的擴(kuò)容條件是數(shù)組長(zhǎng)度大于閾值且存在哈希沖突，在JDK 7中的擴(kuò)容的源碼如下：
void addEntry(int hash, K key, V value, int bucketIndex) {
//數(shù)組長(zhǎng)度大于閾值且存在哈希沖突（即當(dāng)前數(shù)組下標(biāo)有元素），就將數(shù)組擴(kuò)容至2倍
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
而JDK 1.8擴(kuò)容條件是數(shù)組長(zhǎng)度大于閾值或鏈表轉(zhuǎn)為紅黑樹(shù)且數(shù)組元素小于64時(shí)，源碼中的體現(xiàn)如下所示：
//數(shù)組長(zhǎng)度大于閾值，就擴(kuò)容
if (++size > threshold)
resize();
//鏈表轉(zhuǎn)為紅黑樹(shù)時(shí)，若此時(shí)數(shù)組長(zhǎng)度小于64，擴(kuò)容數(shù)組
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
問(wèn)點(diǎn)四：HashMap中的鍵值可以為Null嗎？能簡(jiǎn)單說(shuō)一下原理嗎？
在JDK7中是允許null存進(jìn)去的，通過(guò) putForNullKey(value)方法來(lái)存儲(chǔ)key為null值，具體的實(shí)現(xiàn)的源代碼如下：
if (key == null)
return putForNullKey(value);
而在JDK 8中當(dāng)傳進(jìn)key為null值的時(shí)候，就直接將hash值取0，進(jìn)行計(jì)算存入值的位置。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
問(wèn)點(diǎn)五：HashMap中能put兩個(gè)相同的Key嗎？為什么能或?yàn)槭裁床荒埽?/strong>
這個(gè)問(wèn)題比較簡(jiǎn)單，在JDK7和JDK8中的做法是一樣的，若是存入的key值一樣，就會(huì)將原來(lái)的key所對(duì)應(yīng)的value值直接替換掉，可以從源碼中看出：
// JDK1.7
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
// 直接替換原來(lái)的value值
e.value = value;
e.recordAccess(this);
return oldValue;
}
// JDK 1.8
else {
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;
}
// 存在key值相同
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)
// 替換掉原來(lái)value值
e.value = value;
afterNodeAccess(e);
return oldValue;
}
問(wèn)點(diǎn)六：聊一聊JDK 7的HashMap中的“死鎖”是怎么回事？
HashMap是線程不安全的，在HashMap的源碼中并未對(duì)其操作進(jìn)行同步執(zhí)行，所以在并發(fā)訪問(wèn)的時(shí)候就會(huì)出現(xiàn)線程安全的問(wèn)題。
由于上一篇的ConcurrentHashMap篇中講到了死鎖，也畫(huà)了圖，但是很多讀者說(shuō)看不懂，這里我的鍋，在這里詳細(xì)的進(jìn)行圖解。
假設(shè)：有線程A和線程B，并發(fā)訪問(wèn)HashMap中的數(shù)據(jù)。假設(shè)HashMap的長(zhǎng)度為2(這里只是為了講解方便假設(shè)長(zhǎng)度為2)，鏈表的結(jié)構(gòu)圖如下所示：
4和8都位于同一條鏈表上，其中的threshold為1，現(xiàn)在線程A和線程B都要進(jìn)行put操作，首先線程A進(jìn)行插入值。
此時(shí)，線程A執(zhí)行到transfer函數(shù)中（transfer函數(shù)是resize擴(kuò)容方法中調(diào)用的另一個(gè)方法），當(dāng)執(zhí)行（1）位置的時(shí)候，如下所示：
/**
* Transfers all entries from current table to newTable.
*/
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next; ---------------------(1)
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} // while
}
}
此時(shí)線程A掛起，在此時(shí)在線程A的棧中就會(huì)存在如下值：
e = 4
next = 8
此時(shí)線程B執(zhí)行put的操作，并發(fā)現(xiàn)在進(jìn)行put操作的時(shí)候需要擴(kuò)容，當(dāng)線程B執(zhí)行 transfer函數(shù)中的while循環(huán)，即會(huì)把原來(lái)的table變成新一table（線程B自己的棧中），再寫(xiě)入到內(nèi)存中。
執(zhí)行的過(guò)程如下圖所示（假設(shè)兩個(gè)元素在新的hash函數(shù)下也會(huì)映射到同一個(gè)位置）：
此時(shí)線程A有獲取到
cpu的執(zhí)行時(shí)間，接著執(zhí)行（但是纖層A中的數(shù)據(jù)仍是舊表數(shù)據(jù)），即從
transfer代碼（1）處接著執(zhí)行，當(dāng)前的
e = 4, next = 8, 上面已經(jīng)描述，執(zhí)行的的過(guò)程若下圖所示：
當(dāng)操作完成，執(zhí)行查找時(shí)，會(huì)陷入死循環(huán)！
問(wèn)點(diǎn)七：HashMap是線程安全的嗎？為什么安全或者不安全？
從上圖JDK8的put操作原理圖中可以看出為HashMap的put方法的詳細(xì)過(guò)程，其中造成線程不安全的方法主要是resize(擴(kuò)容)方法.
假設(shè)，現(xiàn)在有線程A 和線程B 共同對(duì)同一個(gè)HashMap進(jìn)行put操作，假設(shè)A和B插入的Key-Value中key的hashcode是相同的,這說(shuō)明該鍵值對(duì)將會(huì)插入到Table的同一個(gè)下標(biāo)的,也就是會(huì)發(fā)生哈希碰撞。
此時(shí)HashMap按照平時(shí)的做法是形成一個(gè)鏈表(若超過(guò)八個(gè)節(jié)點(diǎn)則是紅黑樹(shù)),現(xiàn)在我們插入的下標(biāo)為null(Table[i]==null)則進(jìn)行正常的插入。
此時(shí)線程A進(jìn)行到了這一步正準(zhǔn)備插入，這時(shí)候線程A堵塞，線程B獲得運(yùn)行時(shí)間，進(jìn)行同樣操作，也是Table[i]==null 。此時(shí)它直接運(yùn)行完整個(gè)put方法,成功將元素插入.。
隨后，線程A獲得運(yùn)行時(shí)間接上上面的判斷繼續(xù)運(yùn)行，進(jìn)行了Table[i]==null的插入(此時(shí)其實(shí)應(yīng)該是Table[i]!=null的操作，因?yàn)榍懊婢€程B已經(jīng)插入了一個(gè)元素了)，這樣就會(huì)直接把原來(lái)線程B插入的數(shù)據(jù)直接覆蓋了，如此一來(lái)就造成了線程不安全問(wèn)題.
問(wèn)點(diǎn)八：為什么重寫(xiě)對(duì)象的Equals方法時(shí)，要重寫(xiě)HashCode方法？這個(gè)和HashMap有關(guān)系嗎？為什么？
對(duì)于這個(gè)問(wèn)題，我之前已經(jīng)詳細(xì)寫(xiě)過(guò)一篇文章，這里就不再做贅述。
特別推薦一個(gè)分享架構(gòu)+算法的優(yōu)質(zhì)內(nèi)容，還沒(méi)關(guān)注的小伙伴，可以長(zhǎng)按關(guān)注一下：
長(zhǎng)按訂閱更多精彩▼
如有收獲，點(diǎn)個(gè)在看，誠(chéng)摯感謝
免責(zé)聲明：本文內(nèi)容由21ic獲得授權(quán)后發(fā)布，版權(quán)歸原作者所有，本平臺(tái)僅提供信息存儲(chǔ)服務(wù)。文章僅代表作者個(gè)人觀點(diǎn)，不代表本平臺(tái)立場(chǎng)，如有問(wèn)題，請(qǐng)聯(lián)系我們，謝謝！
下載文檔
