[go]map基本使用和底层原理

佚名 4年前 (2020-04-15) go 560人围观抢沙发百度已收录

1、map基本使用

map声明

var m4 map[int]int  //只是声明  没有开辟空间
m4[1]=100 //报错
log.Println(m4)

创建

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

//1
m3:=make(map[int]string,100) //可以指定长度
log.Println(len(m3)) //0 键值对的数量

m2:=make(map[string]string) //使用默认长度
m2["你"] = "你好啊"
log.Println(m2)

//2
d2 :=map[string]int{"one":1, "tow":2} //初始化
d3 :=map[int]int{} //创建了空map

判断值是否存在

只接受一个的话默认返回的是value，两个的话有exists

//判断是否存在
val,exists :=d3["tow"]  //如果不存在 返回零值 exists为false

map遍历

m5:=map[string]string{"one":"1","tow":"2","three":"3"}
for k:=range m5{ //默认是key
	log.Println(k) //one tow...
}

for k,v:=range m5{ //k-v
	log.Println(k,v) //
}

删除

m5:=map[string]string{"one":"1","tow":"2","three":"3"}
delete(m5, "one")

2、map和set

go没有内置set类型，但是可以用map很轻松模仿，因为map的key是唯一的

type StrSet struct {
	data map[string]bool
	sync.RWMutex //读写锁 保证线程安全
}

func New() *StrSet {
	return &StrSet{
		data: make(map[string]bool),
	}
}

func (this *StrSet)Add(val string) {
	this.Lock()
	defer this.Unlock()
	if this.data==nil{
		this = New()
	}
	this.data[val] = true
}

func (this *StrSet)Delete(val string)  {
	this.Lock()
	defer this.Unlock()
	if this.data==nil{
		return
	}
	delete(this.data,val)
}

func (this *StrSet) IsExist(val string) bool {
	this.RLock()
	defer this.RUnlock()
	if this.data==nil{
		return false
	}

	_,ok:=this.data[val]
	return ok
}

func (this *StrSet) GetAll() (result []string)  {
	if this.data==nil{
		return
	}
	for val :=range this.data{
		result = append(result, val)
	}
	return
}

func (this *StrSet) Clear()  {
	this.Lock()
	defer this.Unlock()
	this.data = map[string]bool{}
}




func main() {
	s:=New()
	s.Add("panbin")
	s.Add("biningo")
	s.Add("a")
	s.Add("b")
	s.Add("panbin")
	log.Println(s.GetAll())
}

3、map底层结构

借鉴了如下博客。写的很好

深入Go的Map使用和实现原理

先来观摩一波map底层结构，第一眼肯定万脸懵逼

// A header for a Go map.
type hmap struct { 
	count     int  // 元素个数
	flags     uint8  
	B         uint8  //包含2^B个桶  指向bmap结构 用hash来散列k-v要到哪个桶
	noverflow uint16 //溢出的桶的个数  桶的数组可能会溢出 
    hash0     uint32 //hash种子
	
    //桶数组的指针指向bmap结构
    //bucket[0]->bucket[1]->...
    buckets    unsafe.Pointer
    
	oldbuckets unsafe.Pointer //扩容的时候用于复制的buckets数组
	nevacuate  uintptr //搬迁进度（已经搬迁的buckets数量）
	extra *mapextra  //用于扩容  如果元素过多 超过了buckets数组的范围 就要扩容
}

mapextra 用于扩容的结构体指针

type mapextra struct {
	overflow    *[]*bmap //扩容的地址
	oldoverflow *[]*bmap //用于扩容
	nextOverflow *bmap //链表链接的指针
}

bmap map存储k或v的数组，

// A bucket for a Go map.
type bmap struct {
	tophash [bucketCnt]uint8
}

map的实现过程

底层一个数组arr

index = hash(key)

arr[index] = struct{xxxx}

go map的每个arr下面存的是一个 bucket

注意，这里的value都会转化为byte类型，也就是uint8类型，key是int64类型的，每个bucket中可以存储8个kv键值对，

hash值的高八位存储在bucket中的tophash中，用来快速判断key是否存在

// A bucket for a Go map.
type bmap struct {
	tophash [bucketCnt]uint8 //bucketCnt=8 [8]uint8  这个值会动态增加
}

当每个bucket存储的kv对到达8个之后，会通过指针指向一个新的bucket，从而形成一个链表

这个指针事实上并没有显示定义，是通过指针运算进行访问的。可以想象成静态链表类型，并且k-v对也是通过指针运算得出的，tophash只是用来检查key是否存在

当往map中存储一个kv对时，通过k获取hash值，hash值的低八位和bucket数组长度取余，定位到在数组中的那个下标，hash值的高八位存储在bucket中的tophash中，用来快速判断key是否存在，key和value的具体值则通过指针运算存储，当一个bucket满时，通过overfolw指针链接到下一个bucket。

4、关于并发

map不是并发安全的

要支持并发，可以用 sync.Map，里面都是go的原子操作

sm:=sync.Map{}
sm.Store("one","1") //无返回值
sm.Store("tow","2")
sm.LoadOrStore("3","three") //取元素 如果没有就存进去 并返回值
sm.Delete("1") //无返回值
log.Println(sm.Load("1")) 
log.Println(sm)