哈希表對字元串的高效處理

哈希表對字元串的高效處理

       哈希表（散清單）是一種非常高效的查找資料結構，在原理上也與其他的查找不盡相同，它回避了關鍵字之間反複比較的繁瑣，而是直接一步到位查找結果。當然，這也帶來了記錄之間沒有任何關聯的弊端。應該說，散清單對于那些查找性能要求高，記錄之間關系無要求的資料有非常好的适用性。注意對散列函數的選擇和處理沖突的方法。

       Hash表是使用 O(1)時間進行資料的插入、删除和查找，但是 hash 表不保證表中資料的有序性，這樣在 hash 表中查找最大資料或者最小資料的時間是 O(N) 。

/* 字元串中完成過濾重複字元的功能，

【輸入】:1.常字元串；2.字元串長度；3.【out】用于輸出過濾後的字元串.

【輸出】：過濾後的字元串。

*/

思路1, 循環判定法。第1步，先記錄字元串中第1個字元；第2步，然後從第2個字元開始，判定其和其前面的字元是否相同，不相同的話，則統計進去；相同的話則繼續周遊，直到字元串末尾（遇到’\0’）。時間複雜度：O（n2）。

思路2, 哈希表過濾法。第1步，初始化一個哈希表，用以存儲字元（key）及字元出現的次數；第2步，周遊哈希表，進行統計計數；第3步，輸出統計次數為1及統計次數多餘1的（輸出1次）。時間複雜度：O（n）。

//循環判定法過濾掉重複字元

void stringFilter(const char*pInputStr, long lInputLen, char *pOutputStr)

{

      if(pInputStr== NULL || lInputLen == 0 || pOutputStr == NULL)

      {

             return;

      }

      intnCnt = 0;

      *pOutputStr= pInputStr[0];            //先處理第一個

      ++nCnt;

      intnNotEqualCnt = 0;                 //統計計數

      for(inti = 1; i < lInputLen; i++)

             nNotEqualCnt= 0;

             for(intj = i-1; j >=0; j--)

             {

                    if(pInputStr[i]!= pInputStr[j])

                    {

                           ++nNotEqualCnt;

                    }

             }

             if(nNotEqualCnt== i)  //和前面的都不一樣.

                    pOutputStr[nCnt++]= pInputStr[i];

      }//endfor

      pOutputStr[nCnt]= '\0';

}

//哈希表法過濾字元串中的重複字元

void stringFilterFast(const char*pInputStr, long lInputLen, char *pOutputStr)

      charrstChar = '\0';

      boolbNotRepeatFound = false;

      constunsigned int size = 256;

      unsignedint hashTable[size];

      constchar* pHashKey = pInputStr;

      intoutPutCnt = 0;

      if(pInputStr== NULL)

      //初始化哈希表

      for(unsignedint i = 0; i < size; i++)

             hashTable[i]= 0;

      //将pString讀入到哈希表中

      while(*pHashKey!= '\0')

             cout<< *pHashKey << "\t";

             hashTable[*pHashKey]++;    //統計計數

             pHashKey++;

      }    

      //讀取哈希表，對隻出現1次的進行存儲，對出現多次的進行1次存儲。

      pHashKey= pInputStr;

             if((hashTable[*(pHashKey)])== 1)   //僅有一次，

                    pOutputStr[outPutCnt++]= *pHashKey;

             elseif((hashTable[*(pHashKey)]) > 1) // 多餘一次，統計第一次

                    hashTable[*(pHashKey)]= 0;

      pOutputStr[outPutCnt]= '\0';

int main()

      constchar* strSrc = "desdefedeffdsswwwwwwwwwwdd";//"desdefedeffdssw";

      char*strRst =new char[strlen(strSrc)+1];

      stringFilter(strSrc,strlen(strSrc), strRst);

      cout<< strRst << endl;

      if (NULL != strRst){  delete[] strRst;  strRst = NULL;}      return 0;

//哈希表法查找字元串中第一個不重複的字元

【功能】：查找字元串中第一個不重複的字元。

【輸入】：字元串。

【輸出】：第一個不重複的字元。

時間複雜度O（n），思路類似于上面的哈希表過濾法。

char FirstNotRepeatingChar(constchar* pString)

      unsignedchar hashTable[size];

      constchar* pHashKey = pString;

      if(pString== NULL)

             returnrstChar;

             hashTable[i] = 0;

      //将pString存入到哈希表中

             hashTable[*(pHashKey++)]++;    //統計計數

      //讀取哈希表，找到第一個=1的字元，bNotRepeatFound用于查找。.

      pHashKey= pString;

             if((hashTable[*(pHashKey)]) == 1)

                    bNotRepeatFound= true;

                    rstChar= *pHashKey;

                    break;

      if(bNotRepeatFound)

             cout<< "The first not Repeate char is " << rstChar <<endl;

      else

             cout<< "The first not Repeate char is not Exist " << endl;

      returnrstChar;

      constchar* strSrc = "google";

      constchar* strSrc2 = "[email protected]";

      constchar* strSrc3 = "aabbccddeeff";

      constchar* strsrc4 = "11111111";  

      constchar* strArray[4] = {strSrc, strSrc2, strSrc3, strsrc4};

     for(inti = 0; i < 4; i++)

     {

             FirstNotRepeatingChar(strArray[i]);

      return0;

舉一反三：【百度面試題】對于一個海量的檔案中存儲着不同的URL，用最小的時間複雜度去除重複的URL。可借鑒字元串處理的哈希表過濾法。不過，這裡的大檔案等價于之前的字元串，這裡的URL等價于之前的字元。