C语言实现hashMap

分手后的思念是犯贱 2022-12-29 14:18 83阅读 0赞

[https://blog.csdn.net/sxf1061700625/article/details/109594495][https_blog.csdn.net_sxf1061700625_article_details_109594495]

![watermark_text_aH][]

图中，紫色部分即代表哈希表，也称为哈希数组，数组的每个元素都是一个单链表的头节点，链表是用来解决冲突的，如果不同的key映射到了数组的同一位置处，就将其放入单链表中。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aH][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N4ZjEwNjE3MDA2MjU_size_16_color_FFFFFF_t_70][]

**下载链接：**[https://download.csdn.net/download/sxf1061700625/13101710][https_download.csdn.net_download_sxf1061700625_13101710]

**供参考学习**

### hashMap.h ###

1.  `#ifndef _HASHMAP_H`
2.  `#define _HASHMAP_H`
3.  
4.  `typedef struct HashNode`
5.  `{`
6.  `char* key;`
7.  `char* value;`
8.  `struct HashNode* next; // 当key相同时，指向集合中的下一个节点`
9.  `}HashNode;`
10. 
11. `typedef struct`
12. `{`
13. `int size; // hash map不重复node的数量`
14. `HashNode** hashArr; // 二维数组，存key值不重复的node，key重复的node链接在HashNode->next`
15. `}HashMap;`
16. 
17. 
18. `HashMap* CreateHashMap(int n);`
19. `int InsertHashMap(HashMap* hashMap, char* key, char* value);`
20. `char* GetHashMap(HashMap* hashMap, char* key);`
21. `void DeleteHashMap(HashMap* hashMap);`
22. `int RemoveHashMap(HashMap* hashMap, char* key);`
23. `void PrintHashMap(HashMap* hashMap);`
24. `void hashMapTest(void);`
25. 
26. 
27. `#endif`

### hashMap.c ###

1.  `#include <stdio.h>`
2.  `#include <string.h>`
3.  `#include <stdlib.h>`
4.  `#include "hashUtil.h"`
5.  `#include "hashMap.h"`
6.  
7.  `#define myMalloc malloc // 使用哪个malloc函数`
8.  `#define myCalloc calloc // 使用哪个calloc函数`
9.  `#define myFree free // 使用哪个free函数`
10. `#define myHash hash // 使用哪个hash函数`
11. 
12. `// /images/20221120/ec79b7a9c39847fe8bd5c605811a7a2f.png`
13. `// 图中，紫色部分即代表哈希表，也称为哈希数组，数组的每个元素都是一个单链表的头节点，链表是用来解决冲突的，如果不同的key映射到了数组的同一位置处，就将其放入单链表中。`
14. 
15. `// 有些如STM32就不自带strdup函数`
16. `#if !HAVE_STRDUP`
17. `#undef strdup`
18. `char *strdup(const char *s)`
19. `{`
20. `size_t len = strlen(s) + 1;//计算字符串的长度`
21. `void *new = malloc(len);//分配一个新的空间给new`
22. `if(new == NULL) return NULL;`
23. `return (char *)memcpy(new, s, len);//拷贝s数据到new中`
24. `}`
25. `#endif`
26. 
27. 
28. `/**`
29. `* @description: 创建一个node数量为n的hash表`
30. `* @param {n} node数量`
31. `* @return {*} 创建的hash map`
32. `*/`
33. `HashMap* CreateHashMap(int n)`
34. `{`
35. `HashMap* hashMap = (HashMap*)myCalloc(1, sizeof(HashMap));`
36. `hashMap->hashArr = (HashNode**)myCalloc(n, sizeof(HashNode*));`
37. `if (hashMap==NULL || hashMap->hashArr==NULL) {`
38. `return NULL;`
39. `}`
40. `hashMap->size = n;`
41. `return hashMap;`
42. `};`
43. 
44. `/**`
45. `* @description: 插入1个键值对`
46. `* @param {*hashMap} 待操作的hash表`
47. `* @param {*key} 键`
48. `* @param {*value} 值`
49. `* @return {int} 是否操作成功，0:失败；1:成功`
50. `* @attention 如果key相同，则后插入的value会覆盖已有的value`
51. `*/`
52. `int InsertHashMap(HashMap* hashMap, char* key, char* value)`
53. `{`
54. `// 创建一个node节点`
55. `HashNode* node = (HashNode*)myCalloc(1, sizeof(HashNode));`
56. `if (node == NULL) {`
57. `return 0;`
58. `}`
59. 
60. `// 复制键和值`
61. `node->key = strdup(key);`
62. `node->value = strdup(value);`
63. `node->next = NULL;`
64. `// 对hash结果求余，获取key位置`
65. `int index = myHash(key) % hashMap->size;`
66. `// 如果当前位置没有node，就将创建的node加入`
67. `if (hashMap->hashArr[index] == NULL) {`
68. `hashMap->hashArr[index] = node;`
69. `}`
70. `// 否则就要在已有的node往后添加`
71. `else {`
72. `// 用于遍历node的临时游标`
73. `HashNode *temp = hashMap->hashArr[index];`
74. `// 记录上一个node`
75. `HashNode *prev = temp;`
76. `// 循环遍历至最后一个节点node_end的next`
77. `while (temp != NULL) {`
78. `// 如果两个key相同，则直接用新node的value覆盖旧的`
79. `if (strcmp(temp->key, node->key) == 0) {`
80. `// 释放旧value`
81. `myFree(temp->value);`
82. `// 复制新value`
83. `temp->value = strdup(node->value);`
84. `return 1;`
85. `}`
86. `prev = temp;`
87. `temp = temp->next;`
88. `}`
89. `// 最后一个节点node_end的next指向新建的node`
90. `prev->next = node;`
91. `}`
92. `return 1;`
93. `}`
94. 
95. `/**`
96. `* @description: 通过key查找value`
97. `* @param {*hashMap} 待操作的hash表`
98. `* @param {*key} 通过key找对应的value`
99. `* @return {*} 找到的value`
100. `*/`
101. `char* GetHashMap(HashMap* hashMap, char* key)`
102. `{`
103. `// 对hash结果求余，获取key位置`
104. `int index = myHash(key) % hashMap->size;`
105. `// 用于遍历node的临时游标`
106. `HashNode *temp = hashMap->hashArr[index];`
107. `// 循环遍历至最后一个节点node_end的next`
108. `while (temp != NULL) {`
109. `// 如果两个key相同，则用新node的value覆盖旧的`
110. `if (strcmp(temp->key, key) == 0) {`
111. `return temp->value;`
112. `}`
113. `temp = temp->next;`
114. `}`
115. `return NULL;`
116. `}`
117. 
118. `/**`
119. `* @description: 释放hash map内存`
120. `* @param {*hashMap} 待操作的hash表`
121. `* @return {}`
122. `*/`
123. `void DeleteHashMap(HashMap* hashMap)`
124. `{`
125. `for (int i = 0; i < hashMap->size; i++)`
126. `{`
127. `// 用于遍历node的临时游标`
128. `HashNode *temp = hashMap->hashArr[i];`
129. `HashNode *prev = temp;`
130. `// 循环遍历至最后一个节点node_end的next`
131. `while (temp != NULL) {`
132. `prev = temp;`
133. `temp = temp->next;`
134. `myFree(prev->key);`
135. `myFree(prev->value);`
136. `myFree(prev);`
137. `}`
138. `}`
139. `myFree(hashMap->hashArr);`
140. `myFree(hashMap);`
141. `hashMap->hashArr = NULL;`
142. `hashMap = NULL;`
143. `}`
144. 
145. `/**`
146. `* @brief 删除由key指定的键值对`
147. `* @param hashMap 待操作的hash表`
148. `* @param key`
149. `* @return`
150. `*/`
151. `int RemoveHashMap(HashMap* hashMap, char* key)`
152. `{`
153. `// 对hash结果求余，获取key位置`
154. `int index = myHash(key) % hashMap->size;`
155. `// 用于遍历node的临时游标`
156. `HashNode *temp = hashMap->hashArr[index];`
157. `if (temp == NULL) {`
158. `return 0;`
159. `}`
160. 
161. `// 如果第一个就匹配中`
162. `if (strcmp(temp->key, key) == 0) {`
163. `// printf("找到:%s->%s\n", temp->key, temp->value);`
164. `hashMap->hashArr[index] = temp->next;`
165. `myFree(temp->key);`
166. `myFree(temp->value);`
167. `myFree(temp);`
168. `return 1;`
169. `}else {`
170. `HashNode *prev = temp;`
171. `temp = temp->next;`
172. `// 循环遍历至最后一个节点node_end的next`
173. `while (temp != NULL) {`
174. `// 如果两个key相同，则用新node的value覆盖旧的`
175. `if (strcmp(temp->key, key) == 0) {`
176. `// printf("找到:%s->%s\n", temp->key, temp->value);`
177. `prev->next = temp->next;`
178. `myFree(temp->key);`
179. `myFree(temp->value);`
180. `myFree(temp);`
181. `return 1;`
182. `}`
183. `prev = temp;`
184. `temp = temp->next;`
185. `}`
186. `}`
187. `return 0;`
188. `}`
189. 
190. `/**`
191. `* @description: 打印hash map`
192. `* @param {*hashMap}`
193. `* @return {}`
194. `*/`
195. `void PrintHashMap(HashMap* hashMap)`
196. `{`
197. `printf("===========PrintHashMap==========\n");`
198. `HashNode* node = NULL;`
199. `for (int i = 0; i < hashMap->size; i++)`
200. `{`
201. `node = hashMap->hashArr[i];`
202. `if (node != NULL) {`
203. `HashNode* temp = node;`
204. `while (temp != NULL) {`
205. `printf("[%d]: %s -> %s\t", i, temp->key, temp->value);`
206. `temp = temp->next;`
207. `}`
208. `printf("\n");`
209. `}`
210. `}`
211. `printf("===============End===============\n");`
212. `}`
213. 
214. `void hashMapTest(void)`
215. `{`
216. `HashMap* hashMap = CreateHashMap(5);`
217. `if (hashMap) {`
218. `printf("创建完成\n");`
219. `}`
220. 
221. `InsertHashMap(hashMap, "a", "a1");`
222. `InsertHashMap(hashMap, "a", "a2");`
223. `InsertHashMap(hashMap, "b", "b1");`
224. `InsertHashMap(hashMap, "b", "b2");`
225. `InsertHashMap(hashMap, "c", "c1");`
226. `InsertHashMap(hashMap, "d", "d1");`
227. `InsertHashMap(hashMap, "e", "e1");`
228. `InsertHashMap(hashMap, "f", "f1");`
229. `InsertHashMap(hashMap, "f", "f1");`
230. `InsertHashMap(hashMap, "g", "g1");`
231. `InsertHashMap(hashMap, "h", "h1");`
232. `PrintHashMap(hashMap);`
233. 
234. `int code = RemoveHashMap(hashMap, "a");`
235. `if (code) {`
236. `printf("删除成功\n");`
237. `}`
238. 
239. `PrintHashMap(hashMap);`
240. 
241. `char* res = GetHashMap(hashMap, "g");`
242. `if (res) {`
243. `printf("找到, g -> %s\n", res);`
244. `}`
245. `res = GetHashMap(hashMap, "q");`
246. `if (res == NULL) {`
247. `printf("未找到, q -> %s\n", res);`
248. `}`
249. 
250. `DeleteHashMap(hashMap);`
251. `printf("销毁完成\n");`
252. `}`
253. 
254. `int main(int argc, char const *argv[])`
255. `{`
256. `hashMapTest();`
257. `return 0;`
258. `}`

### hashUtil.h ###

1.  `#ifndef _HASHUTIL_H`
2.  `#define _HASHUTIL_H`
3.  
4.  `unsigned int hashMysqlNR(const char *key, unsigned int len);`
5.  `unsigned int hashMysqlNRCaseUp(const char *key, unsigned int len);`
6.  `unsigned long hashPhp(char *arKey, unsigned int nKeyLength);`
7.  `unsigned long hashOpenSSL(char *str);`
8.  `unsigned int hash(char *str);`
9.  `void hashTest(void);`
10. 
11. `#endif`

### hashUtil.c ###

1.  `#include <stdio.h>`
2.  `#include <string.h>`
3.  `#include <ctype.h>`
4.  `#include "hashUtil.h"`
5.  
6.  `/**`
7.  `* MySql中出现的字符串Hash函数`
8.  `* 这种哈希是迄今为止我们所见过的所有函数中产生碰撞最少的，对数字和字符串都很有效。`
9.  `*/`
10. `unsigned int hashMysqlNR(const char *key, unsigned int len)`
11. `{`
12. `const char *end=key+len;`
13. `unsigned int hash;`
14. 
15. `for (hash = 0; key < end; key++) {`
16. `hash *= 16777619;`
17. `hash ^= (unsigned int) *(unsigned char*) key;`
18. `}`
19. 
20. `return (hash);`
21. `}`
22. 
23. `/**`
24. `* MySql中出现的字符串Hash函数`
25. `* 计算一个键的哈希值，大小写独立`
26. `*/`
27. `unsigned int hashMysqlNRCaseUp(const char *key, unsigned int len)`
28. `{`
29. `const char *end=key+len;`
30. `unsigned int hash;`
31. 
32. `for (hash = 0; key < end; key++) {`
33. `hash *= 16777619;`
34. `hash ^= (unsigned int) (unsigned char) toupper(*key);`
35. `}`
36. 
37. `return (hash);`
38. `}`
39. 
40. 
41. `/**`
42. `* PHP中出现的字符串Hash函数`
43. `*/`
44. `unsigned long hashPhp(char *arKey, unsigned int nKeyLength)`
45. `{`
46. `unsigned long h = 0, g;`
47. `char *arEnd=arKey+nKeyLength;`
48. 
49. `while (arKey < arEnd) {`
50. `h = (h << 4) + *arKey++;`
51. `if ((g = (h & 0xF0000000))) {`
52. `h = h ^ (g >> 24);`
53. `h = h ^ g;`
54. `}`
55. `}`
56. `return h;`
57. `}`
58. 
59. `/**`
60. `* OpenSSL中出现的字符串Hash函数`
61. `*/`
62. `unsigned long hashOpenSSL(char *str)`
63. `{`
64. `int i,l;`
65. `unsigned long ret=0;`
66. `unsigned short *s;`
67. 
68. `if (str == NULL) return(0);`
69. `l=(strlen(str)+1)/2;`
70. `s=(unsigned short *)str;`
71. 
72. `for (i=0; i<l; i++)`
73. `ret^=(s[i]<<(i&0x0f));`
74. `return(ret);`
75. `}`
76. 
77. `/**`
78. `* 另一个经典字符串Hash函数`
79. `*/`
80. `unsigned int hash(char *str)`
81. `{`
82. `register unsigned int h;`
83. `register unsigned char *p;`
84. 
85. `for(h=0, p = (unsigned char *)str; *p ; p++) {`
86. `h = 31 * h + *p;`
87. `}`
88. 
89. `return h;`
90. `}`
91. 
92. 
93. `void hashTest(void)`
94. `{`
95. `unsigned long h = hashPhp("ABCabc", 6);`
96. `printf("hashPhp: %ld\r\n", h); // 72783747`
97. 
98. `unsigned int h2 = hashMysqlNR("ABCabc", 6);`
99. `printf("hashMysqlNR: %d\r\n", h2); // 1403034336`
100. 
101. `unsigned int h3 = hashMysqlNRCaseUp("ABCabc", 6);`
102. `printf("hashMysqlNRCaseUp: %d\r\n", h3); // 860927488`
103. 
104. `unsigned long h4 = hashOpenSSL("ABCabc");`
105. `printf("hashOpenSSL: %ld\r\n", h4); // 68943`
106. 
107. `unsigned int h5 = hash("ABCabc");`
108. `printf("hash: %d\r\n", h5); // 1923939552`
109. `}`

[https_blog.csdn.net_sxf1061700625_article_details_109594495]: https://blog.csdn.net/sxf1061700625/article/details/109594495
[watermark_text_aH]: /images/20221120/ec79b7a9c39847fe8bd5c605811a7a2f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aH]: /images/20221120/13d29e1d0af544289cd42e22ff566cd6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N4ZjEwNjE3MDA2MjU_size_16_color_FFFFFF_t_70]: /images/20221120/f6f0b3c7c61d4330ba1548ae443b7bcc.png
[https_download.csdn.net_download_sxf1061700625_13101710]: https://download.csdn.net/download/sxf1061700625/13101710