散清單---算法導論第十一章 Hash Tables

一、散清單概念

1、 直接尋址表

直接将關鍵字作為數組下标。複雜度O(1)

2、 散清單

k->h(k)

降低了空間開銷，會産生碰撞，解決碰撞的簡單方法是連結法。

對連結法散列，平均情況下，複雜度也是O(1)

3、 散列函數

1） 除法散列法

h(k)=k mod m，m最好選取與2的整數幂不太接近的質數

2） 乘法散列法

h(k)=[m(kA mod 1)], A為一個常數(0 < A < 1)。

乘法方法的優點是對m的選擇沒有什麼特别的要求，一般選擇它為2的某個幂次。

3） 全域散列(universal hashing)

在執行開始時，從一族仔細設計的函數中，随機地選擇一個作為散列函數。這裡的随機選擇針對的是一次對散清單的應用，而不是一次簡單的插入或查找操作。散列函數的确定性，是查找操作正确執行的保證。全域散列法確定，當k!=l時，兩者發生碰撞的機率不大于1/m。設計一個全域散列函數類的方法如下，該方法中，散清單大小m的大小是任意的。

選擇一個足夠大的質數p，使得每一個可能的關鍵字都落在到p-的範圍内。設Zp表示集合{,
, …, p-}，Zp*表示集合{, , …, p-}。假定關鍵字全域的大小大于散清單中的槽
數，故有p>m。對于任何a∈Zp*和任何b∈Zp，定義散列函數ha,b(k)：
ha,b(k) = ((ak+b) mod p) mod m
所有這樣的散列函數構成的函數族為：
Hp,m = {ha,b : a∈Zp*和b∈Zp}
每一個散列函數ha,b都将Zp映射到Zm。由于對a來說有p-種選擇，對于b來說有p種選擇，因
而，Hp,m中共有p(p-)個散列函數。
在一次散清單應用中，a、b是随機生成的在一定範圍的數。舉個例子：若p=,m=,此次散列
應用中随機生成a=,b=則h3,（）=
           

4、 完全散列

一種兩級的散列方案

每一級上都采用全域散列。

第一級将n個關鍵字散列到m個槽中，每個槽j中有一個較小的二次散清單Sj。通過仔細的選擇第二級散列函數，可以確定在第二級上不出現碰撞。

期望使用的總體存儲空間為O(n)

二、散列函數構造方法

1、散列函數的選擇有兩條标準：簡單和均勻。

　 簡單指散列函數的計算簡單快速；均勻指對于關鍵字集合中的任一關鍵字，散列函數能以等機率将其映射到表空間的任何一個位置上。也就是說，散列函數能将子集K随機均勻地分布在表的位址集{0，1，…，m-1}上，以使沖突最小化。

2、常用散列函數

為簡單起見，假定關鍵字是定義在自然數集合上。其它關鍵字可以轉換到自然數集合上。

（1）平方取中法

具體方法：先通過求關鍵字的平方值擴大相近數的差别，然後根據表長度取中間的幾位數作為散列函數值。又因為一個乘積的中間幾位數和乘數的每一位都相關，是以由此産生的散列位址較為均勻。

【例】将一組關鍵字(0100，0110，1010，1001，0111)平方後得 (0010000，0012100，1020100，1002001，0012321) ，若取表長為1000，則可取中間的三位數作為散列位址集：(100，121，201，020，123)。

相應的散列函數用C實作很簡單：

int Hash(int key){ //假設key是4位整數

key *= key； key /= 100； //先求平方值，後去掉末尾的兩位數

return key％1000； //取中間三位數作為散列位址傳回

}

（2）除餘法

該方法是最為簡單常用的一種方法。它是以表長m來除關鍵字，取其餘數作為散列位址，即 h(key)=key％m。該方法的關鍵是選取m。選取的m應使得散列函數值盡可能與關鍵字的各位相關。m最好為素數。

【例】若選m是關鍵字的基數的幂次，則就等于是選擇關鍵字的最後若幹位數字作為位址，而與高位無關。于是高位不同而低位相同的關鍵字均互為同義詞。

【例】若關鍵字是十進制整數，其基為10，則當m=100時，159，259，359，…，等均互為同義詞。

（3）相乘取整法

。。。

三 、解決沖突方法

通常有兩類方法處理沖突：開放尋址(Open Addressing)法和連結(Chaining)法。前者是将所有結點均存放在散清單T[0..m-1]中；後者通常是将互為同義詞的結點鍊成一個單連結清單，而将此連結清單的頭指針放在散清單T[0..m-1]中。

1、 開放尋址法

開放尋址法指所有的元素都存放在散清單裡。

在開放尋址法裡，當要插入一個元素時，可以連續地檢查散清單的各項，直到遇到一個空槽存放待插入的關鍵字。對每一個關鍵字k，探查序列 < h(k,0),h(k,1),…h(k,m-1) > 必須是< 0,1,..,m-1 >的一個排列。

僞代碼

HASH­-INSERT(T,k)

i <- 
repeat j <- h(k,i)
      if T[j] = NIL
           then T[j] <- k
                 return j
           else i <- i+
  until i=m
error “hash table overflow”
           

僞代碼

HASH­-SEARCH(T,k)

i <- 
repeat j <- h(k,i)
      if T[j] = k
           then return j
      i <- i+
  until i =m or T[j]=NIL
return NIL
           

按照形成探查序列的方法不同，可将開放尋址法區分為線性探查法、二次探查法、雙重散列法等。

1） 線性探查Linear Probing

h(k,i)=(h’(k)+i) mod m, i=0,1,…,m-1

初始探查位置确定了整個序列，隻有m種不同的探查序列。

該方法的基本思想是：将散清單T[0..m-1]看成是一個循環向量，若初始探查的位址為d(即h(key)=d)，則最長的探查序列為：d，d+l，d+2，…，m-1，0，1，…，d-1 .即:探查時從位址d開始，首先探查T[d]，然後依次探查T[d+1]，…，直到T[m-1]，此後又循環到T[0]，T[1]，…，直到探查到T[d-1]為止。探查過程終止于三種情況：

　(1)若目前探查的單元為空，則表示查找失敗（若是插入則将key寫入其中）；

　(2)若目前探查的單元中含有key，則查找成功，但對于插入意味着失敗；

　(3)若探查到T[d-1]時仍未發現空單元也未找到key，則無論是查找還是插入均意味着失敗(此時表滿)。

　

存在問題，一次群集，即随着時間的推移，連續被占用的槽不斷增加，平均查找時間也随着不斷增加。

【例9.1】已知一組關鍵字為(26，36，41，38，44，15，68，12，06，51)，用除餘法構造散列函數，用線性探查法解決沖突構造這組關鍵字的散清單。

　　解答:為了減少沖突，通常令裝填因子α < l。這裡關鍵字個數n=10，不妨取m=13，此時α≈0.77，散清單為T[0..12]，散列函數為：h(key)=key％13。由除餘法的散列函數計算出的上述關鍵字序列的散列位址為(0，10，2，12，5，2，3，12，6，12)。前5個關鍵字插入時，其相應的位址均為開放位址，故将它們直接插入T[0]，T[10)，T[2]，T[12]和T[5]中。當插入第6個關鍵字15時，其散列位址2(即h(15)=15％13=2)已被關鍵字41(15和41互為同義詞)占用。故探查h1=(2+1)％13=3，此位址開放，是以将15放入T[3]中。當插入第7個關鍵字68時，其散列位址3已被非同義詞15先占用，故将其插入到T[4]中。當插入第8個關鍵字12時，散列位址12已被同義詞38占用，故探查hl=(12+1)％13=0，而T[0]亦被26占用，再探查h2=(12+2)％13=1，此位址開放，可将12插入其中。類似地，第9個關鍵字06直接插入T[6]中；而最後一個關鍵字51插人時，因探查的位址12，0，1，…，6均非空，故51插入T[7]中。

　 用線性探查法解決沖突時，當表中i,i+1，…，i+k的位置上已有結點時，一個散列位址為i，i+1，…，i+k+1的結點都将插入在位置i+k+1上。把這種散列位址不同的結點争奪同一個後繼散列位址的現象稱為聚集或堆積(Clustering)。這将造成不是同義詞的結點也處在同一個探查序列之中，進而增加了探查序列的長度，即增加了查找時間。若散列函數不好或裝填因子過大，都會使堆積現象加劇。

【例】上例中，h(15)=2，h(68)=3，即15和68不是同義詞。但由于處理15和同義詞41的沖突時，15搶先占用了T[3]，這就使得插入68時，這兩個本來不應該發生沖突的非同義詞之間也會發生沖突。

　 為了減少堆積的發生，不能像線性探查法那樣探查一個順序的位址序列(相當于順序查找)，而應使探查序列跳躍式地散列在整個散清單中。

　

2） 二次探查Quadratic Probing

該方法是開放定址法中最好的方法之一，它的探查序列是

h(k,i)=(h’(k)+a*i+b*i^2) mod m

初始探查位置确定了整個序列，隻有m種不同的探查序列。

存在問題，程度較輕的群集現象，二次群集

3） 雙重散列Double Hashing

該方法是開放定址法中最好的方法之一，它的探查序列是：

h(k,i)=(h1(k)+i*h2(k)) mod m

為能查找整個散清單，h2(k)要與表的大小m互質。

【例】若m為素數，則h2(key)取1到m-1之間的任何數均與m互素，是以，我們可以簡單地将它定義為：h2(key)=key％(m-2)+1

【例】對例9.1，我們可取h1(key)=key％13，而h2(key)=key％11+1。

【例】若m是2的方幂，則h2(key)可取1到m-1之間的任何奇數。

用了O(m^2)種探查序列

2、連結法

（1）連結法解決沖突的方法

　 連結法解決沖突的做法是：将所有關鍵字為同義詞的結點連結在同一個單連結清單中。若標明的散清單長度為m，則可将散清單定義為一個由m個頭指針組成的指針數組T[0..m-1]。凡是散列位址為i的結點，均插入到以T[i]為頭指針的單連結清單中。T中各分量的初值均應為空指針。在連結法中，裝填因子α可以大于1，但一般均取α≤1。

連結法示意圖：

【例9.2】已知一組關鍵字和標明的散列函數和例9.1相同，用連結法解決沖突構造這組關鍵字的散清單。

　　解答：不妨和例9.1類似，取表長為13，故散列函數為h(key)=key％13，散清單為T[0..12]。 注意：當把h(key)=i的關鍵字插入第i個單連結清單時，既可插入在連結清單的頭上，也可以插在連結清單的尾上。這是因為必須确定key不在第i個連結清單時，才能将它插入表中，是以也就知道鍊尾結點的位址。

（2）連結法的優點

　 與開放定址法相比，連結法有如下幾個優點：(1)連結法處理沖突簡單，且無堆積現象，即非同義詞決不會發生沖突，是以平均查找長度較短；(2)由于連結法中各連結清單上的結點空間是動态申請的，故它更适合于造表前無法确定表長的情況；(3)開放定址法為減少沖突，要求裝填因子α較小，故當結點規模較大時會浪費很多空間。而連結法中可取α≥1，且結點較大時，連結法中增加的指針域可忽略不計，是以節省空間；(4)在用連結法構造的散清單中，删除結點的操作易于實作。隻要簡單地删去連結清單上相應的結點即可。而對開放位址法構造的散清單，删除結點不能簡單地将被删結點的空間置為空，否則将截斷在它之後填人散清單的同義詞結點的查找路徑。這是因為各種開放位址法中，空位址單元(即開放位址)都是查找失敗的條件。是以在用開放位址法處理沖突的散清單上執行删除操作，隻能在被删結點上做删除标記，而不能真正删除結點。

（3）連結法的缺點

　 連結法的缺點是：指針需要額外的空間，故當結點規模較小時，開放定址法較為節省空間，而若将節省的指針空間用來擴大散清單的規模，可使裝填因子變小，這又減少了開放定址法中的沖突，進而提高平均查找速度。

參考：http://www.cnblogs.com/zhanglanyun/archive/2011/09/01/2161729.html