基於BKDRhash實現Hash算法

哈希(Hash)算法,即散列函數。它是一種單向密碼體制,即它是一個從明文到密文的不可逆的映射,只有加密過程,沒有解密過程。同時,哈希函數可以將任意長度的輸入經過變化以後得到固定長度的輸出。hash算法一般用於快速查找和加密。

hash算法可以使用的哈希函數種類很多，處理沖突的方法也有開放定址、再哈希、鏈地址、公共溢出區等。

因此，在編寫代碼之前，首先需要根據所要處理的數據，選擇合適的hash函數和沖突處理辦法。開放定址需要空閒存儲單元，所需要的表比實際容量大，而且容易產生二次聚集發生新沖突。鏈地址使用鏈表存儲關鍵字，可以隨時插入新數據，數據量大小不受限制。缺點是要用到指針，給新單元分配地址需要時間，會一定程度上減慢算法速度，但影響不大可以忽略。

筆者需要處理的是一個10W行字符串的字典，關鍵字重復率高。因此選擇適用於字符串的哈希函數，常用字符串哈希函數有 BKDRhash,APHash,DJBHash,JSHash,RSHash,SDBMHash,PJWHash,ELFHash等，個人傾向於BKDRHash，記憶和使用都很簡便。

BKDRHash函數代碼如下：

unsigned int BKDRhash(TYPE key)
{//BKDRhash函數
unsigned int seed = 131;
unsigned int hash = 0;

while(*key != '\n' && *key != 0) //通常使用時，判別條件為*key != 0即可，此處的*key != '\n'是因筆者程序需要
hash = hash * seed + (*key++);

return hash % DICLEN;
}
對於關鍵字重復的沖突處理方法，筆者這裡使用鏈地址法。hash表結構體如下：

#define STRLEN 15
  #define DICLEN 100000

  typedef char* TYPE;
  typedef int BOOL;

  typedef struct _NODE{
      TYPE data;
      struct _NODE* next;
 }NODE;

 typedef struct _HASH_TABLE{
     NODE* phead;           //此變量可以不用，這裡使用是為了減少其他函數中的重新定義過程
     NODE** chainhash;
 }HASH_TABLE;

准備工作OK，整理好思路，可以開始編寫hash算法了。O(∩_∩)O

首先，創建一個hash表，並對哈希表，鏈表，頭節點進行初始化。

NODE* create_node()
  {//開辟節點
      NODE* pnode = (NODE*)malloc(sizeof(NODE));
      memset(pnode, 0, sizeof(NODE));

      pnode->data = (char*)malloc(STRLEN * sizeof(char));
      memset(pnode->data, 0, STRLEN * sizeof(char));
      pnode->next = NULL;

     return pnode;
 }

 HASH_TABLE* create_hash()
 {//創建hash表
     HASH_TABLE* new_hash_table = (HASH_TABLE*)malloc(sizeof(HASH_TABLE));
     memset(new_hash_table, 0, sizeof(HASH_TABLE));

     new_hash_table->phead = create_node();
     new_hash_table->chainhash = (NODE**)malloc(DICLEN * sizeof(NODE*));

     for(int i = 0; i < DICLEN; i++){        
         new_hash_table->chainhash[i] = (NODE*)malloc(sizeof(NODE));
         memset(new_hash_table->chainhash[i], 0, sizeof(NODE));
     }

     return new_hash_table;
 }

插入數據

鏈表的chainhash每個分量的初始狀態都是空指針，凡是哈希函數值 BKDRhash(data)相同的記錄，都插入同一個鏈表chainhash[i]，此時i = BKDRhash(data)。該鏈表頭結點不為空的話，指針就後移，在表尾插入新記錄（表頭、表尾插入均可，只要保持每次操作相同，即同一鏈表中的關鍵字有序）。

BOOL insert_data(HASH_TABLE* hash, NODE* phead, TYPE data)
  {//插入新數據
      if(hash == NULL)
          return 0;

      if(hash->chainhash[BKDRhash(data)]->data == NULL){
          NODE* newnode = create_node();

          strcpy(newnode->data, data);
         newnode->next = NULL;
         hash->chainhash[BKDRhash(data)]->data = newnode->data;
         hash->chainhash[BKDRhash(data)]->next = newnode->next;

         free(newnode);
         return 1;
     }

     else{        
         phead = hash->chainhash[BKDRhash(data)];

         while(phead->next != NULL)
             phead = phead->next;

         phead->next = create_node();

         strcpy(phead->next->data, data);
         phead->next->next = NULL;

         return 1;
     }
 }

查找數據

查找數據時，首先通過哈希函數值找到對應的鏈表，然後比較字符串內容。

NODE* find_data(HASH_TABLE* hash, NODE* phead, TYPE data)
  {//查找數據
      phead = hash->chainhash[BKDRhash(data)];

      if(hash == NULL)
          return NULL;

      while(phead != NULL){

         if(strncmp(phead->data, data, STRLEN) == 0)
             return phead;
         else
             phead = phead->next;
     }

     return NULL;
 }

刪除數據

刪除數據類似於單鏈表的刪除操作

BOOL del_data(HASH_TABLE* hash, NODE* phead, TYPE data)
  {//刪除數據

      phead->next = create_node();
      phead->next = hash->chainhash[BKDRhash(data)];

      if(hash == NULL)
          return 0;

     while(phead->next != NULL){

         if(strncmp(phead->next->data, data, STRLEN) == 0){

             if(phead->next->data == hash->chainhash[BKDRhash(data)]->data)
                 hash->chainhash[BKDRhash(data)] = phead->next->next;
             else
                 phead->next = phead->next->next;

             return 1;
         }
         else
             phead->next = phead->next->next;
     }

     free(phead->next);

     return 0;
 }

修改數據

修改數據非常簡單，即先刪除後插入

 BOOL alter_data(HASH_TABLE* hash, NODE* phead, TYPE data, TYPE new_data)
  {//修改數據
      if(hash == NULL)
          return 0;

      if(data == new_data)
          return 1;

      if(del_data(hash, phead, data) == 1){

         if(insert_data(hash, phead, new_data) == 1)
             return 1;
         else
             return 0;
     }

     else
         return 0;
 }

這樣，一個簡單的hash算法就寫好了！筆者冗長的測試代碼如下。。。。至於為什麼測試要寫這麼長，筆者也不造o(╯□╰)o

 int main(int argc, char* argv[])
  {//測試
      int i = 0;
      char* testdata = "kyxntghcxolgqlw\n";
      char data[STRLEN + 2] = {0};

      HASH_TABLE* dic = create_hash();

      FILE* fp = fopen("dic.txt", "r+");
     assert(fp != 0);

     while(i < DICLEN){
         fgets(data, STRLEN + 2, fp);
         insert_data(dic, dic->phead, data);    
         i++;
    }

     //查找測試
     if(find_data(dic, dic->phead, testdata) != NULL)    
         printf("find it: %s\n", (find_data(dic, dic->phead, testdata))->data);    
     else
         printf("no this data!\n");

     //刪除再查找測試
     if(del_data(dic, dic->phead, testdata) == 1)
         printf("delete it!\n");
     else
         printf("try again!\n");

     if(find_data(dic, dic->phead, testdata) != NULL)    
         printf("find it: %s\n", (find_data(dic, dic->phead, testdata))->data);
     else
         printf("no this data!\n");

     //修改數據測試
     testdata = "fpwdwpk";
     char* newdata = "bibibibibiu\n";

     if(alter_data(dic, dic->phead, testdata, newdata) == 1){

         if(find_data(dic, dic->phead, newdata) != NULL)    
             printf("find it: %s\n", (find_data(dic, dic->phead, newdata))->data);
         else
             printf("no this data!\n");
     }

     fclose(fp);
     free(dic);

     return 0;
 }