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 mainimport (    "testing")var n = 1000000func 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 mainimport (    "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 这一机制，在呈现较多溢出桶时会整顿哈希的内存缩小空间的占用。