go语言底层数据结构之map解析

友情提示：本文共有 1397 个字，阅读大概需要 3 分钟。

go语言中map类型

首先我们来看一段代码：

大家想下程序会输出什么？如果go语言是传递引用的话，那输出应该是false，但是实际输出是true，fn内部申请的map[int][int]不影响外部m，那此时我们就要问：如果map不是引用类型，那map是什么？

上面代码打印出了m的地址，m的内容，m的大小，输出为：

所有m是一个指针，那具体m的结构是什么呢？可以通过gdb调试，关于如何调试可以看我前面一篇文章。

可以看到m是一个struct hash结构，这种形式就像c++中的模板，因为此处m声明的是map[int][int]，所以实例化struct hash的时候就是key类型int，value类型int（注：此处只是以c++中模板为例子，实际go没有使用模板实现）

小结：当目前为止，我们知道了go语言中map的传递是值传递，对于map类型的变量，只是保存了一个指针，要确定一个map，需要知道key和value的类型，但是go语言在实现上没有像c++一样使用泛型，具体怎么做的，我们稍后讲解，下面我们来看下map的实现原理。

map原理

map用函数描述就是：map(key) → value ，输入key，返回value，然后提供下面的数据操作函数：

map还有一个重要的功能hash函数，即 hash(key) → integer ，将key映射为整数，然后所有key放入数组里，通过计算出来的hash(key)找到数组下标，用一个示意图描述下：

更具体的譬如哈希冲突问题自然自行Google。

这里总结下一个hashmap的关键点：

一个hash函数，完成key的映射key比较函数key和value的类型，能够在map中保存我们来看下c++中unordered_map的类型：

c++中通过泛型实现了不同类型的map，在编译期间就能确认类型，那go语言中没有泛型，怎么实现map呢？

我们还是用gdb来调试代码：

runtime.makemap (h=0xc420047ec8, hint=100, t=0x10c6d80 , ~r3=0x10bf600 )at /usr/local/opt/go/libexec/src/runtime/hashmap.go:298298 func makemap(t *maptype, hint int, h *hmap) *hmap

在创建map的时候，会执行到runtime.makemap，里面有maptype，hmap:

我们可以看到maptype中保存了key和value的类型，以及我们bucket的类型，所以go语言在编译的时候，会根据我们的声明，来生成maptype，每个map的maptype都是唯一的，根据maptype，我们就实现了一份map代码，不同key和value的类型，来看下runtime._type:

其中 runtime.typeAlg 记录了hash函数和比较函数，所以go语言在实现map上，没有像c++一样，通过泛型来生成N份map代码，而是通过N个maptype，一份map代码来实现map的通用。

总结

本文带领大家查看了go语言中map的实现，知道了map在go中是一个指针，另外虽然go不支持泛型，但是go中通过maptype实现了c++中的泛型map，至于map具体的实现细节，大家可以直接看go runtime包即可。

本文如果对你有帮助，请点赞收藏《go语言底层数据结构之map解析》，同时在此感谢原作者。