网站及新媒体帐号内容建设,广东建筑企业50强,网站备案需要那些资料,做网站有什么好处和切片相比#xff0c;map类型的内部实现要复杂得多。Go运行时使用一张哈希表来实现抽象的map类型。运行时实现了map操作的所有功能#xff0c;包括查找、插入、删除、遍历等。在编译阶段#xff0c;Go编译器会将语法层面的map操作重写成运行时对应的函数调用。 下面是大致的… 和切片相比map类型的内部实现要复杂得多。Go运行时使用一张哈希表来实现抽象的map类型。运行时实现了map操作的所有功能包括查找、插入、删除、遍历等。在编译阶段Go编译器会将语法层面的map操作重写成运行时对应的函数调用。 下面是大致的对应关系
// $GOROOT/src/cmd/compile/internal/gc/walk.go
// $GOROOT/src/runtime/map.go
m : make(map[keyType]valType, capacityhint) → m : runtime.makemap(maptype, capacityhint, m)
v : m[key] → v : runtime.mapaccess1(maptype, m, key)
v, ok : m[key] → v, ok : runtime.mapaccess2(maptype, m, key)
m[key] value → v : runtime.mapassign(maptype, m, key) // v是用于后续存储value 的空间的地址
delete(m, key) → runtime.mapdelete(maptype, m, key)下图是map类型在运行时层实现的示意图。 1. 初始状态
从图上中我们可以看到与语法层面map类型变量一一对应的是runtime.hmap类型的实例。hmap是map类型的header可以理解为map类型的描述符它存储了后续map类型操作所需的所有信息。
● count当前map中的元素个数对map类型变量运用len内置函数时len函数返回的就是count这个值。
● flags当前map所处的状态标志目前定义了4个状态值——iterator、oldIterator、hashWriting和sameSizeGrow。
● BB的值是bucket数量的以2为底的对数即2^B bucket数量。
● noverflowoverflow bucket的大约数量。
● hash0哈希函数的种子值。
● buckets指向bucket数组的指针。
● oldbuckets在map扩容阶段指向前一个bucket数组的指针。
● nevacuate在map扩容阶段充当扩容进度计数器。所有下标号小于nevacuate的bucket都已经完成了数据排空和迁移操作。
● extra可选字段。如果有overflow bucket存在且key、value都因不包含指针而被内联inline的情况下该字段将存储所有指向overflow bucket的指针保证overflow bucket是始终可用的不被垃圾回收掉。
真正用来存储键值对数据的是bucket桶每个bucket中存储的是Hash值低bit位数值相同的元素默认的元素个数为BUCKETSIZ值为8在$GOROOT/src/cmd/compile/internal/gc/reflect.go中定义与runtime/map.go中常量bucketCnt保持一致。
当某个bucket比如buckets[0]的8个空槽slot都已填满且map尚未达到扩容条件时运行时会建立overflow bucket并将该overflow bucket挂在上面bucket如buckets[0]末尾的overflow指针上这样两个bucket形成了一个链表结构该结构的存在将持续到下一次map扩容。
每个bucket由三部分组成tophash区域、key存储区域和value存储区域。
1tophash区域
当向map插入一条数据或从map按key查询数据的时候运行时会使用哈希函数对key做哈希运算并获得一个哈希值hashcode。这个hashcode非常关键运行时将hashcode“一分为二”地看待其中低位区的值用于选定bucket高位区的值用于在某个bucket中确定key的位置。这个过程可参考下图。 因此每个bucket的tophash区域是用于快速定位key位置的这样避免了逐个key进行比较这种代价较大的操作尤其是当key是size较大的字符串类型时这是一种以空间换时间的思路。
2key存储区域
tophash区域下面是一块连续的内存区域存储的是该bucket承载的所有key数据。
运行时在分配bucket时需要知道key的大小。那么运行时是如何知道key的大小的呢当我们声明一个map类型变量时比如var m map[string]intGo运行时就会为该变量对应的特定map类型生成一个runtime.maptype实例如存在则复用
// $GOROOT/src/runtime/type.go
type maptype struct {
typ _type
key *_type
elem *_type
bucket *_type // 表示hash bucket的内部类型
keysize uint8 // key的大小
elemsize uint8 // elem的大小
bucketsize uint16 // bucket的大小
flags uint32
}该实例包含了我们所需的map类型的所有元信息。前面提到过编译器会将语法层面的map操作重写成运行时对应的函数调用这些运行时函数有一个共同的特点
第一个参数都是maptype指针类型的参数。Go运行时就是利用maptype参数中的信息确定key的类型和大小的map所用的hash函数也存放在maptype.key.alg.hash(key, hmap.hash0)中。
同时maptype的存在也让Go中所有map类型共享一套运行时map操作函数而无须像C那样为每种map类型创建一套map操作函数从而减少了对最终二进制文件空间的占用。
运行该程序
$go run map_concurrent_read_and_write.go
fatal error: concurrent map iteration and map write我们会得到上述panic信息。如果仅仅是并发读则map是没有问题的。
Go 1.9版本中引入了支持并发写安全的sync.Map类型可以用来在并发读写的场景下替换掉map。另外考虑到map可以自动扩容map中数据元素的value位置可能在这一过程中发生变化因此Go不允许获取map中value的地址这个约束是在编译期间就生效的。示例 代码如下
p : m[key] // 无法获取m[key]的地址
fmt.Println(p)尽量使用cap参数创建map
从上面的自动扩容原理我们了解到如果初始创建map时没有创建足够多可以应付map使用场景的bucket那么随着插入map元素数量的增多map会频繁扩容而这一过程将降低map的访问性能。
因此如果可能的话我们最好对map使用规模做出粗略的估算并使 用cap参数对map实例进行初始化。下面是使用cap参数与不使用map参数的map写性能基准测 试及测试结果 const mapSize 10000
func BenchmarkMapInitWithoutCap(b *testing.B) {for n : 0; n b.N; n {m : make(map[int]int)for i : 0; i mapSize; i {m[i] i}}
}
func BenchmarkMapInitWithCap(b *testing.B) {for n : 0; n b.N; n {m : make(map[int]int, mapSize)for i : 0; i mapSize; i {m[i] i}
}
}可以看出使用cap参数的map实例的平均写性能是不使用cap参数的2倍。
goos: darwin
goarch: amd64
BenchmarkMapInitWithoutCap-8 2000 645946 ns/op 687188 B/op 276 allocs/op
BenchmarkMapInitWithCap-8 5000 317212 ns/op 322243 B/op 11 allocs/op
PASS
ok command-line-arguments 2.987s
和切片一样map是Go语言提供的重要数据类型也是Gopher日常编码中最常使用的类型之一。通过本条的学习我们掌握了map的基本操作和运行时实现原理并且我们在日常使
用map的场合要把握住下面几个要点
● 不要依赖map的元素遍历顺序
● map不是线程安全的不支持并发写
● 不要尝试获取map中元素value的地址
● 尽量使用cap参数创建map以提升map平均访问性能减少频繁扩容带来的不必要损耗
