Golang map实践及实现原理解析_Golang_

func main(){ fmt.Println("--------------- m ---------------") m := make(map[string]string) m["1"] = "0" fmt.Printf("m outer address %p, m=%v \n", m, m) passMap(m) fmt.Printf("post m outer address %p, m=%v \n", m, m) } func passMap(m map[string]string) { fmt.Printf("m inner address %p \n", m) m["11111111"] = "11111111" fmt.Printf("post m inner address %p \n", m) }

func main(){ fmt.Println("--------------- m2 ---------------") var m2 map[string]string//未初始化 fmt.Printf("m2 outer address %p, m=%v \n", m2, m2) passMapNotInit(m2) fmt.Printf("post m2 outer address %p, m=%v \n", m2, m2) } func passMapNotInit(m map[string]string) { fmt.Printf("inner: %v, %p\n",m, m) m = make(map[string]string, 0) m["a"]="11" fmt.Printf("inner: %v, %p\n",m, m) }

// A header for a Go map. type hmap struct { //map 中的元素个数，必须放在 struct 的第一个位置，因为内置的 len 函数会通过unsafe.Pointer会从这里读取 count int flags uint8 // bucket的数量是2^B, 最多可以放 loadFactor * 2^B 个元素，再多就要 hashGrow 了 B uint8 //overflow 的 bucket 近似数 noverflow uint16 hash0 uint32 // hash seed //2^B 大小的数组，如果 count == 0 的话，可能是 nil buckets unsafe.Pointer // 扩容的时候，buckets 长度会是 oldbuckets 的两倍,只有在 growing 时候为空。 oldbuckets unsafe.Pointer // 指示扩容进度，小于此地址的 buckets 迁移完成 nevacuate uintptr // progress counter for evacuation (buckets less than this have been evacuated) // 当 key 和 value 都可以 inline 的时候，就会用这个字段 extra *mapextra // optional fields } 

type bmap struct { // tophash generally contains the top byte of the hash value // for each key in this bucket. If tophash[0] < minTopHash, // tophash[0] is a bucket evacuation state instead. tophash [bucketCnt]uint8 // Followed by bucketCnt keys and then bucketCnt elems. // NOTE: packing all the keys together and then all the elems together makes the // code a bit more complicated than alternating key/elem/key/elem/... but it allows // us to eliminate padding which would be needed for, e.g., map[int64]int8. // Followed by an overflow pointer. } 

type bmap struct { topbits [8]uint8 keys [8]keytype values [8]valuetype pad uintptr overflow uintptr } 

// mapextra holds fields that are not present on all maps. type mapextra struct { // If both key and elem do not contain pointers and are inline, then we mark bucket // type as containing no pointers. This avoids scanning such maps. // However, bmap.overflow is a pointer. In order to keep overflow buckets // alive, we store pointers to all overflow buckets in hmap.extra.overflow and hmap.extra.oldoverflow. // overflow and oldoverflow are only used if key and elem do not contain pointers. // overflow contains overflow buckets for hmap.buckets. // oldoverflow contains overflow buckets for hmap.oldbuckets. // The indirection allows to store a pointer to the slice in hiter. overflow *[]*bmap oldoverflow *[]*bmap // nextOverflow holds a pointer to a free overflow bucket. nextOverflow *bmap } 

m := make(map[string]string) // 指定 map 长度 m := make(map[string]string, 10) 

// 这里的hint就是我们 make 时候后面指定的初始化长度. func makemap(t *maptype, hint int, h *hmap) *hmap { //......省略各种检查的逻辑 // 找到一个 B，使得 map 的装载因子在正常范围内。 B := uint8(0) for overLoadFactor(hint, B) { B++ } h.B = B // 初始化 hash table // 如果 B 等于 0，那么 buckets 就会在赋值的时候再分配 // 如果长度比较大，分配内存会花费长一点 if h.B != 0 { var nextOverflow *bmap h.buckets, nextOverflow = makeBucketArray(t, h.B, nil) if nextOverflow != nil { h.extra = new(mapextra) h.extra.nextOverflow = nextOverflow } } return h } 

// mapaccess1 returns a pointer to h[key]. Never returns nil, instead // it will return a reference to the zero object for the elem type if // the key is not in the map. func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { //......校验逻辑 //如果 h 什么都没有，返回value类型的零值 if h == nil || h.count == 0 { if t.hashMightPanic() { t.key.alg.hash(key, 0) // see issue 23734 } return unsafe.Pointer(&zeroVal[0]) } // 并发写冲突 if h.flags&hashWriting != 0 { throw("concurrent map read and map write") } // 不同类型 key 使用的 hash 算法在编译期确定 alg := t.key.alg hash := alg.hash(key, uintptr(h.hash0)) // 求低 B 位的掩码. // 比如 B=5，那 m 就是31，低五位二进制是全1 m := bucketMask(h.B) // b 就是 当前key对应的 bucket 的地址 b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize))) // oldbuckets 不为 nil，说明发生了扩容 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 } // 求出 key 在老的 map 中的 bucket 位置 oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize))) // 如果 oldb 没有搬迁到新的 bucket // 那就在老的 bucket 中寻找 if !evacuated(oldb) { b = oldb } } // 计算出高 8 位的 hash // 相当于右移 56 位，只取高8位 top := tophash(hash) // 这里进入bucket的二层循环找到对应的kv(第一层是bucket,第二层是bucket内部的8个slot) bucketloop: // 遍历bucket以及overflow链表 for ; b != nil; b = b.ov
                
提示：
                    本文由神整理自网络，如有侵权请联系本站删除！
                    

                    本站声明： 

                    1、本站所有资源均来源于互联网，不保证100%完整、不提供任何技术支持； 

                    2、本站所发布的文章以及附件仅限用于学习和研究目的;不得将用于商业或者非法用途；否则由此产生的法律后果，本站概不负责！
                
                

                

                                            
上一篇：go中import包的大坑解决方案_Golang_
                                                                
下一篇：Go语言上下文context底层原理_Golang_