算法之個(gè)人總結(jié)：Hash表之簡(jiǎn)單應(yīng)用

前段時(shí)間看了個(gè)微軟編寫(xiě)的C庫(kù)函數(shù)，在這個(gè)庫(kù)函數(shù)里學(xué)到一個(gè)自我感覺(jué)相當(dāng)牛比的小算法，說(shuō)白了是Hash表的應(yīng)用。大家都知道，Hash表最主要是用來(lái)實(shí)現(xiàn)查找功能的，再具體點(diǎn)是用常量級(jí)時(shí)間復(fù)雜度找到你想查找的東西。首先，我以一個(gè)小問(wèn)題引入將要介紹的Hash算法，問(wèn)題如下：現(xiàn)有字符串str1，str2，編寫(xiě)一個(gè)函數(shù)返回str1中有多少個(gè)字符在str2字符串中。其實(shí)這個(gè)函數(shù)也很簡(jiǎn)單(假如我們不考慮時(shí)間復(fù)雜度的話(huà))，遍歷str1字符串，其中對(duì)于str1中的每一個(gè)字符都要去判斷是否在str2字符串中，如果在統(tǒng)計(jì)變量加1，即需要兩個(gè)for循環(huán)，即時(shí)間復(fù)雜度為0(LenA*LenB)，程序也很簡(jiǎn)單，如下：//返回字符串str1中有多少個(gè)字符在str2字符串中int CharCount(const char*str1,const char*str2){int ct=0；const char*ptr；for(；*str1！='\0'；++str1){//每次從str2的開(kāi)頭開(kāi)始遍歷for(ptr=str2；*ptr！='\0'；++ptr){if(*str1==*ptr)//如果發(fā)現(xiàn)str1當(dāng)前字符在str2字符串中{++ct；break；}}}return ct；}這個(gè)程序每次判斷str1中的字符是否在字符串str2中時(shí)，str2字符串均需要從開(kāi)頭遍歷，即每次需要回溯，從而使得整個(gè)算法的時(shí)間復(fù)雜度很高，那么我們是否可以用常量級(jí)時(shí)間復(fù)雜度來(lái)執(zhí)行上面程序的內(nèi)循環(huán)?即我們是否可以用常量級(jí)時(shí)間復(fù)雜度來(lái)判斷某字符是否在字符串str2中?答案是肯定的，此時(shí)就需要Hash表。首先我先敘述下關(guān)于這個(gè)思路微軟的算法是什么。即如何用常量級(jí)時(shí)間復(fù)雜度來(lái)判斷一個(gè)字符是否在某個(gè)字符串中。首先我們先解決這個(gè)問(wèn)題，你能否按照某種映射方式將256個(gè)字符一一映射到一個(gè)數(shù)組里，換句話(huà)說(shuō)已知char arr[32],你能否將256個(gè)字符映射到這個(gè)數(shù)組里?我們都知道ASCII值總共是256個(gè)(即2^8)，如果我們將這256個(gè)字符分組，每組字符個(gè)數(shù)是8，那么可以分256/8組，即32組，因此對(duì)于ASCII值為c的字符，它屬于編號(hào)為c/8的組(組的編號(hào)是0-31)，因此，我們可以建立一個(gè)含有32個(gè)元素的數(shù)組，編號(hào)相同的8個(gè)字符存放在一個(gè)單元，在一個(gè)單元里如何來(lái)區(qū)分這8個(gè)字符呢?如果接著分析下去，易知，每一組中的8個(gè)字符除以8的余數(shù)均是0-7，因此，我們可以根據(jù)這8個(gè)字符除以8的余數(shù)來(lái)分別區(qū)分它們，具體辦法如下：用一個(gè)char類(lèi)型數(shù)據(jù)，char類(lèi)型數(shù)據(jù)的最低位來(lái)表示除以8余數(shù)是0的那個(gè)字符，倒數(shù)第二位表示除以8余數(shù)是1的字符，從而可以將每一組中的8個(gè)字符用一個(gè)char類(lèi)型數(shù)據(jù)的每一位表示。例如：ASCII值是49的字符應(yīng)該這樣存放在Hash表中(含有32個(gè)元素的數(shù)組)，首先49/8等于6即編號(hào)是6，其次49%8等于1，即這個(gè)單元的char數(shù)據(jù)的bit1位是1，即arr[6]中的char數(shù)據(jù)的二進(jìn)制應(yīng)該為00000010；有了上述算法的思想，那么我們就可以用char arr[32]來(lái)存放一個(gè)字符串str2了，依次遍歷這個(gè)字符串，按照上述原則依次標(biāo)記數(shù)組中相應(yīng)位置，字符串str2中每一個(gè)字符c的位置是arr[c/8]，其次使得該char數(shù)據(jù)的第c%8 bit置1，假如arr數(shù)組中每一個(gè)元素初始值均為0，那么可以這樣實(shí)現(xiàn)：//使得編號(hào)為c/8的單元中的char數(shù)據(jù)的第c%8 bit置1 arr[c/8]=arr[c/8]|(1(c%8))；如果將str2中的每一個(gè)字符按照上述原則標(biāo)記好了，假如我們要在str2中查找字符a，那么可以判斷編號(hào)為a/8的單元中的char數(shù)據(jù)的第a%8 bit是否為1，如果是說(shuō)明字符a在str2中，即：if((arr[a/8]&(1(a%8)))！=0)//說(shuō)明字符a存在的看看利用這種方法是不是實(shí)現(xiàn)了常量時(shí)間復(fù)雜度查找某字符是否在字符串中?嘿嘿！重新回到開(kāi)頭的那個(gè)問(wèn)題，判斷str1中的字符是否在str2中，查找算法就可以用上述思路來(lái)實(shí)現(xiàn)，即只需要遍歷str1字符串，之后用上述常量時(shí)間復(fù)雜度的查找算法判斷str1當(dāng)前字符是否在str2中，易知時(shí)間復(fù)雜度是O(LenA)，算法如下：int CharCount_(const char*str1,const char*str2){char hash[32]；//hash表的初始化for(int i=0；i 32；++i)hash=0；//用hash保存str2中所有字符const char*pstr2=str2；for(；*pstr2！='\0'；++pstr2){hash[*pstr2/8]|=(1(*pstr2%8))；}int ct=0；//遍歷str1字符串，判斷每個(gè)字符是否在hash表中(是否在str2字符串中)for(；*str1！='\0'；++str1){if(hash[*str1/8]&(1(*str1%8)))++ct；}return ct；}其實(shí)上述算法還可以加快，我們都知道計(jì)算機(jī)在處理除法以及取模運(yùn)算時(shí)相對(duì)是較慢的，因此我們可以用位運(yùn)算來(lái)實(shí)現(xiàn)上面的除法和取模運(yùn)算，*str1/8等價(jià)于*str1 3，另外，一個(gè)數(shù)N除以2^m的余數(shù)實(shí)際上是N的低m bit位所表示的十進(jìn)制數(shù)，即*str1%(2^3)等價(jià)于*str1&7(具體可以自己想)，因此上述算法的極限代碼是：int CharCount_(const char*str1,const char*str2){char hash[32]；//hash表的初始化for(int i=0；i 32；++i)hash=0；//用hash保存str2中所有字符const char*pstr2=str2；for(；*pstr2！='\0'；++pstr2){hash[*pstr2 3]|=(1(*pstr2&7))；//優(yōu)化之一}int ct=0；//遍歷str1字符串，判斷每個(gè)字符是否在hash表中(是否在str2字符串中)for(；*str1！='\0'；++str1){if(hash[*str1 3]&(1(*str1&7)))//優(yōu)化之二++ct；}return ct；}至此，整個(gè)算法已經(jīng)詳細(xì)給出�？偨Y(jié)：1)看到此不知道你是否徹底理解了上述Hash表的建立，其實(shí)細(xì)心的讀者可能會(huì)提出這樣的問(wèn)題，為什么把256個(gè)字符分成32組(每組只存放8個(gè)字符)?呵呵，其實(shí)不一定非得分成32組，也可以分成16組，也可以分成8組，。其實(shí)算法的本質(zhì)是在內(nèi)存中用256bits來(lái)表示這256個(gè)字符是否存在，我們完全可以分成16組，每一組用16bit來(lái)表示，即short arr[16]；或者分成8組，即int arr[8]，自己可以實(shí)現(xiàn)下。2)現(xiàn)在你能否實(shí)現(xiàn)一個(gè)這樣的函數(shù)：size_t strspn(const char*s,const char*accept)；函數(shù)說(shuō)明：strspn()從參數(shù)s字符串的開(kāi)頭計(jì)算連續(xù)的字符，而這些字符都完全是accept所指字符串中的字符。簡(jiǎn)單的說(shuō)，若strspn()返回的數(shù)值為n，則代表字符串s開(kāi)頭連續(xù)有n個(gè)字符都是屬于字符串a(chǎn)ccept內(nèi)的字符，即字符串s中第n+1個(gè)字符不屬于accept字符串中，要求時(shí)間復(fù)雜度為0(N)(嘿嘿，其實(shí)這就是一個(gè)C庫(kù)函數(shù)，相信你時(shí)間復(fù)雜度為0(N*N)的算法馬上就能寫(xiě)出來(lái)吧)3)回顧文章開(kāi)始那個(gè)問(wèn)題，其實(shí)是利用了空間換取時(shí)間的思想，即增加了算法的空間復(fù)雜度(因?yàn)槲覀冾~外建立了一個(gè)Hash數(shù)組)，但是算法的時(shí)間復(fù)雜度變成了O(N)，因此在內(nèi)存空間不是問(wèn)題的情況下，利用這種增加空間復(fù)雜度換取時(shí)間復(fù)雜度的思想值得我們?nèi)タ紤]。4)如果你足夠細(xì)心，那么利用本篇介紹的Hash算法，你此時(shí)一定能將C庫(kù)函數(shù)strtok實(shí)現(xiàn)出來(lái)，個(gè)人認(rèn)為這個(gè)庫(kù)函數(shù)是字符串庫(kù)函數(shù)中最最難的一個(gè)，不僅其功能難理解，實(shí)現(xiàn)起來(lái)也很困難，呵呵，其實(shí)我就是在看微軟編寫(xiě)的strtok源碼的時(shí)候才發(fā)現(xiàn)了本篇這個(gè)hash算法的，哈哈，strtok這個(gè)函數(shù)一定要去看哦，諾西兩年筆試題目均從不同角度考察了該函數(shù)的實(shí)現(xiàn)。總結(jié)2)strspn函數(shù)代碼補(bǔ)充：//算法時(shí)間復(fù)雜度為O(Len1*Len2)int MyStrspn(const char*str1,const char*str2){const char*temp；int ct=0；//非法輸入if(str1==NULL||str2==NULL)return ct；for(；*str1！='\0'；++str1){//每次令temp指向str2字符串開(kāi)頭，來(lái)判斷*str1是否在字符串str1中for(temp=str2；*temp！='\0'；++temp){if(*str1==*temp)//*str1在字符串str2中，那么停止break；}if(*temp=='\0')//如果遍歷完str2了(說(shuō)明*str1不在str2中)break；else++ct；}return ct；}//時(shí)間復(fù)雜度為O(Len1)int MyStrspn_(const char*str1,const char*str2){//非法輸入if(str1==NULL||str2==NULL)return 0；//分成16組，每組是16 bits(2字節(jié))short Hash[16]；//hash表的初始化for(int i=0；i 16；++i)Hash=0；//將str2字符串每一個(gè)字符映射到數(shù)組Hash中const char*Pstr2；for(Pstr2=str2；*Pstr2！='\0'；++Pstr2)Hash[*Pstr2/16]|=1(*Pstr2%16)；int ct=0；//while(*str1在字符串str2中&&*str1！='\0')while((Hash[*str1/16]&(1(*str1%16)))&&(*str1！='\0')){++str1；++ct；}return ct；}以上只是個(gè)人看法，個(gè)人理解，如有不足請(qǐng)指正！3Q！

【算法之個(gè)人總結(jié)：Hash表之簡(jiǎn)單應(yīng)用】相關(guān)文章：

履歷表之四05-04

履歷表之五05-04

知之好之樂(lè)之03-02

柳之韻，柳之美作文08-08

時(shí)之彼處岸之未央04-28

祭退之,祭退之張籍,祭退之的意思,祭退之賞析 -詩(shī)詞大全03-13

身之所往，心之所向作文09-22

身之所往心之所向作文09-25

心之所向身之所往作文09-24

蔥之黃，蔥之綠_650字05-01