說(shuō)明：該系列博客整理自《算法導(dǎo)論(原書(shū)第二版)》，但更偏重于實(shí)用，所以晦澀偏理論的內(nèi)容未整理，請(qǐng)見(jiàn)諒。另外本人能力有限，如有問(wèn)題，懇請(qǐng)指正！
????在很多應(yīng)用中，都要用到一種動(dòng)態(tài)集合結(jié)構(gòu)，它僅支持INSERT、SEARCH、DELETE字典操作。實(shí)現(xiàn)字典的一種有效數(shù)據(jù)結(jié)構(gòu)為散列表。在最壞情況下，在散列表中，查找一個(gè)元素的時(shí)間與在鏈表中查找一個(gè)元素的時(shí)間相同，在最壞情況下都是Θ(n)，但在實(shí)踐中，散列技術(shù)的效率是很高的。在一些合理的假設(shè)下，在散列表中查找一個(gè)元素的期望時(shí)間為O?(1)。
? ??散列表是普通數(shù)組概念的推廣，因?yàn)榭梢詫?duì)數(shù)組進(jìn)行直接尋址，故可以在O?(1)時(shí)間內(nèi)訪問(wèn)數(shù)組任意元素。1節(jié)進(jìn)一步討論直接尋址問(wèn)題：如果存儲(chǔ)空間允許，我們可以提供一個(gè)數(shù)組，為每個(gè)可能的關(guān)鍵字保留一個(gè)位置，就可以使用直接尋址技術(shù)。
????當(dāng)實(shí)際存儲(chǔ)的關(guān)鍵字?jǐn)?shù)比可能的關(guān)鍵字總數(shù)小時(shí)，采用散列表就會(huì)較直接數(shù)組尋址更為有效，因?yàn)樯⒘斜硗ǔ２捎玫臄?shù)組尺寸與所要存儲(chǔ)的關(guān)鍵字?jǐn)?shù)是成比例的，而數(shù)組此時(shí)使用數(shù)組會(huì)浪費(fèi)空間。在散列表中，不是直接把關(guān)鍵字用作數(shù)組下標(biāo)，而是根據(jù)關(guān)鍵字計(jì)算出下標(biāo)，即散列函數(shù)。2節(jié)介紹這種技術(shù)的主要思想，著重介紹解決“碰撞”的“鏈接”技術(shù)。所謂碰撞，就是指多個(gè)關(guān)鍵字映射到同一個(gè)數(shù)組下標(biāo)位置。3節(jié)介紹如何利用散列函數(shù)，根據(jù)關(guān)鍵字計(jì)算數(shù)組的下標(biāo)；另外，還將討論散列技術(shù)的幾種變形。4節(jié)介紹“開(kāi)放尋址法”，它是處理碰撞的另一種方法。5節(jié)解釋當(dāng)待排序的關(guān)鍵字集合是靜態(tài)的（即當(dāng)關(guān)鍵字集合一旦存入后不再改變），“完全散列”如何能夠在O?(1)最壞情況時(shí)間內(nèi)支持關(guān)鍵字查找。
? ? 散列表是一種及其有效和實(shí)用的技術(shù)：基本的字典操作只需要O?(1)的平均時(shí)間。
????散列表的主要思想就是尋址，1--3節(jié)使讀者全面認(rèn)識(shí)散列表，但它是直接尋址思想下的散列表；4節(jié)介紹另一種尋址思想：開(kāi)放尋址，然后4--5節(jié)使讀者認(rèn)知開(kāi)放尋址思想下的散列表。需要注意的是不同的尋址方式，其處理碰撞的方式是不同的。==>這是我對(duì)本章的認(rèn)知。
1、直接尋址表
????當(dāng)關(guān)鍵字的全域?U?比較小時(shí)(因?yàn)槿?U很大時(shí)數(shù)組占用?？臻g太大)，直接尋址是一種簡(jiǎn)單而有效的技術(shù)。假設(shè)某應(yīng)用要用到一個(gè)動(dòng)態(tài)集合，其中每個(gè)元素都取自全域?U?= { 0， 1， …，?m?- 1 }，并假設(shè)元素的關(guān)鍵字各不相同。
????可以用數(shù)組（或稱(chēng)?直接尋址表?）?T?[ 0 ..?m?- 1 ]表示動(dòng)態(tài)集合，其中每個(gè)位置（或稱(chēng)?槽?）對(duì)應(yīng)全域?U?中的一個(gè)關(guān)鍵字。下圖說(shuō)明了這個(gè)方法；槽?k?指向集合中關(guān)鍵字為?k?的元素。如果該集合中沒(méi)有關(guān)鍵字為?k?的元素，則?T?[?k?] =?NIL?。
幾個(gè)字典操作也很簡(jiǎn)單：
DIRECT-ADDRESS-SEARCH(T, k)
1 return T[k]
DIRECT-ADDRESS-INSERT(T, x)
1 T[x.key] = x
DIRECT-ADDRESS-DELETE(T, x)
1 T[x.key] = NIL
顯而易見(jiàn)，這些操作執(zhí)行起來(lái)只需?O?( 1 )的時(shí)間。
2、散列表
? ? 直接尋址技術(shù)有一個(gè)明顯的問(wèn)題：如果全域?U?很大，那么在內(nèi)存中存儲(chǔ)大小為 |?U?| 的一張表?T?就有點(diǎn)不實(shí)際，甚至是不可能。還有，實(shí)際要存儲(chǔ)的關(guān)鍵字集合?K?相對(duì)于?U?來(lái)說(shuō)可能很小，那么因而分配給?T?的大部分空間都要浪費(fèi)掉。
????當(dāng)存儲(chǔ)在字典中的關(guān)鍵字集合?K?比所有可能的關(guān)鍵字域?U?要小很多時(shí)，散列表需要的存儲(chǔ)空間要比直接尋址表少很多。特別地，在保持僅需?O?( 1 )時(shí)間即可在散列表中查找一個(gè)元素的好處的情況下，存儲(chǔ)要求可以降至?Θ?( |?K?| )。唯一的問(wèn)題是這個(gè)界是針對(duì)平均時(shí)間的，而對(duì)直接尋址來(lái)說(shuō)，它對(duì)最壞情況也成立。
? ??在直接尋址方式下，具有關(guān)鍵字?k?的元素被存放在槽?k?中。在散列方式下，該元素處于?h?(?k?)中，亦即，利用?散列函數(shù)?h?，根據(jù)關(guān)鍵字?k?計(jì)算出槽的位置。函數(shù)?h?將關(guān)鍵字域?U?映射到?散列表?T?[ 0 ..?m?- 1 ]的槽位上：
? ??????????????h?:?U?→ { 0， 1， …，?m?- 1 }
????這時(shí)，可以說(shuō)一個(gè)具有關(guān)鍵字?k?的元素被?散列?到槽?h?(?k?)上，或者說(shuō)?h?(?k?)是關(guān)鍵字?k?的?散列值?。下圖給出了形象的說(shuō)明。采用散列函數(shù)的目的就在于縮小需要處理的下標(biāo)范圍，即我們要處理的值從 |?U?| 降到?m了，從而相應(yīng)地降低了空間開(kāi)銷(xiāo)。
????這樣做有一個(gè)問(wèn)題：兩個(gè)關(guān)鍵字可能映射到同一個(gè)槽上。這種情形稱(chēng)為?碰撞?（collision）。當(dāng)然，最理想的解決方案是完全避免碰撞。要做到這一點(diǎn)，可以考慮選用合適的散列函數(shù)?h?。在選擇時(shí)的一個(gè)主導(dǎo)思想，就是使?h?盡可能的“隨機(jī)”，從而避免或者最小化碰撞。實(shí)際上，術(shù)語(yǔ)“散列”即體現(xiàn)了這種精神。（當(dāng)然，一個(gè)散列函數(shù)?h?必須是確定的，即某一給定的輸入?k?應(yīng)始終產(chǎn)生相同的結(jié)果?h?(?k?)。）但是，由于 |?U?| >?m?，故必然有兩個(gè)關(guān)鍵字的散列值相同，所以想要完全避免碰撞時(shí)不可能的。那么，我們一方面可以通過(guò)精心設(shè)計(jì)的隨機(jī)散列函數(shù)來(lái)盡量減少碰撞，另一方面仍需要有解決有可能出現(xiàn)的碰撞的辦法。
????本節(jié)余下部分介紹一種最簡(jiǎn)單的碰撞解決技術(shù)，稱(chēng)為鏈接法。第4節(jié)介紹另一種碰撞解決辦法，稱(chēng)為開(kāi)放尋址法。
2.1、鏈接法解決碰撞
? ??鏈接法?是一種最簡(jiǎn)單的碰撞解決技術(shù)。在鏈接法中，把散列到同一槽中的所有元素都放在一個(gè)鏈表中。如下圖所示，槽?j?中有一個(gè)指針，它指向由所有散列到?j?的元素構(gòu)成的鏈表的頭：如果不存在這樣的元素，則?j?中為?NIL?。
相應(yīng)操作如下：
CHAINED-HASH-INSERT(A, x)
1 insert x at the head of list T[h(x.key)]
CHAINED-HASH-SEARCH(T, k)
1 search for an element with key k in list T[h(k)]
CHAINED-HASH-DELETE(T, x)
1 delete x from the list T[h(x.key)]
? ? 插入操作的最壞情況運(yùn)行時(shí)間為O(1)。插入過(guò)程要快一些，因?yàn)榧僭O(shè)要插入的元素x沒(méi)有出現(xiàn)在表中；如果需要，在插入前執(zhí)行搜索，可以檢查這個(gè)假設(shè)(付出額外代價(jià))。查找操作的最壞情況運(yùn)行時(shí)間與表的長(zhǎng)度成正比。如果問(wèn)題中的鏈表是雙向鏈表，則刪除一個(gè)元素x的操作可以在O(1)時(shí)間內(nèi)完成(注意，此時(shí)CHAINED-HASH-DELETE以元素x而不是它的關(guān)鍵字k作為輸入，所以無(wú)需先搜索x。如果表是單鏈表，用元素x而不是關(guān)鍵字k作為輸入，將不會(huì)有很大幫助。我們依然必須尋找T[h(x.k))中的x，所以通過(guò)適當(dāng)?shù)脑O(shè)置x的前趨next鏈，把x排除在連接之外。在這種情況下，搜索和插入的運(yùn)行時(shí)間基本相同。
2.2、鏈接法散列的分析
????給定一個(gè)能存放?n?個(gè)元素的，具有?m?個(gè)槽位的散列表?T?，定義?T?的?裝載因子?（load factor）?α?為?n / m?，即一個(gè)鏈中平均存儲(chǔ)的元素?cái)?shù)。我們的分析以?α?來(lái)表達(dá)，?α?可以小于，等于或大于 1 。
????用鏈接法散列的最壞情況性能很差：所有的?n?個(gè)關(guān)鍵字都散列到同一個(gè)槽中，從而產(chǎn)生出一個(gè)長(zhǎng)度為?n?的鏈表。這時(shí)，最壞情況下查找的時(shí)間為?Θ?(?n?)，再加上計(jì)算散列函數(shù)的時(shí)間，這么一來(lái)就和用一個(gè)鏈表來(lái)鏈接所有的元素差不多了。顯然我們并不是因?yàn)樯⒘斜淼淖顗那闆r性能才用它的。(第5節(jié)中介紹的完全散列能夠在關(guān)鍵字集合為靜態(tài)時(shí)，提供比較好的最壞情況性能。)
????散列方法的平均性態(tài)依賴(lài)于所選取的散列函數(shù)?h?，在一般情況下將所有的關(guān)鍵字分布在?m?個(gè)槽位上的均勻程度。第3節(jié)散列函數(shù)中討論了這些問(wèn)題，此時(shí)我們先假設(shè)任何元素散列到?m?個(gè)槽中每一個(gè)槽的可能性都是相同的，且與其他元素已被散列到什么位置上是獨(dú)立無(wú)關(guān)的。稱(chēng)這個(gè)假設(shè)為?簡(jiǎn)單一致散列?（simple uniform hashing）。
????????對(duì)于?j?= 0， 1， …，?m?- 1，列表元素?T?[?j?]所指向的鏈表的長(zhǎng)度用?nj?表示，這樣有：
? ??????n?=?n0?+?n1?+ … +?nm1
? ??????nj?的平均值為E[?nj?] =?α?=?n / m?。
????假定可以在?O?( 1 )時(shí)間內(nèi)算出散列值?h?(?k?)，從而查找具有關(guān)鍵字?k?的元素的時(shí)間線性地依賴(lài)于表?T?[?h?(?k?)]的長(zhǎng)度?nh(k)(說(shuō)明，此處h(k)為n的下標(biāo))?。先不考慮計(jì)算散列函數(shù)和尋址槽?h?(?k?)的?O?( 1 )時(shí)間，只看為比較元素的關(guān)鍵字是否為?k?而檢查的表?T?[?h?(?k?)]中的元素?cái)?shù)。共有兩種情況：查找成功，即表中沒(méi)有一個(gè)元素的關(guān)鍵字為k；查找不成功，即表中具有關(guān)鍵字為k的元素。
? ??定理：對(duì)一個(gè)用鏈接技術(shù)來(lái)解決碰撞的散列表，在簡(jiǎn)單一致散列的情況下，一次不成功查找的期望時(shí)間為?Θ?( 1 +?α?)。
? ??定理：在簡(jiǎn)單一致散列的假設(shè)下，對(duì)于用鏈接技術(shù)解決碰撞的散列表，平均情況下一次成功的查找需要?Θ?( 1 +?α?)。
????這一結(jié)論說(shuō)明，如果散列表中槽數(shù)至少與表中的元素?cái)?shù)成正比，則有?n?=?O?(?m?)，從而?α?=?n / m?=?O?(?m?) /?m?=?O?( 1 )。即平均來(lái)說(shuō)，查找操作需要常量時(shí)間。又知道插入操作和刪除操作在最壞情況下都需要?O?( 1 )時(shí)間。因而，全部的字典操作平均情況下都可以在?O?( 1 )時(shí)間內(nèi)完成。
2.3、散列函數(shù)：根據(jù)關(guān)鍵字計(jì)算下標(biāo)
? ? 本節(jié)我們要討論一些有關(guān)如何設(shè)計(jì)出好的散列函數(shù)的問(wèn)題，并介紹三種設(shè)計(jì)方案。其中兩種方案(用除法進(jìn)行散列、用乘法進(jìn)行散列)從本質(zhì)上來(lái)看，都是啟發(fā)式的方式(啟發(fā)式意味著就是啟發(fā)讀者學(xué)習(xí)的，實(shí)用性不大)。第三種方案(全域散列)則利用了隨機(jī)化的技術(shù)，來(lái)提供可證明的良好性能。
????一個(gè)好的散列函數(shù)應(yīng)（近似地）滿足簡(jiǎn)單一致散列的假設(shè)：每個(gè)關(guān)鍵字都等可能地散列到?m?個(gè)槽位的任何一個(gè)之中去，并與其他的關(guān)鍵字已被散列到哪一個(gè)槽位中無(wú)關(guān)。不幸的是，一般情況下不太可能檢查這一條件是否成立，因?yàn)槿藗兒苌倌苤狸P(guān)鍵字所符合的概率分布，而各關(guān)鍵字可能并不是完全相互獨(dú)立的。
? ? 有時(shí)，我們偶爾也能知道關(guān)鍵字的概率分布。例如，如果已知各關(guān)鍵字都是隨機(jī)的實(shí)數(shù)k，他們獨(dú)立、一致地分布于范圍0<=k<1中，那么散列函數(shù)h(k)=?km?就能滿足簡(jiǎn)單一致散列這一假設(shè)條件。
? ? 在實(shí)踐中，常?？梢赃\(yùn)用啟發(fā)式技術(shù)來(lái)構(gòu)造性能好的散列函數(shù)。在設(shè)計(jì)過(guò)程中，可以利用有關(guān)關(guān)鍵字分布的限制性信息。例如，一個(gè)編譯器的符號(hào)表中，關(guān)鍵字都是字符串，表示程序中的標(biāo)示符。在同一個(gè)程序中，經(jīng)常會(huì)出現(xiàn)一些很相近的符號(hào)，如pt和pts。一個(gè)好的散列函數(shù)應(yīng)能最小化將這些相近符號(hào)散列到同一個(gè)槽中的可能性。
? ? 一種好的做法是以獨(dú)立于數(shù)據(jù)中可能存在的任何模式的方式導(dǎo)出散列值。例如，“除法散列”用一個(gè)特定的質(zhì)數(shù)來(lái)除所給的關(guān)鍵字，所得到的余數(shù)即為該關(guān)鍵字的散列值。假定所選則的質(zhì)數(shù)與關(guān)鍵字分布中的任何模式都是無(wú)關(guān)的。這種方法常?？梢越o出很好的效果。
? ? 最后請(qǐng)注意，散列函數(shù)的某些應(yīng)用可能會(huì)要求比簡(jiǎn)單一致散列更強(qiáng)的性質(zhì)。例如，我們可能希望某些很近似的關(guān)鍵字具有截然不同的散列值(當(dāng)使用第4節(jié)中將定義的線性探查技術(shù)時(shí)，這一性質(zhì)是特別有用的)。2.3.3節(jié)將介紹的全域散列通常能夠提供這些性質(zhì)。
2.3.0、將關(guān)鍵字解釋為自然數(shù)
? ? 多數(shù)散列函數(shù)都假定關(guān)鍵字域?yàn)樽匀粩?shù)集N={ 0， 1， … }。如果所給關(guān)鍵字不是自然數(shù)，則必須有一種方法來(lái)將他們解釋為自然數(shù)。例如，一個(gè)字符串關(guān)鍵字可以被解釋為按適當(dāng)?shù)幕鶖?shù)記號(hào)表示的整數(shù)。這樣，標(biāo)示符pt可以被解釋為十進(jìn)制整數(shù)對(duì)(112,116)，因?yàn)樵贏SCII字符集中，p=112，t=116.然后，按128為基數(shù)來(lái)表示，pt即為112*128+116=14 452。在任一給定的應(yīng)用中，通常都比較容易設(shè)計(jì)出類(lèi)似的方法，來(lái)將每個(gè)關(guān)鍵字解釋為一個(gè)(可能很大)自然數(shù)。在后面的內(nèi)容中，假定所給的關(guān)鍵字都是自然數(shù)。
2.3.1、除數(shù)散列法
????在用來(lái)設(shè)計(jì)散列函數(shù)的?除數(shù)散列法?中，通過(guò)取?k?除以?m?的余數(shù)，來(lái)將關(guān)鍵字?k?映射到?m?個(gè)槽的某一個(gè)中去。亦即，散列函數(shù)為：h?(?k?) =?k?mod?m
????當(dāng)應(yīng)用除數(shù)散列時(shí)，要注意?m?的選擇。例如，m不應(yīng)是2的冪，因?yàn)槿绻鹠等于2的p次冪，則h?(?k?)就是k的p個(gè)最低位數(shù)字。除非我們事先知道光劍子的概率分布使得k的各種最低p位的排列形式的可能性相同，否則在設(shè)計(jì)散列函數(shù)時(shí)，最好考慮關(guān)鍵字的所有位的情況。
????可選的?m?值通常是與 2 的整數(shù)冪不太接近的質(zhì)數(shù)。
2.3.2、乘法散列法
????構(gòu)造散列函數(shù)的?乘法散列法?包含兩個(gè)步驟。第一步，用關(guān)鍵字?k?乘上常數(shù)?A?（0 <?A?< 1），并抽取出?k A?的小數(shù)部分。然后，用?m?乘以這個(gè)值，再取結(jié)果的底（floor）。散列函數(shù)為：
? ??????????????????????????????????????????h?(?k?) = FLOOR(?m?(?k A?mod 1 ))
????乘法方法的一個(gè)優(yōu)點(diǎn)是對(duì)?m?的選擇沒(méi)有什么特別的要求，一般選擇它為 2 的冪（?m?=?2p?，?p?為某個(gè)整數(shù)）。
? ? 雖然乘法散列對(duì)任何的A值都適用，但某些值效果更好。最佳的選擇與待散列的數(shù)據(jù)的特征有關(guān)，不過(guò)Knuth認(rèn)為A=0.618 033 988 7...就是個(gè)比較理想的值。
2.3.3、全域散列
????任何的散列函數(shù)都可能出現(xiàn)最壞情況性態(tài)，即?n?個(gè)關(guān)鍵字都散列到同一個(gè)槽中，使得平均的檢索時(shí)間為?Θ?(?n?)：唯一有效的改進(jìn)方法是隨機(jī)地選擇散列函數(shù)，使之獨(dú)立于要存儲(chǔ)的關(guān)鍵字，這種方法稱(chēng)作?全域散列（universal hashing）。不管面對(duì)什么情況，其平均性態(tài)都很好。
? ??全域散列?的基本思想是在執(zhí)行開(kāi)始時(shí)，就從一族仔細(xì)設(shè)計(jì)的函數(shù)中，隨機(jī)地選擇一個(gè)作為散列函數(shù)。就像在快速排序中一樣，隨機(jī)化保證了沒(méi)有哪一種輸入會(huì)始終導(dǎo)致最壞情況性態(tài)。同時(shí)，隨機(jī)化使得即使是對(duì)同一個(gè)輸入，算法在每一次執(zhí)行時(shí)的性態(tài)也是不一樣的。這樣就可以確保對(duì)于任何輸入，算法都具有良好的平均情況性態(tài)。再來(lái)看看編譯器中符號(hào)表的例子，我們發(fā)現(xiàn)在全域散列方法中，程序員對(duì)標(biāo)示符的選擇就不會(huì)一致的導(dǎo)致較差的散列性能了。僅當(dāng)編譯器選擇了一個(gè)隨機(jī)的散列函數(shù)，使得標(biāo)示符的散列效果較差時(shí)，才會(huì)出現(xiàn)較差的性能，但是，出現(xiàn)這種情況的概率很小，并且這一概率對(duì)任何相同大小的標(biāo)示符集來(lái)說(shuō)都是一樣的。
????設(shè)?H?為有限的一組散列函數(shù)，它將給定的關(guān)鍵字域?U?映射到{ 0， 1， …，?m?- 1 }個(gè)槽中。這樣的一組函數(shù)稱(chēng)為是?全域的?（universal），如果對(duì)任意一組不同的關(guān)鍵字?k?，?l?∈?U?，從H中選定某一hash函數(shù)h，映射到同一個(gè)slot中，即滿足?h?(?k?) =?h?(?l?)的散列函數(shù)?h?∈?H?的個(gè)數(shù)至多為 |?H?| /?m?。換言之，如果從?H?中隨機(jī)選擇一個(gè)散列函數(shù)，此時(shí)概率為1?/?|?H?|，當(dāng)關(guān)鍵字?k?≠?l?時(shí)，這個(gè)散列函數(shù)h使兩個(gè)元素發(fā)生碰撞的概率最大為(1?/?|?H?|) * (|?H?| /?m)，即碰撞的概率不大于 1 /?m?。
? ??定理：如果?h?選擇一組全域的散列函數(shù)，并用于將?n?個(gè)關(guān)鍵字散列到一個(gè)大小為?m?的，用鏈接法解決碰撞的表?T?中。如果關(guān)鍵字?k?不在表中，則?k?被散列至其中的鏈表的期望長(zhǎng)度E[?nh(k)?]至多為?α?。如果關(guān)鍵字?k?在表中，則包含關(guān)鍵字?k?的鏈表的期望長(zhǎng)度E[?nh(k)?]至多為 1 +?α?。注意α=n / m
? ??推論：對(duì)于一個(gè)具有?m?個(gè)槽位的表，利用全域散列和鏈接法解決碰撞，需要?Θ?(?n?)的期望時(shí)間來(lái)處理任何包含了?n?個(gè)?INSERT?，?SEARCH?，?DELETE?操作的操作序列，該序列中包含了?O?(?m?)個(gè)?INSERT?操作。
? ? 說(shuō)明：剛開(kāi)始看的時(shí)候我還以為每次插入一個(gè)關(guān)鍵字時(shí)都要隨機(jī)選擇函數(shù)，但是這樣就沒(méi)法查找關(guān)鍵字了，想了一個(gè)晚上想不出來(lái)，懷疑智商了，看了網(wǎng)上的代碼，發(fā)現(xiàn)在最初執(zhí)行的時(shí)候，從散列集合中隨機(jī)選取一個(gè)散列函數(shù)h后，就把固定使用h函數(shù)作為散列函數(shù)了....
3、開(kāi)放尋址法
????在?開(kāi)放尋址法?（open addressing）中，所有的元素都存放在散列表中。亦即，每個(gè)表項(xiàng)或包含動(dòng)態(tài)集合的一個(gè)元素，或包含?NIL?。當(dāng)查找一個(gè)元素時(shí)，要檢查所有的表項(xiàng)，直到找到所需的元素，或最終發(fā)現(xiàn)該元素不在表中。不像在鏈表法中，這沒(méi)有鏈表，也沒(méi)有元素存放在散列表外。在這種方法中，散列表可能會(huì)被填滿，以至于不能插入任何新的元素，但該方法的裝載因子?α?絕對(duì)不會(huì)超過(guò) 1 。
? ? 當(dāng)然，也可以將用作鏈接的鏈表存放在散列表未用的槽中，但開(kāi)放尋址法的好處就在于它根本不用指針，而是計(jì)算出要存取的各個(gè)槽。這樣一來(lái)由于不用存儲(chǔ)指針而節(jié)省了空間，從而可以用同樣的空間來(lái)提供更多的槽，其潛在的效果就是可以減少碰撞，提高查找速度。
????在開(kāi)放尋址法中，當(dāng)要插入一個(gè)元素時(shí)，可以連續(xù)地檢查（或稱(chēng)?探查?）散列表的各項(xiàng)，直到找到一個(gè)空槽來(lái)放置待插入的關(guān)鍵字為止。檢查的順序不一定是 0， 1， …，?m?- 1 （這種順序下的查找時(shí)間為?Θ?(?n?)），而是要依賴(lài)于待插入的關(guān)鍵字。為了確定要探查哪些槽，應(yīng)該將散列函數(shù)的參數(shù)加以擴(kuò)充，除關(guān)鍵字外，將探查號(hào)（從 0 開(kāi)始）作為第二個(gè)輸入?yún)?shù)。這樣，散列函數(shù)就變?yōu)椋?/p>
? ??????????????????????????h?:?U?ⅹ { 0， 1， …，?m?- 1 } → { 0， 1， …，?m?- 1 }
對(duì)開(kāi)放尋址法來(lái)說(shuō)，要求對(duì)每一個(gè)關(guān)鍵字?k?，?探查序列
????????????????????????????<?h?(?k?， 0 )，?h?(?k?， 1 )， …，?h?(?k?，?m?- 1 ) >
必須是< 0， 1， …，?m?- 1 >的一個(gè)排列，使得當(dāng)散列表逐漸填滿時(shí)，每一個(gè)表位最終都可以被視為用來(lái)插入新關(guān)鍵字的槽。在下面的偽代碼中，假設(shè)關(guān)鍵字k就是帶插入的元素：
HASH-INSERT(T, k)
1? i = 0
2? repeat? j = h(k, i)
3? ? ? if T[j] == nil
4? ? ? ? ? T[j] == k
5? ? ? ? ? return j
6? ? ? else
7? ? ? ? ? i = i + 1
8 until i == m
9 error "hash table overflow"
? ? 查找關(guān)鍵字k的算法的探查序列與將k插入時(shí)的插入算法是一樣的。當(dāng)在查找的過(guò)程中碰到一個(gè)空槽時(shí)，查找算法就停止，因?yàn)槿绻鹝確實(shí)在表中的話，也應(yīng)該在該處，而不是探查序列的稍后位置上(之所以這么說(shuō)，是因?yàn)槲覀兗俣岁P(guān)鍵字不會(huì)被刪除)。過(guò)程HASH-SEARCH的輸入為一個(gè)散列表T和一個(gè)關(guān)鍵字k，如果槽j中包含關(guān)鍵字k，則返回j；如果k不在表T中，則返回nil。
HASH-SEARCH(T, k)
1 i = 0
2 repeat? ?j = h(k, i)
4? ? if T[j] == k
5? ? ? ? return j
6? ? i = i + 1
7 until T[j] == NIL or i == m
8 return NIL
? ??在開(kāi)放尋址法中，對(duì)散列表元素的刪除操作執(zhí)行起來(lái)比較困難。當(dāng)我們從槽?i?中刪除關(guān)鍵字時(shí)，不能僅將?NIL?置于其中來(lái)標(biāo)識(shí)它為空。否則就會(huì)有個(gè)問(wèn)題：在插入某關(guān)鍵字?k?的探查過(guò)程中，發(fā)現(xiàn)?i?被占用了，則?k?被插入到后面的位置上。在將槽?i?中的關(guān)鍵字刪除后，就無(wú)法檢索關(guān)鍵字?k?了。有一個(gè)解決的辦法就是在槽?i?中置一個(gè)特定的值?DELETED?，而不用?NIL?。這樣要對(duì)過(guò)程?HASH-INSERT?作相應(yīng)的修改，使之將這樣的一個(gè)槽當(dāng)作一個(gè)空槽，從而仍然可以插入新的元素。對(duì)HASH-SEARCH無(wú)需做什么改動(dòng)，因?yàn)樗谒阉鲿r(shí)會(huì)繞過(guò)DELETED標(biāo)識(shí)。但是，當(dāng)使用特殊值?DELETED?時(shí)，查找時(shí)間就不再依賴(lài)于裝載因子?α?了，因此，在必須刪除關(guān)鍵字的應(yīng)用中，往往采用鏈接法來(lái)解決碰撞?。。。。。。。。。?！。而且，我認(rèn)為刪除多次以后，大多元素都不在h?(?k?， i)初始計(jì)算出的位置上，查找速度會(huì)越來(lái)越慢，所以“在必須刪除關(guān)鍵字的應(yīng)用中，往往采用鏈接法來(lái)解決碰撞”這個(gè)結(jié)論我認(rèn)為很正確！??！
????在我們的分析中，作了一個(gè)?一致散列?的假設(shè)，即假設(shè)每個(gè)關(guān)鍵字的探查序列是< 0， 1， …，?m?- 1 >的?m!?種排列中的任一種的可能性是相同的。一致散列將前面定義過(guò)的?簡(jiǎn)單一致散列?的概念加以一般化，推廣到散列函數(shù)的結(jié)果不只是一個(gè)數(shù)，而是一個(gè)完整的探查序列的情形。然而，真正的一致散列是很難實(shí)現(xiàn)的，在實(shí)踐中，常常采用它的一些近似方法，如下面介紹的線性探查，二次探查，以及雙重散列。
????在實(shí)踐中，常用三種技術(shù)來(lái)計(jì)算開(kāi)放尋址法中的探查序列：線性探查，二次探查，以及雙重散列。這幾種技術(shù)都能保證對(duì)每個(gè)關(guān)鍵字k，<?h?(?k?， 0 )，?h?(?k?， 1 )， …，?h?(?k?，?m?- 1 ) >都是< 0， 1， …，?m?- 1 >的一個(gè)排列。但是這些技術(shù)都不能實(shí)現(xiàn)一致散列的假設(shè)，因?yàn)樗麄兡墚a(chǎn)生的不同探查序列數(shù)都不超過(guò)m*m個(gè)。在這三種技術(shù)中，雙重散列能產(chǎn)生的探查序列最多，因而能給出最好的結(jié)果。
3.1、線性探查
????給定一個(gè)普通的散列函數(shù)?h?' :?U?→ { 0， 1， …，?m?- 1 }（稱(chēng)為?輔助散列函數(shù)?），?線性探查?（linear probing）方法采用的散列函數(shù)為：h?(?k?，?i?) = (?h?'(?k?) +?i?) mod?m?，?i?= 0， 1， …，?m?- 1
????給定一個(gè)關(guān)鍵字?k?，第一個(gè)探查的槽是?T?[?h?'(?k?) ]，亦即，由輔助散列函數(shù)所給出的槽。接下來(lái)探查的是槽?T?[?h?' (?k?) + 1 ]， …，直到槽?T?[?m?- 1 ]，然后又卷繞到槽?T?[ 0 ]，?T?[ 1 ]， …直到最后探查槽?T?[?h?' (?k?) - 1 ]。在線性探查方法中，初始探查位置確定了整個(gè)序列，故只有?m?種不同的探查序列。
????線性探查方法很容易實(shí)現(xiàn)，但它存在一個(gè)問(wèn)題，稱(chēng)作?一次群集?（primary clustering）。隨著時(shí)間的推移，連續(xù)被占用的槽不斷增加，平均查找時(shí)間也隨著不斷增加。群集現(xiàn)象很容易出現(xiàn)，這是因?yàn)楫?dāng)一個(gè)空槽前有?i個(gè)滿的槽時(shí)，該空槽作為下一個(gè)將被占用槽的概率是(?i?+ 1 ) /?m?。連續(xù)被占用槽的序列將會(huì)越來(lái)越長(zhǎng)，因而平均查找時(shí)間也會(huì)隨之增加。
3.2、二次探查
? ??二次探查?（quadratic probing）采用如下形式的散列函數(shù)：h?(?k?，?i?) = (?h?' (?k?) +?c1?i?+?c2?i2?) mod?m? ?。其中?h?'是一個(gè)輔助散列函數(shù)，?c1?和?c2?為輔助常數(shù)（不等于0），?i?= 0， 1， …，?m?- 1。初始的探查位置為?T?[?h?'(?k?) ]，后續(xù)的探查位置要在此基礎(chǔ)上加上一個(gè)偏移量，該偏移量以二次的方式依賴(lài)于探查號(hào)?i?。這種探查方法的效果要比線性探查好很多，但是，如果兩個(gè)關(guān)鍵字的初始探查位置相同，那么他們的探查序列也是相同的，這是因?yàn)?h?(?k1?， 0 ) =?h?(?k2?， 0 )蘊(yùn)含著?h?(?k1?，?i?) =?h?(?k2?，?i?)。這一性質(zhì)可導(dǎo)致一種程度較輕的群集現(xiàn)象，稱(chēng)為?二次群集?（secondary clustering）。二次探查也只有?m?個(gè)不同的探查序列。
3.3、雙重散列
? ??雙重散列?是用于開(kāi)放尋址法的最好方法之一，它采用如下形式的散列函數(shù)：h?(?k?，?i?) = (?h1?(?k?) +?i h2?(?k?) ) mod?m
????其中?h1?和?h2?為輔助散列函數(shù)。初始探查位置為?T?[?h1?(?k?) ]，后續(xù)的探查位置在此基礎(chǔ)上加上偏移量?h2?(?k?)模?m?。
為能查找整個(gè)散列表，值?h2?(?k?)要與表的大小?m?互質(zhì)。確保這個(gè)條件成立的一種方法是取?m?為 2 的冪，并設(shè)計(jì)一個(gè)總產(chǎn)生奇數(shù)的?h2?。另一種方法是取?m?為質(zhì)數(shù)，并設(shè)計(jì)一個(gè)總是產(chǎn)生較?m?小的正整數(shù)的?h2?。
????雙重散列法中用了?Θ?(?m2?)中探查序列。
3.4對(duì)開(kāi)放尋址散列的分析
????對(duì)開(kāi)放尋址散列的分析也是以散列表的裝載因子?α?=?n / m?來(lái)表達(dá)的。在開(kāi)放尋址法中，由于每個(gè)槽中至多只有一個(gè)元素，因而?n?<=?m?，這意味著?α?<= 1 。
? ? 現(xiàn)在假設(shè)采用的是一致散列法。在這種理想的方法中，用于插入或查找每一個(gè)關(guān)鍵字k的探查序列<?h?(?k?， 0 )，?h?(?k?， 1 )， …，?h?(?k?，?m?- 1 ) >為< 0， 1， …，?m?- 1 >的任一中排列的可能性是相同的。當(dāng)然，每一個(gè)給定的關(guān)鍵字有唯一確定的探查序列。我們這里想說(shuō)的是，考慮到關(guān)鍵字空間上的概率分布及散列函數(shù)函數(shù)施于這些關(guān)鍵字上的操作，每一種探查序列都是等可能的。
? ? 下面就來(lái)分析一下在一直散列的假設(shè)下，用開(kāi)放尋址法進(jìn)行散列時(shí)預(yù)期的探查數(shù)。分析結(jié)果為如下幾個(gè)定理。
? ??定理：給定一個(gè)裝載因子為?α?=?n / m?< 1 的開(kāi)放尋址散列表，在一次不成功的查找中，期望的探查數(shù)至多為 1 / ( 1 -?α?)。假設(shè)散列是一致的。==>我認(rèn)為該定理的前提是該散列上沒(méi)有刪除操作。
????如果?α?是一個(gè)常數(shù)，根據(jù)上述定理，一次不成功查找的運(yùn)行時(shí)間為?O?( 1 )。
? ??推論：平均情況下，向一個(gè)裝載因子為?α?的開(kāi)放尋址散列表中插入一個(gè)元素時(shí)，至多需要做 1 / ( 1 -?α?)次探查。假設(shè)散列是一致的。
? ??定理：給定一個(gè)裝載因子為?α?< 1 的開(kāi)放尋址散列表，一次成功查找中的期望探查數(shù)至多為：( 1 /?α?) ln ( 1 / ( 1 -?α?))。假定散列是一致的，且表中的每個(gè)關(guān)鍵字被查找的可能性是相同的。
4、完全散列
?人們之所以使用散列技術(shù)，主要是因?yàn)樗兄錾钠谕阅?/b>。其實(shí)，當(dāng)關(guān)鍵字集合是靜態(tài)的時(shí)，散列技術(shù)還可以用來(lái)獲得出色的最壞情況性能(我認(rèn)為這句話的意思是：最壞情況的性能也非常好)。所謂靜態(tài)是指關(guān)鍵字集合中關(guān)鍵字就那么多，不是變化的。有些應(yīng)用很自然的有著靜態(tài)的關(guān)鍵字集合，如一門(mén)程序設(shè)計(jì)語(yǔ)言中的保留字集合，或者一張CD-ROM上的文件名集合等。如果某一種散列技術(shù)在進(jìn)行查找時(shí)，其最壞情況內(nèi)存訪問(wèn)次數(shù)為O( 1 )的話，則稱(chēng)為完全散列(perfect hashing)。
設(shè)計(jì)完全散列方案的基本思想是比較簡(jiǎn)單的：我們利用一種兩級(jí)的散列方案，每一級(jí)上都采用全域散列。具體來(lái)講，存在待查找的元素key，經(jīng)過(guò)一次散列，該元素被存放在槽hash(key)處，然而其他元素也有可能被散列至該處，因此對(duì)散列至該槽的元素繼續(xù)進(jìn)行散列，所得到的值hash'(key)即為元素key的確切存儲(chǔ)位置。其中外層hash過(guò)程稱(chēng)為一級(jí)散列，內(nèi)層hash'過(guò)程稱(chēng)為二級(jí)散列。
這個(gè)策略會(huì)存在幾個(gè)問(wèn)題，首先二級(jí)散列之后可能還會(huì)存在碰撞問(wèn)題，是否需要進(jìn)行三級(jí)散列甚至更多級(jí)的散列？其次，某個(gè)槽對(duì)應(yīng)的二級(jí)散列函數(shù)應(yīng)如何選取？最后，一級(jí)散列中某個(gè)槽所對(duì)應(yīng)的二級(jí)散列表的尺寸應(yīng)該如何設(shè)置？這三個(gè)問(wèn)題其實(shí)可以一并解決。首先對(duì)于是否需要更多級(jí)的散列，因?yàn)橥鈱拥囊患?jí)散列已經(jīng)將原集合分為一系列子集，若我們將一級(jí)散列表設(shè)置為與原集合尺寸相近的大小，同時(shí)合理的選取一個(gè)散列函數(shù)，那么在每個(gè)槽中發(fā)生碰撞的元素個(gè)數(shù)將在一個(gè)可控范圍內(nèi)，此時(shí)如果為了少部分元素再設(shè)置三級(jí)散列的話，不僅增加了整個(gè)結(jié)構(gòu)的復(fù)雜性以及對(duì)于內(nèi)存的要求，而且還要再次為三級(jí)散列選取合理的散列函數(shù)，成本相對(duì)較大。接著來(lái)看解決二級(jí)散列函數(shù)的選取問(wèn)題，我們發(fā)現(xiàn)在全域散列法中，只需設(shè)置不同的參數(shù)，即能生成特定于某個(gè)槽的散列函數(shù)，若生成的散列函數(shù)導(dǎo)致二級(jí)散列表中發(fā)生碰撞，那么重新從全域散列函數(shù)簇中選取，直至不發(fā)生碰撞為止即可。另外，只需合理設(shè)置二級(jí)散列表的大小，這種重新選取的概率將變得極低，一個(gè)可行的指導(dǎo)原則是將二級(jí)散列表Sj的大小Mj設(shè)置為外層散列至該槽的元素個(gè)數(shù)Nj的平方。Mj對(duì)Nj的這種二次依賴(lài)關(guān)系看上去可能使得總體存儲(chǔ)需求很大，但是通過(guò)證明我們發(fā)現(xiàn)：通過(guò)適當(dāng)?shù)倪x取第一次散列函數(shù)，預(yù)期使用的總存儲(chǔ)空間仍然為O(n)。
????完全散列的分析更形象化的說(shuō)明上圖所示。第一級(jí)與帶鏈接的散列基本上是一致的：利用從某一全域散列函數(shù)簇中仔細(xì)選出的一個(gè)散列函數(shù)h，將n個(gè)關(guān)鍵字散列到m個(gè)槽中。然后，對(duì)散列到槽j中的關(guān)鍵字建立一個(gè)鏈表Sj，對(duì)應(yīng)的散列函數(shù)為hj（j是下標(biāo)）。通過(guò)仔細(xì)選取散列函數(shù)hj，可以確保在第二級(jí)上不出現(xiàn)碰撞。
????最后要說(shuō)明的一點(diǎn)是，這種通過(guò)兩次散列的方法雖然提供了高效的搜索，但代價(jià)是花費(fèi)了更多的內(nèi)存空間，同時(shí)因?yàn)椴迦氩僮饔锌赡軐?dǎo)致在二級(jí)散列表中發(fā)生碰撞，因此這種方法只適用于靜態(tài)關(guān)鍵字集合中，“靜態(tài)”意指該集合一旦確定，便不再發(fā)生動(dòng)態(tài)變化，即不發(fā)生插入或是刪除操作。
? ? 下面的定理說(shuō)明兩個(gè)問(wèn)題。首先，要確定如何才能確保二次散列表中不出現(xiàn)碰撞。其次，要說(shuō)明期望使用的總體存儲(chǔ)空間(即主散列表和所有的二次散列表所占的空間)為O(n)。
? ? 定理11.9：如果利用從一個(gè)全域散列函數(shù)類(lèi)中隨機(jī)選出的散列函數(shù)h，將n個(gè)關(guān)鍵字存儲(chǔ)在一個(gè)大小為m=n2的散列表中，那么出現(xiàn)碰撞的概率小于1/2.====>通過(guò)定理我們知道，在m=n2的全域散列表中更大的可能是不發(fā)生碰撞。給定待散列的包含n個(gè)關(guān)鍵字的集合K（注意K是靜態(tài)的），只需幾次隨機(jī)的嘗試，即能比較容易的找出一個(gè)沒(méi)有碰撞的散列函數(shù)h。但是當(dāng)n比較大時(shí)，一個(gè)大小m=n2的散列表還是很大的。因此我們采用二次散列的方法，并利用定理11.9中所述的方法，對(duì)每個(gè)槽中的關(guān)鍵字進(jìn)行僅一次散列。一個(gè)外層的（或稱(chēng)一級(jí)的）散列函數(shù)h用于將各關(guān)鍵字散列到m=n個(gè)槽中。那么，如果有nj（j為下標(biāo)）個(gè)關(guān)鍵字被散列到槽j中的話，可以用一個(gè)大小mj?= nj2的二次散列表Sj來(lái)提供無(wú)碰撞的常亮?xí)r間查找。
????下面的定理說(shuō)明如何確保期望使用的總體存儲(chǔ)空間(即主散列表和所有的二次散列表所占的空間)為O(n)。
? ? 定理11.10：如果從某一個(gè)全域散列函數(shù)類(lèi)中隨機(jī)選出散列函數(shù)hh，用它將nn個(gè)關(guān)鍵字存儲(chǔ)在一個(gè)大小為m=nm=n的散列表中，則有E[∑m?1j=0n2j]<2nE[∑j=0m?1nj2]<2n，這里njnj為散列到槽jj中的關(guān)鍵字?jǐn)?shù)。
? ??推論11.11：如果從某一全域散列函數(shù)類(lèi)中隨機(jī)選出散列函數(shù)hh，用它將nn個(gè)關(guān)鍵字存儲(chǔ)在一個(gè)大小m=nm=n的散列表中，并將每一個(gè)二級(jí)散列表的大小設(shè)置為mj=n2j(j=0,1,...,m?1)mj=nj2(j=0,1,...,m?1)，則在一個(gè)完全散列方案中，存儲(chǔ)在所有二次散列表中所需的存儲(chǔ)總量的期望值小于2n2n。
? ??推論11.12：如果從某一個(gè)全域散列函數(shù)類(lèi)中隨機(jī)選出散列函數(shù)hh，用它將nn個(gè)關(guān)鍵字存儲(chǔ)到一個(gè)大小為m=nm=n的散列表中，并將每個(gè)二級(jí)散列表的大小置為mj=n2j(j=0,1,...,m?1)mj=nj2(j=0,1,...,m?1)，則用于存儲(chǔ)所有二級(jí)散列表的存儲(chǔ)總量等于或大于4n4n的概率小于1/21/2。===>從推論2中可以看出，只需從全域散列函數(shù)類(lèi)中隨機(jī)選出幾個(gè)散列函數(shù)，嘗試幾次就可以快速地找到一個(gè)所需存儲(chǔ)量較為合理的函數(shù)。===>完全散列最壞存儲(chǔ)為4n，期望為2n，我認(rèn)為有一點(diǎn)空間換時(shí)間的味道。
參考：
? ? 1、算法導(dǎo)論讀書(shū)筆記（11）
? ? 2、對(duì)《算法導(dǎo)論》完全散列的分析
? ? 3、淺談散列
