麻省理工學(xué)院公開課：算法導(dǎo)論优炬。B站地址粪小，網(wǎng)易公開課也有對應(yīng)的資源气忠。
https://www.bilibili.com/video/av1149902/?p=7
哈希表維基百科的解釋：
https://zh.wikipedia.org/wiki/%E5%93%88%E5%B8%8C%E8%A1%A8
參考：https://hit-alibaba.github.io/interview/basic/algo/Hash-Table.html

哈希表的內(nèi)容比較多，這里花兩個課時來講伐憾，包括下一節(jié)課背亥。

這節(jié)課的主要內(nèi)容是：常用的兩種哈希算法秒际，除法哈希法和乘法哈希法，以及解決碰撞的兩種方法狡汉，鏈接法和開放尋址法娄徊。

引入——符號表問題

哈希是一項強(qiáng)大的技術(shù)，在很多地方都有用到轴猎。這里用一個問題來引入嵌莉，這個問題經(jīng)常出現(xiàn)在編譯器里进萄，即符號表問題捻脖。
有一個表S，里面放著n條記錄中鼠，對于每條記錄可婶，有個指針x，x通常是一個指向?qū)嶋H數(shù)據(jù)的指針援雇，x.key或x->key矛渴。接下來要對這張表上的數(shù)據(jù)進(jìn)行一系列操作：

• 插入：在表內(nèi)插入一條數(shù)據(jù)x，insert(S, x)惫搏，即S <- S ∪ {x}
• 刪除：從表里刪除一條記錄具温，delete(S, x)，即S <- S - {x}筐赔。注：刪除不是刪除鍵值铣猩，是刪除整條記錄。如果想要刪除有特定鍵值的記錄茴丰，即只知道k达皿，不知道x天吓，則需要先進(jìn)行搜索。
• 搜索：用給定的鍵k進(jìn)行搜索峦椰，search(S, k)龄寞，當(dāng)x的鍵值為k時，這個函數(shù)返回x汤功。即key[x] = k物邑，如果沒有相應(yīng)的記錄，返回nil（空值）冤竹。

因為這個集合可以進(jìn)行動態(tài)的插入和刪除拂封，所以也稱為動態(tài)集。即插入和刪除的操作鹦蠕，將集合動態(tài)化了冒签。

直接映射表

直接映射表是一個比較簡單的結(jié)構(gòu)，但不是一直能用钟病，這里會列出它能發(fā)揮作用的情況萧恕。
當(dāng)鍵值的分布比較小的時候，就能發(fā)揮作用肠阱。假設(shè)這些鍵是來自一個有m個元素的集合U票唆，即U = {0,1,2,...,m-1}，并假設(shè)這些鍵相互獨立屹徘。

直接映射表是如何工作的走趋？
建立一個數(shù)組T = [0,1,2,...m-1]表示動態(tài)集合S。
T[k] = x噪伊，if x∈S 以及 key[x] = k
T[k] = nil簿煌，else

首先，插入是把相應(yīng)位置的值設(shè)置成要插入的值鉴吹，刪除是直接移除該位置的值姨伟，搜索是直接通過索引來查看槽的內(nèi)容。所有的這些操作豆励，在最壞情況下的時間復(fù)雜度為Θ(1)夺荒。
但在實際中，能用到直接映射表的情況非常少良蒸。主要局限性在于：
if (m-1)是一個非常大的值技扼。假設(shè)這些鍵是取自字符串，比如人名嫩痰，那么表內(nèi)就會有大量的空槽剿吻，遠(yuǎn)超出我們需要保存的數(shù)據(jù)量。我們所希望的是在保存東西之余始赎，還能讓表的規(guī)模盡可能地小和橙，同時還能保留某些特性仔燕。這就需要哈希表了。

哈希表

定義：所謂的哈希法魔招，就是用一個哈希函數(shù)H來“隨機(jī)”映射那些鍵（不是完全的隨機(jī)）晰搀。這種情況下，數(shù)組的索引稱為槽（slots）办斑。

我們可能有一個很大的鍵的全域外恕，稱之為U。有一個由我們建立的有m個槽的表乡翅。U內(nèi)有一個集合S鳞疲，是U內(nèi)很小的一塊。我們要做的就是從S中取出一個鍵蠕蚜，映射到哈希表的某個位置尚洽，然后再取另外一個鍵（把這個鍵代入哈希函數(shù)，函數(shù)會返回給我們一個特定的槽）靶累，映射到哈希表的某個槽里腺毫。最后我們將鍵分布到了整個表里。

但是映射的過程也不是那么順利挣柬，總會碰到一些問題潮酒。比如S中兩個不同的鍵映射到同一個槽里，即碰撞邪蛔。
碰撞：當(dāng)一個記錄要插入到映射表時急黎，卻被映射到一個早已有記錄的槽時，碰撞發(fā)生了侧到。

該如何解決碰撞的問題呢勃教？
不能丟棄任何數(shù)據(jù)，也不能把它當(dāng)成緩存床牧，雖然緩存用的也是哈希結(jié)構(gòu)荣回。

鏈接法解決碰撞

為每個槽創(chuàng)建一個鏈表遭贸，把所有映射到這個槽的元素戈咳，都存到這個槽的鏈表里去。這就是用來解決碰撞的鏈接法壕吹。即把相同的哈希值的記錄放到一個鏈表里儲存著蛙。
例子：
h(49) = h(86) = h(52) = i

最壞情況分析：
所有鍵哈希映射到同一個槽，一直在進(jìn)行碰撞耳贬，最后變成了鏈表踏堡。在里面查找某個鍵值的元素時，花費(fèi)的時間為Θ(n)咒劲，這里假設(shè)S的大小為n顷蟆。

分析平均情況：
一個理想的哈希函數(shù)要做什么呢诫隅？把鍵基本隨機(jī)映射到一個槽上，應(yīng)該真正地隨機(jī)分布帐偎。我們把這種假設(shè)情況稱為“簡單均勻哈现鹞常”。意思是：每個屬于集合S的鍵值k削樊，即k∈S豁生，都有相同的幾率被哈希映射到表T的任何一個槽里。
這里還另外需要一個獨立性的假設(shè)：每個鍵與其它被哈希的記錄或鍵之間漫贞，相互獨立甸箱。
基于以上兩個假設(shè)，兩個鍵被映射到同一個槽的概率為1/m迅脐。

載荷因子

定義一個哈希表芍殖，存放了n個鍵，一共有m個槽谴蔑。其載荷因子α = n/m围小，其實就是每個槽里鍵的平均數(shù)量。

先看下失敗搜索（即搜索的鍵不存在哈希表中）的預(yù)計用時树碱，為Θ(1+α)肯适，這里的1是指把鍵值哈希映射到槽所需要的時間，α是指搜索槽對應(yīng)的鏈表成榜，所花費(fèi)的時間框舔。如果α>1，那么時間接近于α赎婚；否則時間近似為一個常數(shù)量刘绣。

那么什么情況下預(yù)計搜索時間等于Θ(1) ？
α為一個常數(shù)挣输，即α = O(1)纬凤，即n=O(m)。

事實上撩嚼，一個成功搜索所需要的時間也是Θ(1+α)停士，但證明這個需要做一點數(shù)學(xué)運(yùn)算。

如何選一個哈希函數(shù)

因為哈希的插入完丽、刪除和查找都只需要常數(shù)的運(yùn)行時間恋技，這是為什么哈希這么受歡迎的一個原因。只要你的哈希表的大小逻族，不要遠(yuǎn)小于你要放在里面的保存的記錄個數(shù)蜻底，那么所有操作都只需要一個常數(shù)量的運(yùn)行時間。

但在很大程度上聘鳞，這種情況是建立在“簡單均勻哈媳「ǎ”的假設(shè)上要拂，不論你用的是什么哈希函數(shù)，都能找到一些元素站楚，使得哈希映射出的結(jié)果非常糟糕宇弛。比如可以制造出一堆元素，代入到哈希函數(shù)里源请，看看它們會被映射到哪個槽枪芒，但是最后都被映射到了同一個槽里。所以需要反過來想想什么才是好的哈希函數(shù)谁尸。

在實際應(yīng)用中舅踪，大多數(shù)程序用到的并不是真正由逆向工程得到的哈希函數(shù)。有些非常簡單的哈希函數(shù)良蛮，在現(xiàn)實中也能起到很好的作用抽碌。

那如何選擇哈希函數(shù)呢？我們希望的結(jié)果是：

• 把鍵均勻分布到槽里
• 而鍵本身的一些分布的特性决瞳，不會影響到它在哈希表中分布的均勻性货徙。（比如，經(jīng)常見的一個分布特性是皮胡，所有插入的鍵值都是偶數(shù)痴颊。）

除法哈希法

用于快速哈希函數(shù)里，最受歡迎的方法是除法哈希法屡贺。
具體的實現(xiàn)為
h(k) = k mod m （mod表示取余）蠢棱，m是哈希表里槽的數(shù)量
需要注意：不要選太小的值來做除數(shù)，這里把除數(shù)寫成d甩栈，方便下面看

例如：d=2泻仙，即m是一個偶數(shù)。如果剛好碰到了上面提到的情況：所有的鍵都是偶數(shù)量没。因為偶數(shù)對偶數(shù)取余玉转，得到的也是偶數(shù)，所以永遠(yuǎn)不可能映射到一個奇數(shù)位的槽殴蹄，即奇數(shù)槽都不會被用到究抓。

另一個極端的例子，如m=2^r饶套，也就是說漩蟆，它所有的因子等于我們的小除數(shù)d垒探。在這種情況下妓蛮，如果進(jìn)行k mod m，它的哈希過程中就不會考慮到k所有的位（二進(jìn)制）圾叼。
比如定義了二進(jìn)制數(shù)如下蛤克，r=6捺癞，那么m = 2⁶。
k=1011000111011010构挤，這串二進(jìn)制數(shù)對2⁶取余的哈希結(jié)果如何髓介？
對2的冪取余，如果是2¹筋现，結(jié)果為0唐础；如果是2²，結(jié)果為10矾飞；如果是2³一膨，結(jié)果為010；所以對2⁶取余洒沦，結(jié)果為k的后六位豹绪，即011010。所以h(k)的結(jié)果為011010申眼。

對2的冪取余的時候瞒津，其實是在取它（二進(jìn)制）后幾位的數(shù)字。對2^r取余括尸，就是取它的后r位數(shù)字森枪。

這樣的話，哈希函數(shù)就與簡直的其它幾位（前面的位數(shù)）無關(guān)了镀迂。所以好的方法是取質(zhì)數(shù)來作為m的值缕溉，不要太接近2的冪或者10的冪這些數(shù)。因為2和10是全世界最常見的底數(shù)肴焊，也是最有規(guī)則性的底數(shù)前联。

后面會看一個比除法哈希法更好的算法，但是大家比較喜歡用除法哈希法是因為娶眷，它能方便地嵌入代碼里似嗤。它不是最好的算法的原因之一是：相對于加法和乘法而言，很多計算機(jī)在運(yùn)算時届宠，除法往往有更多的循環(huán)運(yùn)算烁落。而實際上，通常用幾步乘法就能解決問題了豌注。

乘法哈希法

乘法哈希法會更好用一些伤塌，但其實今天提到的哈希算法，在某種意義上轧铁，都不能說是好的哈希函數(shù)每聪。乘法哈希法的優(yōu)點是，基本上只需要用到乘法運(yùn)算。同樣药薯，也需要先定一些假設(shè)條件：
槽的數(shù)量為m绑洛，m是以2為底的冪（這對后面的運(yùn)算有利）。同時還要假定計算機(jī)的一個字的長度是w位（比如比較合適的計算機(jī)的字長有32位的童本，或者64位的）真屯。哈希函數(shù)如下：
h(k) = (Ak mod 2^w) rsh(w-r) ，其中穷娱，mod為取余绑蔫，rsh為二進(jìn)制位運(yùn)算的右偏移。
這里A是一個奇數(shù)泵额，并且2^w-r < A < 2^w晾匠，它是一個等長于計算機(jī)字長的奇數(shù)。

無論k的值為多少梯刚，和A相乘凉馆，然后對2^w取余，最后再右移w-r位數(shù)亡资。

下面看看A要如何取值澜共，以及不能取哪些值：
首先，A的取值不要太接近于以2為底的數(shù)锥腻。這是個快速的方法嗦董，因為乘法和右位移運(yùn)算都很快，尤其是已經(jīng)知道了偏移量是多少的情況下瘦黑。

這里看下這個哈希函數(shù)是如何運(yùn)作的京革？

假設(shè)這里m = 2³ = 8，即r=3幸斥，取一個特殊的字長為7位匹摇，即w=7。A是一個用于哈希函數(shù)的定值甲葬，假定A = 1011001廊勃，設(shè)定k = 1101011，通過乘法運(yùn)算計算Ak经窖，會得到一個2w位的值坡垫。這里的乘積結(jié)果為Ak = 10010100110011。對2^w取余画侣，結(jié)果為0110011冰悠。接著進(jìn)行右偏移w-r位，將0011右移掉了配乱，所以結(jié)果為h(k) = 011溉卓。

在大部分的計算機(jī)里皮迟，當(dāng)用兩個32位數(shù)相乘時，計算機(jī)會有一個指令會直接得出32個低位的值的诵，所以使用這種指令万栅，通常會比先算64位結(jié)果要快得多佑钾。

怎么理解這個運(yùn)算過程呢西疤？

把A看作一個二進(jìn)制的分?jǐn)?shù)，二進(jìn)制小數(shù)點在前面休溶，即A = .1011001代赁，當(dāng)A和某個數(shù)相乘的時候，小數(shù)點會出現(xiàn)在中間的位置兽掰，比如上面的Ak = 1001010.0110011芭碍。把A看成一個數(shù)的小數(shù)部分即可，不需要糾結(jié)具體的計算孽尽。

可以用車輪法來理解這個哈希函數(shù)：
先畫一個車輪窖壕，將其8等分。每一份為1/8杉女，A為0.1011001瞻讽，乘以8即2³，為101.1001份熏挎，即約等于5.5份速勇，即每個A占車輪的5.5/8份的大小。
所以k=1時坎拐，Ak = A·1烦磁，為5.5，從下標(biāo)0的位置開始順時針轉(zhuǎn)到5.5的位置哼勇；
k=1時都伪，Ak = A·2 = 11，大概繞到11%8=3积担，即略微超過3的地方院溺；
k=3時，Ak = A·3 = 16.5磅轻，大概繞道16.5/8=0.5珍逸，即約0.5的位置。
每次加多一個A聋溜，會加多一段A的弧長谆膳，如果A是奇數(shù)，并且不是近似以2為底的冪值撮躁。那么哈希的過程漱病，可以看成是把鍵扔入不同的槽里。類似繞車輪，如果k的值非常大杨帽，那么Ak相當(dāng)于繞k個圈漓穿。

車輪

這是個不錯的哈希函數(shù)，但這只是探索性的哈希方法注盈。因為對于任何哈希函數(shù)而言晃危，你總能找到一些鍵，使得哈希出來的結(jié)果非常糟糕老客。所以問題是僚饭，在實際應(yīng)用中選擇哪個。

開放尋址法解決碰撞

前面討論過用鏈接法解決碰撞問題胧砰，還有另外一個解決碰撞的方法鳍鸵，也是非常有用的。即“開放尋址法”尉间。
這里不會用到鏈表偿乖。如果用鏈接法，在每個記錄里哲嘲，都需要一個額外的關(guān)聯(lián)地址贪薪。對于某些應(yīng)用來說，沒必要為此付出巨大的開支撤蚊，同時也不想對記錄做任何的改動古掏。這種情況下，開放尋址法就是很有效的解決碰撞的方法侦啸。

在用開放尋址法時槽唾，如果哈希到了一個已經(jīng)存有記錄的槽，那么用另一個函數(shù)重新進(jìn)行哈希光涂。第二個哈希函數(shù)也哈希到了一個已經(jīng)存有記錄的槽庞萍，那就下一個哈希函數(shù)。形成一個探查的序列忘闻，然后變成一種算術(shù)排列钝计。已經(jīng)探查過的槽就不再進(jìn)行探查，直到找到一個可以放置記錄的槽齐佳。如果有一個比較好的探查序列私恬，那么就能很快地找到一個放置的地方。

對于查找鍵值而言炼吴，可以用同樣的探查序列來查找本鸣。開放尋址的思想就是：系統(tǒng)地探查哈希表，直到找到一個空槽為止硅蹦。

擴(kuò)展開來看荣德，實際上闷煤，一個哈希函數(shù)有兩個參數(shù)：鍵和探查順序。所以哈希函數(shù)h會把全域里的鍵涮瞻，通過一步步的探查映射到槽里鲤拿。

• h：Ux{0,1,...,m-1} -> {0,1,...,m-1}，U表示鍵的全域署咽，{}內(nèi)的表示探查號近顷，后面的一段{}表示槽。
• 探查序列應(yīng)該是一個算數(shù)排列艇抠，也就是說幕庐，它必須是數(shù)字0到m-1的某種完全隨機(jī)的排列久锥，也就是把0到m-1的數(shù)字全部打亂重排家淤。

開放尋址法不需要擔(dān)心n鏈接的問題，因為哈希表最終會被填滿瑟由。所以哈希表里的元素必須小于哈希表中槽的數(shù)量絮重，即n<=m，這樣才不會溢出歹苦。

這種情況下青伤，刪除比較困難（原因后面有說明），但不是不可能殴瘦，有專門的刪除方案狠角。刪除操作執(zhí)行起來比較困難，因為從表中刪除某個鍵之后蚪腋，有人按探查序列來查找另一個鍵丰歌，他本應(yīng)先發(fā)現(xiàn)這里不是他要的鍵，繼而再向下查找屉凯，然而現(xiàn)在卻發(fā)現(xiàn)這個槽是空的立帖。那么他會認(rèn)為，想要找的鍵很可能不在這個表里悠砚。
解決方案可以是：把元素刪除之后晓勇，在這里做個標(biāo)記。也有其它的方案灌旧，但都比較復(fù)雜绑咱。鏈接法要刪除就比較簡單了，直接從鏈表里刪除就可以了枢泰。
下面舉個例子：
要在下面的哈希表中插入一個鍵k=496
先是第0號探查描融，探查h(496, 0)，假設(shè)它映射到了204的槽宗苍，槽中已經(jīng)存放有記錄了稼稿，所以繼續(xù)探查薄榛。
第1號探查，探查h(496, 1)让歼，假設(shè)映射到了586的槽敞恋，槽中已經(jīng)存放有記錄，所以繼續(xù)探查谋右。
第2號探查硬猫，h(496, 2)，這個比較幸運(yùn)改执，終于找到了一個空槽啸蜜。
對于search操作，則返回nil辈挂，表示空值衬横。如果執(zhí)行的是插入操作，那就把k=496放在這個槽里终蒂。
如果是查找一個已經(jīng)存在哈希表中的值蜂林，那么也是從h(496, 0)開始執(zhí)行，跟插入執(zhí)行的序列一樣拇泣。所以刪除操作才比較難噪叙。。霉翔。

開放尋址法 如何構(gòu)造探查序列睁蕾，如何有效進(jìn)行探查？

線性探查

其中最簡單的方法是“線性探查”：h(k, i) = (h(k, 0) + i) mod m债朵，i表示當(dāng)前進(jìn)行的是第幾輪探查子眶。
i=1時，即是探查h(k, 0)的下一個葱弟；i=2壹店，即是再下一個。這個方法是簡單地向下探查芝加。mod m表示：到達(dá)了表的底下之后硅卢，回到頂端從頭開始。
這個方法比較簡單藏杖，不需要每一輪計算都重新算一次哈希函數(shù)将塑，只需要每次探查都+1。但有個問題是蝌麸，存在“群集現(xiàn)象”：如果一串連續(xù)區(qū)域同時被占用了点寥，那么接下來的所有操作都必須不停探查，直到這串區(qū)域的底部来吩。

二次哈希

二次哈希是個比較受歡迎的方法敢辩。
h(k, i) = ( h₁(k) + i·h₂(k) ) mod m
這是兩個關(guān)于m的哈希函數(shù)
第0次探查只使用h₁(k)函數(shù)進(jìn)行探查蔽莱，1號探查則加上一個h₂(k)函數(shù)，2號探查則繼續(xù)加上一個h₂(k)戚长。
計算起來也比較簡單盗冷，先算出h₁(k)和h₂(k)兩個函數(shù)值，然后后面的計算是不斷加上一個h₂(k)同廉。
通常會把m取為以2為底的冪值仪糖，即m=2^r。以及h₂(k)的值最好為奇數(shù)迫肖。

平均情況分析

這里的分析需要假設(shè)的情況比鏈接法要多一些锅劝。
假設(shè)“均勻哈希”：每個鍵都均等地有m!種探查序列蟆湖，并且每個鍵都是相互獨立的故爵。
這里要證明的理論是：預(yù)期的探查次數(shù)最多不超過1/(1-α)，如果α<1帐姻，那么哈希表里鍵的數(shù)量小于槽的數(shù)量稠集，即n<m奶段。α是前面提到的載荷因子饥瓷。

這里要求α<1是因為，如果鍵的數(shù)量大于槽的數(shù)量痹籍，那么開放尋址法就不起作用了呢铆，分分鐘死循環(huán)。蹲缠。棺克。

先看搜索失敗的情況
首先，一次探查是必不可少的线定。接著娜谊，如果m個槽內(nèi)已經(jīng)有n個元素，那么探查發(fā)生碰撞的概率為n/m斤讥。第二次探查碰撞的概率為(n-1)/(m-1)纱皆。第三次探查碰撞的概率為(n-2)/(m-2)。第i次探查碰撞的概率為(n-i)/(m-i) < n/m = α芭商。

那么預(yù)期探查數(shù)為：
E = 1 + n/m · (1+(n-1)/(m-1)·(1+(n-2)/(m-2·)(...(1+1/(m-n)...)))
... ≤ 1+α(1+α(1+α(...(1+α)...)))
... = 1+α+α²+α³+...
... = ∑αⁱ ---------- 從0到∞
... = 1/(1-α) ------------ 幾何數(shù)列上限

如果α<1派草，并且α為一個常數(shù)，那么預(yù)期探查數(shù)為常數(shù)铛楣，即O(1)
看一下哈希表近迁，如果只存放50%的數(shù)據(jù)，即α=0.5簸州，那么預(yù)期探查數(shù)為1/(1-0.5) = 2鉴竭。如果存放90%的數(shù)據(jù)歧譬，即α=0.9，那么預(yù)期探查數(shù)為1/(1-0.9) = 10搏存。隨著哈希表的密度增大缴罗，探查的時間花費(fèi)會急劇地增加，所以一般不要讓哈希表太過稠密祭埂。