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

1、Hash函數(shù)的設(shè)計(jì)優(yōu)化天津南開中學(xué) 李羽修【摘要】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é)?！娟P(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ì)是無(wú)法預(yù)知的，因此數(shù)學(xué)推理將受到很大限制。我們用實(shí)驗(yàn)的方法研究這個(gè)

2、隨機(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.11.6倍范圍內(nèi)選擇。例如的值域?yàn)?，那么即為一個(gè)不錯(cuò)的選擇。競(jìng)賽的時(shí)候可以寫一個(gè)素

3、數(shù)生成器或干脆自己寫一個(gè)“比擬像素?cái)?shù)的數(shù)。我用4000個(gè)數(shù)插入一個(gè)容量為701的Hash表，得到的結(jié)果是：測(cè)試數(shù)據(jù)隨機(jī)數(shù)據(jù)連續(xù)數(shù)據(jù)最小單元容量：05最大單元容量：156期望容量：標(biāo)準(zhǔn)差：可見對(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ù)最好是無(wú)理數(shù)，得到一個(gè)之間的實(shí)數(shù)；取出其小數(shù)局部，乘以，再取整數(shù)局部，即得在Hash表中的位置。函數(shù)表達(dá)式可以寫成：；其中表示的小數(shù)局部，即。例如，表容量，種子是一個(gè)實(shí)際效果很

4、好的選擇，關(guān)鍵值，那么。同樣用4000個(gè)數(shù)插入一個(gè)容量為701的Hash表，得到的結(jié)果是：測(cè)試數(shù)據(jù)隨機(jī)數(shù)據(jù)連續(xù)數(shù)據(jù)最小單元容量：04最大單元容量：157期望容量：標(biāo)準(zhǔn)差：從公式中可以看出，這個(gè)方法受的影響是很小的，在的值比擬不適合直接取余法的時(shí)候這個(gè)方法的表現(xiàn)很好。但是從上面的測(cè)試來(lái)看，其表現(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ì)其平方中間的假設(shè)干位產(chǎn)生影響，因此這個(gè)方法的效果也是不錯(cuò)的。但是對(duì)于比擬

5、小的值效果并不是很理想，實(shí)現(xiàn)起來(lái)也比擬繁瑣。為了充分利用Hash表的空間，最好取2的整數(shù)次冪。例如，表容量，關(guān)鍵值，那么。用4000個(gè)數(shù)插入一個(gè)容量為512的Hash表注意這里沒有用701，是為了利用Hash表的空間，得到的結(jié)果是：測(cè)試數(shù)據(jù)隨機(jī)數(shù)據(jù)連續(xù)數(shù)據(jù)最小單元容量：01最大單元容量：1717期望容量：標(biāo)準(zhǔn)差：效果比我們想象的要差，尤其是對(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ù)平方取中法中較好

6、快無(wú)從這個(gè)表格中我們很容易看出，直接取余法的性價(jià)比是最高的，因此也是我們競(jìng)賽中用得最多的一種方法。對(duì)于實(shí)數(shù)的Hash函數(shù)，我們可以直接利用乘積取整法；而對(duì)于標(biāo)本為其他類型數(shù)據(jù)的Hash函數(shù)，我們可以先將其轉(zhuǎn)換為整數(shù)，然后再將其插入Hash表。下面我們來(lái)研究把其他類型數(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ù)值都相同。想想看，為什么？常

7、用的字符串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è)不同的句子，作為短字符串和長(zhǎng)字符串的測(cè)試數(shù)據(jù)，然后用不同的Hash函數(shù)把它們變成整數(shù)，再用直接取余法插入一個(gè)容量為1237的Hash表，遇到?jīng)_突那么用新字符串覆蓋舊字符串。通過觀察最后“剩下的字符串的個(gè)數(shù)，我們可以粗略地得出不同的Hash函數(shù)實(shí)際效果。短字符串長(zhǎng)字符串平均編碼

8、難度直接取余數(shù)667676易P. J. Weinberger Hash683676難ELF Hash683676較難SDBM Hash694680易BKDR Hash665710較易DJB Hash694683較易AP Hash684698較難RS Hash691693較難JS Hash684708較易把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ù)的代碼如下：

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ù)雜，如果對(duì)效果要求不是特別高的話SDBMHash是一個(gè)很好的選擇。三、排列的Hash函數(shù)準(zhǔn)確的說，這里我們的研究不再僅僅局限在“Hashing的工作，而是進(jìn)化到一個(gè)“numerize的過程，也就是說我們可以在排列和1到的自然數(shù)之間建立一一對(duì)應(yīng)的關(guān)系。這樣我們就可以利用這個(gè)關(guān)系來(lái)直接定址，或者用作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é)歸納法。時(shí)，等式顯然

11、成立。假設(shè)時(shí)等式成立，即。那么時(shí)，即時(shí)等式亦成立。綜上所述，成立。把這個(gè)式子變形一下：上式和類似。不難證明，從0到的任何自然數(shù)可唯一地表示為其中，。甚至在式子后面加上一個(gè)也無(wú)妨，在后面我們把這一項(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)的某一排列，其中可

12、以看做是排列中數(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；反過來(lái)也可以從19反推到301，再反推到排列4213。3更一般性的排列受到這個(gè)思路啟發(fā)，我們同樣可以把更一般性的排列與自然數(shù)之間建立一一對(duì)應(yīng)關(guān)系。想一想從個(gè)元素中選個(gè)的排列數(shù)的公式是怎么來(lái)的？根據(jù)乘法原理，我們有這是由于在排列的第1個(gè)位置有種選擇，在排列的第2個(gè)位置有種選擇，在排列的第個(gè)位置有種選擇。既然這樣，我們可以定義一種“m-n變進(jìn)制數(shù)，使其第1位是進(jìn)制，第2位

13、是進(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)?,3,4,5；在中取出4，記下，變?yōu)?,3,5；在中取出3，記下，變?yōu)?,5。因此排列243對(duì)應(yīng)于“3-5變進(jìn)制數(shù)121，即

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

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

16、達(dá)了“空間換時(shí)間的思想。在如今競(jìng)賽中內(nèi)存限制越來(lái)越松的情況下，要做到充分利用內(nèi)存空間來(lái)?yè)Q取珍貴的時(shí)間，Hash能夠給我們很大幫助。我們應(yīng)當(dāng)根據(jù)題目的特點(diǎn)，選擇適合題目的數(shù)據(jù)結(jié)構(gòu)來(lái)優(yōu)化算法。對(duì)于組合與自然數(shù)的一一對(duì)應(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é)競(jìng)賽?. 北京：清華大學(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，它可以表示任何一個(gè)自然數(shù)。對(duì)于這種常數(shù)進(jìn)制表示法，以及各種進(jìn)制之間的轉(zhuǎn)換大家應(yīng)該是很熟悉的了，但大家可能很少聽說變進(jìn)制數(shù)。這里我要介紹一種特殊的變

24、進(jìn)制數(shù)，它能夠被用來(lái)實(shí)現(xiàn) 全排列的Hash函數(shù)，并且該Hash函數(shù)能夠?qū)崿F(xiàn)完美的防碰撞和空間利用不會(huì)發(fā)生碰撞，且所有空間被完全使用，不多不少。這種全排列Hash函數(shù)也 被稱為全排列數(shù)化技術(shù)。下面，我們就來(lái)看看這種變進(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ò)展為如下形式因?yàn)榘炊xa0始終為0，以與p進(jìn)制表示相對(duì)應(yīng)：K = a0*0! + a1*1! + a2*2! + a3*3! + . + an*n! 其中0 = ai = i。

25、后面的變進(jìn)制數(shù)均指這種變進(jìn)制數(shù)，且采用前一種表示法先讓我們來(lái)考查一下該變進(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)位，從而是一種合法的計(jì)數(shù)方式。接下來(lái)我們考查n位變進(jìn)制數(shù)K的性質(zhì)：1當(dāng)所有位ai均為i時(shí)，此時(shí)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時(shí)，此時(shí)K有最小值0。因此，n位變進(jìn)制數(shù)能夠表示0到(n+1)!-1的范圍內(nèi)的所有自然數(shù)，共(n+1)!個(gè)。在一些狀態(tài)空間搜索算法中，我們需要快速判斷某個(gè)狀態(tài)是否已經(jīng)出現(xiàn)，此時(shí)常常使用Hash函數(shù)來(lái)實(shí)現(xiàn)。其中，有一類特殊的狀態(tài)空間，它們是由全排列產(chǎn)生 的，比方N數(shù)碼問題。對(duì)于n個(gè)元素的全排列，共產(chǎn)生n!個(gè)不同的排列或狀態(tài)。下面將討論如何使用這里的變進(jìn)制數(shù)來(lái)實(shí)現(xiàn)一個(gè)針對(duì)全排列的Hash函數(shù)。從數(shù)的角度來(lái)看，全排列和變進(jìn)制數(shù)都用到了階乘。如果我們能夠用0到n!-

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

28、就是前面的n位變進(jìn)制數(shù)的各個(gè)位么？于是，我們用n位變進(jìn)制數(shù)M來(lái)表示該排列：M = d1*1! + d2*2! + . + dn*n!因此，每個(gè)排列都可以按這種方式表示成一個(gè)n位變進(jìn)制數(shù)。下面，我們來(lái)考查n位變進(jìn)制數(shù)能否與n+1個(gè)元素的全排列建立起一一對(duì)應(yīng)的關(guān)系。由于n位變進(jìn)制數(shù)能表示(n+1)!個(gè)不同的數(shù)，而n+1個(gè)元素的全排列剛好有(n+1)!個(gè)不同的排列，且每一個(gè)排列都已經(jīng)能表示成一個(gè)n位變進(jìn)制數(shù)。如果我們能夠證明任意兩個(gè)不同的排列產(chǎn)生兩個(gè)不同的變進(jìn)制數(shù)，那么我們就可以得出結(jié)論： 定理1 n+1個(gè)元素的全排列的每一個(gè)排列對(duì)應(yīng)著一個(gè)不同的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ù)算法： 看第二個(gè)，4之前有一個(gè)5，在標(biāo)準(zhǔn)列中5在4的后面，所以記1個(gè) 類似的，第三個(gè) 3 之前有 4 5 都是在標(biāo)準(zhǔn)列中3的后面，所以記2個(gè) 同樣的，2 之前有3個(gè)，1之前有4個(gè) 將這些數(shù)加起來(lái)就是逆序數(shù)=1+2+3+4=10 再舉一個(gè) 2 4 3 1 5 4 之前有0個(gè) 3 之前有1個(gè) 1 之前有3個(gè) 5 之前有0個(gè) 所以逆序數(shù)就是1+3=4 */對(duì)于全排列的任意兩個(gè)不同的排列p0,p1,p2,.,pn排列P和q0,q1,q2,.,qn排列Q，從后往前查找第一個(gè)不相同的元素，分別記為pi和qi0 i pi，那么,

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

31、ionToNumber(const T permutation, int n)/ n不能太大，否那么會(huì)溢出如果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ù)上，求逆序數(shù)相當(dāng)于求排列的次數(shù)，所以是O(n lo

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

33、的數(shù)進(jìn)行hash，但空間上的問題有無(wú)法解決了。 顯然，我們需要的是一個(gè)能夠全排列的hash，而下面得這篇文章也就介紹了對(duì)于一個(gè)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，它可以表示任何一個(gè)自然數(shù)。對(duì)于這種常數(shù)進(jìn)制表示法，以及各種進(jìn)制之間的轉(zhuǎn)換大家應(yīng)該是很熟悉的了，但大家可能很少聽說變進(jìn)制數(shù)。這里我要介紹一種特殊的變進(jìn)制數(shù)，它能夠被用來(lái)實(shí)現(xiàn)全排列的Hash函數(shù)，并且該Hash函數(shù)能夠?qū)崿F(xiàn)完美的防碰撞和空間利用

34、不會(huì)發(fā)生碰撞，且所有空間被完全使用，不多不少。這種全排列Hash函數(shù)也被稱為全排列數(shù)化技術(shù)。下面，我們就來(lái)看看這種變進(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ò)展為如下形式因?yàn)榘炊xa0始終為0，以與p進(jìn)制表示相對(duì)應(yīng)： K = a0*0! + a1*1! + a2*2! + a3*3! + . + an*n! 其中0 = ai = i。后面的變進(jìn)制數(shù)均指這種變進(jìn)制數(shù)，且采用前一種表示法先讓我們來(lái)考查一下該變進(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)位，從而是一種合法的計(jì)數(shù)方式。接下來(lái)我們考查n位變進(jìn)制數(shù)K的性質(zhì)：1當(dāng)所有位ai均為i時(shí)，此時(shí)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時(shí)，此時(shí)K有最小值0。因此，n位變進(jìn)制數(shù)能夠表示0到(n+1)!-1的范圍內(nèi)的所有自然數(shù)，共(n+1)!個(gè)。在一些狀態(tài)空間搜索算法中，我們需要快速判斷某個(gè)狀態(tài)是否已經(jīng)出現(xiàn)，此時(shí)常常使用Hash函數(shù)來(lái)實(shí)現(xiàn)。其中，有一類特殊的狀態(tài)空間，它們是由全排列產(chǎn)生的，比方N數(shù)碼問題。對(duì)于n個(gè)元素的全排列，共產(chǎn)生n!個(gè)不同的排列或狀態(tài)。下面將討論如何使用這里的變進(jìn)制數(shù)來(lái)實(shí)現(xiàn)一個(gè)針對(duì)全排列的Hash函數(shù)。從數(shù)的角度來(lái)看，全排列和變進(jìn)制數(shù)都用到了階乘。如果我們能夠用0到n!-1這n!個(gè)連續(xù)的變進(jìn)制數(shù)來(lái)表示n個(gè)元素的所有排列，那么就能夠把全排列完全地?cái)?shù)化，建立起全排列

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

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

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