Golang面试题：Map 如何扩容?

1、Golang Map 底层实现?

Golang 中 map的底层实现是一个散列表，因此实现 map的过程实际上就是实现散表的过程。在这个散列表中，主 要出现的结构体有两个：

• 一个叫 hmap(a header for a go map)，
• 一个叫 bmap(a bucket for a go map，通常叫 其bucket)。

2、Golang Map 如何扩容?

装载因子: count/2^B

触发条件:

1. 装填因子是否大于6.5
2. overflow bucket 是否太多

解决方法:

1. 双倍扩容: 扩容采取了一种称为“渐进式”地方式，原有的 key 并不会一次性搬迁完毕，每次最多只会搬迁2 个 bucket

2. 等量扩容: 重新排列，极端情况下，重新排列也解决不了，map成了链表，性能大大降低，此时哈希种子 hash0 的设置，可以降低此类极端场景的发生。

3、Golang Map 查找

Go语言中 map采用的是哈希查找表，由一个 key 通过哈希函数得到哈希值，64 位系统中就生成一个64bit 的哈希值，由这个哈希值将 key 对应到不同的桶 bucket)中，当有多个哈希映射到相同的的桶中时，使用链表解决哈希冲突。

key 经过 hash 后共64 位，根 据 hmap中 B的值，计算它到底要落在哪个桶时，桶的数量为2^B，如 B=5，那么用64 位最后5 位表示第几号 桶，在用 hash 值的高8 位确定在 bucket 中的存储位置，当前 bmap中的 bucket 未找到，则查询对应的 overflow bucket，对应位置有数据则对比完整的哈希值，确定是否是要查找的数据。

如果两个不同的 key 落在的同一个桶上，hash 冲突使用链表法接近，遍历 bucket 中的 key 如果当前处于 map进 行了扩容，处于数据搬移状态，则优先从 oldbuckets 查找。