go 源码之 map

参考资料

【腾讯文档】Go 源码之 Map
https://docs.qq.com/doc/DQUlxQnBaQk5lc05O

(30 条消息) 【go 语言之 map 源码分析】_go map 源码解析_不爱学习的王小小的博客-CSDN 博客

常见问题

1. 为什么 map 的 value 不可寻址

具体来说，当我们定义一个 map 时，实际上是创建了一个 hash 表，其中每个元素包含一个 key 和一个 value。在 Go 语言中，map 的 value 是一个类型为 T 的值的副本，而不是指向 T 的指针。这意味着我们不能直接寻址 map 的 value，因为这样会导致 map 内部数据的重新分配和移动，从而破坏 map 的内部机制。

为了避免这种情况，我们可以采用以下两种方式来处理 map 的 value：

1. 使用指针作为 map 的 value。如果我们需要对 map 的 value 进行修改，可以将 value 定义为指向 T 的指针，然后通过指针来修改 value，而不是直接寻址 value。
2. 使用值类型作为 map 的 value，并采用替换的方式来修改 value。如果我们需要修改 map 的 value，可以先将 value 取出来，对 value 进行修改，然后再将修改后的 value 替换回 map 中。

2. map 的负载因子是怎么算的

3. map 的扩容机制

• 等量扩容

  loadFactor 负载因子 （map 中数据总个数 / 桶个数 ）> 6.5

• 翻倍扩容

  当 hmap 中的 B：

  B <=15，已使用的溢出桶个数 >= $2^B$ 时，

  B > 15，已使用的溢出桶个数 >= $2^{15}$ 时，

4. map 的 key 迁移的过程

当 map 需要扩容时，会先分配一个新的哈希表，然后在后续的键值对插入操作中，逐步将原有的键值对数据从旧的哈希表中复制到新的哈希表中。这样可以避免一次性复制大量的键值对数据，从而减少对系统的影响。

5. 为什么 map 是无序的

• key 通过 hash 之后存储本身就是无序的
• map 发生扩容之后，key 存储的位置也会发生变化
• map 底层在遍历的时候也是无序遍历的，并不是从第一个桶开始依次遍历（ go 1.0 ）

6. map 是如何解决哈希冲突的

哈希查找表一般会存在“碰撞”的问题，就是说不同的 key 被哈希到了同一个 bucket。一般有两种应对方法：

• 链表法：将一个 bucket 实现成一个链表，落在同一个 bucket 中的 key 都会插入这个链表

• 开放地址法：则是碰撞发生后，通过一定的规律，在数组的后面挑选“空位”，用来放置新的 key

go 语言中的 map 是也基于哈希表实现的，它解决哈希冲突的方式是链地址法，即通过使用数组 + 链表的数据结构来表达 map