圖文詳解：7000 字哈希表總結(jié)
今天我們來(lái)說(shuō)一種新的數(shù)據(jù)結(jié)構(gòu)散列（哈希）表，散列是應(yīng)用非常廣泛的數(shù)據(jù)結(jié)構(gòu)，在我們的刷題過(guò)程中，散列表的出場(chǎng)率特別高。所以我們快來(lái)一起把散列表的內(nèi)些事給整明白吧，文章框架如下。
說(shuō)散列表之前，我們先設(shè)想以下場(chǎng)景。
袁廚穿越回了古代，憑借從現(xiàn)代學(xué)習(xí)的做飯手藝，開(kāi)了一個(gè)袁記菜館，正值開(kāi)業(yè)初期，店里生意十分火爆，但是顧客結(jié)賬時(shí)就犯難了，由于菜品太多，每當(dāng)結(jié)賬時(shí)，老板娘總是按照菜單一個(gè)一個(gè)找價(jià)格（遍歷查找），每次都要找半天，所以結(jié)賬的地方總是排起長(zhǎng)隊(duì)，顧客們表示用戶(hù)體驗(yàn)很差。袁廚一想這不是辦法啊，太浪費(fèi)大家時(shí)間了，所以袁廚就先把菜單按照首字母排序（二分查找），然后查找的時(shí)候根據(jù)首字母查找，這樣結(jié)賬的時(shí)候就能大大提高檢索效率啦！但是呢？工作日顧客不多，老板娘完全應(yīng)付的過(guò)來(lái)，但是每逢節(jié)假日，還是會(huì)排起長(zhǎng)隊(duì)。那么有沒(méi)有什么更好的辦法呢？對(duì)呀！我們把所有的價(jià)格都背下來(lái)不就可以了嗎？每個(gè)菜的價(jià)格我們都了如指掌，結(jié)賬的時(shí)候我們只需把每道菜的價(jià)格相加即可。所以袁廚和老板娘加班加點(diǎn)的進(jìn)行背誦。下次再結(jié)賬的時(shí)候一說(shuō)吃了什么菜，我們立馬就知道價(jià)格啦。自此以后收銀臺(tái)再也沒(méi)有出現(xiàn)過(guò)長(zhǎng)隊(duì)啦，袁記菜館開(kāi)著開(kāi)著一不小心就成了天下第一飯店。
下面我們來(lái)看一下袁記菜館老板娘進(jìn)化史。
散列表查找步驟
散列表，最有用的基本數(shù)據(jù)結(jié)構(gòu)之一。是根據(jù)關(guān)鍵碼的值直接進(jìn)行訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)，散列表的實(shí)現(xiàn)常常叫做散列（hasing）。散列是一種用于以常數(shù)平均時(shí)間執(zhí)行插入、刪除和查找的技術(shù)，下面我們來(lái)看一下散列過(guò)程。
我們的整個(gè)散列過(guò)程主要分為兩步
（1）通過(guò)散列函數(shù)計(jì)算記錄的散列地址，并按此散列地址存儲(chǔ)該記錄。就好比麻辣魚(yú)，我們就讓它在川菜區(qū)，糖醋魚(yú)，我們就讓它在魯菜區(qū)。但是我們需要注意的是，無(wú)論什么記錄我們都需要用同一個(gè)散列函數(shù)計(jì)算地址，然后再存儲(chǔ)。
（2)當(dāng)我們查找時(shí)，我們通過(guò)同樣的散列函數(shù)計(jì)算記錄的散列地址，按此散列地址訪問(wèn)該記錄。因?yàn)槲覀兇婧腿〉臅r(shí)候用的都是一個(gè)散列函數(shù)，因此結(jié)果肯定相同。
剛才我們?cè)谏⒘羞^(guò)程中提到了散列函數(shù)，那么散列函數(shù)是什么呢？
我們假設(shè)某個(gè)函數(shù)為 f，使得 存儲(chǔ)位置 = f (key) 那樣我們就能通過(guò)查找關(guān)鍵字不需要比較就可獲得需要的記錄的存儲(chǔ)位置。這種存儲(chǔ)技術(shù)被稱(chēng)為散列技術(shù)。散列技術(shù)是在通過(guò)記錄的存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系 f ,使得每個(gè)關(guān)鍵字 key 都對(duì)應(yīng)一個(gè)存儲(chǔ)位置 f(key)。見(jiàn)下圖
這里的 f 就是我們所說(shuō)的散列函數(shù)（哈希）函數(shù)。我們利用散列技術(shù)將記錄存儲(chǔ)在一塊連續(xù)的存儲(chǔ)空間中，這塊連續(xù)存儲(chǔ)空間就是我們本文的主人公------散列(哈希)
上圖為我們描述了用散列函數(shù)將關(guān)鍵字映射到散列表，但是大家有沒(méi)有考慮到這種情況，那就是將關(guān)鍵字映射到同一個(gè)槽中的情況，即 f(k4) = f(k3) 時(shí)。這種情況我們將其稱(chēng)之為沖突，k3 和 k4 則被稱(chēng)之為散列函數(shù) f 的同義詞，如果產(chǎn)生這種情況，則會(huì)讓我們查找錯(cuò)誤。幸運(yùn)的是我們能找到有效的方法解決沖突。
首先我們可以對(duì)哈希函數(shù)下手，我們可以精心設(shè)計(jì)哈希函數(shù)，讓其盡可能少的產(chǎn)生沖突，所以我們創(chuàng)建哈希函數(shù)時(shí)應(yīng)遵循以下規(guī)則
（1）必須是一致的，假設(shè)你輸入辣子雞丁時(shí)得到的是在看，那么每次輸入辣子雞丁時(shí)，得到的也必須為在看。如果不是這樣，散列表將毫無(wú)用處。
（2）計(jì)算簡(jiǎn)單，假設(shè)我們?cè)O(shè)計(jì)了一個(gè)算法，可以保證所有關(guān)鍵字都不會(huì)沖突，但是這個(gè)算法計(jì)算復(fù)雜，會(huì)耗費(fèi)很多時(shí)間，這樣的話就大大降低了查找效率，反而得不償失。所以咱們散列函數(shù)的計(jì)算時(shí)間不應(yīng)該超過(guò)其他查找技術(shù)與關(guān)鍵字的比較時(shí)間，不然的話我們干嘛不使用其他查找技術(shù)呢?
（3）散列地址分布均勻我們剛才說(shuō)了沖突的帶來(lái)的問(wèn)題，所以我們最好的辦法就是讓散列地址盡量均勻分布在存儲(chǔ)空間中，這樣即保證空間的有效利用，又減少了處理沖突而消耗的時(shí)間。
現(xiàn)在我們已經(jīng)對(duì)散列表，散列函數(shù)等知識(shí)有所了解啦，那么我們來(lái)看幾種常用的散列函數(shù)構(gòu)造方法。這些方法的共同點(diǎn)為都是將原來(lái)的數(shù)字按某種規(guī)律變成了另一個(gè)數(shù)字。所以是很容易理解的。
散列函數(shù)構(gòu)造方法
直接定址法
如果我們對(duì)盈利為0-9的菜品設(shè)計(jì)哈希表，我們則直接可以根據(jù)作為地址，則 f(key) = key;
即下面這種情況。
有沒(méi)有感覺(jué)上面的圖很熟悉，沒(méi)錯(cuò)我們經(jīng)常用的數(shù)組其實(shí)就是一張哈希表，關(guān)鍵碼就是數(shù)組的索引下標(biāo)，然后我們通過(guò)下標(biāo)直接訪問(wèn)數(shù)組中的元素。
另外我們假設(shè)每道菜的成本為50塊，那我們還可以根據(jù)盈利+成本來(lái)作為地址，那么則 f(key) = key + 50。也就是說(shuō)我們可以根據(jù)線性函數(shù)值作為散列地址。
f(key) = a * key + b a,b均為常數(shù)
優(yōu)點(diǎn)：簡(jiǎn)單、均勻、無(wú)沖突。
應(yīng)用場(chǎng)景：需要事先知道關(guān)鍵字的分布情況，適合查找表較小且連續(xù)的情況
數(shù)字分析法
該方法也是十分簡(jiǎn)單的方法，就是分析我們的關(guān)鍵字，取其中一段，或?qū)ζ湮灰?，疊加，用作地址。比如我們的學(xué)號(hào)，前 6 位都是一樣的，但是后面 3 位都不相同，我們則可以用學(xué)號(hào)作為鍵，后面的 3 位做為我們的散列地址。如果我們這樣還是容易產(chǎn)生沖突，則可以對(duì)抽取數(shù)字再進(jìn)行處理。我們的目的只有一個(gè)，提供一個(gè)散列函數(shù)將關(guān)鍵字合理的分配到散列表的各位置。這里我們提到了一種新的方式抽取，這也是在散列函數(shù)中經(jīng)常用到的手段。
優(yōu)點(diǎn)：簡(jiǎn)單、均勻、適用于關(guān)鍵字位數(shù)較大的情況
應(yīng)用場(chǎng)景：關(guān)鍵字位數(shù)較大，知道關(guān)鍵字分布情況且關(guān)鍵字的若干位較均勻
折疊法
其實(shí)這個(gè)方法也很簡(jiǎn)單，也是處理我們的關(guān)鍵字然后用作我們的散列地址，主要思路是將關(guān)鍵字從左到右分割成位數(shù)相等的幾部分，然后疊加求和，并按散列表表長(zhǎng)，取后幾位作為散列地址。
比如我們的關(guān)鍵字是123456789，則我們分為三部分 123 ，456 ，789 然后將其相加得 1368 然后我們?cè)偃∑浜笕?368 作為我們的散列地址。
優(yōu)點(diǎn)：事先不需要知道關(guān)鍵字情況
應(yīng)用場(chǎng)景：適合關(guān)鍵字位數(shù)較多的情況
除法散列法
在用來(lái)設(shè)計(jì)散列函數(shù)的除法散列法中，通過(guò)取 key 除以 p 的余數(shù)，將關(guān)鍵字映射到 p 個(gè)槽中的某一個(gè)上，對(duì)于散列表長(zhǎng)度為 m 的散列函數(shù)公式為
f(k) = k mod p (p <= m)
例如，如果散列表長(zhǎng)度為 12，即 m = 12 ，我們的參數(shù) p 也設(shè)為12，那 k = 100時(shí) f(k) = 100 % 12 = 4
由于只需要做一次除法操作，所以除法散列法是非?？斓?。
由上面的公式可以看出，該方法的重點(diǎn)在于 p 的取值，如果 p 值選的不好，就可能會(huì)容易產(chǎn)生同義詞。見(jiàn)下面這種情況。我們哈希表長(zhǎng)度為6，我們選擇6為p值，則有可能產(chǎn)生這種情況，所有關(guān)鍵字都得到了0這個(gè)地址數(shù)。
那我們?cè)谶x用除法散列法時(shí)選取 p 值時(shí)應(yīng)該遵循怎樣的規(guī)則呢？
m 不應(yīng)為 2 的冪，因?yàn)槿绻?m = 2^p ，則 f(k) 就是 k 的 p 個(gè)最低位數(shù)字。例 12 % 8 = 4 ，12的二進(jìn)制表示位1100，后三位為100。
若散列表長(zhǎng)為 m ,通常 p 為 小于或等于表長(zhǎng)（最好接近m）的最小質(zhì)數(shù)或不包含小于 20 質(zhì)因子的合數(shù)。
合數(shù)：合數(shù)是指在大于1的整數(shù)中除了能被1和本身整除外，還能被其他數(shù)（0除外）整除的數(shù)。
質(zhì)因子：質(zhì)因子（或質(zhì)因數(shù)）在數(shù)論里是指能整除給定正整數(shù)的質(zhì)數(shù)。
注：這里的2，3，5為質(zhì)因子
還是上面的例子，我們根據(jù)規(guī)則選擇 5 為 p 值，我們?cè)賮?lái)看。這時(shí)我們發(fā)現(xiàn)只有 6 和 36 沖突，相對(duì)來(lái)說(shuō)就好了很多。
優(yōu)點(diǎn)：計(jì)算效率高，靈活
應(yīng)用場(chǎng)景：不知道關(guān)鍵字分布情況
乘法散列法
構(gòu)造散列函數(shù)的乘法散列法主要包含兩個(gè)步驟
用關(guān)鍵字 k 乘上常數(shù) A(0 < A < 1)，并提取 k A 的小數(shù)部分
用 m 乘以這個(gè)值，再向下取整
散列函數(shù)為
f (k) = ? m(kA mod 1) ?
這里的 kA mod 1 的含義是取 keyA 的小數(shù)部分，即 kA - ?kA? 。
優(yōu)點(diǎn)：對(duì) m 的選擇不是特別關(guān)鍵一般選擇它為 2 的某個(gè)冪次（m = 2 ^ p ,p為某個(gè)整數(shù)）
應(yīng)用場(chǎng)景：不知道關(guān)鍵字情況
平方取中法
這個(gè)方法就比較簡(jiǎn)單了，假設(shè)關(guān)鍵字是 321，那么他的平方就是 103041，再抽取中間的 3 位就是 030 或 304 用作散列地址。再比如關(guān)鍵字是 1234 那么它的平方就是 1522756 ，抽取中間 3 位就是 227 用作散列地址.
優(yōu)點(diǎn)：靈活，適用范圍廣泛
適用場(chǎng)景：不知道關(guān)鍵字分布，而位數(shù)又不是很大的情況。
隨機(jī)數(shù)法
故名思意，取關(guān)鍵字的隨機(jī)函數(shù)值為它的散列地址。也就是 f(key) = random(key)。這里的random是隨機(jī)函數(shù)。（具體解析見(jiàn)隨機(jī)探測(cè)法）
適用場(chǎng)景：關(guān)鍵字的長(zhǎng)度不等時(shí)
上面我們的例子都是通過(guò)數(shù)字進(jìn)行舉例，那么如果是字符串可不可以作為鍵呢？當(dāng)然也是可以的，各種各樣的符號(hào)我們都可以轉(zhuǎn)換成某種數(shù)字來(lái)對(duì)待，比如我們經(jīng)常接觸的ASCII 碼，所以是同樣適用的。
以上就是常用的散列函數(shù)構(gòu)造方法，其實(shí)他們的中心思想是一致的，將關(guān)鍵字經(jīng)過(guò)加工處理之后變成另外一個(gè)數(shù)字，而這個(gè)數(shù)字就是我們的存儲(chǔ)位置，是不是有一種間諜傳遞情報(bào)的感覺(jué)。
一個(gè)好的哈希函數(shù)可以幫助我們盡可能少的產(chǎn)生沖突，但是也不能完全避免產(chǎn)生沖突，那么遇到?jīng)_突時(shí)應(yīng)該怎么做呢？下面給大家?guī)?lái)幾種常用的處理散列沖突的方法。
處理散列沖突的方法
我們?cè)谑褂?hash 函數(shù)之后發(fā)現(xiàn)關(guān)鍵字 key1 不等于 key2 ，但是 f(key1) = f(key2)，即有沖突，那么該怎么辦呢？不急我們慢慢往下看。
開(kāi)放地址法
了解開(kāi)放地址法之前我們先設(shè)想以下場(chǎng)景。
袁記菜館內(nèi)，鈴鈴鈴，鈴鈴鈴 電話鈴響了
大鵬：老袁，給我訂個(gè)包間，我今天要去帶幾個(gè)客戶(hù)去你那談生意。
袁廚：大鵬啊，你常用的那個(gè)包間被人訂走啦。
大鵬：老袁你這不仗義呀，咋沒(méi)給我留住呀，那你給我找個(gè)空房間吧。
袁廚：好滴老哥
哦，穿越回古代就沒(méi)有電話啦，那看來(lái)穿越的時(shí)候得帶著幾個(gè)手機(jī)了。
上面的場(chǎng)景其實(shí)就是一種處理沖突的方法-----開(kāi)放地址法
開(kāi)放地址法就是一旦發(fā)生沖突，就去尋找下一個(gè)空的散列地址，只要列表足夠大，空的散列地址總能找到，并將記錄存入，為了使用開(kāi)放尋址法插入一個(gè)元素，需要連續(xù)地檢查散列表，或稱(chēng)為探查，我們常用的有線性探測(cè)，二次探測(cè)，隨機(jī)探測(cè)。
線性探測(cè)法
下面我們先來(lái)看一下線性探測(cè)，公式：
我們來(lái)看一個(gè)例子，我們的關(guān)鍵字集合為{12，67，56，16，25，37，22，29，15，47，48，21}，表長(zhǎng)為12，我們?cè)儆蒙⒘泻瘮?shù) f(key) = key mod 12。
我們求出每個(gè) key 的 f(key)見(jiàn)下表
我們查看上表發(fā)現(xiàn)，前五位的 f(key) 都不相同，即沒(méi)有沖突，可以直接存入，但是到了第六位 f(37) = f(25) = 1,那我們就需要利用上面的公式 f(37) = f (f(37) + 1 ) mod 12 = 2，這其實(shí)就是我們的訂包間的做法。下面我們看一下將上面的所有數(shù)存入哈希表是什么情況吧。
注：藍(lán)色為計(jì)算哈希值，紅色為存入哈希表
我們把這種解決沖突的開(kāi)放地址法稱(chēng)為線性探測(cè)法。下面我們通過(guò)視頻來(lái)模擬一下線性探測(cè)法的存儲(chǔ)過(guò)程。
另外我們?cè)诮鉀Q沖突的時(shí)候，會(huì)遇到 48 和 37 雖然不是同義詞，卻爭(zhēng)奪一個(gè)地址的情況，我們稱(chēng)其為堆積。因?yàn)槎逊e使得我們需要不斷的處理沖突，插入和查找效率都會(huì)大大降低。
通過(guò)上面的視頻我們應(yīng)該了解了線性探測(cè)的執(zhí)行過(guò)程了，那么我們考慮一下這種情況，若是我們的最后一位不為21，為 34 時(shí)會(huì)有什么事情發(fā)生呢？
此時(shí)他第一次會(huì)落在下標(biāo)為 10 的位置，那么如果繼續(xù)使用線性探測(cè)的話，則需要通過(guò)不斷取余后得到結(jié)果，數(shù)據(jù)量小還好，要是很大的話那也太慢了吧，但是明明他的前面就有一個(gè)空房間呀，如果向前移動(dòng)只需移動(dòng)一次即可。不要著急，前輩們已經(jīng)幫我們想好了解決方法
二次探測(cè)法
其實(shí)理解了我們的上個(gè)例子之后，這個(gè)一下就能整明白了，根本不用費(fèi)腦子，這個(gè)方法就是更改了一下di的取值
注：這里的是 -1^2 為負(fù)值 而不是 （-1)^2
所以對(duì)于我們的34來(lái)說(shuō)，當(dāng)di = -1時(shí)，就可以找到空位置了。
二次探測(cè)法的目的就是為了不讓關(guān)鍵字聚集在某一塊區(qū)域。另外還有一種有趣的方法，位移量采用隨機(jī)函數(shù)計(jì)算得到，接著往下看吧.
隨機(jī)探測(cè)法
大家看到這是不又有新問(wèn)題了，剛才我們?cè)谏⒘泻瘮?shù)構(gòu)造規(guī)則的第一條中說(shuō)
（1）必須是一致的，假設(shè)你輸入辣子雞丁時(shí)得到的是在看，那么每次輸入辣子雞丁時(shí)，得到的也必須為在看。如果不是這樣，散列表將毫無(wú)用處。
咦？怎么又是在看哈哈，那么問(wèn)題來(lái)了，我們使用隨機(jī)數(shù)作為他的偏移量，那么我們查找的時(shí)候豈不是查不到了？因?yàn)槲覀?di 是隨機(jī)生成的呀，這里的隨機(jī)其實(shí)是偽隨機(jī)數(shù)，偽隨機(jī)數(shù)含義為，我們?cè)O(shè)置隨機(jī)種子相同，則不斷調(diào)用隨機(jī)函數(shù)可以生成不會(huì)重復(fù)的數(shù)列，我們?cè)诓檎視r(shí)，用同樣的隨機(jī)種子，它每次得到的數(shù)列是相同的，那么相同的 di 就能得到相同的散列地址。
隨機(jī)種子（Random Seed）是計(jì)算機(jī)專(zhuān)業(yè)術(shù)語(yǔ)，一種以隨機(jī)數(shù)作為對(duì)象的以真隨機(jī)數(shù)（種子）為初始條件的隨機(jī)數(shù)。一般計(jì)算機(jī)的隨機(jī)數(shù)都是偽隨機(jī)數(shù)，以一個(gè)真隨機(jī)數(shù)（種子）作為初始條件，然后用一定的算法不停迭代產(chǎn)生隨機(jī)數(shù)
通過(guò)上面的測(cè)試是不是一下就秒懂啦，使用相同的隨機(jī)種子，生成的數(shù)列是相同的。所以為什么我們可以使用隨機(jī)數(shù)作為它的偏移量。
下面我們?cè)賮?lái)看一下其他的函數(shù)處理散列沖突的方法
再哈希法
這個(gè)方法其實(shí)也特別簡(jiǎn)單，利用不同的哈希函數(shù)再求得一個(gè)哈希地址，直到不出現(xiàn)沖突為止。
f,(key) = RH,( key ) (i = 1,2,3,4…..k)
這里的RH,就是不同的散列函數(shù)，你可以把我們之前說(shuō)過(guò)的那些散列函數(shù)都用上，每當(dāng)發(fā)生沖突時(shí)就換一個(gè)散列函數(shù)，相信總有一個(gè)能夠解決沖突的。這種方法能使關(guān)鍵字不產(chǎn)生聚集，但是代價(jià)就是增加了計(jì)算時(shí)間。是不是很簡(jiǎn)單啊。
鏈地址法
下面我們?cè)僭O(shè)想以下情景。
袁記菜館內(nèi)，鈴鈴鈴，鈴鈴鈴電話鈴又響了，那個(gè)大鵬又來(lái)訂房間了。
大鵬：老袁啊，我一會(huì)去你那吃個(gè)飯，還是上回那個(gè)包間
袁廚：大鵬你下回能不能早點(diǎn)說(shuō)啊，又沒(méi)人訂走了，這回是老王訂的
大鵬：老王這個(gè)老東西啊，反正也是熟人，你再給我整個(gè)桌子，我拼在他后面吧
不好意思啊各位同學(xué)，信鴿最近太貴了還沒(méi)來(lái)得及買(mǎi)。上面的情景就是模擬我們的新的處理沖突的方法鏈地址法。
上面我們都是遇到?jīng)_突之后，就換地方。那么我們有沒(méi)有不換地方的辦法呢？那就是我們現(xiàn)在說(shuō)的鏈地址法。
還記得我們說(shuō)過(guò)的同義詞嗎？就是 key 不同 f(key) 相同的情況，我們將這些同義詞存儲(chǔ)在一個(gè)單鏈表中，這種表叫做同義詞子表，散列表中只存儲(chǔ)同義詞子表的頭指針。我們還是用剛才的例子，關(guān)鍵字集合為{12，67，56，16，25，37，22，29，15，47，48，21}，表長(zhǎng)為12，我們?cè)儆蒙⒘泻瘮?shù) f(key) = key mod 12。我們用了鏈地址法之后就再也不存在沖突了，無(wú)論有多少?zèng)_突，我們只需在同義詞子表中添加結(jié)點(diǎn)即可。下面我們看下鏈地址法的存儲(chǔ)情況。
鏈地址法雖然能夠不產(chǎn)生沖突，但是也帶來(lái)了查找時(shí)需要遍歷單鏈表的性能消耗，有得必有失嘛。
公共溢出區(qū)法
下面我們?cè)賮?lái)看一種新的方法，這回大鵬又要來(lái)吃飯了。
袁記菜館內(nèi)…..
袁廚：呦，這是什么風(fēng)把你給刮來(lái)了，咋沒(méi)開(kāi)你的大奔啊。
大鵬：哎呀媽呀，別那么多廢話了，我快餓死了，你快給我找個(gè)位置，我要吃點(diǎn)飯。
袁廚：你來(lái)的，太不巧了，咱們的店已經(jīng)滿了，你先去旁邊的小屋看會(huì)電視，等有空了我再叫你。小屋里面還有幾個(gè)和你一樣來(lái)晚的，你們一起看吧。
大鵬：電視？看電視？
上面的情景就是模擬我們的公共溢出區(qū)法，這也是很好理解的，你不是沖突嗎？那沖突的各位我先給你安排個(gè)地方呆著，這樣你就有地方住了。我們?yōu)樗袥_突的關(guān)鍵字建立了一個(gè)公共的溢出區(qū)來(lái)存放。
那么我們?cè)趺催M(jìn)行查找呢？我們首先通過(guò)散列函數(shù)計(jì)算出散列地址后，先于基本表對(duì)比，如果不相等再到溢出表去順序查找。這種解決沖突的方法，對(duì)于沖突很少的情況性能還是非常高的。
散列表查找算法(線性探測(cè)法)
下面我們來(lái)看一下散列表查找算法的實(shí)現(xiàn)
首先需要定義散列列表的結(jié)構(gòu)以及一些相關(guān)常數(shù)，其中elem代表散列表數(shù)據(jù)存儲(chǔ)數(shù)組，count代表的是當(dāng)前插入元素個(gè)數(shù)，size代表哈希表容量，NULLKEY散列表初始值，然后我們?nèi)绻檎页晒头祷厮饕绻淮嬖谠撛鼐头祷卦夭淮嬖凇?/span>
我們將哈希表初始化，為數(shù)組元素賦初值。
插入操作的具體步驟：
（1）通過(guò)哈希函數(shù)(除法散列法)，將key轉(zhuǎn)化為數(shù)組下標(biāo)
（2）如果該下標(biāo)中沒(méi)有元素，則插入，否則說(shuō)明有沖突，則利用線性探測(cè)法處理沖突。詳細(xì)步驟見(jiàn)注釋
查找操作的具體步驟：
（1）通過(guò)哈希函數(shù)（同插入時(shí)一樣），將key轉(zhuǎn)化成數(shù)組下標(biāo)
（2）通過(guò)數(shù)組下標(biāo)找到key值，如果key一致，則查找成功，否則利用線性探測(cè)法繼續(xù)查找。
下面我們來(lái)看一下完整代碼
散列表性能分析
如果沒(méi)有沖突的話，散列查找是我們查找中效率最高的，時(shí)間復(fù)雜度為O(1),但是沒(méi)有沖突的情況是一種理想情況，那么散列查找的平均查找長(zhǎng)度取決于哪些方面呢？
1.散列函數(shù)是否均勻
我們?cè)谏衔恼f(shuō)到，可以通過(guò)設(shè)計(jì)散列函數(shù)減少?zèng)_突，但是由于不同的散列函數(shù)對(duì)一組關(guān)鍵字產(chǎn)生沖突可能性是相同的，因此我們可以不考慮它對(duì)平均查找長(zhǎng)度的影響。
2.處理沖突的方法
相同關(guān)鍵字，相同散列函數(shù)，不同處理沖突方式，會(huì)使平均查找長(zhǎng)度不同，比如我們線性探測(cè)有時(shí)會(huì)堆積，則不如二次探測(cè)法好，因?yàn)殒湹刂贩ㄌ幚頉_突時(shí)不會(huì)產(chǎn)生任何堆積，因而具有最佳的平均查找性能
3.散列表的裝填因子
本來(lái)想在上文中提到裝填因子的，但是后來(lái)發(fā)現(xiàn)即使沒(méi)有說(shuō)明也不影響我們對(duì)哈希表的理解，下面我們來(lái)看一下裝填因子的總結(jié)
裝填因子 α = 填入表中的記錄數(shù) / 散列表長(zhǎng)度
散列因子則代表著散列表的裝滿程度，表中記錄越多，α就越大，產(chǎn)生沖突的概率就越大。我們上面提到的例子中 表的長(zhǎng)度為12，填入記錄數(shù)為6，那么此時(shí)的 α = 6 / 12 = 0.5 所以說(shuō)當(dāng)我們的 α 比較大時(shí)再填入元素那么產(chǎn)生沖突的可能性就非常大了。所以說(shuō)散列表的平均查找長(zhǎng)度取決于裝填因子，而不是取決于記錄數(shù)。所以說(shuō)我們需要做的就是選擇一個(gè)合適的裝填因子以便將平均查找長(zhǎng)度限定在一個(gè)范圍之內(nèi)。
到這里咱們的哈希表總結(jié)就結(jié)束了，因?yàn)槲覀兠魈炀烷_(kāi)始哈希表模塊的面試題總結(jié)，所以就寫(xiě)了一篇特別長(zhǎng)的文章來(lái)對(duì)哈希表進(jìn)行總結(jié)，希望能對(duì)初學(xué)數(shù)據(jù)結(jié)構(gòu)的同學(xué)帶來(lái)一點(diǎn)點(diǎn)幫助。
大家快來(lái)打卡哈希表呀！
參考圖書(shū)：
《小灰的算法之旅》、《數(shù)據(jù)結(jié)構(gòu)與算法分析》、《算法導(dǎo)論》、《大話數(shù)據(jù)結(jié)構(gòu)》、《數(shù)據(jù)結(jié)構(gòu)與算法》
推薦閱讀
學(xué)習(xí)更多技能
請(qǐng)點(diǎn)擊下方公眾號(hào)
