一、徹底搞懂HashMap

相信很多朋友對于HashMap，開發中我們幾乎每天都要使用它，但是每當問到map的一些原理時，很多朋友就不知道如何去回答，甚至一問三不知，從而離我們心儀的offer越來越遠，那么今天借著咱們IT 巡游屋這個平臺，和大家分享一下關于map的原理，讓大家讀完這篇文章后，再也不會因為map而倒在面試的路上。

二、什么是哈希？

? 什么是哈希

翻譯成 “散列”，就是把任意長度的輸入，通過散列算法，變成固定長度的輸出，該輸出就是散列值，這個映射函數叫做散列函數，存放記錄的數組叫做散列表。

相信讀完這個概念后，大家一定是一臉茫然的，來，這就給各位讀者老爺解釋：

解釋一：什么是哈希

假設，我們有10個抽屜，我們恰好也有10個有編號隨機 的蘋果，假設每個抽屜只能放一個蘋果，那么恰好10 個蘋果就可以放在10個抽屜里邊去，當然這個順序我們是隨機放的,現在蘋果已經放進去了，假設我們想找6號蘋果，我們就得打開一個一個的抽屜，去看抽屜里邊的蘋果是不是編號6 ，這樣做很有可能會在最后一個抽屜才找到我們想要的蘋果，這樣去查找一個數據無疑會很慢，所以，我們就想能不能給他加下速呢，當然可以，用咱們的哈希算法，我現在就建立起來一個 方法。

抽屜的位置 =int index = fn(編號){
    return 編號 % 抽屜的長度;
}

當我在放元素的時候，我就拿著編號的蘋果去 % 一下抽屜的長度，那只要你了解%的含義，你就一定知道的意思，我現在就按照得出的這個index 的值放在對應的抽屜里邊，找的時候，我也按照這個算法算出來，此時我就能快速的找到蘋果了，什么是哈希呢?哈希其實就是我通過那個方法算出來的index ，什么是哈希函數呢?就是我的那個方法。

解釋二：什么是完美哈希，什么是哈希沖突，以及如何解決哈希沖突

相信通過上邊那個故事，有同學一定想到了這樣的問題，我們有10 個抽屜，但是我們有11個蘋果，那么我們一定會有一個蘋果找不到地方放進去，這個時候呢，多出來這個蘋果如果一定要放進抽屜，那么就只能和其他某一個蘋果，擠一擠啦，這種情況就稱之為哈希沖突，哈希沖突怎么辦呢?他有很多種辦法，咱們就給同學們介紹map中的方式就好了，叫做鏈式地址法，也就是會把后來的蘋果掛在相同index上，形成一個鏈表，至于什么是鏈表我就不多說啦，值得注意的是，1.7的掛法和1.8的掛法并不一樣，這個咱們后邊再聊。

三、map中的哈希算法是怎么回事

前言

我們都知道鏈表他的遍歷效率是很低的，而形成哈希沖突之后，他就得慢慢去遍歷鏈表，效率賊低，所以我們不希望發生哈希沖突，于是我們就得把咱們的哈希算法設計的精妙一些，來避免哈希沖突

map中的哈希算法

以1.8為例

n-1 & (h = key.hashCode()) ^ (h >>> 16)

注意：這個式子就是咱們傳說中的哈希算法，得出的結果就是哈希值，并不是咱們同學們認為的hashCode 就是它的哈希值哦

他為何要這么做

如果要明白為何要這么做，我們就得把這兩個式子拆開來看，并且對二進制有些基本的了解，現在我們把

(h = key.hashCode()) ^ (h >>> 16) 看成式子一，然后把n-1 看成式子二，n就是數組長度

我們先來看式子一

現在為了能夠更好的理解哈希沖突算法，我們把n-1 看成一個常量，也就是說式子一要和一個常量運算，得到的結果要盡可能的不一樣，因為如果一樣不就發生哈希沖突了，那么我們怎么能讓一個數和一個常量計算得到的結果盡可能的不一樣呢，那就是參與運算的位數越多，最終計算出來的結果就越不一樣，因為 key的hashCode 求出一個32 位長度的二進制數字數字，如果我拿32 位的hashCode 值和 n-1 直接計算，相當于有很多位沒有參與到運算，這樣就容易產生重復，那為了能讓32 位數都盡可能參與到運算，那我只能在32 位 長度的二進制頭上來上一刀，再讓前邊的半截和后邊的半截計算一樣，綜合一下，這樣不就盡可能多的參與到運算了嗎，這是怎么做到的呢? 我們來看式子

h =(key.hashCode()) ^ (h >>> 16)

假設 key.hashCode 是： 01000111 01010101 10000000 01001010

本來的哈希code              01000111 01010101 10000000 01001010

向右的移動16                  00000000 00000000 01000111 01010101 高位補0

這樣不就讓一個32位的數盡可能的參與運算了嗎，但是這樣還不夠，萬一前邊的半截和后邊的半截算出來結果 出現了很多的0，要么全是1 ，那大家豈不是算出來的值就沒有區別，所以，我們應該想個辦法讓0,1 盡可能的平均，怎么辦，用^符號，^符號可以在相同的概率下得到0,1 平均概率最高的一個符號，就好像這樣

如果做到了以上兩步，那么我就保證兩件事情

第一點 32位的變化值 他盡可能的參與到運算

第二點 得到的結果是一個0,1 平均最高的數字

接下來我們來看式子二

式子2 很簡單，就是n-1 ，為啥要使用&和式子一計算 ，那又是為啥，接下來我們就來解答這些問題

為什么要用&

問題一 為啥要用&

你有沒有想過，萬一我通過 一個所謂的哈希算法算出來的index它的值并不在數組索引里，比如，我有10個抽屜的位置，我通過哈希算法算出來的index 是101,那這個元素都跑到天邊去了，還怎么放，沒法放，所以我們在選用計算符號時，一定要確保 最終計算出來的結果一定 小于索引的，通過計算的式子1，有16 位之多，可以不用考慮，那么也就是說，最終得到的結果一定得小于或者等于 n-1 ，而數組索引從0 開始計算，如果小于或者等于n-1 不就正好滿足嗎?那&的特性 同1 得1 ，就完全能夠解決這個問題

看一下的這個式子

1010 1010 0100 0101 式子1 0111 1111 式子2

0100 0101

如果式子2 固定，那么如果按照同一得1 來計算，最大的值算出來就是0111 1111 ，而式子2是數組長度-1 ，那么得到的結果不就正好是 數組對應的索引最大值嗎?

問題二 數組長度必須是2的n次冪

偶數必然是二進制末尾位是0，而奇數的末尾必然是1 ，我們還是借助于之前的二進制

1010 1010 0100 010X 式子1 0111 1111 式子2

0100 0101

注意：我在的式子一最后一位寫的是x

式子2 是(n-1)，n是一個偶數，那么(n-1)一定是一個奇數，那么由于&的存在，最終的index 值，就有可能最后的結果 就是有可能是個偶數頁有可能是個奇數，至于算出來到底是個偶數還是個奇數，那么就由你的式子一決定啦~~

四、總結

好了，如果以后面試官問你，map的哈希沖突是怎么一回事，怎么答，你應該知道了吧，希望大家通過學習能有所收獲。

猜你喜歡：

IO流、字節流和字符流分別是什么?

單例模式介紹：懶漢和餓漢代碼

IOC底層實現原理介紹，手動實現IOC容器