HashMap絕對是Java基礎(chǔ)的集合部分最重要的知識點之一了，網(wǎng)上文章也一抓一大把，也就不詳細(xì)分析了，這里針對一些核心點簡單做個小總結(jié)，以備之后查閱。

一、 HashMap 1.7版本介紹

1.1 數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)采用數(shù)組+單鏈表，以拉鏈法來解決hash沖突，其中數(shù)組元素和鏈表節(jié)點由Entry<K,V>實現(xiàn)，表示鍵值對。

1.2 重要參數(shù)

• initialCapacity：容量 默認(rèn)2^4 最大2^30
• loadFactor：加載因子 默認(rèn)0.75
• threshold：擴容閥值 = 容量 * 加載因子

擴容時機：
當(dāng)hashmap中的元素個數(shù)超過擴容閥值，就會進(jìn)行數(shù)組擴容，即擴大一倍，然后重新計算每個元素在數(shù)組中的位置，這個過程非常消耗性能，如果能預(yù)知容量大小，盡量手動設(shè)置initialCapacity。

加載因子：
默認(rèn)為0.75，如果自定義要注意：
設(shè)置太大：空間利用率高（擴容次數(shù)少些）、但沖突的機會加大、查找效率變低（因為鏈表變長了）
設(shè)置太?。嚎臻g利用率?。〝U容次數(shù)多些）、沖突的機會減小、查找效率高（鏈表不長）

1.3 put流程

  /**
    * 源碼分析：主要分析： HashMap的put函數(shù)
    */
   public V put(K key, V value)
//若 哈希表未初始化（即 table為空)， 則初始化 數(shù)組table 
       if (table == EMPTY_TABLE) {
       inflateTable(threshold);
   } 
       // 判斷key是否為空值null， 若key == null，則將該鍵-值 存放到數(shù)組table 中的第1個位置，即table [0]
       //（本質(zhì)：key = Null時，hash值 = 0，故存放到table[0]中）
       // 該位置永遠(yuǎn)只有1個value，新傳進(jìn)來的value會覆蓋舊的value
       if (key == null)
           return putForNullKey(value);
       // 這里首先了解3個概念：
      //hashCode：key對象的hashCode方法的返回值（若沒有重寫則默認(rèn)用Object類的hashCode方法的生成值）
      //hash值：是在hashCode值的基礎(chǔ)上又進(jìn)行了一步運算后的結(jié)果，這個運算過程就是hash方法。
      //數(shù)組下標(biāo)：根據(jù)該hash值和數(shù)組長度計算出數(shù)組下標(biāo)。
      //若 key ≠ null，則根據(jù)鍵值key計算hash值
       int hash = hash(key);
       //根據(jù)hash值 最終獲得 key對應(yīng)存放的數(shù)組Table中位置
      // indexFor的計算是：h & (length-1）  
    //原因：hashMap的初始容量和擴容都是以2的次方來進(jìn)行的，那么length-1換算成二進(jìn)制的話肯定所有位都為1，
    // 所以h& (length-1)運算從數(shù)值上來講其實等價于對length取模。那為什么要是2的N次方呢？以15為例，當(dāng)數(shù)組
   //長度為15的時 候，hash值會與length-1（1110）進(jìn)行按位與，那么最后一位永遠(yuǎn)是0, 結(jié)果是最后一位為1的位置
   //無法存儲元素，造成浪費，也造成跟多碰撞。
       int i = indexFor(hash, table.length);
       //判斷該key對應(yīng)的值是否已存在（通過遍歷 以該數(shù)組元素為頭結(jié)點的鏈表 逐個判斷）
       for (Entry<K,V> e = table[i]; e != null; e = e.next) {
           Object k;
           // 若該key已存在（即 key-value已存在 ），則用 新value 替換 舊value
           if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
               V oldValue = e.value;
               e.value = value;
               e.recordAccess(this);
               return oldValue; //并返回舊的value
           }
       }
       modCount++;
       //若該key不存在，則將“key-value”添加到table中, 這時候會進(jìn)行擴容判斷
       addEntry(hash, key, value, i);
       return null;

     //鏈表的插入方式：頭插法
     //擴容方式：達(dá)到擴容閥值 = 容量 * 加載因子，則double擴容，然后把之前元素重新計算下標(biāo)插入
   }

1.4 get流程

/**
  * 源碼分析
  */
  public V get(Object key) { 
   // 當(dāng)key == null時，則到 以哈希表數(shù)組中的第1個元素（即table[0]）為頭結(jié)點的鏈表去尋找對應(yīng) key == null的鍵
   if (key == null) 
       return getForNullKey(); 
   // 當(dāng)key ≠ null時，去獲得對應(yīng)值
   Entry<K,V> entry = getEntry(key);
   return null == entry ? null : entry.getValue(); 
}

/**
  * 作用：當(dāng)key ≠ null時，去獲得對應(yīng)值
  */ 
final Entry<K,V> getEntry(Object key) { 
   if (size == 0) { 
       return null; 
   } 
   // 根據(jù)key值，通過hash（）計算出對應(yīng)的hash值
   int hash = (key == null) ? 0 : hash(key); 
   // 根據(jù)hash值計算出對應(yīng)的數(shù)組下標(biāo)
   // 遍歷 以該數(shù)組下標(biāo)的數(shù)組元素為頭結(jié)點的鏈表所有節(jié)點，尋找該key對應(yīng)的值
   for (Entry<K,V> e = table[indexFor(hash, table.length)];  e != null;  e = e.next) { 
       Object k; 
       // 若 hash值 & key 相等，則證明該Entry是我們要的鍵值對
       // 通過equals（）判斷key是否相等
       if (e.hash == hash && 
           ((k = e.key) == key || (key != null && key.equals(k)))) 
           return e; 
   } 
   return null; 
}

二、HashMap 1.8新特性

這里簡單列下幾個核心改動：

數(shù)據(jù)結(jié)構(gòu)死亡4連問：

1 為什么引入紅黑樹？

紅黑樹是一種自平衡二叉查找樹，紅黑樹最壞查詢效率為O(log(n)),而鏈表是O(n)。從查詢效率上看紅黑樹是優(yōu)于鏈表的，而當(dāng)碰撞過多導(dǎo)致鏈表過長時，鏈表的查詢效率就會降低，這時候引入紅黑樹目的為了提升此時的查詢效率。

2 為什么不直接用紅黑樹替換鏈表？

鏈表插入效率為O(1)，而紅黑樹是O(log(n))。從插入效率上看鏈表是優(yōu)于紅黑樹的，并且在元素不多的情況下，紅黑樹查詢效率O(log(n))比較與鏈表的O(n)也沒有很明顯的優(yōu)勢，因此選擇混合使用，以達(dá)到最優(yōu)的性能表現(xiàn)。

3 為什么是紅黑樹（BR-Tree）而不是自平衡二叉查找樹（AVL-Tree）？

由于AVL高度平衡，因此AVL的查詢效率更高；但是插入和刪除引起失衡，RB-Tree開銷更小，復(fù)衡效率更高；現(xiàn)在問題是需要解決鏈表的查詢效率問題：
查詢效率：鏈表 < BR < AVL 這倆都能滿足，但是從開銷角度看：AVL的全局平衡自然要比BR的大，因此綜合考慮選紅黑樹。

4 為什么是到8才由鏈表轉(zhuǎn)紅黑樹？為什么到6又轉(zhuǎn)為鏈表？

先說為什么是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](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

當(dāng)hashCode離散性很好的時候，樹型bin用到的概率非常小，因為數(shù)據(jù)均勻分布在每個bin中，幾乎不會有bin中鏈表長度會達(dá)到閾值。但是在隨機hashCode下，離散性可能會變差，然而JDK又不能阻止用戶實現(xiàn)這種不好的hash算法，因此就可能導(dǎo)致不均勻的數(shù)據(jù)分布。不過理想情況下隨機hashCode算法下所有bin中節(jié)點的分布頻率會遵循泊松分布，我們可以看到，一個bin中鏈表長度達(dá)到8個元素的概率為0.00000006，幾乎是不可能事件。所以，之所以選擇8，不是拍拍屁股決定的，而是根據(jù)概率統(tǒng)計決定的。

至于為什么到6才轉(zhuǎn)為鏈表：這個也沒有一個明確的答案，個人感覺就是把7當(dāng)做一個鏈表和紅黑樹的過渡點，一是這個點的效率變化本身也不明顯，二是作為一個緩沖帶減少切換吧。

最后來一張1.8的元素插入整體流程圖結(jié)束

jdk1.8 hashmap 元素插入流程

參考：
https://blog.csdn.net/zyywolf/article/details/101363793
http://www.itdecent.cn/p/e136ec79235c
http://www.itdecent.cn/p/e5c8a814c0ca
http://www.itdecent.cn/p/8324a34577a0