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

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