简单的哈希表实现 C语言
2015年06月30日[TOC] 博客园文章地址 http://www.cnblogs.com/oloroso/archive/2015/06/30/4610109.html
简单的哈希表实现
这是一个简单的哈希表的实现，用c语言做的。
原理
先说一下原理。
先是有一个bucket数组，也就是所谓的桶。
哈希表的特点就是数据与其在表中的位置存在相关性，也就是有关系的，通过数据应该可以计算出其位置。
这个哈希表是用于存储一些键值对(key – value)关系的数据，其key也就是其在表中的索引，value是附带的数据。
通过散列算法，将字符串的key映射到某个桶中，这个算法是确定的，也就是说一个key必然对应一个bucket。
然后是碰撞问题，也就是说多个key对应一个索引值。举个例子：有三个key:key1,key3,key5通过散列算法keyToIndex得到的索引值都为2，也就是这三个key产生了碰撞，对于碰撞的处理，采取的是用链表连接起来，而没有进行再散列。
这是包含的头文件
#include <stdio.h> #include <stdlib.h> #include <string.h>#define BUCKETCOUNT 16
哈希表和节点数据结构的定义
1 struct hashEntry 2 { 3 const char key; 4 char value; 5 struct hashEntry next; 6 }; 7 8 typedef struct hashEntry entry; 9 10 struct hashTable 11 { 12 entry bucket[BUCKETCOUNT]; //先默认定义16个桶 13 }; 14 15 typedef struct hashTable table;
初始化和释放哈希表
1 //初始化哈希表 2 void initHashTable(table t) 3 { 4 int i; 5 if (t == NULL)return; 6 7 for (i = 0; i < BUCKETCOUNT; ++i) { 8 t->bucket[i].key = NULL; 9 t->bucket[i].value = NULL; 10 t->bucket[i].next = NULL; 11 } 12 } 13 14 //释放哈希表 15 void freeHashTable(table t) 16 { 17 int i; 18 entry e,ep; 19 if (t == NULL)return; 20 for (i = 0; i<BUCKETCOUNT; ++i) { 21 e = &(t->bucket[i]); 22 while (e->next != NULL) { 23 ep = e->next; 24 e->next = ep->next; 25 free(ep->key); 26 free(ep->value); 27 free(ep); 28 } 29 } 30 }
哈希散列算法
1 //哈希散列方法函数 2 int keyToIndex(const char key) 3 { 4 int index , len , i; 5 if (key == NULL)return -1; 6 7 len = strlen(key); 8 index = (int)key[0]; 9 for (i = 1; i<len; ++i) { 10 index = 1103515245 + (int)key[i]; 11 } 12 index >>= 27; 13 index &= (BUCKETCOUNT - 1); 14 return index; 15 }
辅助函数strDup
这是比较多余的做法，因为C标准库中string.h中有一系列这样的函数。
1 //在堆上分配足以保存str的内存 2 //并拷贝str内容到新分配位置 3 char strDup(const char str) 4 { 5 int len; 6 char ret; 7 if (str == NULL)return NULL; 8 9 len = strlen(str); 10 ret = (char*)malloc(len + 1); 11 if (ret != NULL) { 12 memcpy(ret , str , len); 13 ret[len] = ‘\0‘; 14 } 15 return ret; 16 }
string.h中的相关函数
#include <string.h><span style="color: #0000ff;">char</span> *strdup(<span style="color: #0000ff;">const</span> <span style="color: #0000ff;">char</span> *<span style="color: #000000;">s); </span><span style="color: #0000ff;">char</span> *strndup(<span style="color: #0000ff;">const</span> <span style="color: #0000ff;">char</span> *<span style="color: #000000;">s, size_t n); </span><span style="color: #0000ff;">char</span> *strdupa(<span style="color: #0000ff;">const</span> <span style="color: #0000ff;">char</span> *<span style="color: #000000;">s); </span><span style="color: #0000ff;">char</span> *strndupa(<span style="color: #0000ff;">const</span> <span style="color: #0000ff;">char</span> *s, size_t n);</pre>
哈希表的插入和修改
这个了插入和修改是一个方法，如果key在哈希表中已经存在，那么就是修改value，否则就是插入一个节点。
1 //向哈希表中插入数据 2 int insertEntry(table* t , const char* key , const char value) 3 { 4 int index , vlen1 , vlen2; 5 entry e , ep; 6 7 if (t == NULL || key == NULL || value == NULL) { 8 return -1; 9 } 10 11 index = keyToIndex(key); 12 if (t->bucket[index].key == NULL) { 13 t->bucket[index].key = strDup(key); 14 t->bucket[index].value = strDup(value); 15 } 16 else { 17 e = ep = &(t->bucket[index]); 18 while (e != NULL) { //先从已有的找 19 if (strcmp(e->key , key) == 0) { 20 //找到key所在，替换值 21 vlen1 = strlen(value); 22 vlen2 = strlen(e->value); 23 if (vlen1 > vlen2) { 24 free(e->value); 25 e->value = (char)malloc(vlen1 + 1); 26 } 27 memcpy(e->value , value , vlen1 + 1); 28 return index; //插入完成了 29 } 30 ep = e; 31 e = e->next; 32 } // end while(e… 33 34 //没有在当前桶中找到 35 //创建条目加入 36 e = (entry)malloc(sizeof (entry)); 37 e->key = strDup(key); 38 e->value = strDup(value); 39 e->next = NULL; 40 ep->next = e; 41 } 42 return index; 43 }
哈希表中查找
因为这个哈希表中保存的是键值对，所以这个方法是从哈希表中查找key对应的value的。要注意，这里返回的是value的地址，不应该对其指向的数据进行修改，否则可能会有意外发生。
1 //在哈希表中查找key对应的value 2 //找到了返回value的地址，没找到返回NULL 3 const char findValueByKey(const table* t , const char key) 4 { 5 int index; 6 const entry e; 7 if (t == NULL || key == NULL) { 8 return NULL; 9 } 10 index = keyToIndex(key); 11 e = &(t->bucket[index]); 12 if (e->key == NULL) return NULL;//这个桶还没有元素 13 while (e != NULL) { 14 if (0 == strcmp(key , e->key)) { 15 return e->value; //找到了，返回值 16 } 17 e = e->next; 18 } 19 return NULL; 20 }
哈希表元素的移除
这个函数用于将哈希表中key对应的节点移除，如果其不存在，那就返回NULL。如果存在，就返回这个节点的地址。注意，这里并没有释放节点，如果不需要了，应该手动释放它。
1 //在哈希表中查找key对应的entry 2 //找到了返回entry，并将其从哈希表中移除 3 //没找到返回NULL 4 entry* removeEntry(table* t , char key) 5 { 6 int index; 7 entry e,*ep; //查找的时候，把ep作为返回值 8 if (t == NULL || key == NULL) { 9 return NULL; 10 } 11 index = keyToIndex(key); 12 e = &(t->bucket[index]); 13 while (e != NULL) { 14 if (0 == strcmp(key , e->key)) { 15 //如果是桶的第一个 16 if (e == &(t->bucket[index])) { 17 //如果这个桶有两个或以上元素 18 //交换第一个和第二个，然后移除第二个 19 ep = e->next; 20 if (ep != NULL) { 21 entry tmp = *e; //做浅拷贝交换 22 *e = *ep;//相当于链表的头节点已经移除 23 ep = tmp; //这就是移除下来的链表头节点 24 ep->next = NULL; 25 } 26 else {//这个桶只有第一个元素 27 ep = (entry)malloc(sizeof(entry)); 28 *ep = e; 29 e->key = e->value = NULL; 30 e->next = NULL; 31 } 32 } 33 else { 34 //如果不是桶的第一个元素 35 //找到它的前一个(这是前面设计不佳导致的多余操作) 36 ep = &(t->bucket[index]); 37 while (ep->next != e)ep = ep->next; 38 //将e从中拿出来 39 ep->next = e->next; 40 e->next = NULL; 41 ep = e; 42 } 43 return ep; 44 }// end if(strcmp… 45 e = e->next; 46 } 47 return NULL; 48 }
哈希表打印
这个函数用于打印哈希表的内容的。
1 void printTable(table t) 2 { 3 int i; 4 entry* e; 5 if (t == NULL)return; 6 for (i = 0; i<BUCKETCOUNT; ++i) { 7 printf(“\nbucket[%d]:\n“ , i); 8 e = &(t->bucket[i]); 9 while (e->key != NULL) { 10 printf(“\t%s\t=\t%s\n“ , e->key , e->value); 11 if (e->next == NULL)break; 12 e = e->next; 13 } 14 } 15 }
测试一下
用于测试的数据来自于本机相关信息。
int main() { table t; initHashTable(&t);insertEntry(</span>&t , <span style="color: #800000;">"</span><span style="color: #800000;">电脑型号</span><span style="color: #800000;">"</span> , <span style="color: #800000;">"</span><span style="color: #800000;">华硕 X550JK 笔记本电脑</span><span style="color: #800000;">"</span><span style="color: #000000;">); insertEntry(</span>&t , <span style="color: #800000;">"</span><span style="color: #800000;">操作系统</span><span style="color: #800000;">"</span> , <span style="color: #800000;">"</span><span style="color: #800000;">Windows 8.1 64位 (DirectX 11)</span><span style="color: #800000;">"</span><span style="color: #000000;">); insertEntry(</span>&t , <span style="color: #800000;">"</span><span style="color: #800000;">处理器</span><span style="color: #800000;">"</span> , <span style="color: #800000;">"</span><span style="color: #800000;">英特尔 Core i7 - 4710HQ @ 2.50GHz 四核</span><span style="color: #800000;">"</span><span style="color: #000000;">); insertEntry(</span>&t , <span style="color: #800000;">"</span><span style="color: #800000;">主板</span><span style="color: #800000;">"</span> , <span style="color: #800000;">"</span><span style="color: #800000;">华硕 X550JK(英特尔 Haswell)</span><span style="color: #800000;">"</span><span style="color: #000000;">); insertEntry(</span>&t , <span style="color: #800000;">"</span><span style="color: #800000;">内存</span><span style="color: #800000;">"</span> , <span style="color: #800000;">"</span><span style="color: #800000;">4 GB(Hynix / Hyundai)</span><span style="color: #800000;">"</span><span style="color: #000000;">); insertEntry(</span>&t , <span style="color: #800000;">"</span><span style="color: #800000;">主硬盘</span><span style="color: #800000;">"</span> , <span style="color: #800000;">"</span><span style="color: #800000;">日立 HGST HTS541010A9E680(1 TB / 5400 转 / 分)</span><span style="color: #800000;">"</span><span style="color: #000000;">); insertEntry(</span>&t , <span style="color: #800000;">"</span><span style="color: #800000;">显卡</span><span style="color: #800000;">"</span> , <span style="color: #800000;">"</span><span style="color: #800000;">NVIDIA GeForce GTX 850M (2 GB / 华硕)</span><span style="color: #800000;">"</span><span style="color: #000000;">); insertEntry(</span>&t , <span style="color: #800000;">"</span><span style="color: #800000;">显示器</span><span style="color: #800000;">"</span> , <span style="color: #800000;">"</span><span style="color: #800000;">奇美 CMN15C4(15.3 英寸)</span><span style="color: #800000;">"</span><span style="color: #000000;">); insertEntry(</span>&t , <span style="color: #800000;">"</span><span style="color: #800000;">光驱</span><span style="color: #800000;">"</span> , <span style="color: #800000;">"</span><span style="color: #800000;">松下 DVD - RAM UJ8E2 S DVD刻录机</span><span style="color: #800000;">"</span><span style="color: #000000;">); insertEntry(</span>&t , <span style="color: #800000;">"</span><span style="color: #800000;">声卡</span><span style="color: #800000;">"</span> , <span style="color: #800000;">"</span><span style="color: #800000;">Conexant SmartAudio HD @ 英特尔 Lynx Point 高保真音频</span><span style="color: #800000;">"</span><span style="color: #000000;">); insertEntry(</span>&t , <span style="color: #800000;">"</span><span style="color: #800000;">网卡</span><span style="color: #800000;">"</span> , <span style="color: #800000;">"</span><span style="color: #800000;">瑞昱 RTL8168 / 8111 / 8112 Gigabit Ethernet Controller / 华硕</span><span style="color: #800000;">"</span><span style="color: #000000;">); insertEntry(</span>&t , <span style="color: #800000;">"</span><span style="color: #800000;">主板型号</span><span style="color: #800000;">"</span> , <span style="color: #800000;">"</span><span style="color: #800000;">华硕 X550JK</span><span style="color: #800000;">"</span><span style="color: #000000;">); insertEntry(</span>&t , <span style="color: #800000;">"</span><span style="color: #800000;">芯片组</span><span style="color: #800000;">"</span> , <span style="color: #800000;">"</span><span style="color: #800000;">英特尔 Haswell</span><span style="color: #800000;">"</span><span style="color: #000000;">); insertEntry(</span>&t , <span style="color: #800000;">"</span><span style="color: #800000;">BIOS</span><span style="color: #800000;">"</span> , <span style="color: #800000;">"</span><span style="color: #800000;">X550JK.301</span><span style="color: #800000;">"</span><span style="color: #000000;">); insertEntry(</span>&t , <span style="color: #800000;">"</span><span style="color: #800000;">制造日期</span><span style="color: #800000;">"</span> , <span style="color: #800000;">"</span><span style="color: #800000;">06 / 26 / 2014</span><span style="color: #800000;">"</span><span style="color: #000000;">); insertEntry(</span>&t , <span style="color: #800000;">"</span><span style="color: #800000;">主人</span><span style="color: #800000;">"</span> , <span style="color: #800000;">"</span><span style="color: #800000;">就是我</span><span style="color: #800000;">"</span><span style="color: #000000;">); insertEntry(</span>&t , <span style="color: #800000;">"</span><span style="color: #800000;">价格</span><span style="color: #800000;">"</span> , <span style="color: #800000;">"</span><span style="color: #800000;">六十张红色毛主席</span><span style="color: #800000;">"</span><span style="color: #000000;">); insertEntry(</span>&t , <span style="color: #800000;">"</span><span style="color: #800000;">主硬盘</span><span style="color: #800000;">"</span> , <span style="color: #800000;">"</span><span style="color: #800000;">换了个120G的固态</span><span style="color: #800000;">"</span><span style="color: #000000;">); entry</span>* e = removeEntry(&t , <span style="color: #800000;">"</span><span style="color: #800000;">主板型号</span><span style="color: #800000;">"</span><span style="color: #000000;">); </span><span style="color: #0000ff;">if</span> (e !=<span style="color: #000000;"> NULL) { puts(</span><span style="color: #800000;">"</span><span style="color: #800000;">找到后要释放</span><span style="color: #800000;">"</span><span style="color: #000000;">); </span><span style="color: #0000ff;">free</span>(e-><span style="color: #000000;">key); </span><span style="color: #0000ff;">free</span>(e-><span style="color: #000000;">value); </span><span style="color: #0000ff;">free</span><span style="color: #000000;">(e); e </span>=<span style="color: #000000;"> NULL; } printTable(</span>&<span style="color: #000000;">t); </span><span style="color: #0000ff;">const</span> <span style="color: #0000ff;">char</span>* keys[] = { <span style="color: #800000;">"</span><span style="color: #800000;">显示器</span><span style="color: #800000;">"</span> , <span style="color: #800000;">"</span><span style="color: #800000;">主人</span><span style="color: #800000;">"</span>,<span style="color: #800000;">"</span><span style="color: #800000;">没有</span><span style="color: #800000;">"</span> , <span style="color: #800000;">"</span><span style="color: #800000;">处理器</span><span style="color: #800000;">"</span><span style="color: #000000;"> }; </span><span style="color: #0000ff;">for</span> (<span style="color: #0000ff;">int</span> i = <span style="color: #800080;">0</span>; i < <span style="color: #800080;">4</span>; ++<span style="color: #000000;">i) { </span><span style="color: #0000ff;">const</span> <span style="color: #0000ff;">char</span>* value = findValueByKey(&<span style="color: #000000;">t , keys[i]); </span><span style="color: #0000ff;">if</span> (value !=<span style="color: #000000;"> NULL) { printf(</span><span style="color: #800000;">"</span><span style="color: #800000;">find %s\t=\t%s\n</span><span style="color: #800000;">"</span><span style="color: #000000;"> ,keys[i], value); } </span><span style="color: #0000ff;">else</span><span style="color: #000000;"> { printf(</span><span style="color: #800000;">"</span><span style="color: #800000;">not found %s\n</span><span style="color: #800000;">"</span><span style="color: #000000;">,keys[i]); } } freeHashTable(</span>&<span style="color: #000000;">t); getchar(); </span><span style="color: #0000ff;">return</span> <span style="color: #800080;">0</span><span style="color: #000000;">;}