大家好，我是小道哥。

今天是： map的实现原理

映射定义映射是key-value密钥-值对的存储结构，key不能重复。 其基础实现使用hash表。

map的数据结构首先显示了在src/runtime/map.go中实现的源结构的重要字段。

类型hmap struct { count int//元素的数量B uint8 //buckets数组的长度为2^B个溢出桶的数量buckets unsafe.Pointer //如果发生对应于2^B个桶的数组指针oldbuckets unsafe.Pointer //扩展，则存储扩展前的buckets数组指针extra *mapextra //溢出桶的地址} bmapoldoverflow * [ ] * bmapnextoverflow * * bmapoldoverflow * typebmapstruct { top hash [ bucket CNT ] uint8}//编译期间新建结构了解生成用于存储哈希值的高8位databyte [1]/kyte ./value/value/value . overflow * bmap//溢出bucket的地址}源代码的结构

在go的map实现中，其基础结构是hmap，hmap relet保护了几个bucket数组，即桶数组。

Bucket序列的各要素为bmap结构。 也就是说，各Bucket (铲斗)是bmap结构。 【ps :后文匹配语义，为了便于理解，不再提及bmap，统称为bocket】每个bocket保存8个kv对，8个满后，另一个key落入该bocket，使用ook

在了解map中的数据操作map的数据结构之后，让我们来学习map中的数据访问过程。

GET获取数据假设当前 B=4 即桶数量为2^B=16个，并从map获取与k4对应的value

参考上图，k4的get流程可以归纳为如下几步：

计算k4的hash值[当前主流是64位操作系统，因此计算结果为64位]

通过最后的“B”位来确定在哪号桶在这种情况下，b为4，所以对应于k4哈希值的后4位，即0101，0101以10进制表示为5，所以位于5号桶)

根据k4对应的hash值前8位快速确定是在这个桶的哪个位置(另外介绍，bmap中存储了与各key对应的tophash，排在key哈希值前8位。 )前8位一致时，进入下一步

对比key完整的hash是否匹配

如果都没有找到，就去连接的下一个溢出桶中找

很多同学会在这里为什么要保持tophash，即hash的前八位？

这是因为tophash可以快速确定key是否正确，也可以将其理解为缓存措施。 如果前8位错了，以后就不需要比较了。

PUT存储数据

map的赋值流程可总结位如下几步：

通过key的hash值后“B”位确定是哪一个桶，图例为4号桶。

遍历当前桶，通过key的tophash和hash值，防止key重复，然后将数据存储在找到第一个可以插入的位置，即空闲位置。

当前桶元素已满，会通过overflow链接创建一个新的桶的话，保存数据。

33558www.Sina.com/:2:当两个不同的key落入同一个桶中时，发生了散列冲突。 冲突的解决手段是采用链表法。 在水桶里，走后找到第一个空位插入。 当8个kv满时，当前桶连接到下一个溢出桶(bmap )。

扩展方式关于hash冲突

由于地图上不断有put和delete key，因此水桶可能会有很多间断的空闲空间。 这些空闲空间会导致连接的bmap溢出水桶，从而增加扫描时间。 这个扩展实际上是整理，在前面整理后置位置的数据。相同容量扩容

这种情况下，元素会发生重排，但不会换桶。的两倍扩展对于当前的铲斗阵列来说是不够的，因此，

g>发生这种扩容时，元素会重排，可能会发生桶迁移。

如图中所示，扩容前B=2,扩容后B=3，假设一元素key的hash值后三位为101，那么由上文的介绍可知，在扩容前，由hash值的后两位来决定几号桶，即 01 所以元素在1号桶。 在扩容发生后，由hash值得后三位来决定几号桶，即101所以元素会迁移到5号桶。

扩容的条件

首先我们了解下**装载因子(loadFactor)**的概念

loadFactor:=count / (2^B) 即 装载因子 = map中元素的个数 / map中当前桶的个数

通过计算公式我们可以得知，装载因子是指当前map中，每个桶中的平均元素个数。

扩容条件1：**装载因子 > 6.5 **(源码中定义的)

这个也非常容易理解，正常情况下，如果没有溢出桶，那么一个桶中最多有8个元素，当平均每个桶中的数据超过了6.5个，那就意味着当前容量要不足了，发生扩容。

扩容条件2: 溢出桶的数量过多

当 B < 15 时，如果overflow的bucket数量超过 2^B。

当 B >= 15 时，overflow的bucket数量超过 2^15。

简单来讲，新加入key的hash值后B位都一样，使得个别桶一直在插入新数据，进而导致它的溢出桶链条越来越长。如此一来，当map在操作数据时，扫描速度就会变得很慢。及时的扩容，可以对这些元素进行重排，使元素在桶的位置更平均一些。

扩容时的细节

在我们的hmap结构中有一个oldbuckets吗，扩容刚发生时，会先将老数据存到这个里面。每次对map进行删改操作时，会触发从oldbucket中迁移到bucket的操作【非一次性，分多次】在扩容没有完全迁移完成之前，每次get或者put遍历数据时，都会先遍历oldbuckets，然后再遍历buckets。 注意事项

对map数据进行操作时不可取地址。常见的错误用例如下：

type Student struct {Name stringAge int}func f1() {m := map[int]Student{1: Student{Age: 15, Name: "jack"},2: Student{Age: 16, Name: "danny"},3: Student{Age: 17, Name: "andy"},}m[1].Name = "JACK"}

这种情况会发生编译错误，因为map元素是无法取址的，也就是说，你可以得到m[1]，但是无法对它的值作出任何修改。如果你想修改value，可以使用带指针的value，如下：

func f2() {m := map[int]*Student{1: &Student{Age: 15, Name: "jack"},2: &Student{Age: 16, Name: "danny"},3: &Student{Age: 17, Name: "andy"},}m[1].Name = "JACK"}

不知道各位道友有没有疑惑，为什么go中要禁止对map的元素进行取址呢？这是因为map 会随着元素数量的增长而重新分配更大的内存空间，会导致之前的地址无效。

map是线程不安全的

在同一时间点，两个 goroutine 对同一个map进行读写操作是不安全的。举个栗子：

某map桶数量为4，即B=2。此时 goroutine1来插入key1， goroutine2来读取 key2. 可能会发生如下过程：

① goroutine2 计算key2的hash值,B=2，并确定桶号为1。

② goroutine1添加key1，触发扩容条件。

③ B=B+1=3, buckets数据迁移到oldbuckets。

④ goroutine2从桶1中遍历，获取数据失败。

在工作中，当我们涉及到对一个map进行并发读写时，一般采用的做法是采用golang中自带的mutex锁

type Resource struct {sync.RWMutexm map[string]int}func main() {r := Resource{m: make(map[string]int)}go func() { //开一个goroutine写mapfor j := 0; j < 100; j++ {r.Lock()r.m[fmt.Sprintf("resource_%d", j)] = jr.Unlock()}}()go func() { //开一个goroutine读mapfor j := 0; j < 100; j++ {r.RLock()fmt.Println(r.m[fmt.Sprintf("resource_%d", j)])r.RUnlock()}}()} 面试点总结

map的底层数据结构

map的GET操作和PUT操作过程

map的扩容条件

map的注意事项：不可对元素取址、线程不安全

后语

如果大家对本文提到的面试技术点有任何问题，都可以在评论区进行回复哈，我们共同学习，一起进步！

关注公众号[简道编程]，每天一个后端技术面试点