图中，紫色部分即代表哈希表，也称为哈希数组，数组的每个元素都是一个单链表的头节点，链表是用来办理冲突的，如果不同的key映射到了数组的同一位置处，就将其放入单链表中。
下载链接：download.csdn.net/download/sxf1061700625/13101710
供参考学习
#ifndef _HASHMAP_H#define _HASHMAP_H typedef struct HashNode{ char key; char value; struct HashNode next; // 当key相同时，指向凑集中的下一个节点}HashNode; typedef struct{ int size; // hash map不重复node的数量 HashNode hashArr; // 二维数组，存key值不重复的node，key重复的node链接在HashNode->next}HashMap; HashMap CreateHashMap(int n);int InsertHashMap(HashMap hashMap, char key, char value);char GetHashMap(HashMap hashMap, char key);void DeleteHashMap(HashMap hashMap);int RemoveHashMap(HashMap hashMap, char key);void PrintHashMap(HashMap hashMap);void hashMapTest(void); #endifhashMap.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映射到了数组的同一位置处，就将其放入单链表中。 // 有些如STM32就不自带strdup函数#if !HAVE_STRDUP#undef strdupchar strdup(const char s){size_t len = strlen(s) + 1;//打算字符串的长度void new = malloc(len);//分配一个新的空间给newif(new == NULL) return NULL;return (char )memcpy(new, s, len);//拷贝s数据到new中}#endif / @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;} / @brief 删除由key指定的键值对 @param hashMap 待操作的hash表 @param key @return /int RemoveHashMap(HashMap hashMap, char key){ // 对hash结果求余，获取key位置 int index = myHash(key) % hashMap->size; // 用于遍历node的临时游标 HashNode temp = hashMap->hashArr[index]; if (temp == NULL) { return 0; } // 如果第一个就匹配中 if (strcmp(temp->key, key) == 0) { // printf("找到:%s->%s\n", temp->key, temp->value); hashMap->hashArr[index] = temp->next; myFree(temp->key); myFree(temp->value); myFree(temp); return 1; }else { HashNode prev = temp; temp = temp->next; // 循环遍历至末了一个节点node_end的next while (temp != NULL) { // 如果两个key相同，则用新node的value覆盖旧的 if (strcmp(temp->key, key) == 0) { // printf("找到:%s->%s\n", temp->key, temp->value); prev->next = temp->next; myFree(temp->key); myFree(temp->value); myFree(temp); return 1; } prev = temp; temp = temp->next; } } return 0;} / @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); int code = RemoveHashMap(hashMap, "a"); if (code) { printf("删除成功\n"); } 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;}hashUtil.h
#ifndef _HASHUTIL_H#define _HASHUTIL_H unsigned int hashMysqlNR(const char key, unsigned int len);unsigned int hashMysqlNRCaseUp(const char key, unsigned int len);unsigned long hashPhp(char arKey, unsigned int nKeyLength);unsigned long hashOpenSSL(char str);unsigned int hash(char str);void hashTest(void); #endifhashUtil.c
#include <stdio.h>#include <string.h>#include <ctype.h>#include "hashUtil.h" / MySql中涌现的字符串Hash函数 这种哈希是迄今为止我们所见过的所有函数中产生碰撞最少的，对数字和字符串都很有效。 /unsigned int hashMysqlNR(const char key, unsigned int len){ const char end=key+len; unsigned int hash; for (hash = 0; key < end; key++) { hash = 16777619; hash ^= (unsigned int) (unsigned char) key; } return (hash);} / MySql中涌现的字符串Hash函数 打算一个键的哈希值，大小写独立 /unsigned int hashMysqlNRCaseUp(const char key, unsigned int len){ const char end=key+len; unsigned int hash; for (hash = 0; key < end; key++) { hash = 16777619; hash ^= (unsigned int) (unsigned char) toupper(key); } return (hash);} / PHP中涌现的字符串Hash函数 /unsigned long hashPhp(char arKey, unsigned int nKeyLength){ unsigned long h = 0, g; char arEnd=arKey+nKeyLength; while (arKey < arEnd) { h = (h << 4) + arKey++; if ((g = (h & 0xF0000000))) { h = h ^ (g >> 24); h = h ^ g; } } return h;} / OpenSSL中涌现的字符串Hash函数 /unsigned long hashOpenSSL(char str){ int i,l; unsigned long ret=0; unsigned short s; if (str == NULL) return(0); l=(strlen(str)+1)/2; s=(unsigned short )str; for (i=0; i<l; i++) ret^=(s[i]<<(i&0x0f)); return(ret);} / 另一个经典字符串Hash函数 /unsigned int hash(char str){ register unsigned int h; register unsigned char p; for(h=0, p = (unsigned char )str; p ; p++) { h = 31 h + p; } return h;} void hashTest(void){ unsigned long h = hashPhp("ABCabc", 6); printf("hashPhp: %ld\r\n", h); // 72783747 unsigned int h2 = hashMysqlNR("ABCabc", 6); printf("hashMysqlNR: %d\r\n", h2); // 1403034336 unsigned int h3 = hashMysqlNRCaseUp("ABCabc", 6); printf("hashMysqlNRCaseUp: %d\r\n", h3); // 860927488 unsigned long h4 = hashOpenSSL("ABCabc"); printf("hashOpenSSL: %ld\r\n", h4); // 68943 unsigned int h5 = hash("ABCabc"); printf("hash: %d\r\n", h5); // 1923939552}
