今天聊聊「哈希表」，「哈希表」主要作用在于高效查找。

在編程實(shí)現(xiàn)中，常常面臨著兩個(gè)問題：存儲(chǔ)和查找，存儲(chǔ)和查找的效率往往決定了整個(gè)程序的效率。

腦補(bǔ)下，你在家里忘記了指甲刀放在哪里，通常要在你家所有抽屜中順序?qū)ふ?，直到找到，最差情況下，有N個(gè)抽屜，你就要打開N個(gè)抽屜。這種存儲(chǔ)方式叫數(shù)組，查找方法稱為「遍歷」。

腦補(bǔ)下，你是一個(gè)整理控，所有物品必須分門別類放入整理箱，再將整理箱編號(hào)，比如1號(hào)放入針線，2號(hào)放入證件，3號(hào)放入細(xì)軟。這種存儲(chǔ)和查找方式稱為「哈?！?，如果這個(gè)時(shí)候要查找護(hù)照，你不許要再翻所有抽屜，直接可在2號(hào)整理箱中獲取，通常只用一次查找即可，如何編號(hào)整理箱，稱為哈希算法。

同樣是查找，差距怎么那么大涅~，假設(shè)我們有100億條數(shù)據(jù)記錄，那差距就變得明顯，遍歷需要查找最多100億次，最少1次，哈希只需1次。

讓我們正式介紹哈希和哈希算法，哈希也稱散列，哈希表是一種與數(shù)組、鏈表等不同的數(shù)據(jù)結(jié)構(gòu)，與他們需要不斷的遍歷比較來查找的辦法，哈希表設(shè)計(jì)了一個(gè)映射關(guān)系f(key)= address，根據(jù)key來計(jì)算存儲(chǔ)地址address，這樣可以1次查找，f既是存儲(chǔ)數(shù)據(jù)過程中用來指引數(shù)據(jù)存儲(chǔ)到什么位置的函數(shù)，也是將來查找這個(gè)位置的算法，叫做哈希算法。

讓我們舉個(gè)例子，比如下面這幾個(gè)人物，按數(shù)組存儲(chǔ)：

這樣我要找到大胸姐的電話號(hào)碼，需要順序查找對(duì)比整個(gè)數(shù)組，第一個(gè)余罪，不是，第二個(gè)不是，第三個(gè)不是，直到第四個(gè)找到大胸姐。

如果以hash存儲(chǔ)呢？首先讓我們來看看如何設(shè)計(jì)哈希算法，哈希算法可以隨意設(shè)計(jì)，教科書上一般會(huì)說以下幾種方法：直接定址發(fā)，平方取中法，除數(shù)取余法，哈希算法的本質(zhì)上是計(jì)算一個(gè)數(shù)字，如果用這幾種方法講解會(huì)稍顯晦澀，我們假設(shè)我們的哈希算法是取姓名的首字母。所以f（余罪） = y， f(傅老大) = f，f(沈嘉文) = s，f(大胸姐) = d。

構(gòu)建的hash表如下：

我們看到他們分別以姓名首字母的位置插入到這一張表格中，這樣我們構(gòu)建了這樣一個(gè)Key-Value表格，此表就是哈希表，也稱為Hash Table。未來，當(dāng)我們要查找余罪的時(shí)候，通過計(jì)算，余罪在y位置，可以通過1次查找，找到這條記錄，也即手機(jī)號(hào)。

這個(gè)時(shí)候有客官問了，那以首字母為哈希函數(shù)的話，應(yīng)該有很多比如以y的姓名啊，這個(gè)時(shí)候就不是一次查找了吧，其實(shí)有很多條記錄都映射到一個(gè)位置上，稱為哈希沖突。

哈希沖突是跟哈希函數(shù)的設(shè)計(jì)正相關(guān)的，你的隨機(jī)性越大，那么產(chǎn)生哈希沖突的可能性越小，在小概率下，如果還有沖突怎么辦，這個(gè)時(shí)候要做些有損的設(shè)計(jì)，比如如果有兩個(gè)首字母為y的姓名，那么可以接到余罪的后面，當(dāng)查找的時(shí)候，需要先查找到y(tǒng)，然后再順序查找，如圖所示：

還有一些解決哈希沖突的辦法叫「哈希再哈希」，也就是針對(duì)第一次哈希的結(jié)果再進(jìn)行一次hash來減小沖突的概率。

這就是Hash表，首先Ta是一種數(shù)據(jù)結(jié)構(gòu)，是一種效率極高的查找方式，哈希表的核心在于哈希函數(shù)的設(shè)計(jì)，哈希沖突了不要緊，我們要增加隨機(jī)性以及對(duì)沖突進(jìn)行適當(dāng)?shù)挠袚p化的處理。

#專欄作家#

給產(chǎn)品經(jīng)理講技術(shù)，微信公眾號(hào)（pm_teacher），人人都是產(chǎn)品經(jīng)理專欄作家。資深程序猿，專注客戶端開發(fā)若干年，對(duì)前端、后臺(tái)技術(shù)略懂，熱衷于對(duì)新的科技領(lǐng)域的探索。

本文原創(chuàng)發(fā)布于人人都是產(chǎn)品經(jīng)理。未經(jīng)許可，禁止轉(zhuǎn)載。

題圖來自PEXELS，基于CC0協(xié)議