C语言实现hashMap

/* * @Author: your name * @Date: 2020-11-06 20:22:58 * @LastEditTime: 2020-11-10 10:53:52 * @LastEditors: Please set LastEditors * @Description: In User Settings Edit * @FilePath: hashMap.c */ #include <stdio.h> #include <string.h> #include <stdlib.h> #include "hashUtil.h" #include "hashMap.h" #define myMalloc malloc // 使用哪个malloc函数 #define myCalloc calloc // 使用哪个calloc函数 #define myFree free // 使用哪个free函数 #define myHash hash // 使用哪个hash函数 // https://img-blog.csdnimg.cn/20190611221404917.png?x-oss-process=image/watermark,text_aH // 图中，紫色部分即代表哈希表，也称为哈希数组，数组的每个元素都是一个单链表的头节点，链表是用来解决冲突的，如果不同的key映射到了数组的同一位置处，就将其放入单链表中。 /** * @description: 创建一个node数量为n的hash表 * @param {n} node数量 * @return {*} 创建的hash map */ HashMap* CreateHashMap(int n) { HashMap* hashMap = (HashMap*)myCalloc(1, sizeof(HashMap)); hashMap->hashArr = (HashNode**)myCalloc(n, sizeof(HashNode*)); if (hashMap==NULL || hashMap->hashArr==NULL) { return NULL; } hashMap->size = n; return hashMap; }; /** * @description: 插入1个键值对 * @param {*hashMap} 待操作的hash表 * @param {*key} 键 * @param {*value} 值 * @return {int} 是否操作成功，0:失败；1:成功 * @attention 如果key相同，则后插入的value会覆盖已有的value */ int InsertHashMap(HashMap* hashMap, char* key, char* value) { // 创建一个node节点 HashNode* node = (HashNode*)myCalloc(1, sizeof(HashNode)); if (node == NULL) { return 0; } // 复制键和值 node->key = strdup(key); node->value = strdup(value); node->next = NULL; // 对hash结果求余，获取key位置 int index = myHash(key) % hashMap->size; // 如果当前位置没有node，就将创建的node加入 if (hashMap->hashArr[index] == NULL) { hashMap->hashArr[index] = node; } // 否则就要在已有的node往后添加 else { // 用于遍历node的临时游标 HashNode *temp = hashMap->hashArr[index]; // 记录上一个node HashNode *prev = temp; // 循环遍历至最后一个节点node_end的next while (temp != NULL) { // 如果两个key相同，则直接用新node的value覆盖旧的 if (strcmp(temp->key, node->key) == 0) { // 释放旧value myFree(temp->value); // 复制新value temp->value = strdup(node->value); return 1; } prev = temp; temp = temp->next; } // 最后一个节点node_end的next指向新建的node prev->next = node; } return 1; } /** * @description: 通过key查找value * @param {*hashMap} 待操作的hash表 * @param {*key} 通过key找对应的value * @return {*} 找到的value */ char* GetHashMap(HashMap* hashMap, char* key) { // 对hash结果求余，获取key位置 int index = myHash(key) % hashMap->size; // 用于遍历node的临时游标 HashNode *temp = hashMap->hashArr[index]; // 循环遍历至最后一个节点node_end的next while (temp != NULL) { // 如果两个key相同，则用新node的value覆盖旧的 if (strcmp(temp->key, key) == 0) { return temp->value; } temp = temp->next; } return NULL; } /** * @description: 释放hash map内存 * @param {*hashMap} 待操作的hash表 * @return {} */ void DeleteHashMap(HashMap* hashMap) { for (int i = 0; i < hashMap->size; i++) { // 用于遍历node的临时游标 HashNode *temp = hashMap->hashArr[i]; HashNode *prev = temp; // 循环遍历至最后一个节点node_end的next while (temp != NULL) { prev = temp; temp = temp->next; myFree(prev->key); myFree(prev->value); myFree(prev); } } myFree(hashMap->hashArr); myFree(hashMap); hashMap->hashArr = NULL; hashMap = NULL; } /** * @description: 打印hash map * @param {*hashMap} * @return {} */ void PrintHashMap(HashMap* hashMap) { printf("===========PrintHashMap==========\n"); HashNode* node = NULL; for (int i = 0; i < hashMap->size; i++) { node = hashMap->hashArr[i]; if (node != NULL) { HashNode* temp = node; while (temp != NULL) { printf("[%d]: %s -> %s\t", i, temp->key, temp->value); temp = temp->next; } printf("\n"); } } printf("===============End===============\n"); } void hashMapTest(void) { HashMap* hashMap = CreateHashMap(5); if (hashMap) { printf("创建完成\n"); } InsertHashMap(hashMap, "a", "a1"); InsertHashMap(hashMap, "a", "a2"); InsertHashMap(hashMap, "b", "b1"); InsertHashMap(hashMap, "b", "b2"); InsertHashMap(hashMap, "c", "c1"); InsertHashMap(hashMap, "d", "d1"); InsertHashMap(hashMap, "e", "e1"); InsertHashMap(hashMap, "f", "f1"); InsertHashMap(hashMap, "f", "f1"); InsertHashMap(hashMap, "g", "g1"); InsertHashMap(hashMap, "h", "h1"); PrintHashMap(hashMap); char* res = GetHashMap(hashMap, "g"); if (res) { printf("找到, g -> %s\n", res); } res = GetHashMap(hashMap, "q"); if (res == NULL) { printf("未找到, q -> %s\n", res); } DeleteHashMap(hashMap); printf("销毁完成\n"); } int main(int argc, char const *argv[]) { hashMapTest(); return 0; }