一. 面試題及剖析

1. 今日面試題

請說一下HashMap及其底層實作原理

HashMap中是如何計算key的hash值的？

HashMap如何確定某個key在table陣列中的索引位置?

HashMap中如果出現沖突怎么解決？

......

2. 題目剖析

在前3篇文章中，壹哥 給大家介紹了HashMap的基本特點、底層資料結構、HashMap中的重要屬性，分析了HashMap的默認初始容量、負載因子，還有HashMap是如何保證其容量必須是2的N次方的，以及HashMap的put()方法執行流程，但在HashMap中，其底層內容非常的復雜，所以接下來在今天的文章中，壹哥 會繼續給大家剖析HashMap的底層原始碼，敬請關注哦，

前3篇文章地址如下：

高薪程式員&面試題精講系列39之說說HashMap的特點及其底層資料結構

高薪程式員&面試題精講系列40之HashMap默認初始容量、最大容量、負載因子是多少？鏈表轉紅黑樹閾值是多少？HashMap什么時候進行擴容？

高薪程式員&面試題精講系列41之HashMap的容量為什么必須是2的N次方？說說HashMap添加資料的流程吧

二. HashMap中對key的hash運算

我們要想搞清楚HashMap的底層原理，其中有一個點必須弄清楚，就是HashMap作為一個存盤結構，我們的key-value資料到底是存到了哪個位置上？是一個接一個的挨著存盤的嗎？還是有其他的存盤方式？接下來我們就研究一下HashMap中key的定位問題，

本節相關面試題:

HashMap中是如何計算key的hash值的？

HashMap中如果出現沖突怎么解決？

壹哥在前面說過，HashMap的底層資料結構是 陣列+鏈表+紅黑樹，核心演算法是哈希演算法，基于哈希演算法的特點，我們會希望HashMap里面元素的位置分布盡量均勻一些，盡量使得每個位置上的元素數量只有一個，這樣當我們用hash演算法求得這個索引位置的時候，馬上就可以得到我們真正想要的資料元素，而不用再通過遍歷鏈表或紅黑樹，這樣就可以大大提高查詢效率，在HashMap中，設計了一個看似簡單但很優秀的hash(key)方法用于計算出key的hash值，

1. hash(key)方法的原始碼實作

我在上面給大家講解put(k,v)方法原始碼時說過，put()方法的第一步就是先要對key進行hash計算，得到一個hash值，后面會根據這個hash值尋找到一個落點，也就是資料插入到table陣列的所在位置，我們不管是進行添加、洗掉，還是進行查找，都要先利用hash(key)方法計算出hash值，進而定位到陣列的位置，所以這是很關鍵的第一步，

讓我們先看看具體的代碼實作，hash(Object key)原始碼如下:

/**
* Computes key.hashCode() *and spreads (XORs) higher *bits of hash to lower. 
**/
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

上面的原始碼其實非常簡單，主要分為3步來進行操作實作:

• ①. 如果key==null，則直接判斷當前key的hash值是0；
• ②. 如果key不為空，則進行h = key.hashCode()操作，得到key的hash值并賦值給變數h；
• ③. 最后將 h 和 h>>>16 進行異或運算，得到真正的hash值，

上面這段代碼的核心思想，就是要先得到 key 的 hashCode，將 hashCode 做一次16位的 無符號右位移，然后將右移的結果再和 hashCode做 異或運算，這段代碼叫做「擾動函式」，

有的小伙伴會問，為什么不直接用這個hashCode作為table陣列的索引，為什么還要對hashCode進行異或運算呢？這個問題問得好，問的妙，問的呱呱叫，

我們試想一下，當我們執行上面代碼中的key.hashCode()方法，最后會得到一個int型的散列值，如果直接用該散列值作為HashMap的陣列下標，那么它的取值范圍則是從?2147483648到2147483648，前后加起來大概有40億的映射空間，這個結果映射的范圍肯定會很均勻分散，一般應用很難出現碰撞，但問題是一個40億長度的陣列，記憶體是放不下的！所以我們就需要對hashCode進行高位的異或運算，減少取值范圍，另外這樣做也保證了隨機性，減少了哈希碰撞的次數，總之，這種異或高位運算主要是從速度、功效、質量來考慮的，這么做可以使得key的高低bit位都參與到Hash計算中，同時又不會有太大的開銷，

2. 關于異或運算的補充說明

可能有些小伙伴對異或運算不太熟悉了，這里我做個補充說明，

異或運算需要先將兩個數轉為二進制，然后從高位開始比較，如果相同則為0，不相同則為1，

比如對 8 ^ 11 進行異或運算，8轉為二進制是1000，11轉為二進制是1011，

從高位開始進行異或運算，最后得到的就是0011，然后二進制轉為十進制就等于3，

3. 關于Hash函式的補充說明

HashMap的核心演算法其實就是哈希函式，但是有不少人對哈希函式是啥，有什么特點還不清楚，所以這里 壹哥 對Hash函式也做個補充說明，如果你之前對Hash函式不是很熟悉，可以看看這里，

3.1 Hash(散列)的概念

所謂的Hash哈希(散列)計算，就是可以把任意長度的輸入，通過哈希演算法或者叫做散列演算法的計算都能變成固定長度的輸出，

3.2 哈希函式的作用

哈希函式的作用就是通過哈希演算法能把任意型別的key，轉換成固定型別、固定長度的散列值(整型)，

3.3 Hash沖突

由于散列是從不定長到定長，屬于是一種壓縮映射，輸出值的域會小于輸入值的域，造成不同的輸入值可能會有相同的輸出值，這就是Hash沖突，也叫做Hash碰撞，

3.4 哈希函式特點

• 相同的內容經過哈希演算法計算后，輸出的結果要一致；
• 不同的內容經過哈希演算法計算后輸出不同的結果，但也可能會出現相同的輸出結果(即哈希碰撞)；
• 同一性: 也可以叫做散列性，即每一個Hash值都要盡可能的均勻，因為存盤在陣列時要盡可能的均勻存盤；
• 遵循雪崩效應: 當有微小的key值輸入時，Hash值要發生巨大的變化，有些Hash函式是為了加密使用(如https協議)，遵循這條可以保證更高的安全性；
• 盡量避免Hash沖突: 當我們要把十個蘋果放到九個抽屜里的時候，總會有至少兩個蘋果放到同一個抽屜里(抽屜原理)，而存放兩個蘋果的抽屜，我們就可以叫它Hash沖突，或者Hash碰撞，同樣因為Hash值的長度是固定的，而key可以是任意的，所以總會出現兩個不同key的hash值相同，這種情況叫做Hash沖突，Hash沖突是不可避免的，但我們要盡可能的減少沖突，

總的來說，一個優秀的哈希演算法要把不同的內容經過哈希計算后，輸出的結果具有分布均勻的特點，也就是低碰撞率，同時計算速度還要很快！

3.5 常見的哈希演算法應用場景

哈希演算法其實是有很多不同的具體實作的，比較出名的哈希演算法有 time33演算法、Murmurhash演算法等，這些演算法都在追求更好的均勻分布和更快的計算速度，

我們也可以打開Java原始碼，看看在Java中哈希演算法的具體應用，比如String類中的hashCode()原始碼，如下所示:

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }

    return h;
}

我們可以利用String的hashCode()方法做個試驗，代碼如下所示:

public static void main(String[] args) {
    String s1="abcdef";
    String s2="abcdeg";
      
	System.out.println("s1="+s1.hashCode());
    System.out.println("s2="+s2.hashCode());
}

最終s1和s2的hash值如下:

s1=-1424385949
s2=-1424385948

s1和s2是兩個不同的字串，輸出的hash值也不同，但是卻很接近，這就說明String類采用的hash演算法分散性不好，也就是產生碰撞的概率會比較大，

而且上面實驗中，我們拿到的hashCode值也很大，無法直接作為陣列的下標，否則我們的陣列占用的記憶體空間就會非常大！

4. 確定某個key在table陣列中的索引位置

本節相關面試題:

HashMap中如果出現沖突怎么解決？

4.1 原始碼展示

上面壹哥給大家分析的hash(key)方法，是用來計算key的hash值的，但最終得到的hash值還并不能直接作為table陣列的索引，最后還需要利用該hash值，對table的length-1 進行 與運算，這樣得到的結果才是真正的table陣列的索引值，也就是靠(n-1)&hash這句話來完成的，

我們來看看HashMap中到底是如何確定一個key在陣列中的索引位置的，如下圖所示:

以上截圖，就給大家展示了HashMap是如何確定一個key在table陣列中的索引位置的，HashMap中有兩個場景用到了這里展示的索引計算公式:

• put方法插入鍵值對的時候；
• resize 擴容的時候，

4.2 計算程序分析(重點)

接下來 壹哥 會結合上圖源代碼，講解HashMap到底是如何確定一個key的索引位置的，

接下來我會列舉4種情況，分別假設HashMap的容量n為 8、16、32、64，則對應的 n-1 分別為7、15、31、63，我們將這4個數字分別轉為對應的二進制，

此時假設hash(key)計算出的hash值=99，那么我們利用(n - 1) & hash這個公式進行計算，則可以如下圖所示:

根據上圖的計算程序可知，當HashMap的容量n=64，則n-1=63，63&99進行計算就得到了35，這個35才是HashMap中table陣列具體存盤某個資料的索引位置，也就是說 key 會落到 table[35] 這個位置上，

最終HashMap存盤資料時采用的是下圖所示的結構，

以上就是HashMap計算確定一個key在table陣列中索引位置的詳細程序，

5. 確保 key 的唯一性

我們知道，HashMap中是不允許存在相同key的，那怎么才能保證 key 的唯一性呢? 實作該功能的原始碼如下:

if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
   e = p;

在我們呼叫put(k，v)方法時，首先通過hash()方法得到int型別的hash值，所以這里可以用 == 號來做判斷，但如果只有這一個條件還不行，我們還要再利用 待插入元素的key == 當前元素的p.key，或者用 待插入元素的key.equals(當前已存在的k)，經過這樣的判斷比較，就可以確定key的唯一性了，遇到相同的key，直接進行覆寫，所以HashMap就保證了key的唯一性，

三. Hash沖突(碰撞)的解決策略【重點】

本節相關面試題:

HashMap中如果出現沖突怎么解決？

上面我們說過，在hash演算法中，相同的物件產生的hashCode肯定相等，但是不同的物件也可能會產生相同的HashCode值，這就叫做哈希碰撞(沖突)，雖然很多哈希演算法經過優化，已經很大程度上減少了碰撞發生的概率，但卻無法做到100%的完全避免，

在HashMap中如果出現了哈希沖突會怎么樣呢？該怎么解決這些沖突呢？

下圖給大家展示了HashMap中不同key出現哈希沖突的解決思路，我們可以看到，在同一鏈表中的key都是不同的，但它們的hash值卻是相同的，

一般解決hash沖突的方法有兩種，一種是 開放尋址法，另一種是 拉鏈法(鏈表法)，而在HashMap中采用的是 拉鏈法 和 鏈表轉換成樹 兩種方案的結合，

1. 開放尋址法(了解)

開放尋址法的原理很簡單，就是當一個Key通過hash函式獲得對應的陣列下標，發現該下標已被占用的時候，我們可以尋找下一個空檔位置，

比如有個Entry6通過hash函式得到的下標是2，但該下標在陣列中已經被其他元素占用了，那么就向后移動1位，看看陣列下標為3的位置是否有空位，

如果下標為3的陣列也被占用了，那么就再向后移動1位，看看陣列下標為4的位置是否為空，

如果陣列下標為4的位置還沒有被占用，就把Entry6存入到陣列下標為4的位置上，這就是開放尋址的基本思路，尋址的方式有很多種，這里只是簡單的一個示例，

2. 拉鏈法(掌握)

而HashMap發生哈希碰撞時，采用的是 拉鏈法(鏈表法) 來解決問題，

當哈希碰撞發生時，HashMap會在出現沖突的位置上拉出一條鏈表，用鏈表來存盤出現沖突的資料，我們知道，HashMap中有一個Node型別，里面有個屬性叫做 next，它就是為這種鏈表設計的，

HashMap陣列中的每個元素不僅是一個Node(Entry)物件，還是一個鏈表的頭節點，每個Node(Entry)物件通過next屬性指向它的下一個Node(Entry)節點，當新來的Node(Entry)映射到與之沖突的陣列位置時，只需要插入到對應的鏈表中即可，

如下圖所示，node1、node2、node3都落在了同一個位桶上，這時就可以用鏈表的方式來處理了，node1.next = node2，node2.next = node3，這樣就可以將鏈表串起來了，而 node3.next = null，則說明這是鏈表的尾部，

大家注意，當有新元素準備插入到鏈表的時候，JDK 8中采用的是 尾插法，而不是 頭插法，在JDK 7 中采用的是頭插法，但是頭插法有個問題，就是在兩個執行緒執行 resize()擴容的時候，很可能會造成 環形鏈表，導致 get()時 出現死回圈，

3. 鏈表轉換成樹

在HashMap中，鏈表法并不是處理Hash碰撞的唯一方法，另一種策略是結合紅黑樹，當鏈表長度達到 8 之后，如果再有新元素添加進來，就會將鏈表轉換為紅黑樹，HashMap中是利用treeifyBin()方法來完成這個程序的，鏈表轉紅黑樹如下圖所示：

使用紅黑樹是出于性能方面的考慮，因為紅黑樹的查找速度優于鏈表，有的人會問，那為什么不一開始就直接生成紅黑樹，非要等鏈表長度大于等于8 之后才升級成樹呢？

首先，哈希碰撞的概率是很小的，大部分情況下都是一個位桶裝一個 Node；

另外，即便發生了哈希碰撞，都碰撞到一個桶上的概率那就更是少之又少，所以鏈表長度很少有機會能達到 8；

即使鏈表長度真到到 8 了，那說明當前 HashMap中的元素數量已經非常大了，這時候用紅黑樹來提高性能是可取的，

而反過來，如果 HashMap中總的元素很少，即便用紅黑樹對性能的提升也不大，況且紅黑樹對空間的使用要比鏈表大很多，

三. 結語

至此，壹哥 就把今天的內容給大家講解完畢，我們要重點掌握HashMap對key的hash運算，對key的定位，并且要掌握hash演算法存盤的沖突問題，以及HashMap是如何解決這些沖突問題的，這些問題都是面試時的重點，

但HashMap的內容，我們還沒有研究完，所以接下來，壹哥 會繼續分析HashMap的底層原理，比如HashMap中的擴容機制、get()取值流程等，請各位繼續關注 壹哥，送給你的肯定都是滿滿的干貨！