散列

文章目錄

• 散列的基本概念
• 一、散列函數的設計
• 二、幾個散列函數
• • 1.除餘法(division method)
  • 2.MAD法(Multiply-add-divide method)
  • 3.數字分析法
  • 4.随機數法
• 二、沖突解決辦法
• • 1.封閉定址法(closed addressing)
  • 1.開放定址法(open addressing)
• 總結

散列的基本概念

什麼是散列？為什麼需要散列？

散列是一種思想。與已經學過的其他資料結構相比較，向量是采用循秩通路(call by rank)的通路方式，清單是采用循位置通路(call by position)的通路方式，二叉搜尋樹是采用循關鍵碼通路(call by key)的通路方式，散列與他們都不一樣，是采用循值通路(call by value)的通路方式。

舉個例子，你現在身處哪裡也不是的場所的中央，四周一片沉默，仿佛全世界所有細雨落到全世界所有草坪上，這個時候你想回家了。沿世界上所有的街道一間一間房找過去，這是循秩通路；你記得你家是住在某省某市某街道多少号，然後你可以依次先到某省，再到某市，再到某條街道，然後找到你家，這是循關鍵碼通路；而循值通路，則是你通常會采用的方法——你根本不用去回想我家的位址是多少，你知道它就在那裡，就在家這個詞剛剛出現在你的腦海中的時候。想到家鄉，你想到的不是位址或者一串數字，而是一個生動的影像，包含它的環境，四周的風物，以及曾經的朋友。這就是循值通路。

可以看到，相對于其他的通路方式，循值通路是将被通路對象的數值，與它在容器中的位置之間，直接建立了一個映射關系，進而對于任何對象的基本操作（通路，插入，删除）都隻需要常數O(1)的時間，達到了最理想的境地。這就是人類需要散列的原因，你無法不被如此的誘惑所吸引。

完美散列

在時間與空間性能上均達到完美的散列，稱為完美散列。

也就是說，對于完美散列，其中的每一個值，都可以唯一地映射到散清單中的一個位置，既無空餘，亦無重複。從映射角度來看，完美散列是一個單射，同時也是一個滿射。Bitmap就是完美散列的一個例子。

可以看出，完美散列實際中并不常見，在大多數的情形下，關鍵碼的取值是遠遠大于詞條的個數的，設關鍵碼的取值為[ 0 , R ) [0, R)[0,R), 詞條的個數為N NN，則R > > N R >> NR>>N。設散清單的大小為M MM，此時，從定義域[ 0 , R ) [0, R)[0,R)到值域[ 0 , M ) [0, M)[0,M)的映射不可能是單射，即不可避免地會出現不同的關鍵碼映射到散清單中的同一個位置，即所謂沖突。是以就需要合理地選擇這一個映射關系，即散列函數，使沖突出現的可能性最小；同時還應該事先約定好一旦出現這種沖突，應該采取的解決方案。這兩個問題将在下面重點讨論，即散列函數的設計與沖突解決方案。

一、散列函數的設計

散列函數的設計方案？什麼是好的散列函數？

前面提到，從詞條空間到位址空間的映射，即散列函數，絕對不可能是單射，沖突是一定不可能避免的，但是好的散列函數應該保證盡可能地少出現沖突。由此，可以提煉出散列函數的幾個設計名額。

确定性。散列函數确定的條件下，同一個關鍵碼應該總是映射到同一個位址，這樣才滿足一個函數的定義。

快速性。是指散列位址的計算過程要盡可能快，要能在常數時間内完成。

滿射。好的散列函數最好是一個滿射，這樣可以充分利用散列空間，盡可能地減少沖突的發生。

均勻性。也是為了減少沖突的發生，關鍵碼被映射到各個散列位址的機率應該接近于1 / M 1/M1/M，這樣可以防止彙聚(clustering)現象的發生，即關鍵碼隻被映射到少數的幾個散列位址，在局部加劇散列沖突，全局的散列空間也沒有得到充分地利用。

總之，為了保證沖突盡可能地少，散列函數越是随機，越是沒有規律越好。

二、幾個散列函數

1.除餘法(division method)

除餘法的整體思路非常簡單，即用關鍵碼的值對散清單的長度M MM取餘，即h a s h ( k e y ) = k e y m o d M hash(key) = key\ mod\ Mhash(key)=key mod M，這樣可以将關鍵碼映射到整個散列空間上。

這裡問題的關鍵在于散清單長度M MM的選擇。考慮有一組資料，其中的關鍵碼以固定步長S SS變化（實際中的資料往往就是這種形式的，而不是随機的，例如for循環一般就是固定步長的資料）。設第i ii個資料第一次與第j jj個資料的關鍵碼發生沖突，即

S × i ≡ S × j ( m o d M ) S\times i \equiv S\times j\ (mod M)

S×i≡S×j (modM)

即S i SiSi與S j SjSj是同餘類，是以

S ( j − i ) ≡ 0 ( m o d M ) S(j - i) \equiv 0 \ (mod M)

S(j−i)≡0 (modM)

由此可解得

j − i = M g c d ( M , S ) g c d f o r G r e a t e s t C o m m o n D i v i s o r j - i = \frac{M}{gcd(M, S)}\ gcd\ for\ Greatest\ Common\ Divisor

j−i=

gcd(M,S)

M

​

gcd for Greatest Common Divisor

根據上面對散列函數設計要求的分析，我們是希望散列函數可以盡可能地減少沖突，即這裡的j − i j - ij−i盡可能地大，就需要保證M MM和S SS的最大公因數要盡可能小，是以M MM要和S SS互質。但是由于散清單存儲的不同資料具有不同的步長S SS值，要使M MM與所有可能的步長S SS互質，隻有當M MM本身就是一個素數才可能實作。

2.MAD法(Multiply-add-divide method)

上面的除餘法還存在着一些問題。

首先，除餘法得到的散列位址，依然存在一定程度的連續性，即原來相鄰的關鍵碼對應的散列位址也仍然是相鄰的；其次，在除餘法中關鍵碼較小的那些詞條，始終被映射到散清單的起始區段，其中關鍵碼為零的元素，其散列位址總是零，即是一個不動點，這顯然違背了散列函數應該越随機，越沒有規律越好的原則。MAD法正是對除餘法上述問題的一個改進。

MAD法，顧名思義，就是對于關鍵碼，依次執行乘法、加法和模餘運算，即

h a s h ( k e y ) = ( a × k e y + b ) m o d M hash(key) = (a \times key + b)\ mod\ M

hash(key)=(a×key+b) mod M

這樣，隻要适當選擇a , b a, ba,b，MAD法可以很好的克服除餘法原有的連續性缺陷，其中參數a aa的作用是使相鄰關鍵碼的散列位址更加分散，b bb的作用是作為一個偏移量，去掉不動點。

3.數字分析法

遵循散列函數越是随機沒有規律，就越好的原則，引入了數字分析法，即對于關鍵碼key的特定進制展開，抽取其中的幾位，映射到一個散列位址。

比較簡單的情形就是取十進制展開中的奇數位，作為散列位址，例如

h a s h ( 123456789 ) = 13579 hash(123456789) = 13579

hash(123456789)=13579

除此以外，還有平方取中法，即對于關鍵碼k e y keykey取平方，然後截取中間的幾位來作為散列位址。之是以選擇中間的幾位，是因為中間的幾位是受到了原來的關鍵碼更多數位的影響；相對于取高位數字（隻受到原關鍵碼高位數字影響）或者低位數字（隻受到原關鍵碼低位數字影響），取中間位數綜合了更多位數的影響，是以随機性、均勻性更強，更不易出現沖突。

此外，還有折疊法，往複折疊法。

為了保證經過這些方法得到的值仍然落在散列空間以内，通常還都需要對散清單長度M MM再取餘。

4.随機數法

既然散列函數是随機性越強越好，那一個簡明的思想是直接利用生成的僞随機數來構造散列位址。這樣的話，任意一個僞随機數發生器本身就是一個好的散列函數了。即

h a s h ( k e y ) = r a n d ( k e y ) m o d M hash(key) = rand(key)\ mod\ M

hash(key)=rand(key) mod M

其中，r a n d ( k e y ) rand(key)rand(key)是系統定義的第k e y keykey個僞随機數。

`

二、沖突解決辦法

無論如何精心設計的散列函數，都不能完全地避免沖突的發生，随着資料量的增大，沖突的發生幾乎是必然的。是以，就需要事先規定好沖突發生時的解決方案，進而保證散清單的正常工作。

1.封閉定址法(closed addressing)

多槽位法(multiple slots)

所謂沖突發生不過是不同的關鍵碼被散列函數映射到同一個散列位址，既然如此，那我們事先為可能到來的、沖突的關鍵碼預留一個位置不就可以了嗎？這種簡明的思想就是多槽位法。

多槽位法就類似于一山二虎，将原來對應一個關鍵碼的桶單元，劃分為若幹更小的槽位，進而可以容納後續到來的沖突的關鍵碼。

顯而易見，這種方法具有緻命的缺陷，即你永遠也不知道槽位應該細分到何種程度，才能保證在任何情況下都夠用。槽位劃分太多的話，空間使用率會非常低；槽位劃分不夠，又不足以應對可能出現的沖突。此外，在極端條件下，當資料量非常大的時候，無論再多的槽位，也仍然有可能會産生溢出。

獨立鍊法(separate chaining)

多槽位法所面臨的問題，其實就是類似于數組這種靜态資料結構所面臨的問題，即在實際應用之前，你不會清楚數組的大小應該劃分到多大。采用連結清單可以有效的解決數組空間不足的問題，而将連結清單應用到散清單的沖突解決方案，就成為了獨立鍊法。

獨立鍊法與多槽位法的核心思想是完全相同的，即預備空間來應對可能出現的沖突情況。不過與多槽位法不同，獨立鍊法是将所有沖突的關鍵碼組織成一個清單，利用清單的動态增長特性，來規避預備的沖突空間不足的問題。

公共溢出區法(overflow area)

基本思想與上面兩個也是相同的，即在事先預備公共的溢出區，來存儲關鍵碼沖突的詞條。

上面幾種方法都具有相同的思想，即在原有的散清單外還預備額外的空間來存儲詞條，此時散列位址不僅僅局限于散清單所覆寫的範圍内，還包括這個額外的存儲沖突詞條的空間，故也稱作開散列(open hashing)，或者封閉定址法(closed addressing)，因為任一給定的詞條隻可能存儲在某一确定的桶單元，其他的桶單元對該詞條是不開放的。

1.開放定址法(open addressing)

線性試探法(linear probing)

線性試探法是指，在插入關鍵碼k e y keykey時，若發現第h a s h ( k e y ) hash(key)hash(key)個桶空間已被占用，則繼而試探它的下一個桶空間，如此不斷，直到發現一個可用的空桶。

線性試探法的問題在于，随着散清單裝填因子的增大，散清單中的查找鍊也會随之增長，進而降低了散清單的查找性能。另一方面，采用線性試探法時，一旦在某一局部發生沖突，極有可能後續的插入會在這裡引發更多的沖突，并且多組各自沖突的查找鍊有可能互相重疊。

但如果散清單的裝填因子不大λ < 0.5 \lambda < 0.5λ<0.5，采用線性試探法的散清單的平均效率，通常都可保持在較為理想的水準。并且線性試探法中的詞條，具有良好的局部性，可以極大地降低I/O操作的開銷。

單向平方試探法(quadratic probing)

平方試探法可以在一定程度上緩解上述的沖突聚集現象。在試探過程中發生第j jj次發生沖突時，轉而試探

( h a s h ( k e y ) + j 2 ) m o d M , j = 0 , 1 , 2 , ⋯ (hash(key) + j^2) \ mod \ M, j = 0, 1, 2, \cdots

(hash(key)+j

2

) mod M,j=0,1,2,⋯

由于各次試探的位置到起始位置的距離，以平方速率增長，故稱為平方試探法。

與線性試探法比較，平方試探法可以了解為迅速離開發生沖突的“是非之地”，以平方的速率迅速跳離關鍵碼聚集的區段，是以可以在一定程度上緩解彙聚的現象。

可是，關于平方試探法，我們不難提出一些問題，比如平方試探法果真可以覆寫整個散清單嗎？是否存在散清單本來有空桶，卻無法被探測到的現象？

這種情況是存在的，可以自己舉一些例子要驗證一下。不過，隻要散清單長度M MM為素數，并且裝填因子λ ≤ 0.5 \lambda \le 0.5λ≤0.5，則平方試探法遲早必然會終止于某個空桶，即n 2 m o d M n^2 \ mod\ Mn

2

mod M的取值恰好有c e i l ( M 2 ) ceil(\frac{M}{2})ceil(

2

M

​

)種，并且恰好由查找鍊的前c e i l ( M 2 ) ceil(\frac{M}{2})ceil(

2

M

​

)取遍。以下給出證明：

設a < b < c e i l ( M 2 ) a < b < ceil(\frac{M}{2})a<b<ceil(

2

M

​

)，并且第a aa次試探與第b bb次試探沖突，即a 2 , b 2 a^2, b^2a

2

,b

2

是M MM的同餘類

a 2 ≡ b 2 ( m o d M ) a^2 \equiv b^2\ (mod\ M)

a

2

≡b

2

(mod M)

是以

b 2 − a 2 ≡ 0 ( m o d M ) b^2 - a^2 \equiv 0\ (mod\ M)

b

2

−a

2

≡0 (mod M)

即( b − a ) ( b + a ) (b - a)(b + a)(b−a)(b+a)可以整除M MM。但是由于b − a < M , b + a < M b - a < M, b + a < Mb−a<M,b+a<M，如果( b − a ) ( b + a ) (b-a)(b+a)(b−a)(b+a)可以整除M MM的話，則M MM必有不為一的因子，與M MM為素數沖突，是以前c e i l ( M 2 ) ceil(\frac{M}{2})ceil(

2

M

​

)次試探必不沖突，故得證。

雙向平方試探法

根據上面的分析，在M MM為素數并且裝填因子λ < 0.5 \lambda < 0.5λ<0.5的時候，單向平方試探法可以保證試探必然終止。一個自然的想法是，另一半的桶，是否也可以利用起來呢？這就是雙向平方探測法。

雙向平方探測法，就是在發生沖突時，依次向前向後進行平方探測，即

( h a s h ( k e y ) ± j 2 ) m o d M , j = 0 , 1 , 2 , ⋯ (hash(key) \pm j^2)\ mod \ M, j = 0, 1, 2, \cdots

(hash(key)±j

2

) mod M,j=0,1,2,⋯

這種方法看似是把兩側的桶都利用起來了，但是我們也不禁産生一個問題，即這雙向的探測是否是互相獨立呢？它們之間除了零，是否還有其他公共的桶？

答案是，是存在不獨立的情況的，并且這種情況還相當的多，也可以自己舉幾個例子來看一下。但是，如果散清單的長度取做素數，并且M = 4 k + 3 M = 4k + 3M=4k+3，則必然可以保證查找鍊的前M MM項都是互異的，以下來證明這個結論。

這裡，我們首先需要提到費馬的雙平方定理，即任意素數p pp可以表示為兩個正整數的平方和，當且僅當p = 4 k + 1 p = 4k + 1p=4k+1。

在此基礎上，如果我們可以注意到

( u 2 + v 2 ) ( s 2 + t 2 ) = ( u s + v t ) 2 + ( u t − v s ) 2 (u^2 + v2)(s2 + t^2) = (us + vt)^2 + (ut - vs)^2

(u

2

+v

2

)(s

2

+t

2

)=(us+vt)

2

+(ut−vs)

2

即任意兩個可以表示為兩個正整數的平方和的正整數的乘積，也可以表示為兩個正整數的平方和。

就可以推知，任意自然數n nn可以表示為一對整數的平方和，當且僅當在其素分解中，形如M = 4 k + 3 M = 4k + 3M=4k+3形式的每一個素因子均為偶數次方。這個推導的過程要知道啊，我這裡就不寫了。

進而我們假設對于a < c e i l ( M 2 ) , b < c e i l ( M 2 ) a < ceil(\frac{M}{2}), b < ceil(\frac{M}{2})a<ceil(

2

M

​

),b<ceil(

2

M

​

)，并且− a 2 -a^2−a

2

與b 2 b^2b

2

是同餘類，即

− a 2 ≡ b 2 ( m o d M ) -a^2 \equiv b^2 \ (mod \ M)

−a

2

≡b

2

(mod M)

是以

a 2 + b 2 ≡ 0 ( m o d M ) a^2 + b^2 \equiv 0 \ (mod \ M)

a

2

+b

2

≡0 (mod M)

即a 2 + b 2 a^2 + b^2a

2

+b

2

可以整除M MM。由于M = 4 k + 3 M = 4k + 3M=4k+3且為素數，是以a 2 + b 2 a^2 + b^2a

2

+b

2

可以整除M 2 M^2M

2

，但是a 2 + b 2 < M 2 a^2 + b^2 < M^2a

2

+b

2

<M

2

，是以假設不成立，故原命題得證。

随機試探法(pseudo-random probing)

仿照散列函數中的随機數法，在發生沖突時也可以采用随機數發生器來确定試探的位置，就是随機試探法。

再散列法(double hashing)

顧名思義，設定一個二級散列函數來确定試探位置，即

[ h a s h ( k e y ) + j × h a s h 2 ( k e y ) ] m o d M [hash(key) + j \times hash_2(key)] \ mod\ M

[hash(key)+j×hash

2

​

(key)] mod M

其他的方法其實都可以視作再散列法的一個執行個體。

總結

散列。