要说hashmap大家都并不陌生，像在C++，JAVA中就原生支持各种hashmap，在脚本语言如javascript，不仅直接支持hashmap，甚至可以直接将对象转换成JSON格式，相比在C语言里要使用这些“高级”的数据结构，还真得花费一点心思。今天呢，阿圆就给大家带来一个阿圆觉得在C里面算得上一个非常优雅的hashmap实现，即libcutils中的hashmap。

为什么阿圆推荐呢，主要有以下几个优点

纯C代码实现，编码风格非常优秀

使用回调函数对Hashmap进行操作，灵活

支持多线程访问

可移植性非常好

我们先看下Hashmap的基本数据结构

一个Entry里包含了key,value,hashCode还有一个Entry的next指针，不得不怀疑这个Hashmap是不是一个链表实现呢？这个问题在后面会有解答。

而结构Hashmap里除了用来存放Entry的buckets和计数bucketCount外，需要注意的是两个函数指针hash和equals，这是用来比较key的hash值是否相等用的，如果相等旧key中的值就会被新key中的值给替换。C++没有模板或者泛化的功能，所以不同的hashmap需要实现自己不同的hash函数和equals函数，来达到模板的功能。

这个hashmap主要提供了hashmapCreate，hashmapFree，hashmapPut，hashmapGet，hashmapRemove，hashmapSize，hashmapForEach，hashmapLock，hashmapUnlock等常用的一些功能。

现在我们就来简单介绍一下其使用方法

[1]用STM32CubMx新建一个带USART的FreeRTOS STM32工程（说过好多回了）[2]添下载好的hashmap.c及hashmap.h添到工程目录[3]修改hashmap.c

注释掉不支持的头文件，同时添加FreeRTOS.h及semphr.h，再定义好互斥锁就可以了

[4]写下简单测试的代码

首先要先好hash和equals回调函数，为了使用hashmapForEach函数，还得实现foreach的回调，如下图所示

编写简单的测试用示例

[5]调试运行，没有问题

这里就要回到一开始说的到next指针了，在理想情况下，每个key的hash值都不一样，这样就可以直接在buckets里直接通过不同的hash结果得不同的index，从而用这个index直接在buckets里直接拿到相应的value，算法上的时间复杂度就是O(1)，而最坏的情况下，hashmap就会退化成为了一个链表，算法上的时间复杂度就变成了O(N)，原因就是每次根据key hash出来的index都是相同的值, 而因为每次插入的index都相同，所以buckets[index]则退化为一个链表头，新添加的Entry都会在链表中依次链接起来，这就是为什么Entry上有一个next指针。

说了hashmap的使用，现在要来注意下这个hashmap的坑

Hashmap是直接使用malloc,free，在嵌入式系统上并不是最优实现

在使用hashmapPut时需要注意返回值，如果返回值不为NULL就需要根据情况手动释放分配的内存

不过总得来说hashmap的C实现还是非常不错的，值得收藏使用~

今天阿圆的分享就到这里，谢谢大家！