散列表

直接尋址表

???????? 一個數組T[0..m-1]中的每個位置分別對應全域U中的一個關鍵字，槽k指向集合中一個關鍵字為k的元素，如果該集合中沒有關鍵字為k的元素，則T[k] = NIL

全域U={0,1,…,9}中的每個關鍵字都對應于表中的一個下標值，由實際關鍵字構成的集合K={2,3,5,8}決定表中的一些槽，這些槽包含指向元素的指針，而另一些槽包含NIL?

????????

???????? 直接尋址的技術缺點非常明顯：如果全域U很大，則在一臺標準的計算機可用內存容量中，要存儲大小為|U|的一張表T也許不太實際，甚至是不可能的。還有，實際存儲的關鍵字集合K相對于U來說可能很小，使得分配給T的大部分空間都將浪費掉，此時可以使用散列表改進。

散列表

???????? 在直接尋址方式下，具有關鍵字k的元素被存放在槽k中，在散列方式下，該元素存放在h(k)中；即利用散列函數h，由關鍵字k計算出槽的位置，這里，函數h將關鍵字的全域U映射到散列表T[0,..,m-1]的槽位上。

h : U???? {0,…,m-1}

???????? 這里散列表的大小m一般要比|U|小得多，可以說一個具有關鍵字k的元素被散列到槽h(k)上

?

?

???????? 這里存在一個缺點：兩個關鍵字可能映射到同一個槽中，這種情形稱為沖突，解決沖突的方法有很多。

解決沖突

鏈接法

???????? 在鏈接法中，把散列到同一槽中的所有元素都放在一個鏈表中，如下圖所示，槽j中有一個指針，它指向存儲所有散列到j的元素的鏈表的表頭；如果不存在這樣的元素，槽j中為NIL

?

鏈表可以是單鏈表，但雙鏈表的刪除操作會更快

分析（查找一個關鍵字）

???????? 給定一個能存放n個元素的，具有m個槽位的散列表T，定義T的裝載因子α為n/m，即一個鏈表的平均存儲元素數量，α可以大于，等于或者小于1.

???????? 用鏈接法散列的最壞情況性能很差：所有的n個關鍵字都散列到同一個槽中，從而產生一個長度為n的鏈表，這時，最壞情況下查找時間為θ(n)，再加上計算散列函數的時間，如果就和用一個鏈表來鏈接所有的元素差不多了。

???????? 散列方法的平均性能依賴于所選取的散列函數h，將所有關鍵字集合分布在m個槽位上的均勻程度。

???????? 在平均情況下，查找一個關鍵字有兩個結果：查找成功和查找不成功。

???????? 在簡單均勻散列的情況下，任何尚未被存儲在表中的關鍵字k都等可能地被散列到m個槽中的任何一個，因此，當查找一個關鍵字k時，在不成功的情況下，查找的期望時間就是查找到鏈表T[h(k)]末尾的期望時間，這一時間的期望長度為α，于是一次不成功的查找平均要檢查α個元素，并且所需要的總時間（包括計算h(k)的時間）為θ(1+α)

???????? 在查找成功的情況下，平均需要的時間也是θ(1+α)，具體證明參考《算法導論》中文版146頁。

總結

???????? 上述的分析意味著，如果散列表中槽數至少與表中的元素成正比（比如說，當要散列的元素的數量增加時，散列表T的槽數也要保持同樣比例的增長），則有

n = Ο(m)，從而α= n/m = Ο(m) / m = Ο(1)，所以查找操作平均時間需要常數時間。如果散列的元素的數量增加了，但是散列表的槽數沒有增長，此時n = Ο(m)就不成立，散列表的操作時間就和之前的不一樣了。

開放尋址法

???????? 在開放尋址法中，所有的元素都存放在散列表中，也就是說，每個表項或包含動態集合的一個元素，或包含NIL。當查找某個元素時，要系統地檢查所有的表項，知道查找到所需要的元素，或者最終查明該元素不在表中。不像鏈接法，這里既沒有鏈表，也沒有元素存放在散列表外，因此在開放尋址法中，散列表可能會被填滿，以至于不能插入任何新的元素，因此裝載因子α = n / m絕對不會超過1，也就是說，要散列的元素絕對不會多于槽的數量。

探查方式

線性探查

???????? 給定一個普通的散列函數 h ' : U → { 0， 1， …， m - 1 }（稱為輔助散列函數），線性探查方法采用的散列函數為：

?????????????????? h ( k ， i ) = ( h '( k ) + i ) mod m ， i = 0， 1， …， m - 1

???????? 給定一個關鍵字 k ，第一個探查的槽是 T [ h '( k ) ]，亦即，由輔助散列函數所給出的槽。接下來探查的是槽 T [ h ' ( k ) + 1 ]， …，直到槽 T [ m - 1 ]，然后又繞到槽 T [ 0 ]， T [ 1 ]， …直到最后探查槽 T [ h ' ( k ) - 1 ]。在線性探查方法中，初始探查位置確定了整個序列，故只有 m 種不同的探查序列。

???????? 線性探查方法很容易實現，但它存在一個問題，稱作一次群集。隨著時間的推移，連續被占用的槽不斷增加，平均查找時間也隨著不斷增加。群集現象很容易出現，這是因為當一個空槽前有 i 個滿的槽時，該空槽作為下一個將被占用槽的概率是( i + 1 ) / m 。連續被占用槽的序列將會越來越長，因而平均查找時間也會隨之增加。

二次探查

???????? 二次探查采用如下形式的散列函數：

??????????????????????????? h ( k ， i ) = ( h ' ( k ) + c₁ i + c₂i²) mod m

???????? 其中 h '是一個輔助散列函數， c₁ 和 c₂ 為輔助常數（不等于0）， i = 0， 1， …， m - 1。初始的探查位置為 T [ h '( k ) ]，后續的探查位置要在此基礎上加上一個偏移量，該偏移量以二次的方式依賴于探查號 i 。這種探查方法的效果要比線性探查好很多，但是，如果兩個關鍵字的初始探查位置相同，那么他們的探查序列也是相同的，這是因為 h ( k1 ， 0 ) = h ( k2 ， 0 )蘊含著 h ( k1 ， i ) = h ( k2 ， i )。這一性質可導致一種程度較輕的群集現象，稱為 二次群集。二次探查也只有 m 個不同的探查序列。

雙重散列

???????? 雙重散列?是用于開放尋址法的最好方法之一，它采用如下形式的散列函數：

h?(?k?，?i?) = (?h₁?(?k?) +?i h₂?(?k?) ) mod?m

???????? 其中?h₁?和?h₂?為輔助散列函數。初始探查位置為?T?[?h₁?(?k?) ]，后續的探查位置在此基礎上加上偏移量?h₂?(?k?)模?m?。

???????? 為能查找整個散列表，值?h₂?(?k?)要與表的大小?m?互質。確保這個條件成立的一種方法是取?m?為 2 的冪，并設計一個總產生奇數的?h₂?。另一種方法是取?m?為質數，并設計一個總是產生較?m?小的正整數的函數?h₂?。例如，可以取m為素數，m^’略小于m，如下：

h₁ ( k ) = k mod m, ??h₂ ( k ) = 1 + ( k mod m^’ )

???????? 雙重散列法中用了?Θ?(?m²?)中探查序列。

分析

???????? 相對于鏈接法，開放尋址法的好處在于不需要用到指針，而是計算出槽的序列，于是，不用存儲指針而節省的空間，使得可以用同樣地空間來提供更多的槽，潛在地減少了沖突，提高了檢索速度。

???????? 從開放尋址法的散列表中刪除元素比較困難，當從槽i中刪除關鍵字時，不能僅僅將NIL置于其中來標識它為空，如果這樣做就會出現問題：在插入關鍵字k時，發現槽i被占用了，則k會插入到后面的位置上；此時將槽i中的關鍵字刪除后，就無法檢索到關鍵字k了，有一個解決方法就是，在槽i中置一個特定的值DELETED替代NIL來標記空槽。當使用特殊的值DELETED時，查找時間就不再依賴于裝載因子了，為此，在必須刪除關鍵字的應用中，更常見的方法是采用鏈接法來解決沖突。

???????? 給定一個裝載因子為α = n / m，α<1，的開放尋址散列表，并假設是均勻散列的，則對于一次不成功的查找，其期望的探查次數至多為1 / (1 – α)。具體證明參考《算法導論中文版》P155.

???????? 1/(1 - α) = 1 + α + α² + α³ + … 這個界有一個直觀的解釋，無論如何，總要進行第一次探查，第一次探查發現的是一個已經占用的槽時，必須要進行第二次探查，進行第二次探查的概率大約為α，前兩次探查所發現的槽均已被占用時，進行第三次探查的概率大約為α²，等等

???????? 如果α是一個常數，一次不成功查找的運行時間為Ο(1)，例如，如果散列表一半是滿的，一次不成功查找的平均探查次數至多為1 / ( 1- 0.5) = 2，如果散列表90%是滿的，則平均探查次數至多為1 / ( 1 – 0.9) = 10

???????? 假設采用的是均勻散列，平均情況下，向一個裝載因子為α的開放尋址散列表中插入一個元素之多需要做1/(1 - α)次探查，因為插入一個關鍵字首先要做一次不成功查找，所以插入元素的時間和一次不成功的探查時間相同。

???????? 對于一個裝載因子為α<1的開放尋址散列表，一次成功查找中的探查期望數至多為(1/α)ln(1/(1-α))。具體證明參考《算法導論中文版》P155.如果散列表是半滿的，則一次成功的探查中，探查的期望數小于1.39，如果散列表為90%滿的，則探查的期望數小于2.56

散列函數

除法散列法

???????? 在?除數散列法?中，通過取?k?除以?m?的余數，來將關鍵字?k?映射到?m?個槽的某一個中去。亦即，散列函數為：

h?(?k?) =?k?mod?m

???????? 當應用除數散列時，要注意?m?的選擇，可選的?m?值通常是與 2 的整數冪不太接近的質數。

乘法散列法

???????? 乘法散列法?包含兩個步驟。第一步，用關鍵字?k?乘上常數?A?（0 <?A?< 1），并抽取出?k A?的小數部分。然后，用?m?乘以這個值，再向下取整。散列函數為：

h?(?k?) = floor(?m?(?k A?mod 1 ))

???????? floor()函數為向下取整的意思。乘法方法的一個優點是對?m?的選擇沒有什么特別的要求，一般選擇它為 2 的冪（?m?=?2^p?，?p?為某個整數）。

???????? 例如：h ( k ) = ( A * k mod 2^w) rsh (w – r)，其中w為計算機的位數（32或者64位），m為槽的數量，rsh(w – r)意思為向右移位w – r 位，A是一個奇數，并且2^w-r < A < 2^w，m = 2^r

全域散列法

???????? 任何的散列函數都可能出現最壞情況性態，即?n?個關鍵字都散列到同一個槽中，使得平均的檢索時間為?Θ?(?n?)：唯一有效的改進方法是隨機地選擇散列函數，使之獨立于要存儲的關鍵字。這種方法稱作全域散列。

???????? 全域散列的基本思想是在執行開始時，就從一組仔細設計的函數中，隨機地選擇一個作為散列函數。隨機化保證了沒有哪一種輸入會始終導致最壞情況性態。同時，隨機化使得即使是對同一個輸入，算法在每一次執行時的性態也是不一樣的。這樣就可以確保對于任何輸入，算法都具有良好的平均情況性態。

???????? 設?H?為有限的一組散列函數，它將給定的關鍵字域?U?映射到{ 0， 1， …，?m?- 1 }。這樣的一組函數稱為是?全域的?，如果對每一對不同的關鍵字?k?，?l?∈?U?，滿足?h?(?k?) =?h?(?l?)的散列函數?h?∈?H?的個數至多為 |?U?| /?m?。換言之，如果從?H?中隨機選擇一個散列函數，當關鍵字?k?≠?l?時，兩個發生碰撞的概率不大于 1 /?m?，這也正是從集合{ 0， 1， …，?m?- 1 }中隨機地，獨立地選擇?h?(?k?)和?h?(?l?)時發生碰撞的概率。

???????? 如果?h?選擇一組全域的散列函數，并用于將?n?個關鍵字散列到一個大小為?m?的，用鏈接法解決碰撞的表?T?中。如果關鍵字?k?不在表中，則?k?被散列至其中的鏈表的期望長度E[?n_h(k)?]至多為?α?。如果關鍵字?k?在表中，則包含關鍵字?k?的鏈表的期望長度E[?n_h(k)?]至多為 1 +?α?。

???????? 對于一個具有?m?個槽位的表，利用全域散列和鏈接法解決碰撞，需要?Θ?(?n?)的期望時間來處理任何包含了?n?個?INSERT，?SEARCH?，?DELETE?操作的操作序列，該序列中包含了?O?(?m?)個?INSERT?操作。

設計一個全域散列函數類

　　1.選擇一個素數，用m表示

　　2.把k分解成r+1位的數，k = <k₀, k_1, k₂, … k_r>??? 0 <= k_r <= m-1

　　3.選擇一個數a = <a₀ , a₁ , … , a_r >,每一個a_i都從{0, 1, … , m-1}中隨機選擇

　　4.H_a ( k ) = mod m

完全散列

???????? 可以采用兩級的散列方法來設計完全散列方案，在每級上都使用全域散列，如下圖所示：

外層的散列函數為h(k) = ((ak + b) mod p)mod m，一個二級散列表S_j中存儲了所有散列到槽j中的關鍵字，其大小為m_j=n_j²,并且相關的散列函數為h_j(k) = ((a_jk + b_j)mod p)mod m_j

?

???????? 第一級與帶連接的散列表基本上一樣：利用從某一全域組中仔細選出的一個散列函數h，將n個關鍵字散列到m個槽中。

???????? 然而，采用一個較小的二次散列表S_j，及相關的散列函數h_j，而不是將散列到槽j中的所有關鍵字建立一個鏈表，利用精心選擇的散列函數h_j，可以確保在第二級上不出現沖突。

???????? 為了確保第二級上不出現沖突，需要讓散列表S_j的大小m_j為散列到槽j中的關鍵字數n_j的平方，盡管m_j對n_j的這種二次依賴看上去可能使得總體存儲需求很大，但是可以通過適當地選擇第一級散列函數，可以將預期使用的總體存儲空間限制為Ο(n)。

二級散列沖突的概率

???????? 如果從一個全域散列函數類中隨機選出散列函數h，將n個關鍵字存儲在一個大小為m = n²的散列表中，那么表中出現沖突的概率小于1/2

???????? 上述定理的意思：對于一個從H中隨機選出的散列函數h，較有可能不會發生沖突，給定待散列的包含n個關鍵字的集合K，只需要幾次隨機的嘗試，就能比較容易地找出一個沒有沖突的散列函數h。

完全散列所需空間

???????? 如果從某一個全域散列函數類中隨機選出散列函數h，用它將n個關鍵字存儲到一個大小為m = n的散列表中，并將每個二次散列表的大小設置為m_j = n_j²，則在一個完全散列方案中，存儲所有二次散列表所需要的存儲總量的期望值小于2n

?

轉載于:https://www.cnblogs.com/eagle159/p/3875502.html

總結

以上是生活随笔為你收集整理的散列表（算法导论笔记）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。