算法之個人總結：Hash表之簡單應用

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

【算法之個人總結：Hash表之簡單應用】相關文章：

履歷表之四05-04

履歷表之五05-04

知之好之樂之03-02

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

時之彼處岸之未央04-28

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

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

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

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

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