深入浅出Go语言Map
Map在Go语言中一般被称为“字典”,他跟我们传统的哈希表差别并不是很大,但是也有些地方的设计和使用值得我们注意下,下面我们开始讲解~
1 使用方式
func NewMap() {
//初始化方式1
map1 := map[string]int{"A": 1, "B": 2}
//初始化方式2
map2 := make(map[string]int, 10)
//初始化方式3
map3 := new(map[string]int)
map1["C"] = 3
map2["A"] = 11
map3 = &map[string]int{"A": 111}
printMap(map1)
printMap(map2)
printMap(*map3)
}
func printMap(m map[string]int) {
i := len(m)
fmt.Println("len = ",i)
for s := range m {
fmt.Print(m[s], " ")
}
fmt.Println()
}
运行结果:
遍历Map的K,V
func TestMap(t *testing.T) {
m := map[string]int{"A": 1, "B": 2, "C": 3, "D": 4, "E": 5}
fmt.Println("First range ...")
for s := range m {
fmt.Println("key = ",s," ","val = ",m[s])
}
fmt.Println("Second range ...")
for s := range m {
fmt.Println("key = ",s," ","val = ",m[s])
}
}
运行结果:
2 原理探究
Go官网对Map的简单介绍:
-
Map是一种无序元素组,它由另一种类型的一组唯一键建立索引。未初始化映射的值为nil。
-
比较操作符==和!=必须为键类型的操作数完全定义;因此键类型不能是函数、映射或片。
-
如果键类型是接口类型,则必须为动态键值定义这些比较操作符;失败将导致panics。
-
map元素的数量称为它的长度。可以使用内置函数 len 发现它,并且在执行过程中可能会改变。
-
元素可以在执行过程中使用assignments添加,使用index expressions检索;它们可以通过delete 内置函数删除。
-
使用内置函数make 生成一个新的空map值,它接受map类型和一个可选的容量提示作为参数:
-
初始容量不限制其大小:地图会增长以适应存储在其中的项目的数量,nil地图除外。一个nil映射相当于一个空映射,除了不能添加任何元素。
回到我们这里:
根据上述的运行结果,我们很容易发现:Map每次遍历后结果的顺序是不同的
,为什么会这样?
这就要从Go语言中对Map的设计开始分析,首先看下源码${GO_PATH}/src/runtime/map.go
map数据结构:
// A header for a Go map.
type hmap struct {
count int // 元素个数
flags uint8
B uint8 // buckets(桶)的数量的对数,也就是说该哈希表中桶的数量为 2^B 个
noverflow uint16 // 溢出桶数
hash0 uint32 // 哈希种子
buckets unsafe.Pointer // 指向 buckets 数组的指针,数组大小为 2^B,如果元素个数为 0,它为 nil。
oldbuckets unsafe.Pointer // 指向老的buckets数组的指针,老的大小是新的1/2。非扩容状态为 nil。
nevacuate uintptr // 表示扩容进度,小于此地址的 buckets 代表已搬迁完成
extra *mapextra // extra 是指向 mapextra 类型的指针。
}
mapextra结构:
type mapextra struct {
// 如果 key 和 value 都不包含指针,并且可以被 inline(<=128 字节)
// 就使用 hmap 的 extr a字段来存储 overflow buckets,这样可以避免 GC 扫描整个 map
// 然而 bmap.overflow 也是个指针。随意其实 bmap.overflow 的指针也是指向了
// hmap.extra.overflow 和 hmap.extra.oldoverflow 中
// overflow 包含的是 hmap.buckets 的 overflow 的 buckets
// oldoverflow 包含扩容时的 hmap.oldbuckets 的 overflow 的 bucket
overflow *[]*bmap
oldoverflow *[]*bmap
// 指向空闲的 overflow bucket 的指针
nextOverflow *bmap
}
map结构中的bucket结构:
type bmap struct {
// Tophash通常包含散列值的顶字节对于这个bucket中的每个键。
// 如果tophash[0] < minTopHash,Tophash[0]是桶清空状态。
tophash [bucketCnt]uint8
}
遍历Key源码:
func mapaccessK(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer) {
if h == nil || h.count == 0 {
return nil, nil
}
hash := t.hasher(key, uintptr(h.hash0))
m := bucketMask(h.B)
b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + (hash&m)*uintptr(t.bucketsize)))
if c := h.oldbuckets; c != nil {
if !h.sameSizeGrow() {
// There used to be half as many buckets; mask down one more power of two.
m >>= 1
}
oldb := (*bmap)(unsafe.Pointer(uintptr(c) + (hash&m)*uintptr(t.bucketsize)))
if !evacuated(oldb) {
b = oldb
}
}
top := tophash(hash)
bucketloop:
for ; b != nil; b = b.overflow(t) {
for i := uintptr(0); i < bucketCnt; i++ {
if b.tophash[i] != top {
if b.tophash[i] == emptyRest {
break bucketloop
}
continue
}
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
if t.indirectkey() {
k = *((*unsafe.Pointer)(k))
}
if t.key.equal(key, k) {
e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
if t.indirectelem() {
e = *((*unsafe.Pointer)(e))
}
return k, e
}
}
}
return nil, nil
}
(图片链接:https://img-blog.csdnimg.cn/img_convert/a3647de3340e08b6700ce3e15cb9d30a.webp?x-oss-process=image/format,png)
由此,我们知道了为什么Map的遍历是无序的:
map 在扩容后,会发生 key 的搬迁,原来落在同一个 bucket 中的 key,搬迁后,有些 key 就要变更位置了。而遍历的过程,就是按顺序遍历 bucket,同时按顺序遍历 bucket 中的 key。搬迁后,key 的位置发生了重大的变化,有些 key 变更了bucket ,有些 key 则原地不动。这样,遍历 map 的结果就不可能按原来的顺序了。
那么Go语言中的Map是线程安全的吗?
非线程安全。但是go语言在sync包中提供了一种线程安全的map,我们下次再进行探讨
参考:
https://blog.csdn.net/weixin_42767757/article/details/112007958
https://blog.csdn.net/shunuanwei/article/details/124582949
相关文章
- 【Go命令教程】4. go get
- 如何安装 第三方 Go 离线包? (GOPATH、 go install)
- [Go] 字典(map)
- 【Go入门教程4】变量(var),常量(const),内置基础类型(Boolean、数值 byte,int,rune、字符串、错误类型),分组,iota枚举,array(数值),slice(切片),map(字典),make/new操作,零值
- 【Go语言】【13】再谈GO语言的结构体
- 使用athens部署企业内部Gitlab go mod包的Go私服代理
- [Go] go-nsq 使用指南
- 我的Go+语言初体验——go【Format】goplus
- 【Go基础】使用go语言函数
- 【Go基础】理解go语言变量
- Go语言自学系列 | golang包管理工具go module
- Go语言自学系列 | golang map
- Go语言自学系列 | go语言切片元素的添加和删除copy
- Go语言自学系列 | go语言访问数组元素
- Go语言自学系列 | go语言中的流程控制
- Map生成器 map适配器如今能够使用各种不同的Generator,iterator和常量值的组合来填充Map初始化对象
- Linux下安装Go环境
- Go语言参数校验(go-playground / validator)——基本使用
- go map数据结构和源码详解
- Go 参数传递:值、引用及指针之间的区别?