golang 中的 map

0.1、索引

https://waterflow.link/articles/1666339004798

1、map 的结构

map 提供了键值对的无序集合，所有的键都是不重复的。在 go 中 map 是基于 bmap 数据结构的。在内部 hash 表是一个桶数组，每个桶是一个指向键值对数组的指针。每个桶里面可以保存 8 个元素。我们可以简化成下面的结构。

如果我们继续插入一个元素，hash 键返回相同的索引，则另一个元素也会插入相同的桶中。

如果正常桶中的元素已满，还有元素继续往相同的索引插入的话，go 会创建另一个包含 8 个元素的桶并将前一个桶指向他。

所以当我们读取、更新和删除 map 元素时，Go 必须计算相应的数组索引。 然后 Go 依次遍历所有键，直到找到提供的键。 因此，这三个操作的最坏情况时间复杂度为 O(p)，其中 p 是桶中元素的总数（默认为一个桶，溢出时为多个桶）。

2、map 初始化

首先我们先初始化一个包含 3 个元素的 map：

m := map[string]int{    "haha": 3,    "hehe": 5,    "hoho": 7,  }

我们可能只需要遍历 2 个桶就可以找到上面的所有元素。

但是当我们添加 100 万个元素的时候，我们可能需要遍历上千个桶去找到指定的元素。

为了应对元素的增长，map 会选择扩容，一般是当前桶数量增加一倍。那什么时候会扩容呢？

• 负载因子大于 6.5

• 溢出桶太多

当 map 扩容的时候，所有的键都会重新分配到新的桶。所以最坏情况下，插入元素有可能是 O(n)。

我们知道，在使用切片时，如果我们预先知道要添加到切片的元素数量，我们可以用给定的大小或容量对其进行初始化。这避免了不断应对切片增长导致底层数组频繁复制的问题。map 与此类似。实际上，我们可以使用 make 内置函数在创建地图时提供初始大小。例如，如果我们要初始化一个包含 100 万个元素的 map，可以这样写：

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

通过指定大小，go 使用适当数量的桶创建 map 以存储 100 万个元素。 这节省了大量计算时间，因为 map 不用动态创建桶并处理桶溢出后 rehash 的问题。

指定大小 n 并不是说创建最多有 100 万个元素的 map。 我们可以继续往 map 添加元素。 这实际代表着 Go 运行时至少 需要为 n 个元素分配内存。

我们可以运行下基准测试看下这两个的性能差异：

package main
import (  "testing")
var n = 1000000
func BenchmarkWithSize(b *testing.B) {  for i := 0; i < b.N; i++ {    m := make(map[string]int, n)    for j := 0; j < n; j++ {      m["hhs" + string(rune(j))] = j    }  }}
func BenchmarkWithoutSize(b *testing.B) {  for i := 0; i < b.N; i++ {    m := make(map[string]int)    for j := 0; j < n; j++ {      m["hhs"+string(rune(j))] = j    }  }}

go test -bench=.goos: darwingoarch: amd64pkg: go-demo/5cpu: Intel(R) Core(TM) i7-4770HQ CPU @ 2.20GHzBenchmarkWithSize-8                    6         178365104 ns/opBenchmarkWithoutSize-8                 3         362949513 ns/opPASSok      go-demo/5 4.563s

我们可以看到初始化 map 大小的性能是高于未设置初始化大小的性能。其中的原因上面应该解释的很清楚了。

3、map 内存泄漏

我们看下下面的一个例子：

package main
import (  "fmt"  "runtime")
func main() {  n := 1000000  m := make(map[int]struct{})  printAlloc()
  for i := 0; i < n; i++ {    m[i] = struct{}{}  }  printAlloc()
  for i := 0; i < n; i++ {    delete(m, i)  }
  runtime.GC()  printAlloc()  // 保留对m的引用，确保map不会被回收  runtime.KeepAlive(m)
}
// 打印内存分配情况func printAlloc() {  var m runtime.MemStats  runtime.ReadMemStats(&m)  fmt.Printf("%d MB\n", m.Alloc/1024/1024)}

1. 首先我们初始化一个 map，map 的值为空结构体，打印分配堆内存的大小。

2. 接着我们往 map 中添加 100 万个元素，打印分配堆内存的大小。

3. 然后我们删除所有元素，运行垃圾回收，打印分配堆内存的大小。

我们运行下上面的代码：

go run 5.go0 MB33 MB21 MB

当我们添加 100 万元素之后，堆里面会分配 33M 的数据，像下面这样

当我们删除 100 万的数据之后，触发 GC 回收，实际上 GC 只是回收了桶里面的元素数据，桶的数量不会因为删除操作而减少，所以还有 21M 的数据

原因是 map 中的桶数不会缩小。

当然，为了解决大量写入、删除造成的内存泄漏问题，map 引入了 sameSizeGrow 这一机制，在出现较多溢出桶时会整理哈希的内存减少空间的占用。