百度360必应搜狗淘宝本站头条
nodejsbufferorg.jsoupsetnocountoncv2.bitwise_nottime.strptime
当前位置：网站首页 > 编程字典 > 正文

C语言实现hashMap

toyiye 2024-06-21 12:14 14 浏览 0 评论

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


下载链接：download.csdn.net/download/sxf1061700625/13101710

供参考学习

hashMap.h

#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

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映射到了数组的同一位置处，就将其放入单链表中。
 
// 有些如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;
}

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

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

相关推荐

为何越来越多的编程语言使用JSON（为什么编程）

JSON是JavascriptObjectNotation的缩写，意思是Javascript对象表示法，是一种易于人类阅读和对编程友好的文本数据传递方法，是JavaScript语言规范定义的一个子...

何时在数据库中使用 JSON（数据库用json格式存储）

在本文中，您将了解何时应考虑将JSON数据类型添加到表中以及何时应避免使用它们。每天?分享?最新?软件?开发?，Devops，敏捷?，测试?以及?项目?管理?最新?，最热门?的?文章?，每天?花?...

MySQL 从零开始:05 数据类型（mysql数据类型有哪些,并举例）

前面的讲解中已经接触到了表的创建，表的创建是对字段的声明，比如：上述语句声明了字段的名称、类型、所占空间、默认值和是否可以为空等信息。其中的int、varchar、char和decimal都...

JSON对象花样进阶（json格式对象）

一、引言在现代Web开发中，JSON（JavaScriptObjectNotation）已经成为数据交换的标准格式。无论是从前端向后端发送数据，还是从后端接收数据，JSON都是不可或缺的一部分。...

深入理解 JSON 和 Form-data（json和formdata提交区别）

在讨论现代网络开发与API设计的语境下，理解客户端和服务器间如何有效且可靠地交换数据变得尤为关键。这里，特别值得关注的是两种主流数据格式：...

JSON 语法（json 语法 priority）

JSON语法是JavaScript语法的子集。JSON语法规则JSON语法是JavaScript对象表示法语法的子集。数据在名称/值对中数据由逗号分隔花括号保存对象方括号保存数组JS...

JSON语法详解（json的语法规则）

JSON语法规则JSON语法是JavaScript对象表示法语法的子集。数据在名称/值对中数据由逗号分隔大括号保存对象中括号保存数组注意：json的key是字符串,且必须是双引号，不能是单引号...

MySQL JSON数据类型操作（mysql的json）

概述mysql自5.7.8版本开始，就支持了json结构的数据存储和查询，这表明了mysql也在不断的学习和增加nosql数据库的有点。但mysql毕竟是关系型数据库，在处理json这种非结构化的数据...

JSON的数据模式（json数据格式示例）

像XML模式一样，JSON数据格式也有Schema，这是一个基于JSON格式的规范。JSON模式也以JSON格式编写。它用于验证JSON数据。JSON模式示例以下代码显示了基本的JSON模式。{"...

前端学习——JSON格式详解（后端json格式）

JSON(JavaScriptObjectNotation)是一种轻量级的数据交换格式。易于人阅读和编写。同时也易于机器解析和生成。它基于JavaScriptProgrammingLa...

什么是 JSON:详解 JSON 及其优势（什么叫json）

现在程序员还有谁不知道JSON吗？无论对于前端还是后端，JSON都是一种常见的数据格式。那么JSON到底是什么呢？JSON的定义...

PostgreSQL JSON 类型:处理结构化数据

PostgreSQL提供JSON类型，以存储结构化数据。JSON是一种开放的数据格式，可用于存储各种类型的值。什么是JSON类型？JSON类型表示JSON(JavaScriptO...

JavaScript:JSON、三种包装类（javascript 包）

JOSN:我们希望可以将一个对象在不同的语言中进行传递，以达到通信的目的，最佳方式就是将一个对象转换为字符串的形式JSON（JavaScriptObjectNotation）-JS的对象表示法...

Python数据分析 只要1分钟 教你玩转JSON 全程干货

Json简介：Json，全名JavaScriptObjectNotation,JSON(JavaScriptObjectNotation(记号、标记))是一种轻量级的数据交换格式。它基于J...

比较一下JSON与XML两种数据格式?（json和xml哪个好）

JSON（JavaScriptObjectNotation）和XML（eXtensibleMarkupLanguage）是在日常开发中比较常用的两种数据格式，它们主要的作用就是用来进行数据的传...

取消回复欢迎 你 发表评论:

请填写验证码
一周热门
最近发表
标签列表