來吧!一文徹底搞定哈希表!

NO IMAGE

哈希表是個啥?

小白: 慶哥,什麼是哈希表?這個哈希好熟悉,記得好像有HashMap和HashTable之類的吧,這是一樣的嘛?😊

慶哥: 這個哈希確實經常見😂,足以說明它是個使用非常頻繁的玩意兒,而且像你說的HashMap和HashTable之類的與哈希這個詞肯定是有關係的,那哈希是個啥玩意啊,這個咱們還是得先來搞明白啥是個哈希表。😎

我們看看百科解釋吧:

散列表Hash table,也叫哈希表),是根據(Key)而直接訪問在內存存儲位置的數據結構。也就是說,它通過計算一個關於鍵值的函數,將所需查詢的數據映射到表中一個位置來訪問記錄,這加快了查找速度。這個映射函數稱做散列函數,存放記錄的數組稱做散列表

怎麼樣?看到這個,你知道哈希表是什麼了嘛?

小白: 我之前是對哈希表一竅不通啊,不過看了這個百科的解釋,我知道如下這些關於哈希表的簡單知識點:

1、哈希表其實也叫散列表,兩個是一個玩意,英文是Hash Table

2、哈希表是一個數據結構

這兩個概念是比較清晰的,至於其他的說什麼映射函數叫做散列函數,存放記錄的數組叫做散列表這個就有點模糊了,尤其說存放記錄的數組稱為散列表,那意思是哈希表是個數組?🤣

慶哥: 首先你說的很清晰的兩點說的是很準確的,哈希表也叫做散列表,這只不過是叫法而已,英文單詞是Hash table,看到這個英文單詞基本上就能猜到,哈希表其實就是直接根絕英文單詞音譯過來的,至此你應該知道了啥是哈希了吧,對於另外一點,那就很重要了,那就是哈希表其實是一種數據結構。

要知道數據結構有很多中,每一種都有各自的特點,那麼哈希表既然也是一種數據結構,那它有什麼特點呢?按照百科的解釋,我們大致能知道:可以根據一個key值來直接訪問數據,因此查找速度快

對了,你知道最基本的幾個數據結構中,哪個的查詢效率是最高的嘛?

小白: 據我所知,應該是數組吧,我們可以直接使用數組下標來訪問數據,因此查詢效率是很高滴😁

慶哥: 對,非常對,哈希表其實本質上就是一個數組 。

小白: 那為啥還叫哈希表呢?🤣,哈希表肯定有啥特別的吧,為啥本質上是一個數組呢?

哈希表本質是數組?

慶哥: 必須滴啊,哈希表本質上是個數組,只能說它的底層實現是用到了數組,簡單點說,在數組的這個基礎上再捯飭捯飭,加工加工,變得更加有特色了,然後人家就自立門戶,叫哈希表😂

小白: 這是咋個回事啊🤣

慶哥: 為什麼說哈希表的本質是個數組呢?那就得看看,哈希表是怎麼來實現的了,一般來說啊,實現哈希表我們可以採用兩種方法:

1、數組+鏈表

2、數組+二叉樹

簡單點就有這麼兩種方式,其實說白了,無論哪個都是必須有數組啊,都是再數組的基礎上取搞其他的,而且比如第一種數組+鏈表的形式,本質上是出現哈希衝突的一種解決辦法,使用鏈表存放,所以綜合起來叫做數組+鏈表的方式來實現一個哈希表,另外數組中一般就是存放的單一的數據,而哈希表中存放的是一個鍵值對,這是個區別吧!

小白: 停!!!有點迷糊🤣,什麼哈希衝突,什麼玩意兒啊😂

慶哥: 🤪,好吧好吧,我說的有點著急了😂,你就記住,哈希表在本質上就是個數組就ok了。

小白: 可是我還是像知道為啥啊?🤣

慶哥: 彆著急啊,咱慢慢來講,另外在百科上有這麼一個例子,可以幫助你更好的理解哈希表是個啥,它是這樣說的:

來吧!一文徹底搞定哈希表!

怎麼樣?看的懂嘛?

小白: 反正是有點模糊,這其中提到的函數關係啊,關鍵字啊,散列函數還有什麼函數法則的有點迷迷糊糊的🤣

哈希表的幾個概念

啥是散列函數

慶哥: 確實,這都是哈希表中很重要的幾個概念,那咱就先搞懂這幾個概念吧,我用大白話給你說說這個例子。😎

比如說,我現在給你個電話本,上面記錄的有姓名和對應的手機號,我想讓你幫我找王二的手機號是多少,那麼你會怎麼做呢?

小白: 這樣啊,那我就挨個找王二唄?😀

慶哥: 確實可以,那麼你有沒有想過,如果這個王二是在最後幾頁,那你去豈不是前面幾頁都白找了,有沒有更快的方式呢?

小白: 也是哦,那這樣的話,是不是可以按照人名給分個類,比如按照首字母來排序,就abcd那樣的順序,這樣根據王二我就知道去找w這些,這樣不久快很多了😁

慶哥: 的確,我們可以按照人名的首字母去弄一個表格,比如像這樣:

來吧!一文徹底搞定哈希表!

你看,假如現在我讓你去幫我找王二的手機號,你一下子就能找到,不用再挨個的去查找了,這效率就高的多了,那麼現在重點來了,人家本來叫王二,你為啥用一個w來標記人家呢?讓你找王二為啥你不直接找王二而是去找w呢?

小白: 這個?😅,用w可以更快速的去定位到王二啊😂

慶哥: 說的很對,我們取姓名的首字母作為一個標誌,就可以很快的找到以這個字母開頭的人名了,那麼王二也就能更快的被我們找到,我們也不用再費力氣去找什麼張二和李二的,因為人家的名字首字母都不是w。

小白: 那必須啊,這個方法好吧😁

慶哥: 對對對,你說到點子上了,那就是方法二字,這裡我們就是採用一種方法,什麼方法呢?那就是取姓名的首字母做一個排序,那麼這是不是就是通過一些特定的方法去得到一個特定的值,比如這裡取人名的首字母,那麼如果是放到數學中,是不是就是類似一個函數似的,給你一個值,經過某些加工得到另外一個值,就像這裡的給你個人名,經過些許加工我們拿到首字母,那麼這個函數或者是這個方法在哈希表中就叫做散列函數,其中規定的一些操作就叫做函數法則,這下你知道什麼是散列函數了吧😎

小白: 嗯呢,這下真的是很清楚了,說白了,不就是給我一個值,經過捯飭一下,變成另外一個值嗎?花個圖的話就是這個樣子:

來吧!一文徹底搞定哈希表!

哈哈,是不是這樣?😂

慶哥: 簡單來說就是這樣滴😎,咋樣,這下知道什麼是散列函數了吧?

關鍵值key是啥?

小白: 這下知道了,很清楚😎,那這個關鍵字key是個啥玩意?

慶哥: 這個也好理解啊,就像你畫的這個圖,1是怎麼得出來得,是不是根據未加工之前得101得出來得,這個加工過程其實就是個散列函數,而丟給它的這個101就是這個關鍵值啊,為啥叫它關鍵值嘞,那是因為我們要對它做加工才能得出我們想要的1啊,你說它關不關鍵😂

小白: 哦哦,原來是這樣啊,這下就明白啦!對了,我現在有這樣的一個理解,你看看對不對啊,那就是哈希表就是通過將關鍵值也就是key通過一個散列函數加工處理之後得到一個值,這個值就是數據存放的位置,我們就可以根據這個值快速的找到我們想要的數據,是不是這樣啊?😂

慶哥: 說的很正確😎,那你現在對之前那個百科的例子懂了嘛?

小白: 嗯呢,這下懂了😀

慶哥: 嗯呢,那就好,其實吧,上面的那中情況並不好,為啥嘞?你想啊,王二在那個位置,如果再來個王三呢?人家的首字母也是w啊,這咋辦,位置被王二佔了,那王三咋辦?這就是哈希衝突啊,撞衫啦🤣

小白: 阿西吧,又是哈希衝突,它到底似乎個啥玩意啊😂

慶哥: 不著急,咱們繼續來探究哈希表。

再探哈希表

慶哥: 我們在之前已經知道了哈希表的本質其實是個數組,數組有啥特點啊?

小白: 數組嘛,那就是下表從0開始啊,連續的,直接通過下標訪問,比如下面這樣:

來吧!一文徹底搞定哈希表!

有一個數組a,我們可以直接通過a[1]的形式來訪問到數值7,所以查詢效率很高。

慶哥: 完全正確,那麼哈希表本質上是個數組,那它跟這個類似嗎?我們來再深入探究一下,首先看個圖:

來吧!一文徹底搞定哈希表!

這張圖可是信息量很大啊,你看出來個啥了嘛?

小白: 這個?我看到了哈希函數,這是啥?它跟散列函數有啥區別啊?還有Entry是個什麼鬼😂,還有鍵值對🤣,蒙圈啊😥

哈希函數

慶哥: 別蒙圈啊,我來仔細跟你說說,其實這個哈希函數就是我們之前說的散列函數,為啥嘞?這就跟哈希表也叫做散列表一樣啊,你叫作散列表的時候有個散列函數,那你叫哈希表的時候,也得有個哈希函數啊,這樣才公平嘛😀,咋樣,知道了吧?

小白: 我去,原來是這麼回事啊🤣,那鍵值對跟Entry嘞?

鍵值對和Entry

慶哥: 這個可是值得好好說道說道,我們知道哈希表本質上是個數組,難道就跟數組的基本使用那樣,存個數值,然後通過下表讀取之類的嘛?當然不是啦,對於哈希表,它經常存放的是一些鍵值對的數據,啥是鍵值對啊,就是我們經常說的key-value啊,簡單點說就是一個值對應另外一個值,比如a對應b,那麼a就是key,b是value,哈希表存放的就是這樣的鍵值對,在哈希表中是通過哈希函數將一個值映射到另外一個值的,所以在哈希表中,a映射到b,a就叫做鍵值,而b呢?就叫做a的哈希值,也就是hash值。

咋樣,這塊明白了嘛?

小白: 嗯嗯,明白的,慶哥繼續!😎

慶哥: 那好,我們繼續,鍵值對說的簡單點就是有一個key和一個value對應著,比如這張圖裡的學生信息:

來吧!一文徹底搞定哈希表!

學生的學號和姓名就是一個鍵值對啊,根據這個學號就能找到這個學生的姓名,那啥是Entry嘞,我們都知道鍵值對,在很多語言中也許都有鍵值對,說白了就是個大眾臉啊,咋弄,在咱jdk中可不能那麼俗氣,不能再叫鍵值對了,叫啥嘞,那就叫Entry吧😂

咋樣,知道啥是鍵值對和Entry了吧!

小白: 必須滴啊,講的那麼生動😁,這張圖感覺遠不止如此啊,慶哥繼續啊😜

哈希表如何存數據

慶哥: 好滴,那咱們就繼續,來說說哈希表是如何存放數據的,記得看上面的圖啊,我們按照這個圖來說,我們已經知道了哈希表本質是個數組,所以這裡有個數組,長度是8,現在我們要做的是把這個學生信息存放到哈希表中,也就是這個數組中去,那我們需要考慮怎麼去存放呢?

這裡的學號是個key,我們之前也知道了,哈希表就是根據key值來通過哈希函數計算得到一個值,這個值就是用來確定這個Entry要存放在哈希表中的位置的,實際上這個值就是一個下標值,來確定放在數組的哪個位置上。

比如這裡的學號是101011,那麼經過哈希函數的計算之後得到了1,這個1就是告訴我們應該把這個Entry放到哪個位置,這個1就是數組的確切位置的下標,也就是需要放在數組中下表為1的位置,如圖中所示。

我們之前已經介紹過什麼是Entry了,所以這裡你要知道,數組中1的位置存放的是一個Entry,它不是一個簡單的單個數值,而是一個鍵值對,也就是存放了key和value,key就是學號101011,value就是張三,我們經過哈希函數計算得出的1只是為了確定這個Entry該放在哪個位置而已。

現在我們就成功把這個Entry放到了哈希表中了,怎麼樣,這塊聽懂了嘛?

小白: 嗯嗯,聽懂了,不過看到這裡我產生了一個疑問,那就是這個哈希函數,是不是有一個特定的加工過程,比如可以經過某種計算把101011轉換成1,那麼有沒有可能其他的學號經過哈希函數的計算也得出1呢?那這個時候是不是就撞衫啦😂

哈希衝突

慶哥: 的確,你分析得很正確,我們再來看下面這張圖:

來吧!一文徹底搞定哈希表!

你說的這種情況就像圖中展示的那樣,學號為102011的李四,他的學號經過哈希函數的計算也得出了1,那麼也要放到數組中為1的位置,可是這個位置之前已經被張三佔了啊,這怎麼辦?這種情況就是哈希衝突或者也叫哈希碰撞。

既然出現了這情況,不能不管李四啊,總得給他找個位置啊,怎麼找呢?

小白: 我猜肯定有什麼方法可以給李四找位置🤣

處理哈希衝突

慶哥: 那必須滴啊😄,有什麼方法呢?其實關於哈希衝突的解決辦法有好幾種嘞,但是我這裡只介紹兩種主要的方法,一個是開放尋址法,一個是拉鍊法。

那什麼是開放尋址法呢?我們繼續來看圖:

來吧!一文徹底搞定哈希表!

我覺得看圖就足以說明問題了,這裡所說的開放尋址法其實簡單來說就是,既然位置被佔了,那就另外再找個位置不就得了,怎麼找其他的位置呢?這裡其實也有很多的實現,我們說個最基本的就是既然當前位置被佔用了,我們就看看該位置的後一個位置是否可用,也就是1的位置被佔用了,我們就看看2的位置,如果沒有被佔用,那就放到這裡唄,當然,也有可能2的位置也被佔用了,那咱就繼續往下找,看看3的位置,一次類推,直到找到空位置。

對了,Java中的ThreadLocal就是利用了開放尋址法。

小白: 啥是ThreadLocal啊😂

慶哥: 咋滴,你不知道啊,沒事,給你一篇文章,看了包裝你再也不學ThreadLocal了,因為看完這篇,你就再也忘不掉啦,鏈接直達,走起:再也不學ThreadLocal了,看這一篇就忘不掉了!(萬字總結)

小白: 嗯嗯,我會好好看看的。那什麼是拉鍊法啊?

慶哥: 拉鍊法也是比較常用的,像之前你說的HashMap就是使用了這種方法,那這個方法是怎麼個回事呢?我們繼續來看圖:

來吧!一文徹底搞定哈希表!

之前說的開放尋址法採用的方式是在數組上另外找個新位置,而拉鍊法則不同,還是在該位置,可是,該位置被佔用了咋整,總不能打一架,誰贏是誰的吧😂,當然不是這樣,這裡採用的是鏈表,什麼意思呢?就像圖中所示,現在張三和李四都要放在1找個位置上,但是張三先來的,已經佔了這個位置,待在了這個位置上了,那李四呢?解決辦法就是鏈表,這時候這個1的位置存放的不單單是之前的那個Entry了,此時的Entry還額外的保存了一個next指針,這個指針指向數組外的另外一個位置,將李四安排在這裡,然後張三那個Entry中的next指針就指向李四的這個位置,也就是保存的這個位置的內存地址,如果還有衝突,那就把又衝突的那個Entry放在一個新位置上,然後李四的Entry中的next指向它,這樣就形成了一個鏈表。

好啦,這就是拉鍊法,咋樣,明白不😎

小白: 信息量不少啊,好在慶哥講的比較清楚,明白啦😀

慶哥: 明白了就好,那我問你一個問題啊,針對開放尋址和拉鍊法,你有沒有覺得會產生什麼問題呢?

小白: 嗯嗯,我還真有問題,首先是這個拉鍊法啊,如果衝突的很多,那這個增加的鏈表豈不是很長,這樣也不咋好吧😂

慶哥: 的確,如果衝突過多的話,這塊的鏈表會變得比較長,怎麼處理呢?這裡舉個例子吧,拿java集合類中的HashMap來說吧,如果這裡的鏈表長度大於等於8的話,鏈表就會轉換成樹結構,當然如果長度小於等於6的話,就會還原鏈表。以此來解決鏈表過長導致的性能問題。

小白: 為啥是小於等於6啊,咋不是7嘞😂

慶哥: 這樣設計是因為中間有個7作為一個差值,來避免頻繁的進行樹和鏈表的轉換,因為轉換頻繁也是影響性能的啊。

小白: 嗯嗯,這個知道了,關於開放尋址也有個疑問,那就是如果一直找不到空的位置咋整啊?🤣

慶哥: 這個不會的,為啥嘞?你這樣想,是因為你考慮了一個前提,那就是位置已經被佔光了,沒有空位置了,但是實際情況是位置不會被佔光的,因為有一定量的位置被佔了的時候就會發生擴容。

小白: 阿西吧,還有擴容,那這個擴容是咋回事呢?

哈希表的擴容

慶哥: 其實這裡不僅僅是因為你說的那種情況才會擴容,還有一個很重要的原因就是當哈希表被佔的位置比較多的時候,出現哈希衝突的概率也就變高了,所以很有必要進行擴容。

那麼這個擴容是怎麼擴的呢?這裡一般會有一個增長因子的概念,也叫作負載因子,簡單點說就是已經被佔的位置與總位置的一個百分比,比如一共十個位置,現在已經佔了七個位置,就觸發了擴容機制,因為它的增長因子是0.7,也就是達到了總位置的百分之七十就需要擴容。

還拿HashMap來說,當它當前的容量佔總容量的百分之七十五的時候就需要擴容了。

而且這個擴容也不是簡單的把數組擴大,而是新創建一個數組是原來的2倍,然後把原數組的所有Entry都重新Hash一遍放到新的數組。

小白: 這個重新Hash一遍是啥意思啊?

慶哥: 因為數組擴大了,所以一般哈希函數也會有變化,這裡的Hash也就是把之前的數據通過新的哈希函數計算出新的位置來存放。

小白: 嗯嗯,原來是這麼回事啊,懂了,對了,那哈希表的數據讀取怎麼操作的啊?

哈希表如何讀取數據

慶哥: 要知道這個讀取操作,我們還來看這個圖:

來吧!一文徹底搞定哈希表!

比如我們現在要通過學號102011來查找學生的姓名,怎麼操作呢?我們首先通過學號利用哈希函數得出位置1,然後我們就去位置1拿數據啊,拿到這個Entry之後我們得看看這個Entry的key是不是我們的學號102011,一看是101011,什麼鬼,一邊去,這不是我們要的key啊,然後根據這個Entry的next知道下一給位置,在比較key,好成功找到李四。

小白: 哦哦,原來是這麼回事啊,那對於開放尋址那種是不是也是這個思路,先確定到這個位置,然後再看這個位置上的key是不是我們要的,如過不是那就看看下一個位置的。

慶哥: 可以的,完全正確,好了現在我們對哈希表的講解已經差不多了,那麼你覺得對於哈希表而言,什麼是核心呢?

哈希函數是核心

小白: 我覺得應該是哈希函數吧,經過上面的講解,我覺得,如果一個哈希函數設計的足夠好的話,就會減少哈希衝突的概率,如果設計的不好,那就會經常撞衫😂,那就很影響性能了,比如剛開始我們舉的那個例子,拿姓名的首字母來確定位置,這個哈希函數的設計就不咋滴,比如王二,王三,王四什麼的,這都會衝突啊😂

慶哥: 的確,在哈希表中,哈希函數的設計很重要,一個好的哈希函數可以極大的提升性能,而且如果你的哈希函數設計的比較簡單粗陋,那很容易被那些不懷好意的人搗亂,比如知道了你哈希函數的規則,故意製造容易衝突的key值,那就有意思了,你的哈希表就會一直撞啊,一直撞啊😂

小白: 哈哈😂,那設計哈希函數有什麼方法嗎?

慶哥: 必須有啊,比如有直接定址法,數字分析法,摺疊法,隨機數法和除留餘數法等等,要不要繼續講啊😀

小白: 我去🤣,還是不要了吧,消化不了啊,這次先到這吧,謝謝慶哥😘

感謝各位的閱讀!

本文原創作者:慶哥小白
轉載請註明出處,微信公眾號開白請聯繫我微信H653836923

▼ 大家好,非常感謝您能花時間閱讀我的文章,我在編碼之外維護了一個公眾號,名字就叫做“編碼之外”😀。這個公眾號是幹啥的?

編碼之外主要是用對話的形式為你深入講解java技術,堅持原創,並融入顏文字,讀來輕鬆有趣,詼諧幽默,且配以大量圖示加以說明,力求由淺入深,通俗易懂!對了,技術交流群每週定期分享最新java視頻資源,現在關注,後臺回覆“慶哥”,立馬送你2019最新java視頻教程,且不斷更新ing。。。

編碼之外的福利時間
1、加入技術交流群,每週定期分享最新java,Python和前端等視頻資源,幫下CSDN,幫找學習資源!
2、加入知識星球,獲取私人分享和精心維護的5T視頻教程,專屬微信客服服務,朋友圈定期推送最新學習資源,並且在網盤群共享!不怕沒有資源,就怕你學不過來!
3、當然,我會優先服務於知識星球,感興趣的請勾搭我:H653836923

來吧!一文徹底搞定哈希表!

長按二維碼識別關注!

相關文章

前端性能監控方案(首屏、白屏時間等)

100行代碼拆解EventBus核心邏輯(三)

基於Gitlab進行開發團隊管理的嘗試——02.成員負載可視化

feign中的hytrix和turbin配置