匯編Hash函數(shù)的設(shè)計優(yōu)化

1、Hash函數(shù)的設(shè)計優(yōu)化天津南開中學(xué) 李羽修【摘要】Hash是一種在信息學(xué)競賽中經(jīng)常用到的數(shù)據(jù)結(jié)構(gòu)。一個好的Hash函數(shù)可以很大程度上提高程序的整體時間效率和空間效率。本文對面向各種不同標(biāo)本關(guān)鍵值的Hash函數(shù)進(jìn)行討論，并對多種常用的Hash函數(shù)進(jìn)行了分析和總結(jié)?！娟P(guān)鍵字】Hash 函數(shù)，字符串，整數(shù)，實(shí)數(shù)，排列組合【正文】對于一個Hash函數(shù)，評價其優(yōu)劣的標(biāo)準(zhǔn)應(yīng)為隨機(jī)性，即對任意一組標(biāo)本，進(jìn)入Hash表每一個單元cell之概率的平均程度，因為這個概率越平均，數(shù)據(jù)在表中的分布就越平均，表的空間利用率就越高。由于在競賽中，標(biāo)本的性質(zhì)是無法預(yù)知的，因此數(shù)學(xué)推理將受到很大限制。我們用實(shí)驗的方法研究這個

2、隨機(jī)性。一、整數(shù)的Hash函數(shù)常用的方法有三種：直接取余法、乘積取整法、平方取中法。下面我們對這三種方法分別進(jìn)行討論。以下假定我們的關(guān)鍵字是，Hash表的容量是，Hash函數(shù)為。1直接取余法我們用關(guān)鍵字除以，取余數(shù)作為在Hash表中的位置。函數(shù)表達(dá)式可以寫成：。例如，表容量，關(guān)鍵值，那么。該方法的好處是實(shí)現(xiàn)容易且速度快，是很常用的一種方法。但是如果選擇的不好而偏偏標(biāo)本又很特殊，那么數(shù)據(jù)在Hash中很容易扎堆而影響效率。對于的選擇，在經(jīng)驗上，我們一般選擇不太接近的一個素數(shù)；如果關(guān)鍵字的值域較小，我們一般在此值域1.11.6倍范圍內(nèi)選擇。例如的值域為，那么即為一個不錯的選擇。競賽的時候可以寫一個素

3、數(shù)生成器或干脆自己寫一個“比擬像素數(shù)的數(shù)。我用4000個數(shù)插入一個容量為701的Hash表，得到的結(jié)果是：測試數(shù)據(jù)隨機(jī)數(shù)據(jù)連續(xù)數(shù)據(jù)最小單元容量：05最大單元容量：156期望容量：標(biāo)準(zhǔn)差：可見對于隨機(jī)數(shù)據(jù)，取余法的最大單元容量到達(dá)了期望容量的將近3倍。經(jīng)測試，在我的機(jī)器Pentium III 866MHz，128MB RAM上，該函數(shù)的運(yùn)行時間大約是39ns，即大約35個時鐘周期。2乘積取整法我們用關(guān)鍵字乘以一個在中的實(shí)數(shù)最好是無理數(shù)，得到一個之間的實(shí)數(shù)；取出其小數(shù)局部，乘以，再取整數(shù)局部，即得在Hash表中的位置。函數(shù)表達(dá)式可以寫成：；其中表示的小數(shù)局部，即。例如，表容量，種子是一個實(shí)際效果很

4、好的選擇，關(guān)鍵值，那么。同樣用4000個數(shù)插入一個容量為701的Hash表，得到的結(jié)果是：測試數(shù)據(jù)隨機(jī)數(shù)據(jù)連續(xù)數(shù)據(jù)最小單元容量：04最大單元容量：157期望容量：標(biāo)準(zhǔn)差：從公式中可以看出，這個方法受的影響是很小的，在的值比擬不適合直接取余法的時候這個方法的表現(xiàn)很好。但是從上面的測試來看，其表現(xiàn)并不是非常理想，且由于浮點(diǎn)運(yùn)算較多，運(yùn)行速度較慢。經(jīng)反復(fù)優(yōu)化，在我的機(jī)器上仍需892ns才能完成一次計算，即810個時鐘周期，是直接取余法的23倍。3平方取中法我們把關(guān)鍵字平方，然后取中間的位作為Hash函數(shù)值返回。由于的每一位都會對其平方中間的假設(shè)干位產(chǎn)生影響，因此這個方法的效果也是不錯的。但是對于比擬

5、小的值效果并不是很理想，實(shí)現(xiàn)起來也比擬繁瑣。為了充分利用Hash表的空間，最好取2的整數(shù)次冪。例如，表容量，關(guān)鍵值，那么。用4000個數(shù)插入一個容量為512的Hash表注意這里沒有用701，是為了利用Hash表的空間，得到的結(jié)果是：測試數(shù)據(jù)隨機(jī)數(shù)據(jù)連續(xù)數(shù)據(jù)最小單元容量：01最大單元容量：1717期望容量：標(biāo)準(zhǔn)差：效果比我們想象的要差，尤其是對于連續(xù)數(shù)據(jù)。但由于只有乘法和位運(yùn)算，該函數(shù)的速度是最快的。在我的機(jī)器上，一次運(yùn)算只需要23ns，即19個時鐘周期，比直接取余法還要快一些。比擬一下這三種方法：實(shí)現(xiàn)難度實(shí)際效果運(yùn)行速度其他應(yīng)用直接取余法易好較快字符串乘積取整法較易較好慢浮點(diǎn)數(shù)平方取中法中較好

6、快無從這個表格中我們很容易看出，直接取余法的性價比是最高的，因此也是我們競賽中用得最多的一種方法。對于實(shí)數(shù)的Hash函數(shù)，我們可以直接利用乘積取整法；而對于標(biāo)本為其他類型數(shù)據(jù)的Hash函數(shù)，我們可以先將其轉(zhuǎn)換為整數(shù)，然后再將其插入Hash表。下面我們來研究把其他類型數(shù)據(jù)轉(zhuǎn)換成整數(shù)的方法。二、字符串的Hash函數(shù)字符串本身就可以看成一個256進(jìn)制ANSI字符串為128進(jìn)制的大整數(shù)，因此我們可以利用直接取余法，在線性時間內(nèi)直接算出Hash函數(shù)值。為了保證效果，仍然不能選擇太接近的數(shù)；尤其是當(dāng)我們把字符串看成一個進(jìn)制數(shù)的時候，選擇會使得該字符串的任意一個排列的Hash函數(shù)值都相同。想想看，為什么？常

7、用的字符串Hash函數(shù)還有ELFHash，APHash等等，都是十分簡單有效的方法。這些函數(shù)使用位運(yùn)算使得每一個字符都對最后的函數(shù)值產(chǎn)生影響。另外還有以MD5和SHA1為代表的雜湊函數(shù)，這些函數(shù)幾乎不可能找到碰撞MD5前一段時間才剛剛被破解。我從Mark Twain的一篇小說中分別隨機(jī)抽取了1000個不同的單詞和1000個不同的句子，作為短字符串和長字符串的測試數(shù)據(jù)，然后用不同的Hash函數(shù)把它們變成整數(shù)，再用直接取余法插入一個容量為1237的Hash表，遇到?jīng)_突那么用新字符串覆蓋舊字符串。通過觀察最后“剩下的字符串的個數(shù)，我們可以粗略地得出不同的Hash函數(shù)實(shí)際效果。短字符串長字符串平均編碼

8、難度直接取余數(shù)667676易P. J. Weinberger Hash683676難ELF Hash683676較難SDBM Hash694680易BKDR Hash665710較易DJB Hash694683較易AP Hash684698較難RS Hash691693較難JS Hash684708較易把1000個隨機(jī)數(shù)用直接取余法插入容量為1237的Hash表，其覆蓋單元數(shù)也只到達(dá)了694，可見后面的幾種方法已經(jīng)到達(dá)了極限，隨機(jī)性相當(dāng)優(yōu)秀。然而我們卻很難選擇，因為不存在完美的、既簡單又實(shí)用的解決方案。我一般選擇JS Hash或SDBM Hash作為字符串的Hash函數(shù)。這兩個函數(shù)的代碼如下：

9、unsigned int JSHash(char *str)unsigned int hash = 1315423911; / nearly a prime - 1315423911 = 3 * 438474637while (*str)hash = (hash 2);return (hash & 0 x7FFFFFFF);unsigned int SDBMHash(char *str)unsigned int hash = 0;while (*str)/ equivalent to: hash = 65599*hash + (*str+);hash = (*str+) + (hash 6)

10、+ (hash 16) - hash;return (hash & 0 x7FFFFFFF);JSHash的運(yùn)算比擬復(fù)雜，如果對效果要求不是特別高的話SDBMHash是一個很好的選擇。三、排列的Hash函數(shù)準(zhǔn)確的說，這里我們的研究不再僅僅局限在“Hashing的工作，而是進(jìn)化到一個“numerize的過程，也就是說我們可以在排列和1到的自然數(shù)之間建立一一對應(yīng)的關(guān)系。這樣我們就可以利用這個關(guān)系來直接定址，或者用作Hash函數(shù)；在基于狀態(tài)壓縮的動態(tài)規(guī)劃算法中也能用上。1背景知識自然數(shù)的進(jìn)制表示法我們已經(jīng)很熟悉了，即：， 比方便是二進(jìn)制數(shù)，便是十進(jìn)制數(shù)。引理：，。證明：對使用數(shù)學(xué)歸納法。時，等式顯然

11、成立。假設(shè)時等式成立，即。那么時，即時等式亦成立。綜上所述，成立。把這個式子變形一下：上式和類似。不難證明，從0到的任何自然數(shù)可唯一地表示為其中，。甚至在式子后面加上一個也無妨，在后面我們把這一項忽略掉。所以從0到的個自然數(shù)與*一一對應(yīng)。另一方面，不難從算出。我們可以把序列理解為一個“變進(jìn)制數(shù)，也就是第一位二進(jìn)制，第二位三進(jìn)制，第位進(jìn)制，第位進(jìn)制。這樣，我們就可以方便的使用類似“除取余法的方法從一個自然數(shù)算出序列。由于這樣的序列共有個，我們很自然的想到把這個序列和個元素的全排列建立一一對應(yīng)。2全排列與自然數(shù)之一一對應(yīng)為了方便起見，不妨設(shè)個元素為。對應(yīng)的規(guī)那么如下：設(shè)序列*對應(yīng)的某一排列，其中可

12、以看做是排列中數(shù)所在位置右邊比小的數(shù)的個數(shù)。以排列4213為例，它是元素1,2,3,4的一個排列。4的右邊比4小的數(shù)的數(shù)目為3，所以。3右邊比3小的數(shù)的數(shù)目為0，即。同理。所以排列4213對應(yīng)于變進(jìn)制的301，也就是十進(jìn)制的19；反過來也可以從19反推到301，再反推到排列4213。3更一般性的排列受到這個思路啟發(fā)，我們同樣可以把更一般性的排列與自然數(shù)之間建立一一對應(yīng)關(guān)系。想一想從個元素中選個的排列數(shù)的公式是怎么來的？根據(jù)乘法原理，我們有這是由于在排列的第1個位置有種選擇，在排列的第2個位置有種選擇，在排列的第個位置有種選擇。既然這樣，我們可以定義一種“m-n變進(jìn)制數(shù)，使其第1位是進(jìn)制，第2位

13、是進(jìn)制，第位是進(jìn)制。這樣，0到之間的任意一個自然數(shù)都可以唯一地表示成：其中，。注意到證明略，可直接變形結(jié)合前面的引理推得，所以從0到的個自然數(shù)可以與序列一一對應(yīng)。類似地，可以用取余法從自然數(shù)算出。我們設(shè)個元素為，從中取出個。對應(yīng)關(guān)系如下：維護(hù)一個首元素下標(biāo)為0的線性表，初始時。對于某一排列，我們從開始處理。首先在中找到的下標(biāo)記為，然后刪除；接著在中找到的下標(biāo)記為，然后刪除直到被刪除為止。以在5個元素1,2,3,4,5中取出2,4,3為例，這時。首先在中取出2，記下，變?yōu)?,3,4,5；在中取出4，記下，變?yōu)?,3,5；在中取出3，記下，變?yōu)?,5。因此排列243對應(yīng)于“3-5變進(jìn)制數(shù)121，即

14、十進(jìn)制數(shù)19；反過來也可以從十進(jìn)制數(shù)19反推到121，再反推到排列243。各序列及其對應(yīng)的排列如下表：123000034122030124001134222131125002234522232132010335123033134011435223134135012535423235142020641230036143021741330137145022841530238152030942131039153031104233114015403211425312412131001243132042214101134323214321510214435322442311101545133045234

15、11116452331462351121745333247241120185124004824312119513401492451222051440250251130215214105125313122523411522541322352441253312200245314205431420125532421553152022653442256321210275414305732421128542431583252122954343259【總結(jié)】本文對幾個常用的Hash函數(shù)進(jìn)行了總結(jié)性的介紹和分析，并將其延伸到應(yīng)用更加廣泛的“與自然數(shù)建立一一對應(yīng)的過程。Hash是一種相當(dāng)有效的數(shù)據(jù)結(jié)構(gòu)，充分表

16、達(dá)了“空間換時間的思想。在如今競賽中內(nèi)存限制越來越松的情況下，要做到充分利用內(nèi)存空間來換取珍貴的時間，Hash能夠給我們很大幫助。我們應(yīng)當(dāng)根據(jù)題目的特點(diǎn)，選擇適合題目的數(shù)據(jù)結(jié)構(gòu)來優(yōu)化算法。對于組合與自然數(shù)的一一對應(yīng)關(guān)系，我還沒有想到好的方法，歡送大家討論?！緟⒖嘉墨I(xiàn)】Thomas H Cormen, Charles E Leiserson, Ronald L Riverst, Clifford Stald L Riverst, Clifford Stald L Riverst, Clifford Stald L Riverst, Clifford Stald L Riverst, Cliffo

17、rd Stald L Riverst, Clifford Stein. Introduction to Algorithms. Second Edition. The MIT Press, 2001劉汝佳，黃亮. ald L Riverst, Clifford St信息學(xué)競賽?. 北京：清華大學(xué)出版社，2004盧開澄，盧華明. ?組合數(shù)學(xué)?第3版. 北京：清華大學(xué)出版社，2002【附錄】常用的字符串Hash函數(shù)之源代碼：/ RS Hash Functionunsigned int RSHash(char *str)unsigned int b = 378551;unsigned int a =

18、 63689;unsigned int hash = 0;while (*str)hash = hash * a + (*str+);a *= b;return (hash & 0 x7FFFFFFF);/ JS Hash Functionunsigned int JSHash(char *str)unsigned int hash = 1315423911;while (*str)hash = (hash 2);return (hash & 0 x7FFFFFFF);/ P. J. Weinberger Hash Functionunsigned int PJWHash(char *str)

19、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)(0 xFFFFFFFF) (BitsInUnignedInt - OneEighth);unsigned in

20、t hash = 0;unsigned int test = 0;while (*str)hash = (hash ThreeQuarters) & (HighBits);return (hash & 0 x7FFFFFFF);/ ELF Hash Functionunsigned int ELFHash(char *str)unsigned int hash = 0;unsigned int x = 0;while (*str)hash = (hash 24);hash &= x;return (hash & 0 x7FFFFFFF);/ BKDR Hash Functionunsigned

21、 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 & 0 x7FFFFFFF);/ SDBM Hash Functionunsigned int SDBMHash(char *str)unsigned int hash = 0;while (*str)hash = (*str+) + (hash 6) + (hash 16) - has

22、h;return (hash & 0 x7FFFFFFF);/ DJB Hash Functionunsigned int DJBHash(char *str)unsigned int hash = 5381;while (*str)hash += (hash 5) + (*str+);return (hash & 0 x7FFFFFFF);/ AP Hash Functionunsigned int APHash(char *str)unsigned int hash = 0;int i;for (i=0; *str; i+)if (i & 1) = 0)hash = (hash 3);el

23、sehash = (hash 5);return (hash & 0 x7FFFFFFF); while ilen do begin i:=nexti; write(linei.way); end; end;begin propare; init; bfs; print;我們經(jīng)常使用的數(shù)的進(jìn)制為“常數(shù)進(jìn)制，即始終逢p進(jìn)1。例如，p進(jìn)制數(shù)K可表示為K = a0*p0 + a1*p1 + a2*p2 + . + an*pn 其中0 = ai = p-1，它可以表示任何一個自然數(shù)。對于這種常數(shù)進(jìn)制表示法，以及各種進(jìn)制之間的轉(zhuǎn)換大家應(yīng)該是很熟悉的了，但大家可能很少聽說變進(jìn)制數(shù)。這里我要介紹一種特殊的變

24、進(jìn)制數(shù)，它能夠被用來實(shí)現(xiàn) 全排列的Hash函數(shù)，并且該Hash函數(shù)能夠?qū)崿F(xiàn)完美的防碰撞和空間利用不會發(fā)生碰撞，且所有空間被完全使用，不多不少。這種全排列Hash函數(shù)也 被稱為全排列數(shù)化技術(shù)。下面，我們就來看看這種變進(jìn)制數(shù)。我們考查這樣一種變進(jìn)制數(shù)：第1位逢2進(jìn)1，第2位逢3進(jìn)1，第n位逢n+1進(jìn)1。它的表示形式為K = a1*1! + a2*2! + a3*3! + . + an*n! 其中0 = ai = i，也可以擴(kuò)展為如下形式因為按定義a0始終為0，以與p進(jìn)制表示相對應(yīng)：K = a0*0! + a1*1! + a2*2! + a3*3! + . + an*n! 其中0 = ai = i。

25、后面的變進(jìn)制數(shù)均指這種變進(jìn)制數(shù)，且采用前一種表示法先讓我們來考查一下該變進(jìn)制數(shù)的進(jìn)位是否正確。假設(shè)變進(jìn)制數(shù)K的第i位ai為i+1，需要進(jìn)位，而ai*i!=(i+1)*i!=1*(i+1)!，即正確的向高位進(jìn)1。這說明該變進(jìn)制數(shù)能夠正確進(jìn)位，從而是一種合法的計數(shù)方式。接下來我們考查n位變進(jìn)制數(shù)K的性質(zhì)：1當(dāng)所有位ai均為i時，此時K有最大值MAXK = 1*1! + 2*2! + 3*3! + . + n*n! = 1! + 1*1! + 2*2! + 3*3! + . + n*n! - 1 = (1+1)*1! + 2*2! + 3*3! + . + n*n! - 1 = 2! + 2*2!

26、+ 3*3! + . + n*n! - 1 = . = (n+1)!-1因此，n位K進(jìn)制數(shù)的最大值為(n+1)!-1。2當(dāng)所有位ai均為0時，此時K有最小值0。因此，n位變進(jìn)制數(shù)能夠表示0到(n+1)!-1的范圍內(nèi)的所有自然數(shù)，共(n+1)!個。在一些狀態(tài)空間搜索算法中，我們需要快速判斷某個狀態(tài)是否已經(jīng)出現(xiàn)，此時常常使用Hash函數(shù)來實(shí)現(xiàn)。其中，有一類特殊的狀態(tài)空間，它們是由全排列產(chǎn)生 的，比方N數(shù)碼問題。對于n個元素的全排列，共產(chǎn)生n!個不同的排列或狀態(tài)。下面將討論如何使用這里的變進(jìn)制數(shù)來實(shí)現(xiàn)一個針對全排列的Hash函數(shù)。從數(shù)的角度來看，全排列和變進(jìn)制數(shù)都用到了階乘。如果我們能夠用0到n!-

27、1這n!個連續(xù)的變進(jìn)制數(shù)來表示n個元素的所有排列，那么就能夠把全排列完全地 數(shù)化，建立起全排列和自然數(shù)之間一一對應(yīng)的關(guān)系，也就實(shí)現(xiàn)了一個完美的Hash函數(shù)。那么，我們的想法能否實(shí)現(xiàn)呢？答案是肯定的，下面將進(jìn)行討論。假設(shè)我們有b0,b1,b2,b3,.,bn共n+1個不同的元素，并假設(shè)各元素之間有一種次序關(guān)系 b0b1b2.bn。對它們進(jìn)行全排列，共產(chǎn)生(n+1)!種不同的排列。對于產(chǎn)生的任一排列 c0,c1,c2,.,cn，其中第i個元素ci1 = i = n與它前面的i個元素構(gòu)成的逆序?qū)Φ膫€數(shù)為di0 = di = i，那么我們得到一個逆序數(shù)序列d1,d2,.,dn0 = di = i。這不

28、就是前面的n位變進(jìn)制數(shù)的各個位么？于是，我們用n位變進(jìn)制數(shù)M來表示該排列：M = d1*1! + d2*2! + . + dn*n!因此，每個排列都可以按這種方式表示成一個n位變進(jìn)制數(shù)。下面，我們來考查n位變進(jìn)制數(shù)能否與n+1個元素的全排列建立起一一對應(yīng)的關(guān)系。由于n位變進(jìn)制數(shù)能表示(n+1)!個不同的數(shù)，而n+1個元素的全排列剛好有(n+1)!個不同的排列，且每一個排列都已經(jīng)能表示成一個n位變進(jìn)制數(shù)。如果我們能夠證明任意兩個不同的排列產(chǎn)生兩個不同的變進(jìn)制數(shù)，那么我們就可以得出結(jié)論： 定理1 n+1個元素的全排列的每一個排列對應(yīng)著一個不同的n位變進(jìn)制數(shù)。/*補(bǔ)充： 什么是逆序數(shù)：跟標(biāo)準(zhǔn)列相反序

29、數(shù)的總和 比方說 標(biāo)準(zhǔn)列是1 2 3 4 5 那么 5 4 3 2 1 的逆序數(shù)算法： 看第二個，4之前有一個5，在標(biāo)準(zhǔn)列中5在4的后面，所以記1個 類似的，第三個 3 之前有 4 5 都是在標(biāo)準(zhǔn)列中3的后面，所以記2個 同樣的，2 之前有3個，1之前有4個 將這些數(shù)加起來就是逆序數(shù)=1+2+3+4=10 再舉一個 2 4 3 1 5 4 之前有0個 3 之前有1個 1 之前有3個 5 之前有0個 所以逆序數(shù)就是1+3=4 */對于全排列的任意兩個不同的排列p0,p1,p2,.,pn排列P和q0,q1,q2,.,qn排列Q，從后往前查找第一個不相同的元素，分別記為pi和qi0 i pi，那么,

30、如果在排列Q中qi之前的元素x與qi構(gòu)成逆序?qū)Γ从衳 qi，那么在排列P中pi之前也有相同元素x pi因為x qi且qi pi，即在排列P中pi之前的元素x也與pi構(gòu)成逆序?qū)?，所以pi的逆序數(shù)大于等于qi的逆序數(shù)。又qi與pi在排列P中構(gòu)成pi的逆序?qū)Γ詐i的 逆序數(shù)大于qi的逆序數(shù)。2同理，如果pi qi，那么qi的逆序數(shù)大于pi的逆序數(shù)。因此，由1和2知，排列P和排列Q對應(yīng)的變進(jìn)制數(shù)至少有第i位不相同，即全排列的任意兩個不同的排列具有不同的變進(jìn)制數(shù)。至此，定理1得證。計算n個元素的一個排列的變進(jìn)制數(shù)的算法大致如下時間復(fù)雜度為O(n2)：template size_t Permutat

31、ionToNumber(const T permutation, int n)/ n不能太大，否那么會溢出如果size_t為32位，那么n = 12size_t result = 0;for (int j = 1; j n; +j) int count = 0; for (int k = 0; k permutationj) +count; / factorialsj保存著j! result += count * factorialsj;return result;總結(jié)：/實(shí)際上，如果只是求逆序數(shù) 可以做到O(n logn)，時間消耗在求逆序數(shù)上，求逆序數(shù)相當(dāng)于求排列的次數(shù)，所以是O(n lo

32、gn)的據(jù)說還可以用樹狀數(shù)組優(yōu)化。舉例：例如三個元素的排列排列 逆序 Hash123 000 0132 001 2213 010 1231 002 4312 011 3321 012 5說明：1由于n!是一個很大的數(shù)，因此一般只能用于較小的n。2有了計算排列的變進(jìn)制數(shù)的算法，我們就可以使用一個大小為n!的數(shù)組來保存每一個排列的狀態(tài)，使用排列的變進(jìn)制數(shù)作為數(shù)組下標(biāo)，從而實(shí)現(xiàn)狀態(tài)的快速檢索。如果只是標(biāo)記狀態(tài)是否出現(xiàn)，那么可以用一位來標(biāo)記狀態(tài)。end很簡單的思想是用for一遍以前搜過的狀態(tài)。但是，八數(shù)碼問題的狀態(tài)共9！，顯然for在時間上無法承受。另外一種思想是把這9位數(shù)排成一列，轉(zhuǎn)化成一個10進(jìn)制

33、的數(shù)進(jìn)行hash，但空間上的問題有無法解決了。 顯然，我們需要的是一個能夠全排列的hash，而下面得這篇文章也就介紹了對于一個n12的全排列狀態(tài)，我們應(yīng)該怎樣完成hash判重 我們經(jīng)常使用的數(shù)的進(jìn)制為“常數(shù)進(jìn)制，即始終逢p進(jìn)1。例如，p進(jìn)制數(shù)K可表示為 K = a0*p0 + a1*p1 + a2*p2 + . + an*pn 其中0 = ai = p-1，它可以表示任何一個自然數(shù)。對于這種常數(shù)進(jìn)制表示法，以及各種進(jìn)制之間的轉(zhuǎn)換大家應(yīng)該是很熟悉的了，但大家可能很少聽說變進(jìn)制數(shù)。這里我要介紹一種特殊的變進(jìn)制數(shù)，它能夠被用來實(shí)現(xiàn)全排列的Hash函數(shù)，并且該Hash函數(shù)能夠?qū)崿F(xiàn)完美的防碰撞和空間利用

34、不會發(fā)生碰撞，且所有空間被完全使用，不多不少。這種全排列Hash函數(shù)也被稱為全排列數(shù)化技術(shù)。下面，我們就來看看這種變進(jìn)制數(shù)。我們考查這樣一種變進(jìn)制數(shù)：第1位逢2進(jìn)1，第2位逢3進(jìn)1，第n位逢n+1進(jìn)1。它的表示形式為 K = a1*1! + a2*2! + a3*3! + . + an*n! 其中0 = ai = i，也可以擴(kuò)展為如下形式因為按定義a0始終為0，以與p進(jìn)制表示相對應(yīng)： K = a0*0! + a1*1! + a2*2! + a3*3! + . + an*n! 其中0 = ai = i。后面的變進(jìn)制數(shù)均指這種變進(jìn)制數(shù)，且采用前一種表示法先讓我們來考查一下該變進(jìn)制數(shù)的進(jìn)位是否正確。

35、假設(shè)變進(jìn)制數(shù)K的第i位ai為i+1，需要進(jìn)位，而ai*i!=(i+1)*i!=1*(i+1)!，即正確的向高位進(jìn)1。這說明該變進(jìn)制數(shù)能夠正確進(jìn)位，從而是一種合法的計數(shù)方式。接下來我們考查n位變進(jìn)制數(shù)K的性質(zhì)：1當(dāng)所有位ai均為i時，此時K有最大值 MAXK = 1*1! + 2*2! + 3*3! + . + n*n! = 1! + 1*1! + 2*2! + 3*3! + . + n*n! - 1 = (1+1)*1! + 2*2! + 3*3! + . + n*n! - 1 = 2! + 2*2! + 3*3! + . + n*n! - 1 = . = (n+1)!-1 因此，n位K進(jìn)制數(shù)

36、的最大值為(n+1)!-1。2當(dāng)所有位ai均為0時，此時K有最小值0。因此，n位變進(jìn)制數(shù)能夠表示0到(n+1)!-1的范圍內(nèi)的所有自然數(shù)，共(n+1)!個。在一些狀態(tài)空間搜索算法中，我們需要快速判斷某個狀態(tài)是否已經(jīng)出現(xiàn)，此時常常使用Hash函數(shù)來實(shí)現(xiàn)。其中，有一類特殊的狀態(tài)空間，它們是由全排列產(chǎn)生的，比方N數(shù)碼問題。對于n個元素的全排列，共產(chǎn)生n!個不同的排列或狀態(tài)。下面將討論如何使用這里的變進(jìn)制數(shù)來實(shí)現(xiàn)一個針對全排列的Hash函數(shù)。從數(shù)的角度來看，全排列和變進(jìn)制數(shù)都用到了階乘。如果我們能夠用0到n!-1這n!個連續(xù)的變進(jìn)制數(shù)來表示n個元素的所有排列，那么就能夠把全排列完全地數(shù)化，建立起全排列

37、和自然數(shù)之間一一對應(yīng)的關(guān)系，也就實(shí)現(xiàn)了一個完美的Hash函數(shù)。那么，我們的想法能否實(shí)現(xiàn)呢？答案是肯定的，下面將進(jìn)行討論。假設(shè)我們有b0,b1,b2,b3,.,bn共n+1個不同的元素，并假設(shè)各元素之間有一種次序關(guān)系 b0b1b2.bn。對它們進(jìn)行全排列，共產(chǎn)生(n+1)!種不同的排列。對于產(chǎn)生的任一排列 c0,c1,c2,.,cn，其中第i個元素ci1 = i = n與它前面的i個元素構(gòu)成的逆序?qū)Φ膫€數(shù)為di0 = di = i，那么我們得到一個逆序數(shù)序列d1,d2,.,dn0 = di = i。這不就是前面的n位變進(jìn)制數(shù)的各個位么？于是，我們用n位變進(jìn)制數(shù)M來表示該排列： M = d1*1!

38、 + d2*2! + . + dn*n!因此，每個排列都可以按這種方式表示成一個n位變進(jìn)制數(shù)。下面，我們來考查n位變進(jìn)制數(shù)能否與n+1個元素的全排列建立起一一對應(yīng)的關(guān)系。由于n位變進(jìn)制數(shù)能表示(n+1)!個不同的數(shù)，而n+1個元素的全排列剛好有(n+1)!個不同的排列，且每一個排列都已經(jīng)能表示成一個n位變進(jìn)制數(shù)。如果我們能夠證明任意兩個不同的排列產(chǎn)生兩個不同的變進(jìn)制數(shù)，那么我們就可以得出結(jié)論： 定理1 n+1個元素的全排列的每一個排列對應(yīng)著一個不同的n位變進(jìn)制數(shù)。對于全排列的任意兩個不同的排列p0,p1,p2,.,pn排列P和q0,q1,q2,.,qn排列Q，從后往前查找第一個不相同的元素，分

39、別記為pi和qi0 i pi，那么,如果在排列Q中qi之前的元素x與qi構(gòu)成逆序?qū)?，即有x qi，那么在排列P中pi之前也有相同元素x pi因為x qi且qi pi，即在排列P中pi之前的元素x也與pi構(gòu)成逆序?qū)Γ詐i的逆序數(shù)大于等于qi的逆序數(shù)。又qi與pi在排列P中構(gòu)成pi的逆序?qū)Γ詐i的逆序數(shù)大于qi的逆序數(shù)。2同理，如果pi qi，那么qi的逆序數(shù)大于pi的逆序數(shù)。因此，由1和2知，排列P和排列Q對應(yīng)的變進(jìn)制數(shù)至少有第i位不相同，即全排列的任意兩個不同的排列具有不同的變進(jìn)制數(shù)。至此，定理1得證。 我把上面的定理總結(jié)簡化了一下，具體的內(nèi)容是這樣的1、 計算出階乘factorial1n-1的數(shù)值，存放在數(shù)組factorial中2、 對于一個隨機(jī)得到的全排列a。從第二位開始設(shè)為ai，計算在i之前有多少個比ai大的數(shù)也就是ai和aj構(gòu)成逆序?qū)i，設(shè)為count個3、 讓hash值+count*factoriali-1； 以下的偽代碼給出了hash函數(shù)對一個全排列的過程function gethash(全排列a):longint; begin gethash:=0; for i:=2 to n do /注意，一定是第二位，因為從第二位開始才可能出