更新時間:2020-10-29 來源:黑馬程序員 瀏覽量:
一、徹底搞懂HashMap
相信很多朋友對于HashMap,開發(fā)中我們幾乎每天都要使用它,但是每當問到map的一些原理時,很多朋友就不知道如何去回答,甚至一問三不知,從而離我們心儀的offer越來越遠,那么今天借著咱們IT
巡游屋這個平臺,和大家分享一下關(guān)于map的原理,讓大家讀完這篇文章后,再也不會因為map而倒在面試的路上。
二、什么是哈希?
? 什么是哈希
翻譯成 “散列”,就是把任意長度的輸入,通過散列算法,變成固定長度的輸出,該輸出就是散列值,這個映射函數(shù)叫做散列函數(shù),存放記錄的數(shù)組叫做散列表。
相信讀完這個概念后,大家一定是一臉茫然的,來,這就給各位讀者老爺解釋:
解釋一:什么是哈希
假設(shè),我們有10個抽屜,我們恰好也有10個有編號隨機 的蘋果,假設(shè)每個抽屜只能放一個蘋果,那么恰好10 個蘋果就可以放在10個抽屜里邊去,當然這個順序我們是隨機放的,現(xiàn)在蘋果已經(jīng)放進去了,假設(shè)我們想找6號蘋果,我們就得打開一個一個的抽屜,去看抽屜里邊的蘋果是不是編號6 ,這樣做很有可能會在最后一個抽屜才找到我們想要的蘋果,這樣去查找一個數(shù)據(jù)無疑會很慢,所以,我們就想能不能給他加下速呢,當然可以,用咱們的哈希算法,我現(xiàn)在就建立起來一個 方法。
抽屜的位置 =int index = fn(編號){ return 編號 % 抽屜的長度; }
當我在放元素的時候,我就拿著編號的蘋果去 % 一下抽屜的長度,那只要你了解%的含義,你就一定知道的意思,我現(xiàn)在就按照得出的這個index
的值放在對應(yīng)的抽屜里邊,找的時候,我也按照這個算法算出來,此時我就能快速的找到蘋果了,什么是哈希呢?哈希其實就是我通過那個方法算出來的index
,什么是哈希函數(shù)呢?就是我的那個方法。
解釋二:什么是完美哈希,什么是哈希沖突,以及如何解決哈希沖突
相信通過上邊那個故事,有同學一定想到了這樣的問題,我們有10
個抽屜,但是我們有11個蘋果,那么我們一定會有一個蘋果找不到地方放進去,這個時候呢,多出來這個蘋果如果一定要放進抽屜,那么就只能和其他某一個蘋果,擠一擠啦,這種情況就稱之為哈希沖突,哈希沖突怎么辦呢?他有很多種辦法,咱們就給同學們介紹map中的方式就好了,叫做鏈式地址法,也就是會把后來的蘋果掛在相同index上,形成一個鏈表,至于什么是鏈表我就不多說啦,值得注意的是,1.7的掛法和1.8的掛法并不一樣,這個咱們后邊再聊。
三、map中的哈希算法是怎么回事
前言
我們都知道鏈表他的遍歷效率是很低的,而形成哈希沖突之后,他就得慢慢去遍歷鏈表,效率賊低,所以我們不希望發(fā)生哈希沖突,于是我們就得把咱們的哈希算法設(shè)計的精妙一些,來避免哈希沖突
map中的哈希算法
以1.8為例
n-1 & (h = key.hashCode()) ^ (h >>> 16)
注意:這個式子就是咱們傳說中的哈希算法,得出的結(jié)果就是哈希值,并不是咱們同學們認為的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ù)字數(shù)字,如果我拿32 位的hashCode 值和 n-1
直接計算,相當于有很多位沒有參與到運算,這樣就容易產(chǎn)生重復,那為了能讓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)該知道了吧,希望大家通過學習能有所收獲。
猜你喜歡:
IOC底層實現(xiàn)原理介紹,手動實現(xiàn)IOC容器