專注于c++

 

【摘要】

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。各序列及其對應的排列如下表：

 

【總結】

本文對幾個常用的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 & 0xF0000000L) != 0)        {            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); }