【摘要】
Hash是一種在信息學競賽中經常用到的數據結構。一個好的Hash函數可以很大程度上提高程序的整體時間效率和空間效率。本文對面向各種不同標本(關鍵值)的Hash函數進行討論,并對多種常用的Hash函數進行了分析和總結。
【關鍵字】
Hash 函數,字符串,整數,實數,排列組合
【正文】
對于一個Hash函數,評價其優劣的標準應為隨機性,即對任意一組標本,進入Hash表每一個單元(cell)之概率的平均程度,因為這個概率越平均,數據在表中的分布就越平均,表的空間利用率就越高。由于在競賽中,標本的性質是無法預知的,因此數學推理將受到很大限制。我們用實驗的方法研究這個隨機性。
一、整數的Hash函數
常用的方法有三種:直接取余法、乘積取整法、平方取中法。下面我們對這三種方法分別進行討論。以下假定我們的關鍵字是 ,Hash表的容量是 ,Hash函數為 。
1.直接取余法
我們用關鍵字 除以 ,取余數作為在Hash表中的位置。函數表達式可以寫成:
。
例如,表容量 ,關鍵值 ,那么 。該方法的好處是實現容易且速度快,是很常用的一種方法。但是如果 選擇的不好而偏偏標本又很特殊,那么數據在Hash中很容易扎堆而影響效率。
對于 的選擇,在經驗上,我們一般選擇不太接近 的一個素數;如果關鍵字的值域較小,我們一般在此值域1.1~1.6倍范圍內選擇。例如 的值域為 ,那么 即為一個不錯的選擇。競賽的時候可以寫一個素數生成器或干脆自己寫一個“比較像素數”的數。
我用4000個數插入一個容量為701的Hash表,得到的結果是:
測試數據 |
隨機數據 |
連續數據 |
最小單元容量: |
0 |
5 |
最大單元容量: |
15 |
6 |
期望容量: |
5.70613 |
5.70613 |
標準差: |
2.4165 |
0.455531 |
可見對于隨機數據,取余法的最大單元容量達到了期望容量的將近3倍。經測試,在我的機器(Pentium III 866MHz,128MB RAM)上,該函數的運行時間大約是39ns,即大約35個時鐘周期。
2.乘積取整法
我們用關鍵字 乘以一個在 中的實數 (最好是無理數),得到一個 之間的實數;取出其小數部分,乘以 ,再取整數部分,即得 在Hash表中的位置。函數表達式可以寫成:
;
其中 表示 的小數部分,即 。例如,表容量 ,種子 ( 是一個實際效果很好的選擇),關鍵值 ,那么 。
同樣用4000個數插入一個容量為701的Hash表( ),得到的結果是:
測試數據 |
隨機數據 |
連續數據 |
最小單元容量: |
0 |
4 |
最大單元容量: |
15 |
7 |
期望容量: |
5.70613 |
5.70613 |
標準差: |
2.5069 |
0.619999 |
從公式中可以看出,這個方法受 的影響是很小的,在 的值比較不適合直接取余法的時候這個方法的表現很好。但是從上面的測試來看,其表現并不是非常理想,且由于浮點運算較多,運行速度較慢。經反復優化,在我的機器上仍需892ns才能完成一次計算,即810個時鐘周期,是直接取余法的23倍。
3.平方取中法
我們把關鍵字 平方,然后取中間的 位作為Hash函數值返回。由于 的每一位都會對其平方中間的若干位產生影響,因此這個方法的效果也是不錯的。但是對于比較小的 值效果并不是很理想,實現起來也比較繁瑣。為了充分利用Hash表的空間, 最好取2的整數次冪。例如,表容量 ,關鍵值 ,那么 。
用4000個數插入一個容量為512的Hash表(注意這里沒有用701,是為了利用Hash表的空間),得到的結果是:
測試數據 |
隨機數據 |
連續數據 |
最小單元容量: |
0 |
1 |
最大單元容量: |
17 |
17 |
期望容量: |
7.8125 |
7.8125 |
標準差: |
2.95804 |
2.64501 |
效果比我們想象的要差,尤其是對于連續數據。但由于只有乘法和位運算,該函數的速度是最快的。在我的機器上,一次運算只需要23ns,即19個時鐘周期,比直接取余法還要快一些。
比較一下這三種方法:
|
實現難度 |
實際效果 |
運行速度 |
其他應用 |
直接取余法 |
易 |
好 |
較快 |
字符串 |
乘積取整法 |
較易 |
較好 |
慢 |
浮點數 |
平方取中法 |
中 |
較好 |
快 |
無 |
從這個表格中我們很容易看出,直接取余法的性價比是最高的,因此也是我們競賽中用得最多的一種方法。
對于實數的Hash函數,我們可以直接利用乘積取整法;而對于標本為其他類型數據的Hash函數,我們可以先將其轉換為整數,然后再將其插入Hash表。下面我們來研究把其他類型數據轉換成整數的方法。
二、字符串的Hash函數
字符串本身就可以看成一個256進制(ANSI字符串為128進制)的大整數,因此我們可以利用直接取余法,在線性時間內直接算出Hash函數值。為了保證效果, 仍然不能選擇太接近 的數;尤其是當我們把字符串看成一個 進制數的時候,選擇 會使得該字符串的任意一個排列的Hash函數值都相同。(想想看,為什么?)
常用的字符串Hash函數還有ELFHash,APHash等等,都是十分簡單有效的方法。這些函數使用位運算使得每一個字符都對最后的函數值產生影響。另外還有以MD5和SHA1為代表的雜湊函數,這些函數幾乎不可能找到碰撞(MD5前一段時間才剛剛被破解)。
我從Mark Twain的一篇小說中分別隨機抽取了1000個不同的單詞和1000個不同的句子,作為短字符串和長字符串的測試數據,然后用不同的Hash函數把它們變成整數,再用直接取余法插入一個容量為1237的Hash表,遇到沖突則用新字符串覆蓋舊字符串。通過觀察最后“剩下”的字符串的個數,我們可以粗略地得出不同的Hash函數實際效果。
|
短字符串 |
長字符串 |
平均 |
編碼難度 |
直接取余數 |
667 |
676 |
671.5 |
易 |
P. J. Weinberger Hash |
683 |
676 |
679.5 |
難 |
ELF Hash |
683 |
676 |
679.5 |
較難 |
SDBM Hash |
694 |
680 |
687.0 |
易 |
BKDR Hash |
665 |
710 |
687.5 |
較易 |
DJB Hash |
694 |
683 |
688.5 |
較易 |
AP Hash |
684 |
698 |
691.0 |
較難 |
RS Hash |
691 |
693 |
692.0 |
較難 |
JS Hash |
684 |
708 |
696.0 |
較易 |
把1000個隨機數用直接取余法插入容量為1237的Hash表,其覆蓋單元數也只達到了694,可見后面的幾種方法已經達到了極限,隨機性相當優秀。然而我們卻很難選擇,因為不存在完美的、既簡單又實用的解決方案。我一般選擇JS Hash或SDBM Hash作為字符串的Hash函數。這兩個函數的代碼如下:
unsigned int JSHash(char *str) { unsigned int hash = 1315423911; // nearly a prime - 1315423911 = 3 * 438474637 while (*str) { hash ^= ((hash << 5) + (*str++) + (hash >> 2)); } return (hash & 0x7FFFFFFF); }
unsigned int SDBMHash(char *str) { unsigned int hash = 0; while (*str) { // equivalent to: hash = 65599*hash + (*str++); hash = (*str++) + (hash << 6) + (hash << 16) - hash; } return (hash & 0x7FFFFFFF); } |
JSHash的運算比較復雜,如果對效果要求不是特別高的話SDBMHash是一個很好的選擇。
三、排列的Hash函數
準確的說,這里我們的研究不再僅僅局限在“Hashing”的工作,而是進化到一個“numerize”的過程,也就是說我們可以在排列和1到 的自然數之間建立一一對應的關系。這樣我們就可以利用這個關系來直接定址,或者用作Hash函數;在基于狀態壓縮的動態規劃算法中也能用上。
1.背景知識
自然數的 進制表示法我們已經很熟悉了,即:
,
比如 便是二進制數, 便是十進制數。
引理: , 。
證明:對 使用數學歸納法。
1) 時,等式顯然成立。
2)假設 時等式成立,即 。
則 時,
即 時等式亦成立。
3)綜上所述, , 成立。
把這個式子變形一下:
上式和 類似。不難證明,從0到 的任何自然數 可唯一地表示為
其中 , 。甚至在式子后面加上一個 也無妨,在后面我們把這一項忽略掉。所以從0到 的 個自然數與
|
(*) |
一一對應。另一方面,不難從 算出 。
我們可以把序列 理解為一個“變進制數”,也就是第一位二進制,第二位三進制,……,第 位 進制,……,第 位 進制。這樣,我們就可以方便的使用類似“除 取余法”的方法從一個自然數 算出序列 。由于這樣的序列共有 個,我們很自然的想到把這 個序列和 個元素的全排列建立一一對應。
2.全排列與自然數之一一對應
為了方便起見,不妨設 個元素為 。對應的規則如下:設序列(*)對應的某一排列 ,其中 可以看做是排列 中數 所在位置右邊比 小的數的個數。以排列4213為例,它是元素1,2,3,4的一個排列。4的右邊比4小的數的數目為3,所以 。3右邊比3小的數的數目為0,即 。同理 。所以排列4213對應于變進制的301,也就是十進制的19;反過來也可以從19反推到301,再反推到排列4213。
3.更一般性的排列
受到這個思路啟發,我們同樣可以把更一般性的排列與自然數之間建立一一對應關系。想一想從 個元素中選 個的排列數 的公式是怎么來的?根據乘法原理,我們有
這是由于在排列的第1個位置有 種選擇,在排列的第2個位置有 種選擇,……,在排列的第 個位置有 種選擇。既然這樣,我們可以定義一種“m-n變進制數”,使其第1位是 進制,第2位是 進制,……,第 位是 進制。這樣,0到 之間的任意一個自然數 都可以唯一地表示成:
其中 , 。注意到 (證明略,可直接變形結合前面的引理推得),所以從0到 的 個自然數可以與序列
一一對應。類似地,可以用取余法從自然數 算出 。
我們設 個元素為 ,從中取出 個。對應關系如下:維護一個首元素下標為0的線性表 ,初始時 。對于某一排列 ,我們從 開始處理。首先在 中找到 的下標記為 ,然后刪除 ;接著在 中找到 的下標記為 ,然后刪除 ……直到 被刪除為止。以在5個元素1,2,3,4,5中取出2,4,3為例,這時 。首先在 中取出2,記下 , 變為1,3,4,5;在 中取出4,記下 , 變為1,3,5;在 中取出3,記下 , 變為1,5。因此排列243對應于“3-5變進制數”121,即十進制數19;反過來也可以從十進制數19反推到121,再反推到排列243。各序列及其對應的排列如下表:
|
|
|
|
|
|
123 |
000 |
0 |
341 |
220 |
30 |
124 |
001 |
1 |
342 |
221 |
31 |
125 |
002 |
2 |
345 |
222 |
32 |
132 |
010 |
3 |
351 |
230 |
33 |
134 |
011 |
4 |
352 |
231 |
34 |
135 |
012 |
5 |
354 |
232 |
35 |
142 |
020 |
6 |
412 |
300 |
36 |
143 |
021 |
7 |
413 |
301 |
37 |
145 |
022 |
8 |
415 |
302 |
38 |
152 |
030 |
9 |
421 |
310 |
39 |
153 |
031 |
10 |
423 |
311 |
40 |
154 |
032 |
11 |
425 |
312 |
41 |
213 |
100 |
12 |
431 |
320 |
42 |
214 |
101 |
13 |
432 |
321 |
43 |
215 |
102 |
14 |
435 |
322 |
44 |
231 |
110 |
15 |
451 |
330 |
45 |
234 |
111 |
16 |
452 |
331 |
46 |
235 |
112 |
17 |
453 |
332 |
47 |
241 |
120 |
18 |
512 |
400 |
48 |
243 |
121 |
19 |
513 |
401 |
49 |
245 |
122 |
20 |
514 |
402 |
50 |
251 |
130 |
21 |
521 |
410 |
51 |
253 |
131 |
22 |
523 |
411 |
52 |
254 |
132 |
23 |
524 |
412 |
53 |
312 |
200 |
24 |
531 |
420 |
54 |
314 |
201 |
25 |
532 |
421 |
55 |
315 |
202 |
26 |
534 |
422 |
56 |
321 |
210 |
27 |
541 |
430 |
57 |
324 |
211 |
28 |
542 |
431 |
58 |
325 |
212 |
29 |
543 |
432 |
59 |
【總結】
本文對幾個常用的Hash函數進行了總結性的介紹和分析,并將其延伸到應用更加廣泛的“與自然數建立一一對應”的過程。Hash是一種相當有效的數據結構,充分體現了“空間換時間”的思想。在如今競賽中內存限制越來越松的情況下,要做到充分利用內存空間來換取寶貴的時間,Hash能夠給我們很大幫助。我們應當根據題目的特點,選擇適合題目的數據結構來優化算法。對于組合與自然數的一一對應關系,我還沒有想到好的方法,歡迎大家討論。
【參考文獻】
[1] Thomas H Cormen, Charles E Leiserson, Ronald L Riverst, Clifford Stein. Introduction to Algorithms. Second Edition. The MIT Press, 2001
[2] 劉汝佳,黃亮. 《算法藝術與信息學競賽》. 北京:清華大學出版社,2004
[3] 盧開澄,盧華明. 《組合數學》(第3版). 北京:清華大學出版社,2002
【附錄】
常用的字符串Hash函數之源代碼:
// RS Hash Function unsigned int RSHash(char *str) { unsigned int b = 378551; unsigned int a = 63689; unsigned int hash = 0;
while (*str) { hash = hash * a + (*str++); a *= b; }
return (hash & 0x7FFFFFFF); }
// JS Hash Function unsigned int JSHash(char *str) { unsigned int hash = 1315423911;
while (*str) { hash ^= ((hash << 5) + (*str++) + (hash >> 2)); }
return (hash & 0x7FFFFFFF); }
// P. J. Weinberger Hash Function unsigned int PJWHash(char *str) { unsigned int BitsInUnignedInt = (unsigned int)(sizeof(unsigned int) * 8); unsigned int ThreeQuarters = (unsigned int)((BitsInUnignedInt * 3) / 4); unsigned int OneEighth = (unsigned int)(BitsInUnignedInt / 8); unsigned int HighBits = (unsigned int)(0xFFFFFFFF) << (BitsInUnignedInt - OneEighth); unsigned int hash = 0; unsigned int test = 0;
while (*str) { hash = (hash << OneEighth) + (*str++); if ((test = hash & HighBits) != 0) { hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits)); } }
return (hash & 0x7FFFFFFF); }
// ELF Hash Function unsigned int ELFHash(char *str) { unsigned int hash = 0; unsigned int x = 0;
while (*str) { hash = (hash << 4) + (*str++); if ((x = hash & 0xF { hash ^= (x >> 24); hash &= ~x; } }
return (hash & 0x7FFFFFFF); }
// BKDR Hash Function unsigned int BKDRHash(char *str) { unsigned int seed = 131; // 31 131 1313 13131 131313 etc.. unsigned int hash = 0;
while (*str) { hash = hash * seed + (*str++); }
return (hash & 0x7FFFFFFF); }
// SDBM Hash Function unsigned int SDBMHash(char *str) { unsigned int hash = 0;
while (*str) { hash = (*str++) + (hash << 6) + (hash << 16) - hash; }
return (hash & 0x7FFFFFFF); }
// DJB Hash Function unsigned int DJBHash(char *str) { unsigned int hash = 5381;
while (*str) { hash += (hash << 5) + (*str++); }
return (hash & 0x7FFFFFFF); }
// AP Hash Function unsigned int APHash(char *str) { unsigned int hash = 0; int i;
for (i=0; *str; i++) { if ((i & 1) == 0) { hash ^= ((hash << 7) ^ (*str++) ^ (hash >> 3)); } else { hash ^= (~((hash << 11) ^ (*str++) ^ (hash >> 5))); } }
return (hash & 0x7FFFFFFF); } |