HashMap 精選面試題（背誦版）
hello，大家好，我是二哥呀！
明天就是十一黃金周了，小伙伴們是打算出去玩呢，還是選擇陪伴家人，或者戀人？也或者，狗狗和貓貓？??
二哥選擇陪父母，白嫖下他們做的飯啊，聽他們嘮叨嘮叨啊。對于，文末送書，給大家準備的一點小心意，可以先拖到文末參與下，回來再趁著摸魚的時間學習會。完美的節(jié)奏呢~~~
對于 Java 求職者來說，HashMap 可謂是重中之重，是面試的必考點。然而 HashMap 的知識點非常多，復習起來花費精力很大。
為了減輕大家在面試時的痛苦，二哥將讀者庫森的這篇 HashMap 的面試專題文章整理出來分享給大家，希望對小伙伴們有所幫助!
鏈接：https://zhuanlan.zhihu.com/p/362214327
01、HashMap的底層數(shù)據(jù)結構是什么？
JDK 7 中，HashMap 由“數(shù)組+鏈表”組成，數(shù)組是 HashMap 的主體，鏈表則是主要為了解決哈希沖突而存在的。
在 JDK 8 中，HashMap 由“數(shù)組+鏈表+紅黑樹”組成。鏈表過長，會嚴重影響 HashMap 的性能，而紅黑樹搜索的時間復雜度是 O(logn)，而鏈表是糟糕的 O(n)。因此，JDK 8 對數(shù)據(jù)結構做了進一步的優(yōu)化，引入了紅黑樹，鏈表和紅黑樹在達到一定條件會進行轉換：
當鏈表超過 8 且數(shù)據(jù)總量超過 64 時會轉紅黑樹。 將鏈表轉換成紅黑樹前會判斷，如果當前數(shù)組的長度小于 64，那么會選擇先進行數(shù)組擴容，而不是轉換為紅黑樹，以減少搜索時間。
鏈表長度超過 8 體現(xiàn)在 putVal 方法中的這段代碼：
//鏈表長度大于8轉換為紅黑樹進行處理
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
table 長度為 64 體現(xiàn)在 treeifyBin 方法中的這段代碼：：
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();
}
MIN_TREEIFY_CAPACITY 的值正好為 64。
static final int MIN_TREEIFY_CAPACITY = 64;
JDK 8 中 HashMap 的結構示意圖：
02、為什么鏈表改為紅黑樹的閾值是 8?
因為泊松分布，我們來看作者在源碼中的注釋：
Because TreeNodes are about twice the size of regular nodes, we use them only when bins contain enough nodes to warrant use (see TREEIFY_THRESHOLD). And when they become too small (due to removal or resizing) they are converted back to plain bins. In usages with well-distributed user hashCodes, tree bins are rarely used. Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution (http://en.wikipedia.org/wiki/Poisson_distribution) with a parameter of about 0.5 on average for the default resizing threshold of 0.75, although with a large variance because of resizing granularity. Ignoring variance, the expected occurrences of list size k are (exp(-0.5) pow(0.5, k) / factorial(k)). The first values are: 0: 0.60653066
1: 0.30326533
2: 0.07581633
3: 0.01263606
4: 0.00157952
5: 0.00015795
6: 0.00001316
7: 0.00000094
8: 0.00000006
more: less than 1 in ten million
翻譯過來大概的意思是：理想情況下使用隨機的哈希碼，容器中節(jié)點分布在 hash 桶中的頻率遵循泊松分布，按照泊松分布的計算公式計算出了桶中元素個數(shù)和概率的對照表，可以看到鏈表中元素個數(shù)為 8 時的概率已經(jīng)非常小，再多的就更少了，所以原作者在選擇鏈表元素個數(shù)時選擇了 8，是根據(jù)概率統(tǒng)計而選擇的。
03、解決hash沖突的辦法有哪些？HashMap用的哪種？
解決Hash沖突方法有：
開放定址法：也稱為再散列法，基本思想就是，如果p=H(key)出現(xiàn)沖突時，則以p為基礎，再次hash，p1=H(p),如果p1再次出現(xiàn)沖突，則以p1為基礎，以此類推，直到找到一個不沖突的哈希地址pi。因此開放定址法所需要的hash表的長度要大于等于所需要存放的元素，而且因為存在再次hash，所以只能在刪除的節(jié)點上做標記，而不能真正刪除節(jié)點。 再哈希法：雙重散列，多重散列，提供多個不同的hash函數(shù)，當R1=H1(key1)發(fā)生沖突時，再計算R2=H2(key1)，直到?jīng)]有沖突為止。這樣做雖然不易產(chǎn)生堆集，但增加了計算的時間。 鏈地址法：拉鏈法，將哈希值相同的元素構成一個同義詞的單鏈表，并將單鏈表的頭指針存放在哈希表的第i個單元中，查找、插入和刪除主要在同義詞鏈表中進行。鏈表法適用于經(jīng)常進行插入和刪除的情況。 建立公共溢出區(qū)：將哈希表分為公共表和溢出表，當溢出發(fā)生時，將所有溢出數(shù)據(jù)統(tǒng)一放到溢出區(qū)。
HashMap中采用的是鏈地址法 。
04、為什么在解決 hash 沖突的時候，不直接用紅黑樹？而選擇先用鏈表，再轉紅黑樹?
因為紅黑樹需要進行左旋，右旋，變色這些操作來保持平衡，而單鏈表不需要。
當元素小于 8 個的時候，此時做查詢操作，鏈表結構已經(jīng)能保證查詢性能。當元素大于 8 個的時候， 紅黑樹搜索時間復雜度是 O(logn)，而鏈表是 O(n)，此時需要紅黑樹來加快查詢速度，但是新增節(jié)點的效率變慢了。
因此，如果一開始就用紅黑樹結構，元素太少，新增效率又比較慢，無疑這是浪費性能的。
05、HashMap默認加載因子是多少？為什么是 0.75，不是 0.6 或者 0.8 ？
作為一般規(guī)則，默認負載因子（0.75）在時間和空間成本上提供了很好的折衷。
06、HashMap 中 key 的存儲索引是怎么計算的？
首先根據(jù)key的值計算出hashcode的值，然后根據(jù)hashcode計算出hash值，最后通過hash&（length-1）計算得到存儲的位置。
07、JDK 8 為什么要 hashcode 異或其右移十六位的值？
因為在JDK 7 中擾動了 4 次，計算 hash 值的性能會稍差一點點。
從速度、功效、質量來考慮，JDK 8 優(yōu)化了高位運算的算法，通過hashCode()的高16位異或低16位實現(xiàn)：(h = k.hashCode()) ^ (h >>> 16)。
這么做可以在數(shù)組 table 的 length 比較小的時候，也能保證考慮到高低Bit都參與到Hash的計算中，同時不會有太大的開銷。
08、為什么 hash 值要與length-1相與？
把 hash 值對數(shù)組長度取模運算，模運算的消耗很大，沒有位運算快。 當 length 總是 2 的n次方時， h& (length-1)運算等價于對length取模，也就是 h%length，但是 & 比 % 具有更高的效率。
09、HashMap數(shù)組的長度為什么是 2 的冪次方？
2 的 N 次冪有助于減少碰撞的幾率。如果 length 為2的冪次方，則 length-1 轉化為二進制必定是11111……的形式，在與h的二進制與操作效率會非常的快，而且空間不浪費。我們來舉個例子，看下圖：
當 length =15時，6 和 7 的結果一樣，這樣表示他們在 table 存儲的位置是相同的，也就是產(chǎn)生了碰撞，6、7就會在一個位置形成鏈表，4和5的結果也是一樣，這樣就會導致查詢速度降低。
如果我們進一步分析，還會發(fā)現(xiàn)空間浪費非常大，以 length=15 為例，在 1、3、5、7、9、11、13、15 這八處沒有存放數(shù)據(jù)。因為hash值在與14（即 1110）進行&運算時，得到的結果最后一位永遠都是0，即 0001、0011、0101、0111、1001、1011、1101、1111位置處是不可能存儲數(shù)據(jù)的。
再補充數(shù)組容量計算的小奧秘。
HashMap 構造函數(shù)允許用戶傳入的容量不是 2 的 n 次方，因為它可以自動地將傳入的容量轉換為 2 的 n 次方。會取大于或等于這個數(shù)的 且最近的2次冪作為 table 數(shù)組的初始容量，使用tableSizeFor(int)方法，如 tableSizeFor(10) = 16（2 的 4 次冪），tableSizeFor(20) = 32（2 的 5 次冪），也就是說 table 數(shù)組的長度總是 2 的次冪。JDK 8 源碼如下：
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;
}
讓cap-1再賦值給n的目的是另找到的目標值大于或等于原值。例如二進制1000，十進制數(shù)值為8。如果不對它減1而直接操作，將得到答案10000，即16。顯然不是結果。減1后二進制為111，再進行操作則會得到原來的數(shù)值1000，即8。
10、HashMap 的put方法流程？
以JDK 8為例，簡要流程如下：
1、首先根據(jù) key 的值計算 hash 值，找到該元素在數(shù)組中存儲的下標；
2、如果數(shù)組是空的，則調用 resize 進行初始化；
3、如果沒有哈希沖突直接放在對應的數(shù)組下標里；
4、如果沖突了，且 key 已經(jīng)存在，就覆蓋掉 value；
5、如果沖突后，發(fā)現(xiàn)該節(jié)點是紅黑樹，就將這個節(jié)點掛在樹上；
6、如果沖突后是鏈表，判斷該鏈表是否大于 8 ，如果大于 8 并且數(shù)組容量小于 64，就進行擴容；如果鏈表節(jié)點大于 8 并且數(shù)組的容量大于 64，則將這個結構轉換為紅黑樹；否則，鏈表插入鍵值對，若 key 存在，就覆蓋掉 value。
11、HashMap 的擴容方式？
HashMap 在容量超過負載因子所定義的容量之后，就會擴容。
12、一般用什么作為HashMap的key?
一般用Integer、String 這種不可變類當作 HashMap 的 key，String 最為常見。
因為字符串是不可變的，所以在它創(chuàng)建的時候 hashcode 就被緩存了，不需要重新計算。 因為獲取對象的時候要用到 equals() 和 hashCode() 方法，那么鍵對象正確的重寫這兩個方法是非常重要的。Integer、String 這些類已經(jīng)很規(guī)范的重寫了 hashCode() 以及 equals() 方法。
13、HashMap為什么線程不安全？
JDK 7 時多線程下擴容會造成死循環(huán)。 多線程的put可能導致元素的丟失。 put和get并發(fā)時，可能導致get為null。
馬上國慶了，二哥給大家準備了一份小驚喜：送五本《Spring Cloud Alibaba 微服務實戰(zhàn)》。
無套路，直接關注三妹的微信公眾號「程序員寶寶」回復關鍵字「001」就可以拉取到抽獎鏈接了。
覺得這本書不錯的話，也可以點擊下面的鏈接直接下單哦，書的質量真不錯呢，微服務實在是太火了，大公司在用，小公司也在用，學一下肯定是很有必要的。
最后，祝國慶快樂！