C语言实现hashMap

#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);


#endif

#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 strdup
char *strdup(const char *s)
{
	size_t len = strlen(s) + 1;//计算字符串的长度
	void *new = malloc(len);//分配一个新的空间给new
	if(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;
}

#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);

#endif

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