乐趣区

关于go:golang中的map

jiezi

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: darwin
goarch: amd64
pkg: go-demo/5
cpu: Intel(R) Core(TM) i7-4770HQ CPU @ 2.20GHz
BenchmarkWithSize-8                    6         178365104 ns/op
BenchmarkWithoutSize-8                 3         362949513 ns/op
PASS
ok      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.go
0 MB
33 MB
21 MB

当咱们增加 100 万元素之后，堆外面会调配 33M 的数据，像上面这样

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

起因是 map 中的桶数不会放大。

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

退出移动版