/*
* @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;
}
评论2