Basic use and underlying principles of [go]map

1. map Basic Use

map declaration

var m4 map[int]int  //Just declare there is no room
m4[1]=100 //Report errors
log.Println(m4)

Establish

//1
m3:=make(map[int]string,100) //Length can be specified
log.Println(len(m3)) //Number of 0 key-value pairs

m2:=make(map[string]string) //Use default length
m2["you"] = "How do you do"
log.Println(m2)

//2
d2 :=map[string]int{"one":1, "tow":2} //Initialization
d3 :=map[int]int{} //An empty map was created

Determine whether a value exists

Accept only one word and return value by default, two words have exists

//Judging whether there is
val,exists :=d3["tow"]  //If there is no return zero exists is false

map traversal

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

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


delete

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



2. map and set

go does not have a built-in set type, but can be easily mimicked with map because map's key is unique

type StrSet struct {
	data map[string]bool
	sync.RWMutex //Read-write locks keep threads safe
}

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 Bottom Structure

Learn from the following blogs.Well written

Deep into Map Use and Implementation Principles for Go s

First look at the underlying structure of a wave of map s, and at first glance you'll be amazed_

// A header for a Go map.
type hmap struct { 
	count     int  // Number of elements
	flags     uint8  
	B         uint8  //Contains 2^B barrels pointing to bmap structure Hash to hash which barrel k-v will go to
	noverflow uint16 //Number of buckets overflowed Array of buckets may overflow 
    hash0     uint32 //hash seed
	
    //The pointer to the bmap structure of the bucket array
    //bucket[0]->bucket[1]->...
    buckets    unsafe.Pointer
    
	oldbuckets unsafe.Pointer //Bukets array used for replication when expanding capacity
	nevacuate  uintptr //Progress of the move (number of buckets already moved)
	extra *mapextra  //Used to expand if too many elements exceed the range of a buckets array
}

Mappextra Structural Pointer for Expansion

type mapextra struct {
	overflow    *[]*bmap //Expanded Address
	oldoverflow *[]*bmap //For capacity expansion
	nextOverflow *bmap //A pointer to a linked list
}

bmap map map stores an array of k or v,

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

map implementation process

A bottom array arr

index = hash(key)

arr[index] = struct{xxxx}

A bucket exists under each arr of the go map

Notice that the value here is converted to byte, which is the uint8 type, and that the key is of type int64, with eight kv key-value pairs stored in each bucket.

The high eight bits of the hash value are stored in the tophash in the bucket to quickly determine if the key exists

// A bucket for a Go map.
type bmap struct {
	tophash [bucketCnt]uint8 //bucketCnt=8 [8]uint8 This value increases dynamically
}

When each bucket's stored kv pair reaches eight, it points to a new bucket through the pointer, forming a chain table

This pointer does not actually have a display definition, it is accessed through pointer operations.You can imagine a static list type, and k-v pairs are also derived by pointer operations, tophash just checks to see if a key exists

When a kv pair is stored in a map, the hash value is obtained by k, the lower eight bits of the hash value and the length of the bucket array are balanced by k, positioned at the subscript in the array, and the higher eight bits of the hash value are stored in the tophash in the bucket to quickly determine whether the key exists or not. The specific values of the key and value are stored by pointer operations. When a bucket is full, they are linked to the next through the overfolw pointerBuckets.





4. About concurrency

map is not concurrently secure

To support concurrency, you can use sync.Map, which contains atomic operations of go

sm:=sync.Map{}
sm.Store("one","1") //No return value
sm.Store("tow","2")
sm.LoadOrStore("3","three") //Take an element and save it if it doesn't exist and return a value
sm.Delete("1") //No return value
log.Println(sm.Load("1")) 
log.Println(sm)

Keywords: Go

Added by Lirpa on Wed, 15 Apr 2020 05:20:43 +0300