Golang 切片Map源码走读

type hmap struct {
    count           int              // 元素个数，调用len(map)时，直接返回此值
    flags           uint8            // map 状态标识，可以标识出 map 是否被 goroutine 并发读写；
    B               uint8            // buckets 数组的大小的对数 log_2
    noverflow       uint             // map 中溢出桶的数量；
    hash0           uint32           // 计算key的哈希时会传入哈希函数
    buckets         unsafe.Pointer   // 指向buckets数组，大小为2^B; 如果元素个数为0， 就为nil
    oldbuckets      unsafe.Pointer   // 扩容时，bucket长度时oldbuckets的两倍
    nevacuate       uintptr          // 指示扩容进度，小于此地址的buckets完成迁移
    extra           *mapextra       // 预申请的溢出桶.
}

// bmap 就是 map 中的桶，可以存储 8 组 key-value 对的数据，以及一个指向下一个溢出桶的指针；
type bmap struct {
	tophash [8]uint8 // 存储key的哈希值的高八位
	data    []byte  //  存储key-value对: key/key/key/.../value/value/value/...
	overflow *bmap  // 溢出bucket的地址
}

func makemap(t *maptype, hint int, h *hmap) *hmap {
	// 检查bucket个数乘以bucket大小，看是否超出了内存申请的限制
	mem, overflow := math.MulUintptr(uintptr(hint), t.Bucket.Size_)
	if overflow || mem > maxAlloc {
		// 如果超限，会将 hint 置为零；
		hint = 0
	}

	// initialize Hmap
	if h == nil {
		h = new(hmap)
	}
	h.hash0 = fastrand()

	// 找到一个B，使得map的装载因子在正常范围内，计算桶数组的容量 B；
	B := uint8(0)
	for overLoadFactor(hint, B) {
		B++
	}
	h.B = B

    // 初始化hash table；如果B等于0，那么buckets就会在赋值的时候再分配。（lazy模式）
	// 如果长度比较大，清理内存花费的时间就会长一些。
	if h.B != 0 {
		var nextOverflow *bmap
		// 调用 makeBucketArray 方法，初始化桶数组 hmap.buckets；
		h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
		if nextOverflow != nil {
			// 倘若 map 容量较大，会提前申请一批溢出桶 hmap.extra.
			h.extra = new(mapextra)
			h.extra.nextOverflow = nextOverflow
		}
	}

	return h
}

const (
    loadFactorNum = 13
    loadFactorDen = 2
    goarch.PtrSize = 8
    bucketCnt = 8 // abi.MapBucketCount
)

// overLoadFactor reports whether count items placed in 1<<B buckets is over loadFactor.
func overLoadFactor(count int, B uint8) bool {
    return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}

func bucketShift(b uint8) uintptr {
    return uintptr(1) << (b & (goarch.PtrSize*8 - 1))
}

func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
	base := bucketShift(b)
	nbuckets := base
	//  map 的桶数组申请内存，在桶数组的指数 b >= 4时（桶数组的容量 >= 52 ），会需要提前创建溢出桶.
	if b >= 4 {
		// 通过 base 记录桶数组的长度，不包含溢出桶；通过 nbuckets 记录累加上溢出桶后，桶数组的总长度.
		nbuckets += bucketShift(b - 4)
		sz := t.Bucket.Size_ * nbuckets
		up := roundupsize(sz)
		if up != sz {
			nbuckets = up / t.Bucket.Size_
		}
	}
    // 如果 dirtyalloc 为空，将分配一个新的后备数组。
	// 否则 dirtyalloc 将被清除并作为后备数组重新使用。
	if dirtyalloc == nil {
		// 调用 newarray 方法为桶数组申请内存空间，连带着需要初始化的溢出桶：
		buckets = newarray(t.Bucket, int(nbuckets))
	} else {
		buckets = dirtyalloc
		size := t.Bucket.Size_ * nbuckets
		if t.Bucket.PtrBytes != 0 {
			memclrHasPointers(buckets, size)
		} else {
			memclrNoHeapPointers(buckets, size)
		}
	}

	if base != nbuckets {
		// 倘若 base != nbuckets，说明需要创建溢出桶，会基于地址偏移的方式，通过 nextOverflow 指向首个溢出桶的地址.
		nextOverflow = (*bmap)(add(buckets, base*uintptr(t.BucketSize)))
		last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.BucketSize)))
		// 倘若需要创建溢出桶，会在将最后一个溢出桶的 overflow 指针指向 buckets 数组，以此来标识申请的溢出桶已经用完.
		last.setoverflow(t, (*bmap)(buckets))
	}
	return buckets, nextOverflow
}