C语言实现hashMap

  • 时间:
  • 来源:互联网
  • 文章标签:

https://blog.csdn.net/sxf1061700625/article/details/109594495

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

 

下载链接: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. // https://img-blog.csdnimg.cn/20190611221404917.png?x-oss-process=image/watermark,text_aH

  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. }

 

 

 

 

 

 

 

 

 

 

 

  •  

本文链接http://www.taodudu.cc/news/show-1944554.html