基于BKDRhash实现Hash算法

发布时间：2014-09-12 00:00 来源：bibibi_liuliu

哈希(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;
 }