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

news/2024/7/25 2:25:19/文章来源:https://blog.csdn.net/tilblackout/article/details/139072617

在上一节中,我们学习了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) )

也就是获取键值的是保存在这个变量中,但很明显,假设类型为intmap_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_initmap_setmap_get,删掉宏定义的map_setmap_get

  • 对于其它几个宏定义和函数,如map_removemap_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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1052559.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

其二:使用递归法实现二分搜索

开篇 本文主要是利用递归法来实现一个简单的二分搜索程序。题目来源是《编程珠玑》第4章课后习题3。 问题概要 编写并验证一个递归的二分搜索程序, 并返回t在数组x[0…n-1]中第一次出现的位置。 思路分析 本题的思路与第一版相似&#xff0c;不过不同的是&#xff0c;为确保返回…

《Python侦探手册:用正则表达式破译文本密码》

在这个信息爆炸的时代&#xff0c;每个人都需要一本侦探手册。阿佑今天将带你深入Python的正则表达式世界&#xff0c;教你如何像侦探一样&#xff0c;用代码破解文本中的每一个谜题。从基础的字符匹配到复杂的数据清洗&#xff0c;每一个技巧都足以让你在文本处理的领域中成为…

c++ 将指针转换为 void* 后,转换为怎么判断原指针类型?

当将指针转换为void后&#xff0c;擦除了指针所指向对象的类型信息&#xff0c;因此无法通过void指针来判断原始指针的类型。我这里有一套编程入门教程&#xff0c;不仅包含了详细的视频讲解&#xff0c;项目实战。如果你渴望学习编程&#xff0c;不妨点个关注&#xff0c;给个…

【C++】Vector的简易模拟与探索

&#x1f49e;&#x1f49e; 前言 hello hello~ &#xff0c;这里是大耳朵土土垚~&#x1f496;&#x1f496; &#xff0c;欢迎大家点赞&#x1f973;&#x1f973;关注&#x1f4a5;&#x1f4a5;收藏&#x1f339;&#x1f339;&#x1f339; &#x1f4a5;个人主页&#x…

【LeetCode算法】第83题:删除排序链表中的重复元素

目录 一、题目描述 二、初次解答 三、官方解法 四、总结 一、题目描述 二、初次解答 1. 思路&#xff1a;双指针法&#xff0c;只需遍历一遍。使用low指向前面的元素&#xff0c;high用于查找low后面与low不同内容的节点。将具有不同内容的节点链接在low后面&#xff0c;实…

C语言 | Leetcode C语言题解之第116题填充每个节点的下一个右侧节点指针

题目&#xff1a; 题解&#xff1a; struct Node* connect(struct Node* root) {if (root NULL) {return root;}// 从根节点开始struct Node* leftmost root;while (leftmost->left ! NULL) {// 遍历这一层节点组织成的链表&#xff0c;为下一层的节点更新 next 指针stru…

滑动窗口-java

主要通过单调队列来解决滑动窗口问题&#xff0c;得到滑动窗口中元素的最大值和最小值。 目录 前言 一、滑动窗口 二、算法思路 1.滑动窗口 2.算法思路 3.代码详解 三、代码如下 1.代码如下 2.读入数据 3.代码运行结果 总结 前言 主要通过单调队列来解决滑动窗口问题&#xff…

动效设计师的角色与职责:创造视觉魔法!

当今社会&#xff0c;随着视频游戏和数字产品的不断发展&#xff0c;动态设计师这个职业也在逐步发展壮大&#xff0c;同时也吸引了很多热爱动画设计的朋友。动态设计的目的是在第一时间吸引用户的注意力。那你知道动态设计师是做什么的吗&#xff1f;动态设计师的发展前景如何…

微信资源混淆,导致的约束布局 Constraintlayout 控件重叠!

问题 1、广告六要素 虽然我不参与广告 sdk 接入等相关工作&#xff0c;但是最近总是听到一个词广告六要素。这到底是什么&#xff1f; 国内下载类广告&#xff0c;尤其是针对移动应用推广的广告&#xff0c;其成功实施往往围绕几个关键要素进行&#xff0c;这些要素能够帮助…

智研未来,直击 AI DevOps,阿里云用户交流日杭州站来啦!

在这个技术日新月异的时代&#xff0c;云上智能化 DevOps 正以前所未有的速度推动企业创新边界&#xff0c;重塑软件开发的效率与品质。 为深入探索这一变革之路&#xff0c;诚邀您参与我们的专属闭门技术沙龙&#xff0c;携手开启一场关于云上智能化 DevOps 的挑战、实践与未…

展现金融科技前沿力量,ATFX于哥伦比亚金融博览会绽放光彩

不到半个月的时间里&#xff0c;高光时刻再度降临ATFX。而这一次&#xff0c;是ATFX不曾拥有的桂冠—“全球最佳在线经纪商”(Best Global Online Broker)。2024年5月15日至16日&#xff0c;拉丁美洲首屈一指的金融盛会—2024年哥伦比亚金融博览会(Money Expo Colombia 2024) 于…

#12松桑前端后花园周刊-SolidStart、Vercel融资、Angular18、Nextjs15RC、p5.js、ChromeDevTools引入AI

⚡️行业动态 SolidStart 1.0 元框架发布 Solidjs 核心团队发布其元框架 SolidStart 1.0 正式版&#xff0c;其特点如下&#xff1a;基于文件系统的路由&#xff1b;支持SSR、流式SSR、CSR、SSG渲染模式&#xff1b;通过代码分割、树摇和无用代码删除构建优化&#xff1b;基于…

typora自动生成标题序号(修改V1.0)

目录 带序号效果图 解决方法 带序号效果图 解决方法 1.进入文件夹&#xff1a;文件–>偏好设置–>外观–>主题–>打开主题文件夹 2.如果没有base.user.css文件&#xff0c;新建一个。如果有直接用记事本打开&#xff0c;把下面代码拷贝进去保存。 /** initiali…

设计模式 19 模板模式 Template Pattern

设计模式 19 模板模式 Template Pattern 1.定义 模板模式&#xff08;Template Pattern&#xff09;是一种行为设计模式&#xff0c;它定义了一个算法的骨架&#xff0c;将一些步骤的具体实现延迟到子类中。在模板模式中&#xff0c;定义了一个抽象类&#xff0c;其中包含了一个…

什么是光栅化?

一、 什么是光栅化? 光栅化作用是将几何数据变换后转换为像素呈现在显示设备上的一个过程。几何数据转换为像素&#xff0c; 本质是坐标变换、几何离散化&#xff0c;如下&#xff1a; 其中包含了坐标变换和几何离散化&#xff1a; 二、光栅化完成了什么 3D中&#xff0c;物…

Vue2 Element-UI 分页组件el-pagination 修改 自带的total、跳转等默认文字

场景需求&#xff1a; Vue2 Element-UI 分页组件el-pagination 修改 自带的total、跳转等默认文字。如下图&#xff1a;默认提示字变成了英文&#xff0c;如何将其 变成 汉字提示呢&#xff1f; 解决方案&#xff1a; 1.方案1&#xff1a;修改DOM内容 不提倡此方案&#xf…

Mybatis——入门

新建 idea 准备 数据库 create table user(id int unsigned primary key auto_increment comment ID,name varchar(100) comment 姓名,age tinyint unsigned comment 年龄,gender tinyint unsigned comment 性别, 1:男, 2:女,phone varchar(11) comment 手机号 ) comment 用…

【网络安全】勒索软件ShrinkLocker使用 windows系统安全工具BitLocker实施攻击

文章目录 威胁无不不在BitLocker 概述如何利用BitLocker进行攻击如何降低影响Win11 24H2 装机默认开启 BitLocker推荐阅读 威胁无不不在 网络攻击的形式不断发展&#xff0c;即便是合法的 Windows 安全功能也会成为黑客的攻击工具。 卡巴斯基实验室专家 发现 使用BitLocker的…

流程引擎之compileflow idea 2024.*插件支持

之前有使用过多种类型工作流&#xff0c;但最近研究工作流引擎对比各有优劣&#xff0c;compileflow内存支持性能不错&#xff0c;但在idea新版本使用的时候发现插件不支持&#xff0c;干脆自己修改源码手撸一个&#xff08;当前版本2024.1验证可用&#xff0c;如果有其他版本不…

如何给出好的“文言一心”指令?

一、文言一心是什么&#xff1f; 在现代技术背景下&#xff0c;“文言一心”还是百度公司创建的一款大语言模型。这款模型基于飞桨深度学习平台和文心知识增强大模型&#xff0c;并拥有强大的中文语料库&#xff0c;可以理解和生成富含文化内涵和哲理的文本内容。其核心技术架构…