docs(Hashing/Hash_Collision): add go part.

[boloboloda]

If this PR is related to coding or code translation, please read the contribution guideline, fill out the checklist, and paste the console outputs to the PR.

• [x] I've tested the code and ensured the outputs are the same as the outputs of reference codes.
• [x] I've checked the codes (formatting, comments, indentation, file header, etc) carefully.
• [x] The code does not rely on a particular environment or IDE and can be executed on a standard system (Win, macOS, Ubuntu).

[vercel[bot]]

The latest updates on your projects. Learn more about Vercel for Git ↗︎

1 Ignored Deployment

Name	Status	Preview	Comments	Updated
hello-algo	⬜️ Ignored (Inspect)			Mar 14, 2023 at 6:16PM (UTC)

[boloboloda]

Hello @Reanon , I create this PR for #222.

[krahets]

Hi 感谢 PR！

Golang 采用「链式地址」。在 Golang 里触发扩容的条件有两种，根据条件的不同扩容的方式也有所不同。一种是当负载因子大于 0.65 时则触发正常的翻倍扩容的方式，注意此次扩容不是原子的，是运行时的增量触发的；另一种则是当哈希使用了过多的溢出桶（溢出桶是在 Go 语言还使用 C 语言实现时使用的设计，由于它能够减少扩容的频率所以一直使用至今），那么这次扩容会是一次特殊的等量扩容，它是为了解决不断积累的溢出桶后大量写入、删除操作造成的内存泄漏问题而引入的。

有一点疑惑：这里的主语是链式地址，但后面是在讲解哈希表扩容。能否只集中在链式地址的相关概念？

[boloboloda]

Hi 感谢 PR！

Golang 采用「链式地址」。在 Golang 里触发扩容的条件有两种，根据条件的不同扩容的方式也有所不同。一种是当负载因子大于 0.65 时则触发正常的翻倍扩容的方式，注意此次扩容不是原子的，是运行时的增量触发的；另一种则是当哈希使用了过多的溢出桶（溢出桶是在 Go 语言还使用 C 语言实现时使用的设计，由于它能够减少扩容的频率所以一直使用至今），那么这次扩容会是一次特殊的等量扩容，它是为了解决不断积累的溢出桶后大量写入、删除操作造成的内存泄漏问题而引入的。

有一点疑惑：这里的主语是链式地址，但后面是在讲解哈希表扩容。能否只集中在链式地址的相关概念？

hi， 感谢回复。😊 我看了您的回复我也变得疑惑了，我怎么拐到扩容那去了，哈哈，不好意思。 我重新修改提交了一次，麻烦您再次review一下，如果还是不合理我可以再次修改或者关闭这个PR。

[Reanon]

写的还是有点复杂，如果没有研究过go语言源码的话，一时间很难通过这段描述来理解map。感觉要么就是通过源码来分析，要么就是脱离 go 的具体实现只讲抽象的设计。三言两语想讲明白确实不容易_(:3 ⌒ﾞ)_

[boloboloda]

写的还是有点复杂，如果没有研究过go语言源码的话，一时间很难通过这段描述来理解map。感觉要么就是通过源码来分析，要么就是脱离 go 的具体实现只讲抽象的设计。三言两语想讲明白确实不容易_(:3 ⌒ﾞ)_

Hi！谢谢您指出我的问题，我也感觉出我的回答可能太过于底层了，对不了解Go语言或者Go语言初学者可能太过于抽象，所以我重新改进了一下让它更加友好，不知道我这次有没有讲明白。

[krahets]

https://go.dev/src/runtime/map.go

/ This file contains the implementation of Go's map type. // // A map is just a hash table. The data is arranged // into an array of buckets. Each bucket contains up to // 8 key/elem pairs. The low-order bits of the hash are // used to select a bucket. Each bucket contains a few // high-order bits of each hash to distinguish the entries // within a single bucket. // // If more than 8 keys hash to a bucket, we chain on // extra buckets.

我大概总结一下 Go 的处理方法，你们看看对不对：

1. Go 整体上使用的是链式地址，但对链表的处理方式与 Java 不同；
2. 规定每个桶最多包含 8 个 key-val pairs ，超过则连接一个溢出桶；
3. 低位 hash 用于选择桶，高位 hash 用于查询 key-val pair 在该桶里的索引；

以及我有一个问题，那么对于溢出桶导致链表过长的情况，处理方式是否只有扩容，还是有其他机制。

[boloboloda]

我大概总结一下 Go 的处理方法，你们看看对不对：

1. Go 整体上使用的是链式地址，但对链表的处理方式与 Java 不同；
2. 规定每个桶最多包含 8 个 key-val pairs ，超过则连接一个溢出桶；
3. 低位 hash 用于选择桶，高位 hash 用于查询 key-val pair 在该桶里的索引；

以及我有一个问题，那么对于溢出桶导致链表过长的情况，处理方式是否只有扩容，还是有其他机制。

第一个问题，你总结的这三点，后两点来自于源码中的注释我觉得应该没有问题，第一点的话，我觉得使用链表这个词可能不太恰当。实现桶的数据结构是bmap。虽然都是链式结构，但是和我们平常理解的链表还是有点出入。

第二个问题，我理解你的问题是如果桶中元素过量然后又使用了溢出桶以后还是过量，如果直接回答这个问题的话Golang的处理方式确实是只有扩容这一种方式。没有其他额外的机制，但是它处理扩容的方式有所不同。我引用下我在上面说扩容那段

另一种则是当哈希使用了过多的溢出桶，那么这次扩容会是一次特殊的等量扩容，它是为了解决不断积累的溢出桶后大量写入、删除操作造成的内存泄漏问题而引入的。 runtime: limit the number of map overflow buckets

这种扩容方式不会做数据的拷贝和转移，只是对传入到旧桶的数据进行再分配，把数据分流到两个新桶之中。迁移过程是在runtime.evacuate中完成的。

[krahets]

@boloboloda 了解～ 我将表述更新为 Go 规定每个桶最多存储 8 个键值对，超出容量则连接一个溢出桶；当溢出桶过多时，会执行一次特殊的等量扩容操作，以保证性能 。

感谢 PR ！