找回密码
 立即注册→加入我们

QQ登录

只需一步,快速开始

搜索
热搜: 下载 VB C 实现 编写
查看: 1844|回复: 3

c语言实现的哈希表

[复制链接]

9

主题

10

回帖

451

积分

用户组: 中·技术宅

UID
5181
精华
3
威望
39 点
宅币
260 个
贡献
79 次
宅之契约
0 份
在线时间
42 小时
注册时间
2019-7-25
发表于 2021-6-26 01:09:44 | 显示全部楼层 |阅读模式

欢迎访问技术宅的结界,请注册或者登录吧。

您需要 登录 才可以下载或查看,没有账号?立即注册→加入我们

×
本帖最后由 天马座 于 2021-7-11 02:05 编辑
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4. //哈希桶数量

  5. #define HASHSIZE (1 << 16)

  6. typedef int Value;

  7. struct list {
  8.         //单链表
  9.         char *key;
  10.         Value value;
  11.         struct list *next;
  12. }
  13. ;
  14. //哈希表
  15. struct list *hashList[HASHSIZE];

  16. Value valuedup(Value value){
  17.         //兼容字符串代码
  18.         return value;

  19. }

  20. struct list *newNode(char* key,Value value) {
  21.         //创建一个新节点
  22.         struct list *p = (struct list *)malloc(sizeof(struct list));
  23.         if (p == NULL)
  24.                 return NULL;
  25.         p->key = strdup(key);
  26.         if (p->key == NULL){
  27.                 free(p);
  28.                 return NULL;
  29.         }
  30.         p->value = valuedup(value);
  31.         //if (p->value == NULL){
  32.         //        free(p->key);
  33.         //        free(p);
  34.         //        return NULL;
  35.         //}
  36.         return p;

  37. }

  38. void freeNode(struct list *p){
  39.         //释放节点
  40.         free(p->key);
  41.         //free(p->value);
  42.        free(p);
  43. }

  44. unsigned int hashCode(char* s) {
  45.         //计算哈希值
  46.         unsigned int h = 0;
  47.         while(*s != '\0')
  48.                 h = *s++ + 31 * h;
  49.         return h;
  50. }
  51. int indexOf(char *key) {
  52.         //计算key所在的下标
  53.         return hashCode(key) & (HASHSIZE - 1) ;
  54. }
  55. struct list *listFind(struct list *head, char *key) {
  56.         //链表查找键
  57.         for (struct list *p = head; p != NULL; p = p->next)
  58.                 if (strcmp(p->key, key)==0)
  59.                     return p;
  60.         return NULL;
  61. }
  62. struct list *find(char *key) {
  63.         //哈希表查找键
  64.         return listFind(hashList[indexOf(key)],key);
  65. }
  66. int contains(char *key) {
  67.         //key是否存在
  68.         return find(key) == NULL ? 0 : 1;
  69. }
  70. void add(char *key, Value value) {
  71.         //添加键值对
  72.         int i = indexOf(key);
  73.         struct list *p = listFind(hashList[i],key);
  74.         if (p == NULL) {
  75.                 //插入表头
  76.                 struct list *p = newNode(key,value);
  77.                 if (p == NULL)
  78.                             return;
  79.                 p->next = hashList[i];
  80.                 hashList[i] = p;
  81.         } else{
  82.                 Value v = valuedup(value);
  83.                 //if (v == NULL)
  84.         //        return ;
  85.         //      free(p->value);
  86.                 p->value = v;
  87.         }
  88. }
  89. void removeKey(char *key) {
  90.         //删除一个key
  91.         struct list *del = NULL;
  92.         int i = indexOf(key);
  93.         struct list *p = hashList[i];
  94.         if (p == NULL) return;
  95.         if (strcmp(p->key, key)==0) {
  96.                 del = p;
  97.                 hashList[i] = p->next;
  98.         } else {
  99.                 for (; p->next != NULL; p = p->next)
  100.                             if (strcmp(p->next->key, key)==0) {
  101.                         del = p->next;
  102.                         p->next = p->next->next;
  103.                         break;
  104.                 }
  105.         }
  106.         if (del == NULL) return;;
  107.         freeNode(del);
  108. }
  109. void release() {
  110.         //销毁哈希表
  111.         for (int i = 0; i < HASHSIZE; i++)
  112.                 while(hashList[i] != NULL) {
  113.                         struct list *p = hashList[i];
  114.                         hashList[i] = p->next;
  115.                         freeNode(p);
  116.                 }
  117.        
  118. }
  119. void traversal() {
  120.         //遍历哈希表
  121.         for (int i = 0; i < HASHSIZE; i++)
  122.                 for (struct list *p = hashList[i]; p != NULL;p = p->next)
  123.                         printf("key = %s     value = %d \n",p->key ,p->value);
  124.                
  125.        
  126. }
  127. void main() {
  128.         add("a",1);
  129.         add("b",2);
  130.         add("c",3);
  131.         traversal();
  132.         removeKey("c");
  133.         traversal();
  134.         release();
  135. }
复制代码
回复

使用道具 举报

1109

主题

1649

回帖

7万

积分

用户组: 管理员

一只技术宅

UID
1
精华
244
威望
743 点
宅币
24180 个
贡献
46222 次
宅之契约
0 份
在线时间
2294 小时
注册时间
2014-1-26
发表于 2021-6-28 14:04:26 | 显示全部楼层
你这哈希表只能有一个实例啊……
回复 赞! 靠!

使用道具 举报

55

主题

271

回帖

9330

积分

用户组: 管理员

UID
77
精华
16
威望
237 点
宅币
8199 个
贡献
251 次
宅之契约
0 份
在线时间
253 小时
注册时间
2014-2-22
发表于 2021-6-30 08:03:34 | 显示全部楼层
每次看到链表操作之类的代码,就会想起大学时代的C语言课程。
回复 赞! 靠!

使用道具 举报

1109

主题

1649

回帖

7万

积分

用户组: 管理员

一只技术宅

UID
1
精华
244
威望
743 点
宅币
24180 个
贡献
46222 次
宅之契约
0 份
在线时间
2294 小时
注册时间
2014-1-26
发表于 2021-6-30 08:51:31 | 显示全部楼层
美俪女神 发表于 2021-6-30 08:03
每次看到链表操作之类的代码,就会想起大学时代的C语言课程。

哈希表是很有价值的东西,复杂度O(1)的查询速度,缺点是往里面增加数据的时候数组的扩容有个时间成本。
回复 赞! 靠!

使用道具 举报

QQ|Archiver|小黑屋|技术宅的结界 ( 滇ICP备16008837号 )|网站地图

GMT+8, 2024-3-29 21:11 , Processed in 0.035912 second(s), 28 queries , Gzip On.

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表