16｜复合数据类型：原生map类型的实现机制是怎样的？

作者回复: ✅

作者回复: 好问题！ 关于这个问题，官方没有明确说明。 我觉得之所以map element是不可寻址的，还是复杂性和安全性的考虑。 Go slice和map都是复合数据类型，但两者的内部实现复杂度却远远不同。map要远复杂于slice。 slice的元素的地址要么在要么在原底层数组中，要么在扩容后的新数组中。并且slice扩容是一次完成的。 但map扩容是“蚂蚁搬家”，element位置复杂一些，可能在原bucket中、可能在overflow bucket中，也可能在新扩容的bucket中。 此外，一旦暴露map element的地址，比如我们用一个栈上的指针变量引用了该地址，当发生element移动时，go就要考虑连带变更这些栈上指针变量的指向，这些变更操作在每个map操作中都会导致运行时消耗的增加。 至于安全性，map有着一个复杂内部结构，这个结构环环相扣。一旦map element地址被暴露，通过该地址不仅可以修改value值，还可能会对map内部结构造成破坏，这种破坏将导致整个map工作不正常。而slice的element即便被hack，改掉的也只是元素值。

作者回复: 这一话题要追溯到Go 1.0版本发布的时候，从Go 1.0版本的发布文档- https://go.dev/doc/go1中，我们能找到如下内容： The old language specification did not define the order of iteration for maps, and in practice it differed across hardware platforms. This caused tests that iterated over maps to be fragile and non-portable, with the unpleasant property that a test might always pass on one machine but break on another. In Go 1, the order in which elements are visited when iterating over a map using a for range statement is defined to be unpredictable, even if the same loop is run multiple times with the same map. Code should not assume that the elements are visited in any particular order. This change means that code that depends on iteration order is very likely to break early and be fixed long before it becomes a problem. Just as important, it allows the map implementation to ensure better map balancing even when programs are using range loops to select an element from a map. 翻译过来，大致意思就是：1.0版本之前的语言规范中没有规定map的迭代次序，从而导致在实践中的一些糟糕的开发运行体验。于是Go团队选 择故意在map中加入随机迭代功能，这样一旦出现开发人员依赖key迭代顺序的错误行为，这一行为导致的问题在开发和测试早期就能被及时发现，而不会出现在生产运行环境中导致更大的危害。

作者回复: 用代码回答你的问题：） // testnilasmapkey.go package main func main() { var m = make(map[*int]*int) m[nil] = nil println(m) println(len(m)) var b = 5 m[nil] = &b p := m[nil] println(*p) } 0xc0000466b0 1 5 nil作为value不新鲜。但nil可作为key可是很多人都不知道的。

作者回复: 在Go项目源码(Go 1.17版本)的 src/cmd/compile/internal/reflectdata/reflect.go中，func MapBucketType(t *types.Type) *types.Type>这个函数实现中，我们可以勾勒出一个bucket桶的结构： tophash keys values overflow pointer 不过这个overflow pointer有两种情况： // If keys and elems have no pointers, the map implementation // can keep a list of overflow pointers on the side so that // buckets can be marked as having no pointers. // Arrange for the bucket to have no pointers by changing // the type of the overflow field to uintptr in this case. // See comment on hmap.overflow in runtime/map.go. otyp := types.Types[types.TUNSAFEPTR] if !elemtype.HasPointers() && !keytype.HasPointers() { otyp = types.Types[types.TUINTPTR] } 当key和value中都没有指针时，比如map[int]int。此时考虑到gc优化，编译器将overflow的类型设置为uintptr。 uintptr是一个整型，无法被GC识别，这样一来uintptr指向的overflow bucket就没有指向它的指针，这样gc就会将overflow bucket视为unrea chable的mem块而将其释放掉。为了避免这种情况，hmap中的extra此时就会指向上面这类bucket的overflow bucket，保证key和value中都不含指针时，overflow bucket依旧可以不被gc。

作者回复: ✅

作者回复: 好问题。这个等量扩容来自这个issue：https://github.com/golang/go/issues/16070 这是一种比较特殊的情况，即当持续向哈希中插入数据，然后又将它们全部删除时，这个过程如果触发增容扩容，就会导致overflow bucket过多，但此时原bucket中已经没有数据了。所以go引入了利用现有扩容机制的等量扩容 https://github.com/golang/go/commit/9980b70cb460f27907a003674ab1b9bea24a847c 将原bucket的overflow bucket中的数据重新挪到新bucket中。算法较复杂，专栏定位入门，所以没进行深入。感兴趣可以读一下这个cl commit的源码。

作者回复: 过奖。其实原理这东西最终还是要落到代码上。而且不同版本实现也有差异。要想真正把原理吃透，还得自己多过几遍代码

作者回复: 是一个可行方法。

作者回复: go map底层的hash函数要考虑通用性。谁也不能预测用户会使用什么样的key数据。