Go map 的负载因子为什么是 6.5？

参考解析

什么是负载因子?

负载因子（load factor），用于衡量当前哈希表中空间占用率的核心指标，也就是每个 bucket 桶存储的平均元素个数。

  1. 负载因子 = 哈希表存储的元素个数/桶个数

另外负载因子与扩容、迁移等重新散列（rehash）行为有直接关系：

  • 在程序运行时，会不断地进行插入、删除等，会导致 bucket 不均，内存利用率低，需要迁移。
  • 在程序运行时，出现负载因子过大，需要做扩容，解决 bucket 过大的问题。

负载因子是哈希表中的一个重要指标，在各种版本的哈希表实现中都有类似的东西，主要目的是为了平衡 buckets 的存储空间大小和查找元素时的性能高低。

在接触各种哈希表时都可以关注一下，做不同的对比，看看各家的考量。

为什么是 6.5?

为什么 Go 语言中哈希表的负载因子是 6.5，为什么不是 8 ，也不是 1。这里面有可靠的数据支撑吗？

测试报告

实际上这是 Go 官方的经过认真的测试得出的数字，一起来看看官方的这份测试报告。

报告中共包含 4 个关键指标，如下：

loadFactor %overflow bytes/entry hitprobe missprobe
4.00 2.13 20.77 3.00 4.00
4.50 4.05 17.30 3.25 4.50
5.00 6.85 14.77 3.50 5.00
5.50 10.55 12.94 3.75 5.50
6.00 15.27 11.67 4.00 6.00
6.50 20.90 10.79 4.25 6.50
7.00 27.14 10.15 4.50 7.00
7.50 34.03 9.73 4.75 7.50
8.00 41.10 9.40 5.00 8.00
  • loadFactor：负载因子，也有叫装载因子。
  • %overflow：溢出率，有溢出 bukcet 的百分比。
  • bytes/entry：平均每对 key/value 的开销字节数.
  • hitprobe：查找一个存在的 key 时，要查找的平均个数。
  • missprobe：查找一个不存在的 key 时，要查找的平均个数。

选择数值

Go 官方发现：装载因子越大，填入的元素越多，空间利用率就越高，但发生哈希冲突的几率就变大。反之，装载因子越小，填入的元素越少，冲突发生的几率减小，但空间浪费也会变得更多，而且还会提高扩容操作的次数

根据这份测试结果和讨论，Go 官方取了一个相对适中的值，把 Go 中的 map 的负载因子硬编码为 6.5，这就是 6.5 的选择缘由。

这意味着在 Go 语言中，当 map存储的元素个数大于或等于 6.5 * 桶个数 时，就会触发扩容行为。