HashMap基本原理

HashMap原理圖

HashMap主體上是由一個數(shù)組來存儲數(shù)據(jù)，每一個索引的位置在這里我們可以先管他叫“桶”，假設(shè)你定一個HashMap的長度為16，那么就可以說是由16個桶構(gòu)成的數(shù)組。當(dāng)我們插入一個數(shù)據(jù)的時候，并不是按順序一個一個向后存儲的，在HashMap中專門定義了一套用于定位數(shù)據(jù)存儲位置的哈希散列算法來確定數(shù)據(jù)具體的存儲位置，因為是哈希散列計算，所以會存在哈希散列碰撞，意思就是相同的Key計算出的哈希值是相同的，在HashMap中使用的是拉鏈法來解決，散列碰撞問題。

當(dāng)兩個Key的計算出的Hash值相同，但是key的值不同，那么他們就會被定位到同一個HashMap的桶中，這個時候HashMap為了不讓他們相互覆蓋，就會在同一個桶中構(gòu)建一個鏈表來存儲他們。

但是隨著HashMap中存儲的數(shù)據(jù)越來越多，發(fā)生碰撞的概率就會越大，某個桶中的鏈表就會越來越長，當(dāng)一個桶中的鏈表長度達到8這個閾值的時候，HashMap就將桶中的鏈表轉(zhuǎn)換成紅黑樹，以達到提高性能的目的。

HashMap中的桶的長度并不會一成不變，而是當(dāng)HashMap中存儲元素的數(shù)量達到總?cè)萘康?5%的時候就會，觸發(fā)HashMap的擴容機制，這個時候HashMap就會對桶大小進行擴容，擴容的數(shù)量為當(dāng)前桶大小的兩倍。以達到提高性能的目的。

默認(rèn)容量

HashMap的容量就是數(shù)組的長度，默認(rèn)容量是16

• 初始化時如果沒有指定容量，則會使用默認(rèn)值16，我們也可以為HashMap設(shè)置初始容量，而HashMap要求初始容量必須是2的冪次方。保證容量為2的冪次方的目的是：保證最后散列計算的結(jié)果是均勻
• 在設(shè)置HashMap初始化容量時HashMap會對傳入的初始容量值進行轉(zhuǎn)換，并保證初始容量都能為2的冪次方（通過tableSizeFor來保證）

HashMap如何確定Key的唯一性

HashMap是不允許存在相同Key的。
key的唯一性同時滿足如下兩個條件：

• 比較Key的Hash值是否相同。
• 比較是否同一個對象或者key的值是否相等。
  以上兩個條件都為true，則可認(rèn)為是同一個Key。

HashMap為什么要求容量必須是2的冪次方

HashMap容量必須是 2 的冪次方，這樣設(shè)計是為了保證散列計算更加均勻，計算索引的公式為 index = (n - 1) & hash

HashMap的擴容條件

• HashMap中的鍵值對數(shù)據(jù)達到擴容閾值的時候就會觸發(fā)擴容，擴容閾值=容量*負載因子，負載因子默認(rèn)值為0.75。
• HashMap擴容的時候，會創(chuàng)建一個容量為原來容量2倍的新數(shù)組，將數(shù)據(jù)從舊的數(shù)組中取出存入新的數(shù)組中

HashMap擴容負載因為為什么默認(rèn)值設(shè)置為0.75

默認(rèn)值是0.75是對HashMap查詢插入時間和空間利用率權(quán)衡得出的結(jié)果，當(dāng)負載因子為0.75的時候，避免了相當(dāng)多的Hash沖突，HashMap底層的鏈表和紅黑樹的高度也比較低，在HashMap的空間利用率、插入和查詢效率都比較高。

• 如果設(shè)置負載因子值為1.0，就意味著當(dāng)HashMap中的數(shù)組填滿之后才會觸發(fā)擴容，雖然空見的利用率達到了最高。但是也會因為Hash沖突增加，會導(dǎo)致底層的紅黑樹的高度增高，從而影響數(shù)據(jù)的插入和查詢性能。
• 如果設(shè)置負載因子值為0.5，就意味著當(dāng)HahMap存儲的數(shù)據(jù)達到容量的一半時就會觸發(fā)擴容，雖然這樣Hash沖突減少和查詢效率會提升，但是在空間的利用率上就降低了，很多空間還沒來得及使用就觸發(fā)擴容了。

鏈表紅黑樹如何互相轉(zhuǎn)換，閾值多少？

• 鏈表轉(zhuǎn)紅黑樹的閾值為：8
• 紅黑樹轉(zhuǎn)換成鏈表的閾值為：6

經(jīng)過計算，在hash函數(shù)設(shè)計合理的情況下，發(fā)生hash碰撞8次的幾率為百萬分之6，從概率上講，閾值為8足夠用；至于為什么紅黑樹轉(zhuǎn)回來鏈表的條件閾值是6而不是7或9？因為如果hash碰撞次數(shù)在8附近徘徊，可能會頻繁發(fā)生鏈表和紅黑樹的互相轉(zhuǎn)化操作，為了預(yù)防這種情況的發(fā)生。

插入元素的邏輯

• 計算插入元素Key的Hash值
• 判斷HashMap的數(shù)組是否為空，為空則初始化數(shù)組，并返回數(shù)組長度，不為空直接返回數(shù)組長度
• 確定數(shù)據(jù)插入位置，數(shù)據(jù)插入位置=Key的Hash值 & (HashMap數(shù)組長度-1)
• 根據(jù)插入位置，取出舊元素，判斷元素是否為空
• 為空則初始化數(shù)據(jù)為鏈表頭節(jié)點，然后插入數(shù)組
• 如果數(shù)據(jù)不為空，判斷新、舊元素的Key是否相等
• 相等則將新插入的數(shù)據(jù)覆蓋舊的數(shù)據(jù)，然后結(jié)束插入操作。
• 不相等，則判斷取出的數(shù)據(jù)是鏈表頭節(jié)點還是紅黑樹頭節(jié)點。
• 如果是鏈表，則將新插入數(shù)據(jù)插入鏈表尾部，插入成功后判斷鏈表長度是大于等于8，如果大于等于8則轉(zhuǎn)換成紅黑樹。
• 如果是紅黑樹，則將數(shù)據(jù)插入紅黑樹中。
• 元素插入成功這之后，HashMap長度+1。

• 判斷HashMap的數(shù)據(jù)容量是否大于擴容閾值，如果大于則觸發(fā)HashMap擴容。

  
  
  HashMap-PUT操作

HashMap線程不安全問題

• jdk 1.7中HashMap擴容會產(chǎn)生死循環(huán)（元素從鏈表頭部插入）、數(shù)據(jù)丟失、數(shù)據(jù)覆蓋的問題
• jdk1.8 中HashMap 會有數(shù)據(jù)覆蓋的問題（元素從鏈表的尾部插入）