go语言中的map详解

柔情寂寞如烟 03-14 118

前言：

眼前同学们对“map的值”大致比较注意，姐妹们都需要剖析一些“map的值”的相关知识。那么小编在网络上网罗了一些关于“map的值””的相关文章，希望你们能喜欢，朋友们一起来了解一下吧！

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)}

首先我们初始化一个map，map的值为空结构体，打印分配堆内存的大小。接着我们往map中添加100万个元素，打印分配堆内存的大小。然后我们删除所有元素，运行垃圾回收，打印分配堆内存的大小。

我们运行下上面的代码：