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)
}
- 首先我們初始化一個map，map的值為空結構體，列印分配堆記憶體的大小，
- 接著我們往map中添加100萬個元素，列印分配堆記憶體的大小，
- 然后我們洗掉所有元素，運行垃圾回收，列印分配堆記憶體的大小，
我們運行下上面的代碼：
go run 5.go
0 MB
33 MB
21 MB
當我們添加100萬元素之后，堆里面會分配33M的資料，像下面這樣
當我們洗掉100萬的資料之后，觸發GC回收，實際上GC只是回收了桶里面的元素資料，桶的數量不會因為洗掉操作而減少，所以還有21M的資料
原因是map中的桶數不會縮小，
當然，為了解決大量寫入、洗掉造成的記憶體泄漏問題，map引入了 sameSizeGrow 這一機制，在出現較多溢位桶時會整理哈希的記憶體減少空間的占用，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/518841.html
標籤：其他