golang map 底层部分理解-白红宇

部分参考链接

bucket理解

初始的bucket数量通过

// makemap implements Go map creation for make(map[k]v, hint).// If the compiler has determined that the map or the first bucket// can be created on the stack, h and/or bucket may be non-nil.// If h != nil, the map can be created directly in h.// If h.buckets != nil, bucket pointed to can be used as the first bucket.func makemap(t *maptype, hint int, h *hmap) *hmap {	mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)	if overflow || mem > maxAlloc {    	hint = 0	}	// initialize Hmap	if h == nil {    	h = new(hmap)	}	h.hash0 = fastrand()	// Find the size parameter B which will hold the requested # of elements.	// For hint < 0 overLoadFactor returns false since hint < bucketCnt.	B := uint8(0)	for overLoadFactor(hint, B) {    	B++	}	h.B = B}复制代码

即个数由传入的参数hint，通过overLoadFactor函数计算得来一个B，B决定了初始bucket数量，这些buckets以数组形式存储，每一个bucket组成如下：

一个包含8个uint8数组，对应存储的kv的key

key1key2...key8val1val2...val8

指向下一个bucket的指针

每一个map对应的maptype类型中的bucketsize的实现位于reflect包的type.go文件中，具体代码如下：

func MapOf(key, elem Type) Type {	// Make a map type. 即编译器通过这里生成了对应该map的maptype	var imap interface{} = (map[unsafe.Pointer]unsafe.Pointer)(nil)	mt := **(**mapType)(unsafe.Pointer(&imap))	mt.key = ktyp	mt.elem = etyp	mt.bucket = bucketOf(ktyp, etyp)	mt.bucketsize = uint16(mt.bucket.size)  // bucketsize 在这里赋值，其中mt.bucket的结构bucketof()见下文	ti, _ := lookupCache.LoadOrStore(ckey, &mt.rtype)	return ti.(Type)}复制代码

bucketof()定义如下（位于reflect包的type.go中）：

func bucketOf(ktyp, etyp *rtype) *rtype {	// See comment on hmap.overflow in ../runtime/map.go.	// Prepare GC data if any.	// A bucket is at most bucketSize*(1+maxKeySize+maxValSize)+2*ptrSize bytes,	// or 2072 bytes, or 259 pointer-size words, or 33 bytes of pointer bitmap.	// Note that since the key and value are known to be <= 128 bytes,	// they are guaranteed to have bitmaps instead of GC programs.	var gcdata *byte	var ptrdata uintptr	var overflowPad uintptr        // 这里即为bucketsize的最终实现，8字节的hashtop，所有的key value占用空间，可能的pad填充，指向下一个bucket的指针	size := bucketSize*(1+ktyp.size+etyp.size) + overflowPad + ptrSize	b := &rtype{	    align:   ptrSize,	    size:    size,	    kind:    kind,    	ptrdata: ptrdata,    	gcdata:  gcdata,	}	s := "bucket(" + ktyp.String() + "," + etyp.String() + ")"	b.str = resolveReflectName(newName(s, "", false))	return b}复制代码

指向下一个bucket的指针赋值方式

func (h *hmap) newoverflow(t *maptype, b *bmap) *bmap {	var ovf *bmap	if h.extra != nil && h.extra.nextOverflow != nil {    	// We have preallocated overflow buckets available.    	// See makeBucketArray for more details.    	ovf = h.extra.nextOverflow    	if ovf.overflow(t) == nil {    		// We are not at the end of the preallocated overflow buckets. Bump the pointer.    		h.extra.nextOverflow = (*bmap)(add(unsafe.Pointer(ovf), uintptr(t.bucketsize)))    	} else {    		// This is the last preallocated overflow bucket.    		// Reset the overflow pointer on this bucket,    		// which was set to a non-nil sentinel value.    		ovf.setoverflow(t, nil)    		h.extra.nextOverflow = nil    	}	} else {    	ovf = (*bmap)(newobject(t.bucket))	}	h.incrnoverflow()	if t.bucket.kind&kindNoPointers != 0 {    	h.createOverflow()    	*h.extra.overflow = append(*h.extra.overflow, ovf)	}	b.setoverflow(t, ovf) // 最终通过这里的setoverflow将新建的bucket绑定到b的后面	return ovf}func (b *bmap) setoverflow(t *maptype, ovf *bmap) {    // 减去的sys.PtrSize即为链接到后一个bucket的指针的大小，这样得到的刚好是该指针的地址	*(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-sys.PtrSize)) = ovf}// 取overflow同样的道理func (b *bmap) setoverflow(t *maptype, ovf *bmap) {	*(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-sys.PtrSize)) = ovf}复制代码

持续更新中......