Go 语言中 map 的底层原理

Go 语言中 `map` 的底层原理

提示

题眼： 拉链法

当发生哈希冲突时，拉链法的做法是在哈希桶后面挂接额外的溢出桶，用来存放冲突元素。Java 的 HashMap 在元素较多时还会引入红黑树优化，而 Go 的 map 主要还是围绕桶和溢出桶组织数据。

这里总结几个比较重要的点：

map 在定位桶时会利用哈希值的低位来计算桶编号，而哈希高位中的一部分信息会作为 tophash 存在桶里，加快比较过程。
常见触发扩容的情况有两种：装载因子过高，或者溢出桶过多。
每个桶里最多存放 8 个键值对，超出后会挂到溢出桶上。

重要

参考答案：
Go 语言的 map 底层也是基于哈希表实现的。它会维护一组桶，桶的数量通常是 2 的幂次。当我们读写某个键值对时，会先对 key 做哈希，然后根据结果找到对应的桶。
每个桶最多能放 8 个键值对。如果一个桶装不下了，就会分配溢出桶，把多出来的元素挂过去。
Go 还做了一个性能优化：在桶里不会直接一上来就完整比较 key，而是会先比较哈希结果里保留下来的那一小段高位信息，也就是常说的 tophash。如果这部分都对不上，就没必要再继续比较完整 key 了。
因为最终还是要靠 key 做判等，所以 map 的 key 必须是可比较的类型，这也是为什么切片、map、函数不能作为 map key。