c语言实现的哈希表

天马座

1. #include <stdio.h>
   
2. #include <string.h>
   
3. #include <stdlib.h>
   
4. //哈希桶数量
   
5. 
   
6. #define HASHSIZE (1 << 16)
   
7. 
   
8. typedef int Value;
   
9. 
   
10. struct list {
    
11.         //单链表
    
12.         char *key;
    
13.         Value value;
    
14.         struct list *next;
    
15. }
    
16. ;
    
17. //哈希表
    
18. struct list *hashList[HASHSIZE];
    
19. 
    
20. Value valuedup(Value value){
    
21.         //兼容字符串代码
    
22.         return value;
    
23. 
    
24. }
    
25. 
    
26. struct list *newNode(char* key,Value value) {
    
27.         //创建一个新节点
    
28.         struct list *p = (struct list *)malloc(sizeof(struct list));
    
29.         if (p == NULL)
    
30.                 return NULL;
    
31.         p->key = strdup(key);
    
32.         if (p->key == NULL){
    
33.                 free(p);
    
34.                 return NULL;
    
35.         }
    
36.         p->value = valuedup(value);
    
37.         //if (p->value == NULL){
    
38.         //        free(p->key);
    
39.         //        free(p);
    
40.         //        return NULL;
    
41.         //}
    
42.         return p;
    
43. 
    
44. }
    
45. 
    
46. void freeNode(struct list *p){
    
47.         //释放节点
    
48.         free(p->key);
    
49.         //free(p->value);
    
50.        free(p);
    
51. }
    
52. 
    
53. unsigned int hashCode(char* s) {
    
54.         //计算哈希值
    
55.         unsigned int h = 0;
    
56.         while(*s != '\0')
    
57.                 h = *s++ + 31 * h;
    
58.         return h;
    
59. }
    
60. int indexOf(char *key) {
    
61.         //计算key所在的下标
    
62.         return hashCode(key) & (HASHSIZE - 1) ;
    
63. }
    
64. struct list *listFind(struct list *head, char *key) {
    
65.         //链表查找键
    
66.         for (struct list *p = head; p != NULL; p = p->next)
    
67.                 if (strcmp(p->key, key)==0)
    
68.                     return p;
    
69.         return NULL;
    
70. }
    
71. struct list *find(char *key) {
    
72.         //哈希表查找键
    
73.         return listFind(hashList[indexOf(key)],key);
    
74. }
    
75. int contains(char *key) {
    
76.         //key是否存在
    
77.         return find(key) == NULL ? 0 : 1;
    
78. }
    
79. void add(char *key, Value value) {
    
80.         //添加键值对
    
81.         int i = indexOf(key);
    
82.         struct list *p = listFind(hashList[i],key);
    
83.         if (p == NULL) {
    
84.                 //插入表头
    
85.                 struct list *p = newNode(key,value);
    
86.                 if (p == NULL)
    
87.                             return;
    
88.                 p->next = hashList[i];
    
89.                 hashList[i] = p;
    
90.         } else{
    
91.                 Value v = valuedup(value);
    
92.                 //if (v == NULL)
    
93.         //        return ;
    
94.         //      free(p->value);
    
95.                 p->value = v;
    
96.         }
    
97. }
    
98. void removeKey(char *key) {
    
99.         //删除一个key
    
100.         struct list *del = NULL;
     
101.         int i = indexOf(key);
     
102.         struct list *p = hashList[i];
     
103.         if (p == NULL) return;
     
104.         if (strcmp(p->key, key)==0) {
     
105.                 del = p;
     
106.                 hashList[i] = p->next;
     
107.         } else {
     
108.                 for (; p->next != NULL; p = p->next)
     
109.                             if (strcmp(p->next->key, key)==0) {
     
110.                         del = p->next;
     
111.                         p->next = p->next->next;
     
112.                         break;
     
113.                 }
     
114.         }
     
115.         if (del == NULL) return;;
     
116.         freeNode(del);
     
117. }
     
118. void release() {
     
119.         //销毁哈希表
     
120.         for (int i = 0; i < HASHSIZE; i++)
     
121.                 while(hashList[i] != NULL) {
     
122.                         struct list *p = hashList[i];
     
123.                         hashList[i] = p->next;
     
124.                         freeNode(p);
     
125.                 }
     
126.        
     
127. }
     
128. void traversal() {
     
129.         //遍历哈希表
     
130.         for (int i = 0; i < HASHSIZE; i++)
     
131.                 for (struct list *p = hashList[i]; p != NULL;p = p->next)
     
132.                         printf("key = %s     value = %d \n",p->key ,p->value);
     
133.                
     
134.        
     
135. }
     
136. void main() {
     
137.         add("a",1);
     
138.         add("b",2);
     
139.         add("c",3);
     
140.         traversal();
     
141.         removeKey("c");
     
142.         traversal();
     
143.         release();
     
144. }

复制代码

0xAA55

你这哈希表只能有一个实例啊……

Golden Blonde

每次看到链表操作之类的代码，就会想起大学时代的C语言课程。

0xAA55

美俪女神 发表于 2021-6-30 08:03
每次看到链表操作之类的代码，就会想起大学时代的C语言课程。

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