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