C语言实现Hash Map(3)：Map代码优化

2024-05-28 08:12
文章标签 语言 实现 map hash 代码优化

本文主要是介绍C语言实现Hash Map(3)：Map代码优化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在上一节中，我们学习了C语言实现Hash Map(2)：Map代码实现详解，通过代码，我们更深入地了解了Map实现的原理，学习了如何通过key找到对应的桶并加入节点。也正如上一节提到的，虽然这是github中star比较多的代码，但是程序还可以进一步地优化：

  • 程序桶的数量是在每次添加节点的时候自动调节的，即使用realloc函数重新分配
    • 可以固定一下默认的桶的大小，而不是每次都从0开始网上分配
    • 假设使用FreeRTOS，并没有realloc函数，所以将其改为动态分配和释放
  • 程序仅支持值为char *类型的映射，且值的数据是拷贝的
    • 支持不同数据类型的键
    • 支持拷贝值和保存值的指针两种方式

文章目录

  • 1 桶的默认大小
  • 2 桶的内存分配
  • 3 支持不同的数据类型
    • 3.1 数据结构修改
    • 3.2 map_init
    • 3.3 map_set
    • 3.4 map_get
  • 4 测试
  • 5 总结

1 桶的默认大小

首先来解决桶内存的问题。由上一节我们知道，在每次增加节点的时候，若当前节点的数量大于等于桶的数量，则会使用realloc重新分配桶内存。但这样的话，最开始从0开始，随着节点的增加，分配1、 2、 4、 8个桶，未免有点太麻烦了，也可能会产生一些内存碎片。所以我们希望在初始化的时候，就初始化固定的桶。

所以解决办法很简单，我们直接在初始化函数中传入一个默认的桶数量的参数，然后调用map_resize即可。

void map_init(unsigned int nbuckets)
{...assert((nbuckets % 2) == 0);map_resize(&base, nbuckets);
}

由上节课可知，map_bucketidx函数中使用的是按位与来获取余数，所以这里的nbuckets的值应为2的倍数，所以这里断言判断一下。

2 桶的内存分配

另外，在map_resize函数中使用的是stdlib.h库中的realloc函数，我们就在分配之前释放上一次分配的，然后使用MAP_MALLOC分配就行了。如下图所示：

在这里插入图片描述

由于我们设置了桶的默认大小，我们可以根据实际情况调整桶的大小，只要不超过这个大小，就不会调用到map_resize函数。

3 支持不同的数据类型

从代码中可以看出：

int map_set_(map_base_t *m, const char *key, void *value, int vsize)
{...memcpy((*next)->value, value, vsize);...
}

value传入的是一个指针，然后函数中使用memcpy拷贝的是指针指向地址里面的值。所以这种情况就导致我们map的值只能使用字符串或定义一个变量并传入地址。假设我们希望值为int类型，然后直接写入数值就不允许了。另外，有的时候我们又希望这个函数不要拷贝函数的内容，比如我们的值传入的就是常量字符串，那我们在函数中还又拷贝一次，这样浪费了内存。所以我们就来更改一下这部分的代码，让它既支持拷贝参数内容，又支持保存参数的地址。

3.1 数据结构修改

首先我们回顾一下之前的数据结构：

typedef map_t(void*) map_void_t;
typedef map_t(char*) map_str_t;
typedef map_t(int) map_int_t;
typedef map_t(char) map_char_t;
typedef map_t(float) map_float_t;
typedef map_t(double) map_double_t;

其中map_t为：

#define map_t(T)\struct { map_base_t base; T ref;}

我们知道，map实际的数据结构就是map_base_t，而这个T ref就是标记不同数据类型的唯一地方了。而且ref变量仅在下面用到：

#define map_get(m, key)\( (m)->ref = map_get_(&(m)->base, key) )

也就是获取键值的是保存在这个变量中，但很明显，假设类型为int，map_get_却返回的是一个指针，类型明显不符。另外将结果保存在ref中似乎也没什么意义。所以我们直接删除ref这个变量，和所有的类型的typedef，直接typedef整个结构体就行了。

为了能够区别不同数据类型的长度，我们增加两个变量，typeSize表示数据类型的大小，isCpyAddr表示设置键值的时候是拷贝地址里的值(isCpyAddr=1)，还是直接传入值给函数(拷贝参数，isCpyAddr=0)。然后将整个数据结构命名为map_c_t：

typedef struct{map_base_t base;unsigned char typeSize;unsigned char isCpyAddr;
}map_c_t;

接下来我们就改下面三个函数：map_init、map_set和map_get，删掉宏定义的map_set和map_get。

  • 对于其它几个宏定义和函数，如map_remove、map_deinit等，自行更改一下，主要是将函数参数map_base_t修改为map_c_t即可。

3.2 map_init

原来的map_init是一个宏定义，然后用memset将整个map数据结构置0，现在我们将其改为函数。对于不同的数据类型，我们声明一个枚举类型供用户选择传参：

typedef enum{MAP_TYPE_VOID_PTR,    //void *MAP_TYPE_CHAR_PTR,    //char *MAP_TYPE_INT,         //intMAP_TYPE_CHAR,        //charMAP_TYPE_FLOAT,       //floatMAP_TYPE_DOUBLE,      //double
}MAP_TYPE;

然后map_init函数如下：

void map_init(map_c_t *instance, MAP_TYPE type, unsigned char isCpyAddr, unsigned int nbuckets)
{memset(instance, 0, sizeof(map_c_t));switch(type){case MAP_TYPE_VOID_PTR:{instance->typeSize = sizeof(void *);break;}case MAP_TYPE_CHAR_PTR:{instance->typeSize = sizeof(char *);break;}case MAP_TYPE_INT     :{instance->typeSize = sizeof(int);break;}case MAP_TYPE_CHAR    :{instance->typeSize = sizeof(char);break;}case MAP_TYPE_FLOAT   :{instance->typeSize = sizeof(float);break;}case MAP_TYPE_DOUBLE  :{instance->typeSize = sizeof(double);break;}default:break;}instance->isCpyAddr = isCpyAddr; //拷贝地址里的内容assert((nbuckets % 2) == 0);map_resize(&instance->base, nbuckets);
}
  1. 根据枚举类型保存数据的typeSize，这样比如在用户传入数字的时候，就知道拷贝多大的数据。
  2. isCpyAddr保存是否需要拷贝地址里的内容
  3. 最后根据设置的桶的初始大小来分配内存

3.3 map_set

我们直接来看一下代码前后的对比：

在这里插入图片描述

  1. 首先将原来的map_base_t改为我们定义的map_c_t，然后更改下面所有用到base的地方
  2. 这里vsize为我们传入的参数的大小，如果参数为字符串且我们用的是拷贝方式的话，我们需要传入vsize的大小，这样用户传入字符串的时候，我们就知道拷贝多大的长度。在其它时候，vsize可以传0，vsize就设置为数据类型对应的typeSize。
  3. 最后就是根据isCpyAddr来判断是拷贝地址里的值还是拷贝地址，分别在节点已经存在时和创建节点时修改代码。

这里举一个例子，如果我们设置的是MAP_TYPE_INT，然后传入的值是123，那么这个void *类型的value的值就是123，如果直接用memcpy拷贝的话，就拷贝的是123这个地址里的值；所以传入123的时候我们就拷贝value的地址&value就行了。

3.4 map_get

map_get函数不需要做太大的改动，只要把参数改成我们定义的map_c_t，然后把map_getref中的参数改成&m->base就行了。

void *map_get(map_c_t *m, const char *key) {map_node_t **next = map_getref(&m->base, key);return next ? (*next)->value : NULL;
}

4 测试

这里我把各个类型的使用都写了一个例子，只需要更改TEST_MODE宏定义即可：

#include <stdio.h>
#include <stdlib.h>
#include "map.h"#define TEST_MODE 1static map_c_t langMap;
int main()
{
#if (TEST_MODE == 1)       //字符串测试:拷贝字符串地址[常用]map_init(&langMap, MAP_TYPE_CHAR_PTR, 0, 8);map_set(&langMap, "test", "1234", 0);char **ret = map_get(&langMap, "test");printf("%x %x = %s\r\n", "1234", *ret, *ret);
#elif (TEST_MODE == 2)     //字符串测试:拷贝字符串的值map_node_t后面的内存中(需要指定长度)map_init(&langMap, MAP_TYPE_CHAR_PTR, 1, 8);map_set(&langMap, "test", "1234", sizeof("1234"));char *ret = map_get(&langMap, "test");printf("%x %x = %s\r\n", "1234", ret, ret);
#elif (TEST_MODE == 3)     //int测试:保存数字的值到map_node_t后[常用]map_init(&langMap, MAP_TYPE_INT, 0, 8);map_set(&langMap, "test", 123, 0);int *ret = map_get(&langMap, "test");printf("%x = %d\r\n", *ret, *ret);
#elif (TEST_MODE == 4)     //int测试:拷贝int变量的值到map_node_t后const int a = 123;map_init(&langMap, MAP_TYPE_INT, 1, 8);map_set(&langMap, "test", &a, 0);int *ret = map_get(&langMap, "test");printf("%x %x = %d\r\n", &a, *ret, *ret);
#elif (TEST_MODE == 5)     //int测试:保存int变量的地址const int a = 123;map_init(&langMap, MAP_TYPE_INT, 0, 8);map_set(&langMap, "test", &a, 0);int **ret = map_get(&langMap, "test");printf("%x %x = %d\r\n", &a, *ret, **ret);
#elif (TEST_MODE == 6)     //char测试:拷贝字符的值到map_node_t后[常用]map_init(&langMap, MAP_TYPE_CHAR, 0, 8);map_set(&langMap, "test", 'a', 0);char *ret = map_get(&langMap, "test");printf("%x = %c\r\n", *ret, *ret);
#elif (TEST_MODE == 7)     //double测试:保存double变量地址到map_node_t后const double a = 3.14;map_init(&langMap, MAP_TYPE_DOUBLE, 0, 8);map_set(&langMap, "test", &a, 0);double **ret = map_get(&langMap, "test");printf("%x %x = %lf\r\n", &a, *ret, **ret);
#elif (TEST_MODE == 8)     //double测试:拷贝double变量的值到map_node_t后const double a = 3.14;map_init(&langMap, MAP_TYPE_DOUBLE, 1, 8);map_set(&langMap, "test", &a, 0);double *ret = map_get(&langMap, "test");printf("%x %x = %lf\r\n", &a, ret, *ret);
#else//1.float类型:代码同double//2.void *类型:这种情况一般是保存地址,所以map_init最后一个参数为0
#endifreturn 0;
}

这里来展示一下int作为值类型，传入数值时的演示结果：

在这里插入图片描述

可以看到，输出符合预期，0x7b是创建map_node_t节点时分配的内存地址里value的地址。

5 总结

本文基于Github上给的代码进行了一些小小的优化，使其可以适配不同的数据类型，并能够初始分配一个桶的内存。但正如前面所说，代码并没有完整做完适配，如map_deinit等函数还需要小小修改一下。大家可以自行修改，或者大家还有什么优化的建议都可以在我下面的git仓库中进行提交。

  • 完整代码：https://github.com/Vinolzy/map_fix

这篇关于C语言实现Hash Map(3)：Map代码优化的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1010008。

相关文章

学习hash总结

学习hash总结

2014/1/29/   最近刚开始学hash，名字很陌生，但是hash的思想却很熟悉，以前早就做过此类的题，但是不知道这就是hash思想而已，说白了hash就是一个映射，往往灵活利用数组的下标来实现算法，hash的作用：1、判重；2、统计次数；
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
hdu1496（用hash思想统计数目）

hdu1496（用hash思想统计数目）

作为一个刚学hash的孩子，感觉这道题目很不错，灵活的运用的数组的下标。 解题步骤：如果用常规方法解，那么时间复杂度为O（n^4）,肯定会超时，然后参考了网上的解题方法，将等式分成两个部分，a*x1^2+b*x2^2和c*x3^2+d*x4^2， 各自作为数组的下标，如果两部分相加为0，则满足等式； 代码如下： #include<iostream>#include<algorithm
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
让树莓派智能语音助手实现定时提醒功能

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现，因为rasa本身是带有remindschedule模块的。不过经过一番折腾后，忽然发现，chatbot上实现的定时，语音助手不一定会有响应。因为，我目前语音助手的代码设置了长时间无应答会结束对话，这样一来，chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢？ 我最后选择的方法是用threading.Time
阅读更多...
Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸： 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  （注意不能是bmp格式） 替换默认锁屏壁纸： 将图片资源放入vendo
阅读更多...
usaco 1.2 Milking Cows（类hash表）

usaco 1.2 Milking Cows（类hash表）

第一种思路被卡了时间 到第二种思路的时候就觉得第一种思路太坑爹了 代码又长又臭还超时！！ 第一种思路：我不知道为什么最后一组数据会被卡 超时超了0.2s左右 大概想法是 快排加一个遍历 先将开始时间按升序排好 然后开始遍历比较 1 若 下一个开始beg[i] 小于 tem_end 则说明本组数据与上组数据是在连续的一个区间 取max( ed[i],tem_end ) 2 反之 这个
阅读更多...
C#实战|大乐透选号器[6]：实现实时显示已选择的红蓝球数量

C#实战|大乐透选号器[6]：实现实时显示已选择的红蓝球数量

哈喽，你好啊，我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记，这是第6篇； 接下来实现实时显示当前选中红球数量，蓝球数量； 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时，在对应的位置显示实时已选择的红球、蓝球的数量； 02 标签名称 分别设置Label标签名称为：lblRedCount、lblBlueCount
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2