什么是哈希？哈希算法是怎么回事？

一、徹底搞懂HashMap

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

二、什么是哈希？

? 什么是哈希

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

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

解釋一：什么是哈希

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

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

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

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

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

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

前言

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

map中的哈希算法

以1.8為例

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

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

他為何要這么做

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

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

我們先來看式子一

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

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

假設(shè) key.hashCode 是： 01000111 01010101 10000000 01001010

本來的哈希code              01000111 01010101 10000000 01001010

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

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

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

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

第二點 得到的結(jié)果是一個0,1 平均最高的數(shù)字

接下來我們來看式子二

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

為什么要用&

問題一 為啥要用&

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

看一下的這個式子

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

0100 0101

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

問題二 數(shù)組長度必須是2的n次冪

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

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

0100 0101

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

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

四、總結(jié)

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

猜你喜歡：

IO流、字節(jié)流和字符流分別是什么?

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

IOC底層實現(xiàn)原理介紹，手動實現(xiàn)IOC容器