我說HashMap初始容量是16，面試官讓我回去等通知
眾所周知HashMap是工作和面試中最常遇到的數據類型，但很多人對HashMap的知識止步於會用的程度，對它的底層實現原理一知半解，了解過很多HashMap的知識點，卻都是散亂不成體系，今天一燈帶你一塊深入淺出的剖析HashMap底層實現原理。
看下面這些面試題，你能完整的答對幾道？
1. HashMap底層數據結構？
JDK1.7採用的是數組+鏈表，數組可以通過下標訪問，實現快速查詢，鏈表用來解決哈希衝突。
鏈表的查詢時間複雜度是O(n)，性能較差，所以JDK1.8做了優化，引入了紅黑樹，查詢時間複雜度是O(logn)。
JDK1.8採用的是數組+鏈表+紅黑樹的結構，當鏈表長度大於等於8，並且數組長度大於等於64時，鏈表才需要轉換成成紅黑樹。
2. HashMap的初始容量是多少？
如果面試的時候，你回答是16，面試官肯定讓你回去等通知。
JDK1.7的時候初始容量確實是16，但是JDK1.8的時候初始化HashMap的時候並沒有指定容量大小，而是在第一次執行put數據，才初始化容量。
// 負載因子大小
final float loadFactor;
// 默認負載因子大小
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 初始化方法
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
執行new HashMap()方法初始化的時候，只指定了負載因子的大小。
3. HashMap的put方法流程？
- 計算key的哈希值
- 判斷數組是否為空，如果為空，就執行擴容，初始化數據大小。
- 如果數組不為空，根據哈希值找到數組所在下標
- 判斷下標元素是否為null，如果為null就創建新元素
- 如果下標元素不為null，就判斷是否是紅黑樹類型，如果是，則執行紅黑樹的新增邏輯
- 如果不是紅黑樹，說明是鏈表，就追加到鏈表末尾
- 如果判斷鏈表長度是否大於等於8，數組長度是否大於等於64，如果不是就執行擴容邏輯
- 如果是，則需要把鏈錶轉換成紅黑樹
- 最後判斷新增元素後，判斷元素個數是否大於閾值（16*0.75=12），如果是則執行擴容邏輯，結束。
源碼如下：
// 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;
// 判斷數組是否為空，為空的話，則進行擴容初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 計算數組下標位置，判斷下標位置元素是否為null
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 數組中已經存在元素（處理哈希衝突）
else {
Node<K,V> e; K k;
// 判斷元素值是否一樣，如果一樣則替換舊值
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 判斷元素類型是否是紅黑樹
else if (p instanceof TreeNode)
// 執行紅黑樹新增邏輯
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 不是紅黑樹類型則說明是鏈表
else {
// 遍歷鏈表
for (int binCount = 0; ; ++binCount) {
// 到達鏈表的尾部
if ((e = p.next) == null) {
// 在尾部插入新結點
p.next = newNode(hash, key, value, null);
// 鏈表結點數量達到閾值(默認為 8 )，執行 treeifyBin 方法
// 這個方法會根據 HashMap 數組來決定是否轉換為紅黑樹。
// 只有當數組長度大於或者等於 64 的情況下，才會執行轉換紅黑樹操作，以減少搜索時間。否則，就是只是對數組擴容。
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
// 判斷鏈表中結點的key值與插入的元素的key值是否相等
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 相等，跳出循環
break;
// 用於遍歷桶中的鏈表，與前面的e = p.next組合，可以遍歷鏈表
p = e;
}
}
// 表示在數組中找到key值、哈希值與插入元素相等的結點
if (e != null) {
// 記錄e的value
V oldValue = e.value;
// onlyIfAbsent為false或者舊值為null
if (!onlyIfAbsent || oldValue == null)
//用新值替換舊值
e.value = value;
// 訪問後回調
afterNodeAccess(e);
// 返回舊值
return oldValue;
}
}
// 記錄修改次數
++modCount;
// 元素個數大於閾值則擴容
if (++size > threshold)
resize();
// 插入後回調
afterNodeInsertion(evict);
return null;
}
4. HashMap容量大小為什麼要設置成2的倍數？
int index = hash(key) & (n-1);
為了更快的計算key所在的數組下標位置。
當數組長度（n）是2的倍數的時候，就可以直接通過邏輯與運算（&）計算下標位置，比取模速度更快。
5. HashMap為什麼是執行緒不安全？
原因就是HashMap的所有修改方法都沒有加鎖，導致在多執行緒情況下，無法保證數據一致性和安全性。
比如：一個執行緒刪除了一個key，由於沒有加鎖，其他執行緒無法及時感知到，還繼續能查到這個key，無法保證數據的一致性。
比如：一個執行緒添加完一個元素，由於沒有加鎖，其他執行緒無法及時感知到，另一個執行緒正在擴容，擴容後就把上一個執行緒添加的元素弄丟了，無法保證數據的安全性。
6. 解決哈希衝突方法有哪些？
常見有鏈地址法、線性探測法、再哈希法等。
-
鏈地址法
就是把發生哈希衝突的值組成一個鏈表，HashMap就是採用的這種。
-
線性探測法
發生哈希衝突後，就繼續向下遍歷，直到找到空閑的位置，ThreadLocal就是採用的這種，以後再詳細講。
-
再哈希法
使用一種哈希演算法發生了衝突，就換一種哈希演算法，直到不衝突為止（就是這麼聰明）。
7. JDK1.8擴容流程有什麼優化？
在JDK1.7擴容的時候，會遍歷原數組，重新哈希，對新數組長度邏輯與，計算出數據下標，然後放到新數組中，比較麻煩耗時。
在JDK1.8擴容的時候，會遍歷原數組，然後統計出兩組數據，一組是新數組的下標位置不變，另一組是新數組的下標位置等於原數組的下標位置加上原數組的長度。
比如：數組長度由16擴容到32，哈希值是0和32的元素，在新舊數組中下標位置不變，都是下標為0的位置。而哈希值是16和48的元素，在新數組的位置=原數組的下標+原數組的長度，也就是下標為16的位置。
