Go语言中常见100问题-#27 map初始化方法及最佳实践

前言

map实现原理

map是无序的键值对集合，所有的键都是不同的。Go语言中的map实现基于哈希表数据结构, 哈希表的内部是一个桶数组，桶中的元素是一个指针，指向一个键值对数组，如下图所示。图中的哈希表有4个桶，桶中的元素是一个整数索引，指向一个key-value的键值对（例如key为two，value为2）数组，键值对数组大小为8.

map的读写、插入和删除操作围绕key展开，对应到上图Array数组的索引，将键值对映射到Array数组的某个位置依赖哈希函数。哈希函数是稳定的，给定相同的输入值，输出值的key值总是相同。

在上图中，hash("two")返回0，因此键值对(two-2)存储在数组索引0指向的桶中。如果此时再插入一个键值对(six-6),hash("six")返回的也是0，会插入到相同的桶中，如下图所示。

如果继续向桶中插入元素，则可能导致桶满（装8个元素）产生溢出。Go语言中实现方法是创建另一个能够装载8个元素的桶，并且与前面的桶串联起来，效果如下图。

无论是读、更新和删除操作，必须计算元素的hash值，通过hash值定位到数组Array中的位置。然后循环遍历桶中元素，比较key是否相同，直到找到相同的key或迭代完桶中所有元素。因此，这三种操作复杂度最差情况为 O(p），p为桶中元素的数量（默认情况只有一个桶，如果存在溢出，则有多个桶）。

案例引入

为了说明如何高效初始化map问题，下面举例说明，创建一个包含有3个元素类型为map[string]int的map。

m := map[string]int{
    "1": 1,
    "2": 2,
    "3": 3,
}

上述程序中的map m在内部实现上哈希数组只有一个元素，因为只有3个元素只需创建1个桶（装8个数据）就够了。如下图所示，小于8个元素在内部实现调用走 runtime.makemap_small逻辑。

假设此时向m中添加100万个元素，会怎样？在这种情况下，如果哈希数组还是只有一个元素，则会创建过千个桶，查找一个key，最糟糕的情况下需要遍历这上千个桶，性能非常差。这就是为啥map需要自动扩容的原因。

当map扩容的时候，创建桶的数量会加倍。map扩容的条件是什么呢？

• 桶中平均装载的元素（称为装填因子）超过一个常量值6.5（该常量值可能在未来Go版本中发生变化，因为它是内部库中定义的）

• 有太多的桶存在溢出桶（桶中的元素超过8个会创建溢出桶）

当map扩容的时候，它里面的所有的元素重新放置到新的所有桶中，在最糟糕的情况下，插入一个元素需要 O(n) 次操作，n为map中元素的数量。

解决方法

m := make(map[string]int, 1_000_000)

与创建切片不同的是，创建map只需要设置大小不需要设置容量。通过在初始化时就设置map的大小，在内部实现时，会设置合适的桶的数量来装载100万个元素，这将节省大量动态创建map以及处理平衡需要的时间。

指定map的大小为n,并不意味着只能向map中最多只能添加n个元素，是可以添加n个以上元素的。Go运行时在一开始会分配至少n个元素的空间，减少扩容带来的性能损耗。

性能测试对比

为了直观感受设置map大小的重要性，通过运行基准测试来对比说明。下面的两个测试都是向map中插入100万个元素，一个不设置初始大小，另一个设置初始大小，测试结果如下。可以看到，设置初始化大小的版本比不设置大小大约快60%，通过设置初始大小，可以防止map扩容时计算开销。

BenchmarkMapWithoutSize-4 6 227413490 ns/op
BenchmarkMapWithSize-4 13 91174193 ns/op

因此，同切片那样，如果已知添加的元素数量，在创建时就设置为给定的大小，避免潜在的扩容增长，因为这个过程需要很多计算、重新定位元素的位置以及重新平衡所有元素。