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

一、徹底搞懂HashMap

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

二、什么是哈希？

? 什么是哈希

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

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

解釋一：什么是哈希

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

抽屜的位置 =int index = fn(編號(hào)){
    return 編號(hào) % 抽屜的長(zhǎng)度;
}

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

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

相信通過(guò)上邊那個(gè)故事，有同學(xué)一定想到了這樣的問(wèn)題，我們有10 個(gè)抽屜，但是我們有11個(gè)蘋(píng)果，那么我們一定會(huì)有一個(gè)蘋(píng)果找不到地方放進(jìn)去，這個(gè)時(shí)候呢，多出來(lái)這個(gè)蘋(píng)果如果一定要放進(jìn)抽屜，那么就只能和其他某一個(gè)蘋(píng)果，擠一擠啦，這種情況就稱之為哈希沖突，哈希沖突怎么辦呢?他有很多種辦法，咱們就給同學(xué)們介紹map中的方式就好了，叫做鏈?zhǔn)降刂贩?，也就是?huì)把后來(lái)的蘋(píng)果掛在相同index上，形成一個(gè)鏈表，至于什么是鏈表我就不多說(shuō)啦，值得注意的是，1.7的掛法和1.8的掛法并不一樣，這個(gè)咱們后邊再聊。

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

前言

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

map中的哈希算法

以1.8為例

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

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

他為何要這么做

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

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

我們先來(lái)看式子一

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

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

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

本來(lái)的哈希code              01000111 01010101 10000000 01001010

向右的移動(dòng)16                  00000000 00000000 01000111 01010101 高位補(bǔ)0

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

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

第一點(diǎn) 32位的變化值 他盡可能的參與到運(yùn)算

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

接下來(lái)我們來(lái)看式子二

式子2 很簡(jiǎn)單，就是n-1 ，為啥要使用&和式子一計(jì)算 ，那又是為啥，接下來(lái)我們就來(lái)解答這些問(wèn)題

為什么要用&

問(wèn)題一 為啥要用&

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

看一下的這個(gè)式子

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

0100 0101

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

問(wèn)題二 數(shù)組長(zhǎng)度必須是2的n次冪

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

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

0100 0101

注意：我在的式子一最后一位寫(xiě)的是x

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

四、總結(jié)

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

猜你喜歡：

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

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

IOC底層實(shí)現(xiàn)原理介紹，手動(dòng)實(shí)現(xiàn)IOC容器