一、HashMap集合簡介

特點：

• HashMap是Map接口的一個重要實現類，基於哈希表，以key-value的形式存儲數據，線程不安全；
• null可以作為鍵，這樣的鍵只能有一個，可以有一個或多個鍵對應的值為null；
• 存取元素無序。

底層數據結構：

• JDK1.8之前，由數組+鏈表構成，數組是存儲數據的主體，鏈表是為了解決哈希衝突而存在的；
• JDK1.8以後，由數組+鏈表+紅黑樹構成，當鏈表長度大於閾值（默認為8），並且數組長度大於64時，鏈表會轉化為紅黑樹去解決哈希衝突。

注意： 鏈表轉化為紅黑樹之前會進行判斷，若果閾值大於8，但是數組長度小於64，這時鏈表不會轉化為紅黑樹去存儲數據，而是會對數組進行擴容。

這樣做的原因： 如果數組比較小，應儘量避免紅黑樹結構。因為紅黑樹結構較為複雜，紅黑樹又稱為平衡二叉樹，需要進行左旋、右旋、變色這些操作才能保證平衡。在數組容量較小的情況下，操作數組要比操作紅黑樹更節省時間。綜上所述：為了提高性能以及減少搜索時間，在閾值大於8並且數組長度大於64的情況下鏈表才會轉化為紅黑樹而存在。具體參考treeifyBin方法。

HashMap存儲數據結構圖：

二、HashMap底層存儲數據的過程

1.以下面代碼所示進行分析：

<code>package hashmap_demo;
import java.util.HashMap;
public class HashMapTest {
    public static void main(String[] args) {
        HashMap<string> map = new HashMap<>();
        map.put("柳巖", 18);
        map.put("楊冪", 28);
        map.put("劉德華", 40);
        map.put("柳巖", 20);
        System.out.println(map);
    }
}
//輸出結果：{楊冪=28, 柳巖=20, 劉德華=40}/<string>/<code>

2.HashMap存儲過程圖：

3.存儲過程分析：

1.當執行HashMap<string> map = new HashMap<>();這行代碼創建HashMap實例對象時；在JDK1.8之前，會在構造方法中創建一個長度為16 的Entry[] table數組用來存儲鍵值對；JDK1.8之後，創建數組的時機發生了變化，不是在構造方法中創建數組了，而是在第一次調用put()方法時（即第一次向HashMap中添加元素）創建Node[] table數組。/<string>

注意： 創建HashMap實例對象在JDK1.8前後發生了變化，主要有兩點：創建的時機發生了變化；數組類型發生了變化，由原來的Entry[]類型變為Node[]類型。

2.向哈希表中存儲柳巖-18，會根據柳巖調用String類中重寫後的hashCode()方法計算出柳巖對應的哈希值，然後結合數組長度採用某種算法計算出柳巖在Node[]數組中的索引值。如果該索引位置上無數據，則直接將柳巖-18插入到該索引位置。比如計算出柳巖對應的索引為3，如上圖所示。

面試題：哈希表底層採用那種算法計算出索引值？還有哪些算法計算索引值？

答：採用key的hashCode()方法計算出哈希值，然後結合數組長度進行無符號右移（>>>）、按位異或（^）、按位與（&）計算出索引值；還可以採用平方取中法、取餘數、偽隨機數法。

取餘數：10%8=2 11%8=3；位運算效率最高，其他方式效率較低。

3.向哈希表中存儲楊冪-28，計算出該索引位置無數據，直接插入。

4.向哈希表中存儲劉德華-40，假設劉德華計算出的索引也是3，那麼此時該索引位置不為null，這時底層會比較柳巖和劉德華的哈希值是否一致，如果不一致，則在此索引位置上劃出一個節點來存儲劉德華-40，這種方式稱為拉鍊法。

補充：索引計算源碼p = tab[i = (n - 1) & hash]，即索引=哈希值&（數組長度-1），按位與運算等價於取餘運算，因為11%8=3，19%8=3，所以會出現索引相同，數組長度相同，但哈希值不同的情況。

5.最後向哈希表中存儲柳巖-20，柳巖對應的索引值為3。因為該索引位置已有數據，所以此時會比較柳巖與該索引位置上的其他數據的哈希值是否相等，如果相等，則發生哈希碰撞。此時底層會調用柳巖所屬String字符串類中的equals()方法比較兩個對象的內容是否相同：

相同：則後添加數據的value值會覆蓋之前的value值，即柳巖-20覆蓋掉柳巖-18。

不相同：繼續和該索引位置的其他對象進行比較，如果都不相同，則向下劃出一個節點存儲（拉鍊法）。

注意點：如果一個索引位置向下拉鍊，即鏈表長度大於閾值8且數組長度大於64，則會將此鏈表轉化為紅黑樹。因為鏈表的時間複雜度為O（N），紅黑樹的時間複雜度為O（logN），鏈表長度多大時O（N）>O（logN）。

三、HashMap的擴容機制

1.HashMap什麼時候進行擴容？

首先看添加元素的put()方法流程：

說明：

• 上圖中的size表示HashMap中K-V的實時數量，不等於數組的長度；
• threshold（臨界值）=capacity（數組容量）*loadFactory（加載因子），臨界值表示當前已佔用數組的最大值。size如果超過這個臨界值進調用resize()方法進行擴容，擴容後的容量是原來的兩倍；
• 默認情況下，16*0.75=12，即HashMap中存儲的元素超過12就會進行擴容。

2.HashMap擴容後的大小是多少？

<code>是原來容量的2倍，即HashMap是以2n進行擴容的。/<code>

3.HashMap的默認初始容量是多少？

HashMap的無參構造，默認初始值為16，源碼如下：

<code>/**
 * Constructs an empty HashMap with the default initial capacity
 * (16) and the default load factor (0.75).
 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}/<code>

默認初始值源碼：

<code>/**
 * The default initial capacity - MUST be a power of two.
 * 默認初始容量必須是2的冪
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; /<code>

由源碼可以看到，HashMap的默認初始容量為1左移4位，即1*2的4次方為16。如果使用HashMap的無參構造進行初始化，第一次put元素時，會觸發resize()方法（擴容方法），擴容後的容量為16。這一點和ArrayList初始化過程很相似（使用ArrayList的無參構造初始化時，創建的是一個空數組，當第一次向空數組添加元素時會觸發grow()擴容方法，擴容後的容量為10）。

4.指定初始容量為什麼必須是2的冪？

HashMap的有參構造，即可以指定初始化容量大小，源碼如下：

<code>/**
 * Constructs an empty HashMap with the specified initial
 * capacity and the default load factor (0.75).
 *
 * @param  initialCapacity the initial capacity.
 * @throws IllegalArgumentException if the initial capacity is negative.
 */
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}/<code>

即構造一個指定容量和默認加載因子（0.75）的空HashMap。

由上面的內容我們知道，當向HashMap中添加元素時，首先會根據key的哈希值結合數組長度計算出索引位置。HashMap為了存取高效需要減少哈希碰撞，使數據分配均勻，採用按位與**hash&（length-1）**計算索引值。

HashMap採用取餘的算法計算索引，即hash%length，但是取餘運算不如位運算效率高，所以底層採用按位與**hash&（length-1）**進行運算。兩種算法等價的前提就是length是2的n次冪。

5.為什麼這樣就能均勻分佈？

我們需要知道兩個結論：

• 2的n次方就是1後面n個0；如2的4次方為16，二進制表示為10000；
• 2的n次方-1就是n個1；比如2的4次方-1位15，二進制表示為1111。

舉例說明為什麼數組長度是2的n次冪可以均勻分佈：

<code>按位與運算：相同二進制位上都是1，結果為1，否則為0。
假設數組長度為2的3次冪8，哈希值為3，即3&（8-1）=3，索引為3；
假設數組長度為2的3次冪8，哈希值為2，即2&（8-1）=2，索引為2；
運算過程如下：
3&（8-1）
0000 0011 -->3
0000 0111 -->7
----------------
0000 0011 -->3

2&（8-1）
0000 0010 -->2 

0000 0111 -->7
----------------
0000 0010 -->2

結論：索引值不同，不同索引位置都有數據分佈，分佈均勻。/<code>

假設數組長度不是2的n次冪，比如長度為9，運算過程如下：

<code>假設數組長度為9，哈希值為3，即3&（9-1）=3，索引為0；
假設數組長度為9，哈希值為2，即2&（9-1）=2，索引為2；
運算過程如下：
3&（9-1）
0000 0011 -->3
0000 1000 -->8
----------------
0000 0000 -->0

2&（9-1）
0000 0010 -->2
0000 1000 -->8
----------------
0000 0000 -->0

結論：索引值都為0，導致同一索引位置上有很多數據，而其他索引位置沒有數據，致使鏈表或紅黑樹過長，效率降低。/<code>

注意： hash%length等價於hash&（length-1）的前提條件是數組長度為2的n次冪。由於底層採用按位與運算計算索引值，所以需要保證數組長度必須為2的n次冪。

6.如果指定的初始容量不是2的n次冪會怎樣？

<code>這時HashMap會通過位運算和或運算得到一個2的冪次方數，並且這個數是離指定容量最小的2的冪次數。比如初始容量為10，經過運算最後會得到16。/<code>

該過程涉及到的源碼如下：

<code>//創建HashMap集合對象，並指定容量為10，不是2的冪
HashMap<string> map = new HashMap<>(10);
//調用有參構造
public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//this關鍵字繼續調用
public HashMap(int initialCapacity, float loadFactor) {//initialCapacity=10
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);//initialCapacity=10
}
//調用tableSizeFor()方法
/**
* Returns a power of two size for the given target capacity.
* 返回指定目標容量的2的冪。
*/
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;
}/<string>/<code>

下面分析tableSizeFor()方法：

• int n = cap - 1;為什麼要減1操作呢？

<code>這是為了防止`cpa`已經是2的冪了。如果`cpa`已經是2的冪，又沒有執行減1的操作，則執行完下面的無符號右移後，返回的將為`cap`的2倍。/<code>

• n等與0時，返回1，這裡不討論你等於0的情況。
• |表示按位或運算：運算規則為相同二進制位上都是0，結果為0，否則為1。

第1次運算：

<code>int n = cap - 1;//cap=10，n=9
n |= n >>> 1;//無符號右移1位，然後再與n進行或運算
00000000 00000000 00000000 00001001  //n=9
00000000 00000000 00000000 00000100  //9無符號右移1位變為4
-----------------------------------------------
00000000 00000000 00000000 00001101  //按位或運算結果為13，即此時n=13/<code>

第2次運算：

<code>int n = 13
n |= n >>> 2;
00000000 00000000 00000000 00001101  //n=13
00000000 00000000 00000000 00000011  //13無符號右移2位變為3
------------------------------------------------ 

00000000 00000000 00000000 00001111  //按位或運算結果為15，即此時n=15/<code>

第3次運算：

<code>int n = 15
n |= n >>> 4;
00000000 00000000 00000000 00001111  //n=15
00000000 00000000 00000000 00000000  //15無符號右移4位變為0
------------------------------------------------
00000000 00000000 00000000 00001111  //按位或運算結果為15，即此時n=15/<code>

接下來的運算結果都是n=15，由於最後有一個n + 1操作，最後結果為16。

總結： 由以上運算過程可以看出，如果指定的初始容量不是2的n次冪，經過運算後會得到離初始容量最小的2冪。

四、HashMap源碼分析

1.成員變量

<code>private static final long serialVersionUID = 362498820763181265L; //序列化版本號/<code>

<code>static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //初始化容量，必須是2的n次冪/<code>

<code>static final int MAXIMUM_CAPACITY = 1 << 30; //集合最大容量：2的30次冪/<code>

<code>static final float DEFAULT_LOAD_FACTOR = 0.75f; //默認的加載因子
/**1.加載因子是用來衡量HashMap的疏密程度，計算HashMap的實時加載因子的方法為：size/capacity；
  *2.加載因子太大導致查找元素效率低，太小導致數組的利用率低，默認值為0.75f是官方給出的一個較好的臨界值； 

  *3.當HashMap裡面容納的元素已經達到HashMap數組長度的75%時，表示HashMap太擠了，需要擴容，而擴容這個過程涉及到rehash、複製數據等操作，非常消耗性能，所以開發中儘量減少擴容的次數，可以通過創建HashMap集合對象時指定初始容量來儘量避免擴容；
  *4.同時在HashMap的構造方法中可以指定加載因子大小。
  */
HashMap(int initialCapacity, float loadFactor) //構造一個帶指定初始容量和加載因子的空HashMap/<code>

<code>static final int TREEIFY_THRESHOLD = 8; //鏈表轉紅黑樹的第一個條件，鏈表長度大於閾值8/<code>

<code>static final int UNTREEIFY_THRESHOLD = 6; //刪除紅黑樹節點時，當紅黑樹節點小於6，轉化為鏈表/<code>

<code>static final int MIN_TREEIFY_CAPACITY = 64; //鏈表轉紅黑樹的第二個條件，數組長度大於64/<code>

五、常見面試題

1.發生哈希碰撞的條件是什麼？

<code>兩個對象的索引相同，並且hashCode（即哈希值）相等時，會發生哈希碰撞。/<code>

2.如何解決哈希衝突？

<code>JDK1.8之前，採用鏈表解決；JDK1.8之後，採用鏈表+紅黑樹解決。/<code>

3.如果兩個key的hashCode相同，如何存儲？

<code>使用equals比較內容是否相同：

相同：後添加的value值會覆蓋之前的value值；

不相同：劃出一個節點存儲（拉鍊法）。/<code>

4.HashMap的底層數據結構？

JDK1.8：數組+鏈表+紅黑樹。其中數組是主體，鏈表和紅黑樹是為解決哈希衝突而存在的，具體如下圖所示：

5.JDK1.8為什麼引入了紅黑樹？紅黑樹結構不是更復雜嗎？

JDK1.8以前HashMap的底層數據是數組+鏈表，我們知道，即使哈希函數做得再好，哈希表中的元素也很難達到百分之百均勻分佈。當HashMap中有大量的元素都存在同一個桶（同一個索引位置），這個桶下就會產生一個很長的鏈表，這時HashMap就相當於是一個單鏈表的結構了，假如單鏈表上有n個元素，則遍歷的時間複雜度就是O（n），遍歷效率很低。針對這種情況，JDK1.8引入了紅黑樹，遍歷紅黑樹的時間複雜度為O（logn)，由於O（n）>O（logn)；所以這一問題得到了優化。

6.為什麼鏈表長度大於8才轉化為紅黑樹？

我們知道8是從鏈表轉成紅黑樹的閾值，在源碼中有這樣一段註釋內容：

<code>/** 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
  *//<code>

翻譯過來的的值意思就是說：

紅黑樹節點所佔空間是普通鏈表節點的兩倍，並且鏈表中存儲數據的頻率符合泊松分佈，我們可以看到，在鏈表為8的節點上存儲數據的概率是0.00000006，這也就表明超過8以後的節點存儲數據的概率就非常小了。

由上述分析可以得出：

• 如果小於閾值8就是用紅黑樹，會使得結構一開始就很複雜；
• 如果大於閾值8還使用鏈表，會導致鏈表節點不能被充分利用；
• 所以，閾值8是科學合理的一個值，是空間和時間的權衡值。

7.為什麼加載因子設置為0.75？邊界值是12？

• 如果加載因子是0.4，那麼16*0.4=6，致使數組中滿6個空間就擴容，造成數組利用率太低了；
• 如果加載因子是0.9，那麼16*0.9=14，這樣就會使數組太滿，很大幾率造成某一個索引節點下的鏈表過長，進而導致查找元素效率低；
• 所以兼顧數組利用率又考慮鏈表不要太長，經過大量測試0.75是最佳值。

作者：Helay
原文鏈接：https://juejin.im/post/5e817b886fb9a03c7d3cee7c

閱讀更多 追逐仰望星空 的文章

關鍵字: 頭條女神 數據結 Java虛擬機