[[325902]]

哈希表是個(gè)啥?

小白：慶哥，什么是哈希表?這個(gè)哈希好熟悉，記得好像有HashMap和HashTable之類的吧，這是一樣的嘛?😊

慶哥： 這個(gè)哈希確實(shí)經(jīng)常見😂，足以說明它是個(gè)使用非常頻繁的玩意兒，而且像你說的HashMap和HashTable之類的與哈希這個(gè)詞肯定是有關(guān)系的，那哈希是個(gè)啥玩意啊，這個(gè)咱們還是得先來搞明白啥是個(gè)哈希表。😎

我們看看百科解釋吧：

“散列表(Hash table，也叫哈希表)，是根據(jù)鍵(Key)而直接訪問在內(nèi)存存儲(chǔ)位置的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過計(jì)算一個(gè)關(guān)于鍵值的函數(shù)，將所需查詢的數(shù)據(jù)映射到表中一個(gè)位置來訪問記錄，這加快了查找速度。這個(gè)映射函數(shù)稱做散列函數(shù)，存放記錄的數(shù)組稱做散列表。

怎么樣?看到這個(gè)，你知道哈希表是什么了嘛?

小白： 我之前是對(duì)哈希表一竅不通啊，不過看了這個(gè)百科的解釋，我知道如下這些關(guān)于哈希表的簡單知識(shí)點(diǎn)：

1、哈希表其實(shí)也叫散列表，兩個(gè)是一個(gè)玩意，英文是Hash Table

2、哈希表是一個(gè)數(shù)據(jù)結(jié)構(gòu)

這兩個(gè)概念是比較清晰的，至于其他的說什么映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表這個(gè)就有點(diǎn)模糊了，尤其說存放記錄的數(shù)組稱為散列表，那意思是哈希表是個(gè)數(shù)組?🤣

慶哥： 首先你說的很清晰的兩點(diǎn)說的是很準(zhǔn)確的，哈希表也叫做散列表，這只不過是叫法而已，英文單詞是Hash table，看到這個(gè)英文單詞基本上就能猜到，哈希表其實(shí)就是直接根絕英文單詞音譯過來的，至此你應(yīng)該知道了啥是哈希了吧，對(duì)于另外一點(diǎn)，那就很重要了，那就是哈希表其實(shí)是一種數(shù)據(jù)結(jié)構(gòu)。

要知道數(shù)據(jù)結(jié)構(gòu)有很多中，每一種都有各自的特點(diǎn)，那么哈希表既然也是一種數(shù)據(jù)結(jié)構(gòu)，那它有什么特點(diǎn)呢?按照百科的解釋，我們大致能知道：可以根據(jù)一個(gè)key值來直接訪問數(shù)據(jù)，因此查找速度快

對(duì)了，你知道最基本的幾個(gè)數(shù)據(jù)結(jié)構(gòu)中，哪個(gè)的查詢效率是最高的嘛?

小白： 據(jù)我所知，應(yīng)該是數(shù)組吧，我們可以直接使用數(shù)組下標(biāo)來訪問數(shù)據(jù)，因此查詢效率是很高滴😁

慶哥： 對(duì)，非常對(duì)，哈希表其實(shí)本質(zhì)上就是一個(gè)數(shù)組 。

小白： 那為啥還叫哈希表呢?🤣，哈希表肯定有啥特別的吧，為啥本質(zhì)上是一個(gè)數(shù)組呢?

哈希表本質(zhì)是數(shù)組?

慶哥： 必須滴啊，哈希表本質(zhì)上是個(gè)數(shù)組，只能說它的底層實(shí)現(xiàn)是用到了數(shù)組，簡單點(diǎn)說，在數(shù)組的這個(gè)基礎(chǔ)上再捯飭捯飭，加工加工，變得更加有特色了，然后人家就自立門戶，叫哈希表😂

小白： 這是咋個(gè)回事啊🤣

慶哥： 為什么說哈希表的本質(zhì)是個(gè)數(shù)組呢?那就得看看，哈希表是怎么來實(shí)現(xiàn)的了，一般來說啊，實(shí)現(xiàn)哈希表我們可以采用兩種方法：

1、數(shù)組+鏈表

2、數(shù)組+二叉樹

簡單點(diǎn)就有這么兩種方式，其實(shí)說白了，無論哪個(gè)都是必須有數(shù)組啊，都是再數(shù)組的基礎(chǔ)上取搞其他的，而且比如第一種數(shù)組+鏈表的形式，本質(zhì)上是出現(xiàn)哈希沖突的一種解決辦法，使用鏈表存放，所以綜合起來叫做數(shù)組+鏈表的方式來實(shí)現(xiàn)一個(gè)哈希表，另外數(shù)組中一般就是存放的單一的數(shù)據(jù)，而哈希表中存放的是一個(gè)鍵值對(duì)，這是個(gè)區(qū)別吧!

小白： 停!!!有點(diǎn)迷糊🤣，什么哈希沖突，什么玩意兒啊😂

慶哥： 🤪，好吧好吧，我說的有點(diǎn)著急了😂，你就記住，哈希表在本質(zhì)上就是個(gè)數(shù)組就ok了。

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

慶哥： 別著急啊，咱慢慢來講，另外在百科上有這么一個(gè)例子，可以幫助你更好的理解哈希表是個(gè)啥，它是這樣說的：

怎么樣?看的懂嘛?

小白： 反正是有點(diǎn)模糊，這其中提到的函數(shù)關(guān)系啊，關(guān)鍵字啊，散列函數(shù)還有什么函數(shù)法則的有點(diǎn)迷迷糊糊的🤣

哈希表的幾個(gè)概念

啥是散列函數(shù)

慶哥： 確實(shí)，這都是哈希表中很重要的幾個(gè)概念，那咱就先搞懂這幾個(gè)概念吧，我用大白話給你說說這個(gè)例子。😎

比如說，我現(xiàn)在給你個(gè)電話本，上面記錄的有姓名和對(duì)應(yīng)的手機(jī)號(hào)，我想讓你幫我找王二的手機(jī)號(hào)是多少，那么你會(huì)怎么做呢?

小白： 這樣啊，那我就挨個(gè)找王二唄?😀

慶哥： 確實(shí)可以，那么你有沒有想過，如果這個(gè)王二是在最后幾頁，那你去豈不是前面幾頁都白找了，有沒有更快的方式呢?

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

慶哥： 的確，我們可以按照人名的首字母去弄一個(gè)表格，比如像這樣：

你看，假如現(xiàn)在我讓你去幫我找王二的手機(jī)號(hào)，你一下子就能找到，不用再挨個(gè)的去查找了，這效率就高的多了，那么現(xiàn)在重點(diǎn)來了，人家本來叫王二，你為啥用一個(gè)w來標(biāo)記人家呢?讓你找王二為啥你不直接找王二而是去找w呢?

小白： 這個(gè)?😅，用w可以更快速的去定位到王二啊😂

慶哥： 說的很對(duì)，我們?nèi)⌒彰氖鬃帜缸鳛橐粋€(gè)標(biāo)志，就可以很快的找到以這個(gè)字母開頭的人名了，那么王二也就能更快的被我們找到，我們也不用再費(fèi)力氣去找什么張二和李二的，因?yàn)槿思业拿质鬃帜付疾皇莣。

小白： 那必須啊，這個(gè)方法好吧😁

慶哥： 對(duì)對(duì)對(duì)，你說到點(diǎn)子上了，那就是方法二字，這里我們就是采用一種方法，什么方法呢?那就是取姓名的首字母做一個(gè)排序，那么這是不是就是通過一些特定的方法去得到一個(gè)特定的值，比如這里取人名的首字母，那么如果是放到數(shù)學(xué)中，是不是就是類似一個(gè)函數(shù)似的，給你一個(gè)值，經(jīng)過某些加工得到另外一個(gè)值，就像這里的給你個(gè)人名，經(jīng)過些許加工我們拿到首字母，那么這個(gè)函數(shù)或者是這個(gè)方法在哈希表中就叫做散列函數(shù)，其中規(guī)定的一些操作就叫做函數(shù)法則，這下你知道什么是散列函數(shù)了吧😎

小白： 嗯呢，這下真的是很清楚了，說白了，不就是給我一個(gè)值，經(jīng)過捯飭一下，變成另外一個(gè)值嗎?畫個(gè)圖的話就是這個(gè)樣子：

哈哈，是不是這樣?😂

慶哥： 簡單來說就是這樣滴😎，咋樣，這下知道什么是散列函數(shù)了吧?

關(guān)鍵值key是啥?

小白： 這下知道了，很清楚😎，那這個(gè)關(guān)鍵字key是個(gè)啥玩意?

慶哥： 這個(gè)也好理解啊，就像你畫的這個(gè)圖，1是怎么得出來得，是不是根據(jù)未加工之前得101得出來得，這個(gè)加工過程其實(shí)就是個(gè)散列函數(shù)，而丟給它的這個(gè)101就是這個(gè)關(guān)鍵值啊，為啥叫它關(guān)鍵值嘞，那是因?yàn)槲覀円獙?duì)它做加工才能得出我們想要的1啊，你說它關(guān)不關(guān)鍵😂

小白： 哦哦，原來是這樣啊，這下就明白啦!對(duì)了，我現(xiàn)在有這樣的一個(gè)理解，你看看對(duì)不對(duì)啊，那就是哈希表就是通過將關(guān)鍵值也就是key通過一個(gè)散列函數(shù)加工處理之后得到一個(gè)值，這個(gè)值就是數(shù)據(jù)存放的位置，我們就可以根據(jù)這個(gè)值快速的找到我們想要的數(shù)據(jù)，是不是這樣啊?😂

慶哥： 說的很正確😎，那你現(xiàn)在對(duì)之前那個(gè)百科的例子懂了嘛?

小白： 嗯呢，這下懂了😀

慶哥： 嗯呢，那就好，其實(shí)吧，上面的那中情況并不好，為啥嘞?你想啊，王二在那個(gè)位置，如果再來個(gè)王三呢?人家的首字母也是w啊，這咋辦，位置被王二占了，那王三咋辦?這就是哈希沖突啊，撞衫啦🤣

小白： 阿西吧，又是哈希沖突，它到底似乎個(gè)啥玩意啊😂

慶哥： 不著急，咱們繼續(xù)來探究哈希表。

再探哈希表

慶哥： 我們在之前已經(jīng)知道了哈希表的本質(zhì)其實(shí)是個(gè)數(shù)組，數(shù)組有啥特點(diǎn)啊?

小白： 數(shù)組嘛，那就是下表從0開始啊，連續(xù)的，直接通過下標(biāo)訪問，比如下面這樣：

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

慶哥： 完全正確，那么哈希表本質(zhì)上是個(gè)數(shù)組，那它跟這個(gè)類似嗎?我們來再深入探究一下，首先看個(gè)圖：

這張圖可是信息量很大啊，你看出來個(gè)啥了嘛?

小白： 這個(gè)?我看到了哈希函數(shù)，這是啥?它跟散列函數(shù)有啥區(qū)別啊?還有Entry是個(gè)什么鬼😂，還有鍵值對(duì)🤣，蒙圈啊😥

哈希函數(shù)

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

小白： 我去，原來是這么回事啊🤣，那鍵值對(duì)跟Entry嘞?

鍵值對(duì)和Entry

慶哥： 這個(gè)可是值得好好說道說道，我們知道哈希表本質(zhì)上是個(gè)數(shù)組，難道就跟數(shù)組的基本使用那樣，存?zhèn)€數(shù)值，然后通過下表讀取之類的嘛?當(dāng)然不是啦，對(duì)于哈希表，它經(jīng)常存放的是一些鍵值對(duì)的數(shù)據(jù)，啥是鍵值對(duì)啊，就是我們經(jīng)常說的key-value啊，簡單點(diǎn)說就是一個(gè)值對(duì)應(yīng)另外一個(gè)值，比如a對(duì)應(yīng)b，那么a就是key，b是value，哈希表存放的就是這樣的鍵值對(duì)，在哈希表中是通過哈希函數(shù)將一個(gè)值映射到另外一個(gè)值的，所以在哈希表中，a映射到b，a就叫做鍵值，而b呢?就叫做a的哈希值，也就是hash值。

咋樣，這塊明白了嘛?

小白： 嗯嗯，明白的，慶哥繼續(xù)!😎

慶哥： 那好，我們繼續(xù)，鍵值對(duì)說的簡單點(diǎn)就是有一個(gè)key和一個(gè)value對(duì)應(yīng)著，比如這張圖里的學(xué)生信息：

學(xué)生的學(xué)號(hào)和姓名就是一個(gè)鍵值對(duì)啊，根據(jù)這個(gè)學(xué)號(hào)就能找到這個(gè)學(xué)生的姓名，那啥是Entry嘞，我們都知道鍵值對(duì)，在很多語言中也許都有鍵值對(duì)，說白了就是個(gè)大眾臉啊，咋弄，在咱jdk中可不能那么俗氣，不能再叫鍵值對(duì)了，叫啥嘞，那就叫Entry吧😂

咋樣，知道啥是鍵值對(duì)和Entry了吧!

小白： 必須滴啊，講的那么生動(dòng)😁，這張圖感覺遠(yuǎn)不止如此啊，慶哥繼續(xù)啊😜

哈希表如何存數(shù)據(jù)

慶哥： 好滴，那咱們就繼續(xù)，來說說哈希表是如何存放數(shù)據(jù)的，記得看上面的圖啊，我們按照這個(gè)圖來說，我們已經(jīng)知道了哈希表本質(zhì)是個(gè)數(shù)組，所以這里有個(gè)數(shù)組，長度是8，現(xiàn)在我們要做的是把這個(gè)學(xué)生信息存放到哈希表中，也就是這個(gè)數(shù)組中去，那我們需要考慮怎么去存放呢?

這里的學(xué)號(hào)是個(gè)key，我們之前也知道了，哈希表就是根據(jù)key值來通過哈希函數(shù)計(jì)算得到一個(gè)值，這個(gè)值就是用來確定這個(gè)Entry要存放在哈希表中的位置的，實(shí)際上這個(gè)值就是一個(gè)下標(biāo)值，來確定放在數(shù)組的哪個(gè)位置上。

比如這里的學(xué)號(hào)是101011，那么經(jīng)過哈希函數(shù)的計(jì)算之后得到了1，這個(gè)1就是告訴我們應(yīng)該把這個(gè)Entry放到哪個(gè)位置，這個(gè)1就是數(shù)組的確切位置的下標(biāo)，也就是需要放在數(shù)組中下表為1的位置，如圖中所示。

我們之前已經(jīng)介紹過什么是Entry了，所以這里你要知道，數(shù)組中1的位置存放的是一個(gè)Entry，它不是一個(gè)簡單的單個(gè)數(shù)值，而是一個(gè)鍵值對(duì)，也就是存放了key和value，key就是學(xué)號(hào)101011，value就是張三，我們經(jīng)過哈希函數(shù)計(jì)算得出的1只是為了確定這個(gè)Entry該放在哪個(gè)位置而已。

現(xiàn)在我們就成功把這個(gè)Entry放到了哈希表中了，怎么樣，這塊聽懂了嘛?

小白： 嗯嗯，聽懂了，不過看到這里我產(chǎn)生了一個(gè)疑問，那就是這個(gè)哈希函數(shù)，是不是有一個(gè)特定的加工過程，比如可以經(jīng)過某種計(jì)算把101011轉(zhuǎn)換成1，那么有沒有可能其他的學(xué)號(hào)經(jīng)過哈希函數(shù)的計(jì)算也得出1呢?那這個(gè)時(shí)候是不是就撞衫啦😂

哈希沖突

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

你說的這種情況就像圖中展示的那樣，學(xué)號(hào)為102011的李四，他的學(xué)號(hào)經(jīng)過哈希函數(shù)的計(jì)算也得出了1，那么也要放到數(shù)組中為1的位置，可是這個(gè)位置之前已經(jīng)被張三占了啊，這怎么辦?這種情況就是哈希沖突或者也叫哈希碰撞。

既然出現(xiàn)了這情況，不能不管李四啊，總得給他找個(gè)位置啊，怎么找呢?

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

處理哈希沖突

慶哥： 那必須滴啊😄，有什么方法呢?其實(shí)關(guān)于哈希沖突的解決辦法有好幾種嘞，但是我這里只介紹兩種主要的方法，一個(gè)是開放尋址法，一個(gè)是拉鏈法。

那什么是開放尋址法呢?我們繼續(xù)來看圖：

我覺得看圖就足以說明問題了，這里所說的開放尋址法其實(shí)簡單來說就是，既然位置被占了，那就另外再找個(gè)位置不就得了，怎么找其他的位置呢?這里其實(shí)也有很多的實(shí)現(xiàn)，我們說個(gè)最基本的就是既然當(dāng)前位置被占用了，我們就看看該位置的后一個(gè)位置是否可用，也就是1的位置被占用了，我們就看看2的位置，如果沒有被占用，那就放到這里唄，當(dāng)然，也有可能2的位置也被占用了，那咱就繼續(xù)往下找，看看3的位置，一次類推，直到找到空位置。

對(duì)了，Java中的ThreadLocal就是利用了開放尋址法。

小白： 啥是ThreadLocal啊😂

慶哥： 咋滴，你不知道啊，沒事，給你一篇文章，看了包裝你再也不學(xué)ThreadLocal了，因?yàn)榭赐赀@篇，你就再也忘不掉啦，鏈接直達(dá)，走起：再也不學(xué)ThreadLocal了，看這一篇就忘不掉了!(萬字總結(jié))

小白： 嗯嗯，我會(huì)好好看看的。那什么是拉鏈法啊?

慶哥： 拉鏈法也是比較常用的，像之前你說的HashMap就是使用了這種方法，那這個(gè)方法是怎么個(gè)回事呢?我們繼續(xù)來看圖：

之前說的開放尋址法采用的方式是在數(shù)組上另外找個(gè)新位置，而拉鏈法則不同，還是在該位置，可是，該位置被占用了咋整，總不能打一架，誰贏是誰的吧😂，當(dāng)然不是這樣，這里采用的是鏈表，什么意思呢?就像圖中所示，現(xiàn)在張三和李四都要放在1找個(gè)位置上，但是張三先來的，已經(jīng)占了這個(gè)位置，待在了這個(gè)位置上了，那李四呢?解決辦法就是鏈表，這時(shí)候這個(gè)1的位置存放的不單單是之前的那個(gè)Entry了，此時(shí)的Entry還額外的保存了一個(gè)next指針，這個(gè)指針指向數(shù)組外的另外一個(gè)位置，將李四安排在這里，然后張三那個(gè)Entry中的next指針就指向李四的這個(gè)位置，也就是保存的這個(gè)位置的內(nèi)存地址，如果還有沖突，那就把又沖突的那個(gè)Entry放在一個(gè)新位置上，然后李四的Entry中的next指向它，這樣就形成了一個(gè)鏈表。

好啦，這就是拉鏈法，咋樣，明白不😎

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

慶哥： 明白了就好，那我問你一個(gè)問題啊，針對(duì)開放尋址和拉鏈法，你有沒有覺得會(huì)產(chǎn)生什么問題呢?

小白： 嗯嗯，我還真有問題，首先是這個(gè)拉鏈法啊，如果沖突的很多，那這個(gè)增加的鏈表豈不是很長，這樣也不咋好吧😂

慶哥： 的確，如果沖突過多的話，這塊的鏈表會(huì)變得比較長，怎么處理呢?這里舉個(gè)例子吧，拿java集合類中的HashMap來說吧，如果這里的鏈表長度大于等于8的話，鏈表就會(huì)轉(zhuǎn)換成樹結(jié)構(gòu)，當(dāng)然如果長度小于等于6的話，就會(huì)還原鏈表。以此來解決鏈表過長導(dǎo)致的性能問題。

小白： 為啥是小于等于6啊，咋不是7嘞😂

慶哥： 這樣設(shè)計(jì)是因?yàn)橹虚g有個(gè)7作為一個(gè)差值，來避免頻繁的進(jìn)行樹和鏈表的轉(zhuǎn)換，因?yàn)檗D(zhuǎn)換頻繁也是影響性能的啊。

小白： 嗯嗯，這個(gè)知道了，關(guān)于開放尋址也有個(gè)疑問，那就是如果一直找不到空的位置咋整啊?🤣

慶哥： 這個(gè)不會(huì)的，為啥嘞?你這樣想，是因?yàn)槟憧紤]了一個(gè)前提，那就是位置已經(jīng)被占光了，沒有空位置了，但是實(shí)際情況是位置不會(huì)被占光的，因?yàn)橛幸欢康奈恢帽徽剂说臅r(shí)候就會(huì)發(fā)生擴(kuò)容。

小白： 阿西吧，還有擴(kuò)容，那這個(gè)擴(kuò)容是咋回事呢?

哈希表的擴(kuò)容

慶哥： 其實(shí)這里不僅僅是因?yàn)槟阏f的那種情況才會(huì)擴(kuò)容，還有一個(gè)很重要的原因就是當(dāng)哈希表被占的位置比較多的時(shí)候，出現(xiàn)哈希沖突的概率也就變高了，所以很有必要進(jìn)行擴(kuò)容。

那么這個(gè)擴(kuò)容是怎么擴(kuò)的呢?這里一般會(huì)有一個(gè)增長因子的概念，也叫作負(fù)載因子，簡單點(diǎn)說就是已經(jīng)被占的位置與總位置的一個(gè)百分比，比如一共十個(gè)位置，現(xiàn)在已經(jīng)占了七個(gè)位置，就觸發(fā)了擴(kuò)容機(jī)制，因?yàn)樗脑鲩L因子是0.7，也就是達(dá)到了總位置的百分之七十就需要擴(kuò)容。

還拿HashMap來說，當(dāng)它當(dāng)前的容量占總?cè)萘康陌俜种呤宓臅r(shí)候就需要擴(kuò)容了。

而且這個(gè)擴(kuò)容也不是簡單的把數(shù)組擴(kuò)大，而是新創(chuàng)建一個(gè)數(shù)組是原來的2倍，然后把原數(shù)組的所有Entry都重新Hash一遍放到新的數(shù)組。

小白： 這個(gè)重新Hash一遍是啥意思啊?

慶哥： 因?yàn)閿?shù)組擴(kuò)大了，所以一般哈希函數(shù)也會(huì)有變化，這里的Hash也就是把之前的數(shù)據(jù)通過新的哈希函數(shù)計(jì)算出新的位置來存放。

小白： 嗯嗯，原來是這么回事啊，懂了，對(duì)了，那哈希表的數(shù)據(jù)讀取怎么操作的啊?

哈希表如何讀取數(shù)據(jù)

慶哥： 要知道這個(gè)讀取操作，我們還來看這個(gè)圖：

比如我們現(xiàn)在要通過學(xué)號(hào)102011來查找學(xué)生的姓名，怎么操作呢?我們首先通過學(xué)號(hào)利用哈希函數(shù)得出位置1，然后我們就去位置1拿數(shù)據(jù)啊，拿到這個(gè)Entry之后我們得看看這個(gè)Entry的key是不是我們的學(xué)號(hào)102011，一看是101011，什么鬼，一邊去，這不是我們要的key啊，然后根據(jù)這個(gè)Entry的next知道下一給位置，在比較key，好成功找到李四。

小白： 哦哦，原來是這么回事啊，那對(duì)于開放尋址那種是不是也是這個(gè)思路，先確定到這個(gè)位置，然后再看這個(gè)位置上的key是不是我們要的，如過不是那就看看下一個(gè)位置的。

慶哥： 可以的，完全正確，好了現(xiàn)在我們對(duì)哈希表的講解已經(jīng)差不多了，那么你覺得對(duì)于哈希表而言，什么是核心呢?

哈希函數(shù)是核心

小白： 我覺得應(yīng)該是哈希函數(shù)吧，經(jīng)過上面的講解，我覺得，如果一個(gè)哈希函數(shù)設(shè)計(jì)的足夠好的話，就會(huì)減少哈希沖突的概率，如果設(shè)計(jì)的不好，那就會(huì)經(jīng)常撞衫😂，那就很影響性能了，比如剛開始我們舉的那個(gè)例子，拿姓名的首字母來確定位置，這個(gè)哈希函數(shù)的設(shè)計(jì)就不咋滴，比如王二，王三，王四什么的，這都會(huì)沖突啊😂

慶哥： 的確，在哈希表中，哈希函數(shù)的設(shè)計(jì)很重要，一個(gè)好的哈希函數(shù)可以極大的提升性能，而且如果你的哈希函數(shù)設(shè)計(jì)的比較簡單粗陋，那很容易被那些不懷好意的人搗亂，比如知道了你哈希函數(shù)的規(guī)則，故意制造容易沖突的key值，那就有意思了，你的哈希表就會(huì)一直撞啊，一直撞啊😂

小白： 哈哈😂，那設(shè)計(jì)哈希函數(shù)有什么方法嗎?

慶哥： 必須有啊，比如有直接定址法，數(shù)字分析法，折疊法，隨機(jī)數(shù)法和除留余數(shù)法等等，要不要繼續(xù)講啊😀

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