首頁技術(shù)文章正文

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

更新時(shí)間:2020-10-29 來源:黑馬程序員 瀏覽量:

1577370495235_學(xué)IT就到黑馬程序員.gif

一、徹底搞懂HashMap

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

二、什么是哈希?

? 什么是哈希

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

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

解釋一:什么是哈希

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

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

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

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

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

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

前言

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

map中的哈希算法

以1.8為例

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

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

他為何要這么做

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

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

我們先來看式子一

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

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

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

本來的哈希code              01000111 01010101 10000000 01001010

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

這樣不就讓一個(gè)32位的數(shù)盡可能的參與運(yùn)算了嗎,但是這樣還不夠,萬一前邊的半截和后邊的半截算出來結(jié)果 出現(xiàn)了很多的0,要么全是1 ,那大家豈不是算出來的值就沒有區(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ù)字

接下來我們來看式子二

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

為什么要用&

問題一 為啥要用&

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

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

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

0100 0101

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

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

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

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

0100 0101

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

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

四、總結(jié)

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

猜你喜歡:

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

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

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



分享到:
在線咨詢 我要報(bào)名
和我們?cè)诰€交談!