简单的哈希表实现 C语言

简单的哈希表实现

这是一个简单的哈希表的实现，用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] = '';
14     }
15     return ret;
16 }

string.h中的相关函数

       #include <string.h>

       char *strdup(const char *s);

       char *strndup(const char *s, size_t n);
       char *strdupa(const char *s);
       char *strndupa(const char *s, size_t n);

哈希表的插入和修改

这个了插入和修改是一个方法，如果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("
bucket[%d]:
" , i);
 8         e = &(t->bucket[i]);
 9         while (e->key != NULL) {
10             printf("	%s	=	%s
" , e->key , e->value);
11             if (e->next == NULL)break;
12             e = e->next;
13         }
14     }
15 }

测试一下

用于测试的数据来自于本机相关信息。

int main()
{
    table t;
    initHashTable(&t);

    insertEntry(&t , "电脑型号" , "华硕 X550JK 笔记本电脑");
    insertEntry(&t , "操作系统" , "Windows 8.1 64位 (DirectX 11)");
    insertEntry(&t , "处理器" , "英特尔 Core i7 - 4710HQ @ 2.50GHz 四核");
    insertEntry(&t , "主板" , "华硕 X550JK(英特尔 Haswell)");
    insertEntry(&t , "内存" , "4 GB(Hynix / Hyundai)");
    insertEntry(&t , "主硬盘" , "日立 HGST HTS541010A9E680(1 TB / 5400 转 / 分)");
    insertEntry(&t , "显卡" , "NVIDIA GeForce GTX 850M       (2 GB / 华硕)");
    insertEntry(&t , "显示器" , "奇美 CMN15C4(15.3 英寸)");
    insertEntry(&t , "光驱" , "松下 DVD - RAM UJ8E2 S DVD刻录机");
    insertEntry(&t , "声卡" , "Conexant SmartAudio HD @ 英特尔 Lynx Point 高保真音频");
    insertEntry(&t , "网卡" , "瑞昱 RTL8168 / 8111 / 8112 Gigabit Ethernet Controller / 华硕");
    insertEntry(&t , "主板型号" , "华硕 X550JK");
    insertEntry(&t , "芯片组" , "英特尔 Haswell");
    insertEntry(&t , "BIOS" , "X550JK.301");
    insertEntry(&t , "制造日期" , "06 / 26 / 2014");
    insertEntry(&t , "主人" , "就是我");
    insertEntry(&t , "价格" , "六十张红色毛主席");
    insertEntry(&t , "主硬盘" , "换了个120G的固态");

    entry* e = removeEntry(&t , "主板型号");
    if (e != NULL) {
        puts("找到后要释放");
        free(e->key);
        free(e->value);
        free(e);
        e = NULL;
    }

    printTable(&t);

    const char* keys[] = { "显示器" , "主人","没有" , "处理器" };
    for (int i = 0; i < 4; ++i) {
        const char* value = findValueByKey(&t , keys[i]);
        if (value != NULL) {
            printf("find %s	=	%s
" ,keys[i], value);
        }
        else {
            printf("not found %s
",keys[i]);
        }
    }


    freeHashTable(&t);
    getchar();
    return 0;
}
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/oloroso/p/4610109.html