首页 > 代码库 > 逐步实现hash算法（基于BKDRhash函数）
逐步实现hash算法（基于BKDRhash函数）
哈希(Hash)算法,即散列函数。它是一种单向密码体制,即它是一个从明文到密文的不可逆的映射,只有加密过程,没有解密过程。同时,哈希函数可以将任意长度的输入经过变化以后得到固定长度的输出。hash算法一般用于快速查找和加密。
hash算法可以使用的哈希函数种类很多，处理冲突的方法也有开放定址、再哈希、链地址、公共溢出区等。
因此，在编写代码之前，首先需要根据所要处理的数据，选择合适的hash函数和冲突处理办法。开放定址需要空闲存储单元，所需要的表比实际容量大，而且容易产生二次聚集发生新冲突。链地址使用链表存储关键字，可以随时插入新数据，数据量大小不受限制。缺点是要用到指针，给新单元分配地址需要时间，会一定程度上减慢算法速度，但影响不大可以忽略。
笔者需要处理的是一个10W行字符串的字典，关键字重复率高。因此选择适用于字符串的哈希函数，常用字符串哈希函数有 BKDRHash,APHash,DJBHash,JSHash,RSHash,SDBMHash,PJWHash,ELFHash等，个人倾向于BKDRHash，记忆和使用都很简便。
BKDRHash函数代码如下：
1 unsigned int BKDRhash(TYPE key) 2 {//BKDRhash函数 3 unsigned int seed = 131; 4 unsigned int hash = 0; 5 6 while(*key != ‘\n‘ && *key != 0) //通常使用时，判别条件为*key != 0即可，此处的*key != ‘\n‘是因笔者程序需要 7 hash = hash * seed + (*key++); 8 9 return hash % DICLEN;10 }对于关键字重复的冲突处理方法，笔者这里使用链地址法。hash表结构体如下：
1 #define STRLEN 15 2 #define DICLEN 100000 3 4 typedef char* TYPE; 5 typedef int BOOL; 6 7 typedef struct _NODE{ 8 TYPE data; 9 struct _NODE* next;10 }NODE;11 12 typedef struct _HASH_TABLE{13 NODE* phead; //此变量可以不用，这里使用是为了减少其他函数中的重新定义过程14 NODE** chainhash;15 }HASH_TABLE;
准备工作OK，整理好思路，可以开始编写hash算法了。O(∩_∩)O
首先，创建一个hash表，并对哈希表，链表，头节点进行初始化。
1 NODE* create_node() 2 {//开辟节点 3 NODE* pnode = (NODE*)malloc(sizeof(NODE)); 4 memset(pnode, 0, sizeof(NODE)); 5 6 pnode->data = http://www.mamicode.com/(char*)malloc(STRLEN * sizeof(char)); 7 memset(pnode->data, 0, STRLEN * sizeof(char)); 8 pnode->next = NULL; 9 10 return pnode;11 }12 13 HASH_TABLE* create_hash()14 {//创建hash表15 HASH_TABLE* new_hash_table = (HASH_TABLE*)malloc(sizeof(HASH_TABLE));16 memset(new_hash_table, 0, sizeof(HASH_TABLE));17 18 new_hash_table->phead = create_node();19 new_hash_table->chainhash = (NODE**)malloc(DICLEN * sizeof(NODE*));20 21 for(int i = 0; i < DICLEN; i++){ 22 new_hash_table->chainhash[i] = (NODE*)malloc(sizeof(NODE));23 memset(new_hash_table->chainhash[i], 0, sizeof(NODE));24 }25 26 return new_hash_table;27 }插入数据
链表的chainhash每个分量的初始状态都是空指针，凡是哈希函数值 BKDRhash(data)相同的记录，都插入同一个链表chainhash[i]，此时i = BKDRhash(data)。该链表头结点不为空的话，指针就后移，在表尾插入新记录（表头、表尾插入均可，只要保持每次操作相同，即同一链表中的关键字有序）。
1 BOOL insert_data(HASH_TABLE* hash, NODE* phead, TYPE data) 2 {//插入新数据 3 if(hash == NULL) 4 return 0; 5 6 if(hash->chainhash[BKDRhash(data)]->data =http://www.mamicode.com/= NULL){ 7 NODE* newnode = create_node(); 8 9 strcpy(newnode->data, data);10 newnode->next = NULL;11 hash->chainhash[BKDRhash(data)]->data = http://www.mamicode.com/newnode->data;12 hash->chainhash[BKDRhash(data)]->next = newnode->next;13 14 free(newnode);15 return 1;16 }17 18 else{ 19 phead = hash->chainhash[BKDRhash(data)];20 21 while(phead->next != NULL)22 phead = phead->next;23 24 phead->next = create_node();25 26 strcpy(phead->next->data, data);27 phead->next->next = NULL;28 29 return 1;30 }31 }查找数据
查找数据时，首先通过哈希函数值找到对应的链表，然后比较字符串内容。
1 NODE* find_data(HASH_TABLE* hash, NODE* phead, TYPE data) 2 {//查找数据 3 phead = hash->chainhash[BKDRhash(data)]; 4 5 if(hash == NULL) 6 return NULL; 7 8 while(phead != NULL){ 9 10 if(strncmp(phead->data, data, STRLEN) == 0)11 return phead;12 else13 phead = phead->next;14 }15 16 return NULL;17 }删除数据
删除数据类似于单链表的删除操作
1 BOOL del_data(HASH_TABLE* hash, NODE* phead, TYPE data) 2 {//删除数据 3 4 phead->next = create_node(); 5 phead->next = hash->chainhash[BKDRhash(data)]; 6 7 if(hash == NULL) 8 return 0; 9 10 while(phead->next != NULL){11 12 if(strncmp(phead->next->data, data, STRLEN) == 0){13 14 if(phead->next->data =http://www.mamicode.com/= hash->chainhash[BKDRhash(data)]->data)15 hash->chainhash[BKDRhash(data)] = phead->next->next;16 else17 phead->next = phead->next->next;18 19 return 1;20 }21 else22 phead->next = phead->next->next;23 }24 25 free(phead->next);26 27 return 0;28 }修改数据
修改数据非常简单，即先删除后插入
1 BOOL alter_data(HASH_TABLE* hash, NODE* phead, TYPE data, TYPE new_data) 2 {//修改数据 3 if(hash == NULL) 4 return 0; 5 6 if(data =http://www.mamicode.com/= new_data) 7 return 1; 8 9 if(del_data(hash, phead, data) == 1){10 11 if(insert_data(hash, phead, new_data) == 1)12 return 1;13 else14 return 0;15 }16 17 else18 return 0;19 }
这样，一个简单的hash算法就写好了！笔者冗长的测试代码如下。。。。至于为什么测试要写这么长，笔者也不造o(╯□╰)o
测试用10W行字典：
http://yunpan.cn/Q7BBIXwd3uTYe 访问密码 8889
1 int main(int argc, char* argv[]) 2 {//测试 3 int i = 0; 4 char* testdata = http://www.mamicode.com/"kyxntghcxolgqlw\n"; 5 char data[STRLEN + 2] = {0}; 6 7 HASH_TABLE* dic = create_hash(); 8 9 FILE* fp = fopen("dic.txt", "r+");10 assert(fp != 0);11 12 while(i < DICLEN){13 fgets(data, STRLEN + 2, fp);14 insert_data(dic, dic->phead, data); 15 i++;16 }17 18 //查找测试19 if(find_data(dic, dic->phead, testdata) != NULL) 20 printf("find it: %s\n", (find_data(dic, dic->phead, testdata))->data); 21 else22 printf("no this data!\n");23 24 //删除再查找测试25 if(del_data(dic, dic->phead, testdata) == 1)26 printf("delete it!\n");27 else28 printf("try again!\n");29 30 if(find_data(dic, dic->phead, testdata) != NULL) 31 printf("find it: %s\n", (find_data(dic, dic->phead, testdata))->data);32 else33 printf("no this data!\n");34 35 //修改数据测试36 testdata = http://www.mamicode.com/"fpwdwpk";37 char* newdata = http://www.mamicode.com/"bibibibibiu\n";38 39 if(alter_data(dic, dic->phead, testdata, newdata) == 1){40 41 if(find_data(dic, dic->phead, newdata) != NULL) 42 printf("find it: %s\n", (find_data(dic, dic->phead, newdata))->data);43 else44 printf("no this data!\n");45 }46 47 fclose(fp);48 free(dic);49 50 return 0;51 }
欢迎转载，请备注原始连接http://www.cnblogs.com/liuliuliu/p/3966851.html，并注明转载。
作者bibibi_liuliu，联系方式395985239@qq.com
逐步实现hash算法（基于BKDRhash函数）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。