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

1、map基本使用

map宣告

var m4 map[int]int  //只是宣告  沒有開辟空間
m4[1]=100 //報錯
log.Println(m4)

創建

//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=https://www.cnblogs.com/biningooginind/p/=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)

標籤：Go

上一篇：一文讀懂goroutine和channel

下一篇：[Go] 使用go mod進行依賴管理