專注于c++

 

【摘要】

Hash是一種在信息學(xué)競(jìng)賽中經(jīng)常用到的數(shù)據(jù)結(jié)構(gòu)。一個(gè)好的Hash函數(shù)可以很大程度上提高程序的整體時(shí)間效率和空間效率。本文對(duì)面向各種不同標(biāo)本（關(guān)鍵值）的Hash函數(shù)進(jìn)行討論，并對(duì)多種常用的Hash函數(shù)進(jìn)行了分析和總結(jié)。

 

【關(guān)鍵字】

Hash 函數(shù)，字符串，整數(shù)，實(shí)數(shù)，排列組合

 

【正文】

對(duì)于一個(gè)Hash函數(shù)，評(píng)價(jià)其優(yōu)劣的標(biāo)準(zhǔn)應(yīng)為隨機(jī)性，即對(duì)任意一組標(biāo)本，進(jìn)入Hash表每一個(gè)單元（cell）之概率的平均程度，因?yàn)檫@個(gè)概率越平均，數(shù)據(jù)在表中的分布就越平均，表的空間利用率就越高。由于在競(jìng)賽中，標(biāo)本的性質(zhì)是無法預(yù)知的，因此數(shù)學(xué)推理將受到很大限制。我們用實(shí)驗(yàn)的方法研究這個(gè)隨機(jī)性。

 

一、整數(shù)的Hash函數(shù)

常用的方法有三種：直接取余法、乘積取整法、平方取中法。下面我們對(duì)這三種方法分別進(jìn)行討論。以下假定我們的關(guān)鍵字是 ，Hash表的容量是 ，Hash函數(shù)為 。

 

1．直接取余法

我們用關(guān)鍵字 除以 ，取余數(shù)作為在Hash表中的位置。函數(shù)表達(dá)式可以寫成：

。

例如，表容量 ，關(guān)鍵值 ，那么 。該方法的好處是實(shí)現(xiàn)容易且速度快，是很常用的一種方法。但是如果 選擇的不好而偏偏標(biāo)本又很特殊，那么數(shù)據(jù)在Hash中很容易扎堆而影響效率。

對(duì)于 的選擇，在經(jīng)驗(yàn)上，我們一般選擇不太接近 的一個(gè)素?cái)?shù)；如果關(guān)鍵字的值域較小，我們一般在此值域1.1~1.6倍范圍內(nèi)選擇。例如 的值域?yàn)?/span> ，那么 即為一個(gè)不錯(cuò)的選擇。競(jìng)賽的時(shí)候可以寫一個(gè)素?cái)?shù)生成器或干脆自己寫一個(gè)“比較像素?cái)?shù)”的數(shù)。

我用4000個(gè)數(shù)插入一個(gè)容量為701的Hash表，得到的結(jié)果是：

測(cè)試數(shù)據(jù)	隨機(jī)數(shù)據(jù)	連續(xù)數(shù)據(jù)
最小單元容量：	0	5
最大單元容量：	15	6
期望容量：	5.70613	5.70613
標(biāo)準(zhǔn)差：	2.4165	0.455531

 

可見對(duì)于隨機(jī)數(shù)據(jù)，取余法的最大單元容量達(dá)到了期望容量的將近3倍。經(jīng)測(cè)試，在我的機(jī)器（Pentium III 866MHz，128MB RAM）上，該函數(shù)的運(yùn)行時(shí)間大約是39ns，即大約35個(gè)時(shí)鐘周期。

 

2．乘積取整法

我們用關(guān)鍵字 乘以一個(gè)在 中的實(shí)數(shù) （最好是無理數(shù)），得到一個(gè) 之間的實(shí)數(shù)；取出其小數(shù)部分，乘以 ，再取整數(shù)部分，即得 在Hash表中的位置。函數(shù)表達(dá)式可以寫成：

；

其中 表示 的小數(shù)部分，即 。例如，表容量 ，種子 （ 是一個(gè)實(shí)際效果很好的選擇），關(guān)鍵值 ，那么 。

同樣用4000個(gè)數(shù)插入一個(gè)容量為701的Hash表（ ），得到的結(jié)果是：

測(cè)試數(shù)據(jù)	隨機(jī)數(shù)據(jù)	連續(xù)數(shù)據(jù)
最小單元容量：	0	4
最大單元容量：	15	7
期望容量：	5.70613	5.70613
標(biāo)準(zhǔn)差：	2.5069	0.619999

 

從公式中可以看出，這個(gè)方法受 的影響是很小的，在 的值比較不適合直接取余法的時(shí)候這個(gè)方法的表現(xiàn)很好。但是從上面的測(cè)試來看，其表現(xiàn)并不是非常理想，且由于浮點(diǎn)運(yùn)算較多，運(yùn)行速度較慢。經(jīng)反復(fù)優(yōu)化，在我的機(jī)器上仍需892ns才能完成一次計(jì)算，即810個(gè)時(shí)鐘周期，是直接取余法的23倍。

 

3．平方取中法

我們把關(guān)鍵字 平方，然后取中間的 位作為Hash函數(shù)值返回。由于 的每一位都會(huì)對(duì)其平方中間的若干位產(chǎn)生影響，因此這個(gè)方法的效果也是不錯(cuò)的。但是對(duì)于比較小的 值效果并不是很理想，實(shí)現(xiàn)起來也比較繁瑣。為了充分利用Hash表的空間， 最好取2的整數(shù)次冪。例如，表容量 ，關(guān)鍵值 ，那么 。

用4000個(gè)數(shù)插入一個(gè)容量為512的Hash表（注意這里沒有用701，是為了利用Hash表的空間），得到的結(jié)果是：

測(cè)試數(shù)據(jù)	隨機(jī)數(shù)據(jù)	連續(xù)數(shù)據(jù)
最小單元容量：	0	1
最大單元容量：	17	17
期望容量：	7.8125	7.8125
標(biāo)準(zhǔn)差：	2.95804	2.64501

 

效果比我們想象的要差，尤其是對(duì)于連續(xù)數(shù)據(jù)。但由于只有乘法和位運(yùn)算，該函數(shù)的速度是最快的。在我的機(jī)器上，一次運(yùn)算只需要23ns，即19個(gè)時(shí)鐘周期，比直接取余法還要快一些。

 

比較一下這三種方法：

	實(shí)現(xiàn)難度	實(shí)際效果	運(yùn)行速度	其他應(yīng)用
直接取余法	易	好	較快	字符串
乘積取整法	較易	較好	慢	浮點(diǎn)數(shù)
平方取中法	中	較好	快	無

 

從這個(gè)表格中我們很容易看出，直接取余法的性價(jià)比是最高的，因此也是我們競(jìng)賽中用得最多的一種方法。

 

對(duì)于實(shí)數(shù)的Hash函數(shù)，我們可以直接利用乘積取整法；而對(duì)于標(biāo)本為其他類型數(shù)據(jù)的Hash函數(shù)，我們可以先將其轉(zhuǎn)換為整數(shù)，然后再將其插入Hash表。下面我們來研究把其他類型數(shù)據(jù)轉(zhuǎn)換成整數(shù)的方法。

二、字符串的Hash函數(shù)

字符串本身就可以看成一個(gè)256進(jìn)制（ANSI字符串為128進(jìn)制）的大整數(shù)，因此我們可以利用直接取余法，在線性時(shí)間內(nèi)直接算出Hash函數(shù)值。為了保證效果， 仍然不能選擇太接近 的數(shù)；尤其是當(dāng)我們把字符串看成一個(gè) 進(jìn)制數(shù)的時(shí)候，選擇 會(huì)使得該字符串的任意一個(gè)排列的Hash函數(shù)值都相同。（想想看，為什么？）

常用的字符串Hash函數(shù)還有ELFHash，APHash等等，都是十分簡(jiǎn)單有效的方法。這些函數(shù)使用位運(yùn)算使得每一個(gè)字符都對(duì)最后的函數(shù)值產(chǎn)生影響。另外還有以MD5和SHA1為代表的雜湊函數(shù)，這些函數(shù)幾乎不可能找到碰撞（MD5前一段時(shí)間才剛剛被破解）。

我從Mark Twain的一篇小說中分別隨機(jī)抽取了1000個(gè)不同的單詞和1000個(gè)不同的句子，作為短字符串和長字符串的測(cè)試數(shù)據(jù)，然后用不同的Hash函數(shù)把它們變成整數(shù)，再用直接取余法插入一個(gè)容量為1237的Hash表，遇到?jīng)_突則用新字符串覆蓋舊字符串。通過觀察最后“剩下”的字符串的個(gè)數(shù)，我們可以粗略地得出不同的Hash函數(shù)實(shí)際效果。

	短字符串	長字符串	平均	編碼難度
直接取余數(shù)	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個(gè)隨機(jī)數(shù)用直接取余法插入容量為1237的Hash表，其覆蓋單元數(shù)也只達(dá)到了694，可見后面的幾種方法已經(jīng)達(dá)到了極限，隨機(jī)性相當(dāng)優(yōu)秀。然而我們卻很難選擇，因?yàn)椴淮嬖谕昝赖摹⒓群?jiǎn)單又實(shí)用的解決方案。我一般選擇JS Hash或SDBM Hash作為字符串的Hash函數(shù)。這兩個(gè)函數(shù)的代碼如下：

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的運(yùn)算比較復(fù)雜，如果對(duì)效果要求不是特別高的話SDBMHash是一個(gè)很好的選擇。

 

三、排列的Hash函數(shù)

準(zhǔn)確的說，這里我們的研究不再僅僅局限在“Hashing”的工作，而是進(jìn)化到一個(gè)“numerize”的過程，也就是說我們可以在排列和1到 的自然數(shù)之間建立一一對(duì)應(yīng)的關(guān)系。這樣我們就可以利用這個(gè)關(guān)系來直接定址，或者用作Hash函數(shù)；在基于狀態(tài)壓縮的動(dòng)態(tài)規(guī)劃算法中也能用上。

 

1．背景知識(shí)

自然數(shù)的 進(jìn)制表示法我們已經(jīng)很熟悉了，即：

，

比如 便是二進(jìn)制數(shù)， 便是十進(jìn)制數(shù)。

引理： ， 。

證明：對(duì) 使用數(shù)學(xué)歸納法。

1)              時(shí)，等式顯然成立。

2)假設(shè) 時(shí)等式成立，即 。
則 時(shí)，

即 時(shí)等式亦成立。

3)綜上所述， ， 成立。

把這個(gè)式子變形一下：

上式和 類似。不難證明，從0到 的任何自然數(shù) 可唯一地表示為

其中 ， 。甚至在式子后面加上一個(gè) 也無妨，在后面我們把這一項(xiàng)忽略掉。所以從0到 的 個(gè)自然數(shù)與

（*）

一一對(duì)應(yīng)。另一方面，不難從 算出 。

我們可以把序列 理解為一個(gè)“變進(jìn)制數(shù)”，也就是第一位二進(jìn)制，第二位三進(jìn)制，……，第 位 進(jìn)制，……，第 位 進(jìn)制。這樣，我們就可以方便的使用類似“除 取余法”的方法從一個(gè)自然數(shù) 算出序列 。由于這樣的序列共有 個(gè)，我們很自然的想到把這 個(gè)序列和 個(gè)元素的全排列建立一一對(duì)應(yīng)。

 

2．全排列與自然數(shù)之一一對(duì)應(yīng)

為了方便起見，不妨設(shè) 個(gè)元素為 。對(duì)應(yīng)的規(guī)則如下：設(shè)序列（*）對(duì)應(yīng)的某一排列 ，其中 可以看做是排列 中數(shù) 所在位置右邊比 小的數(shù)的個(gè)數(shù)。以排列4213為例，它是元素1,2,3,4的一個(gè)排列。4的右邊比4小的數(shù)的數(shù)目為3，所以 。3右邊比3小的數(shù)的數(shù)目為0，即 。同理 。所以排列4213對(duì)應(yīng)于變進(jìn)制的301，也就是十進(jìn)制的19；反過來也可以從19反推到301，再反推到排列4213。

 

3．更一般性的排列

受到這個(gè)思路啟發(fā)，我們同樣可以把更一般性的排列與自然數(shù)之間建立一一對(duì)應(yīng)關(guān)系。想一想從 個(gè)元素中選 個(gè)的排列數(shù) 的公式是怎么來的？根據(jù)乘法原理，我們有

這是由于在排列的第1個(gè)位置有 種選擇，在排列的第2個(gè)位置有 種選擇，……，在排列的第 個(gè)位置有 種選擇。既然這樣，我們可以定義一種“m-n變進(jìn)制數(shù)”，使其第1位是 進(jìn)制，第2位是 進(jìn)制，……，第 位是 進(jìn)制。這樣，0到 之間的任意一個(gè)自然數(shù) 都可以唯一地表示成：

其中 ， 。注意到 （證明略，可直接變形結(jié)合前面的引理推得），所以從0到 的 個(gè)自然數(shù)可以與序列

一一對(duì)應(yīng)。類似地，可以用取余法從自然數(shù) 算出 。

我們?cè)O(shè) 個(gè)元素為 ，從中取出 個(gè)。對(duì)應(yīng)關(guān)系如下：維護(hù)一個(gè)首元素下標(biāo)為0的線性表 ，初始時(shí) 。對(duì)于某一排列 ，我們從 開始處理。首先在 中找到 的下標(biāo)記為 ，然后刪除 ；接著在 中找到 的下標(biāo)記為 ，然后刪除 ……直到 被刪除為止。以在5個(gè)元素1,2,3,4,5中取出2,4,3為例，這時(shí) 。首先在 中取出2，記下 ， 變?yōu)?/span>1,3,4,5；在 中取出4，記下 ， 變?yōu)?/span>1,3,5；在 中取出3，記下 ， 變?yōu)?/span>1,5。因此排列243對(duì)應(yīng)于“3-5變進(jìn)制數(shù)”121，即十進(jìn)制數(shù)19；反過來也可以從十進(jìn)制數(shù)19反推到121，再反推到排列243。各序列及其對(duì)應(yīng)的排列如下表：

 

【總結(jié)】

本文對(duì)幾個(gè)常用的Hash函數(shù)進(jìn)行了總結(jié)性的介紹和分析，并將其延伸到應(yīng)用更加廣泛的“與自然數(shù)建立一一對(duì)應(yīng)”的過程。Hash是一種相當(dāng)有效的數(shù)據(jù)結(jié)構(gòu)，充分體現(xiàn)了“空間換時(shí)間”的思想。在如今競(jìng)賽中內(nèi)存限制越來越松的情況下，要做到充分利用內(nèi)存空間來換取寶貴的時(shí)間，Hash能夠給我們很大幫助。我們應(yīng)當(dāng)根據(jù)題目的特點(diǎn)，選擇適合題目的數(shù)據(jù)結(jié)構(gòu)來優(yōu)化算法。對(duì)于組合與自然數(shù)的一一對(duì)應(yīng)關(guān)系，我還沒有想到好的方法，歡迎大家討論。

 

【參考文獻(xiàn)】

[1]    Thomas H Cormen, Charles E Leiserson, Ronald L Riverst, Clifford Stein. Introduction to Algorithms. Second Edition. The MIT Press, 2001

[2]    劉汝佳，黃亮. 《算法藝術(shù)與信息學(xué)競(jìng)賽》. 北京：清華大學(xué)出版社，2004

[3]    盧開澄，盧華明. 《組合數(shù)學(xué)》（第3版）. 北京：清華大學(xué)出版社，2002

 

【附錄】

常用的字符串Hash函數(shù)之源代碼：

// 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); }