映射 #

// A header for a Go map.
type hmap struct {
	count     int //  元素个数，用于len函数返回map元素数量
	flags     uint8 // 标志位，标志当前map正在写等状态
	B         uint8  // buckets个数的对数，即桶数量 = 2 ^ B
	noverflow uint16 // overflow桶数量的近似值，overflow桶即溢出桶，即链表法中存在链表上的桶的个数
	hash0     uint32 // 随机数种子，用于计算key的哈希值

	buckets    unsafe.Pointer // 指向buckets数组，如果元素个数为0时，该值为nil
	oldbuckets unsafe.Pointer // 扩容时指向旧的buckets
	nevacuate  uintptr        // 用于指示迁移进度，小于此值的桶已经迁移完成
	
	extra *mapextra // 额外记录overflow桶信息
}

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

type bmap struct{
	tophash [8]uint8
	keys [8]keytype // keytype 由编译器编译时候确定
	values [8]elemtype // elemtype 由编译器编译时候确定
	overflow uintptr // overflow指向下一个bmap，overflow是uintptr而不是*bmap类型，是为了减少gc
}

func tophash(hash uintptr) uint8 {
	top := uint8(hash >> (sys.PtrSize*8 - 8))
	if top < minTopHash {
		top += minTopHash
	}
	return top
}

emptyRest      = 0 // 表明此桶单元为空，且更高索引的单元也是空
emptyOne       = 1 // 表明此桶单元为空
evacuatedX     = 2 // 用于表示扩容迁移到新桶前半段区间
evacuatedY     = 3 // 用于表示扩容迁移到新桶后半段区间
evacuatedEmpty = 4 // 用于表示此单元已迁移
minTopHash     = 5 // key的tophash值与桶状态值分割线值，小于此值的一定代表着桶单元的状态，大于此值的一定是key对应的tophash值

// mapextra holds fields that are not present on all maps.
type mapextra struct {
	overflow    *[]*bmap // 指向overflow桶指针组成的切片，防止这些溢出桶被gc了
	oldoverflow *[]*bmap // 扩容时候，指向旧的溢出桶组成的切片，防止这些溢出桶被gc了

	//指向下一个可用的overflow 桶
	nextOverflow *bmap
}

func makemap_small() *hmap {
	h := new(hmap)
	h.hash0 = fastrand()
	return h
}

func makemap(t *maptype, hint int, h *hmap) *hmap {
	mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
	if overflow || mem > maxAlloc { // 检查所有桶占用的内存是否大于内存限制
		hint = 0
	}

	// h不nil，说明map结构已经创建在栈上了，这个操作由编译器处理的
	if h == nil { // h为nil，则需要创建一个hmap类型
		h = new(hmap)
	}
	h.hash0 = fastrand() // 设置map的随机数种子

	B := uint8(0)
	for overLoadFactor(hint, B) { // 设置合适B的值
		B++
	}
	h.B = B

	// 如果B == 0，那么map的buckets，将会惰性分配（allocated lazily），使用时候再分配
	// 如果B != 0时，初始化桶
	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 // extra.nextOverflow指向下一个可用溢出桶位置
		}
	}

	return h
}

func overLoadFactor(count int, B uint8) bool {
	// count > bucketCnt，bucketCnt值是8，每一个桶可以存放8个key-value，如果map中元素个数count小于8那么一定不会超过加载因子

	// loadFactorNum和loadFactorDen的值分别是13和2，bucketShift(B)等效于1<<B
	// 所以 uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen) 等于  uintptr(count) > 6.5 * 2^ B
	return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}

// bucketShift returns 1<<b, optimized for code generation.
func bucketShift(b uint8) uintptr {
	return uintptr(1) << (b & (sys.PtrSize*8 - 1))
}

func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
	base := bucketShift(b) // 等效于 base := 1 << b
	nbuckets := base

	if b >= 4 { // 对于小b，不太可能出现溢出桶，所以B超过4时候，才考虑提前分配写溢出桶
		nbuckets += bucketShift(b - 4)
		sz := t.bucket.size * nbuckets
		up := roundupsize(sz)
		if up != sz {
			nbuckets = up / t.bucket.size
		}
	}

	if dirtyalloc == nil {
		buckets = newarray(t.bucket, int(nbuckets))
	} else {
		// 若dirtyalloc不为nil时，
		// dirtyalloc指向的之前已经使用完的map的buckets，之前已使用完的map和当前map具有相同类型的t和b，这样它buckets可以拿来复用
		// 此时只需对dirtyalloc进行清除操作就可以作为当前map的buckets
		buckets = dirtyalloc
		size := t.bucket.size * nbuckets
		// 下面是清空dirtyalloc操作
		if t.bucket.ptrdata != 0 { // map中key或value是指针类型
			memclrHasPointers(buckets, size)
		} else {
			memclrNoHeapPointers(buckets, size)
		}
	}

	if base != nbuckets { // 多创建一些溢出桶
		nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))
		// 溢出桶的最后一个的overflow字段指向buckets
		last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))
		last.setoverflow(t, (*bmap)(buckets))
	}
	return buckets, nextOverflow
}

v := a["x"]

v, ok := a["x"]

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
	if h == nil || h.count == 0 { // map为nil或者map中元素个数为0，则直接返回零值
		if t.hashMightPanic() {
			t.hasher(key, 0) // see issue 23734
		}
		return unsafe.Pointer(&zeroVal[0])
	}
	if h.flags&hashWriting != 0 { // 有其他Goroutine正在写map，则直接panic
		throw("concurrent map read and map write")
	}
	hash := t.hasher(key, uintptr(h.hash0)) // 计算出key的hash值
	m := bucketMask(h.B) // m = 2^h.B - 1
	b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize))) // 根据上面介绍的取余操作转换成位与操作来获取key所在的桶
	if c := h.oldbuckets; c != nil { // 如果oldbuckets不为0，说明该map正在处于扩容过程中
		if !h.sameSizeGrow() { // 如果不是等容量扩容，此时buckets大小是oldbuckets的两倍，那么m需减半，然后用来定位key在旧桶中位置
			m >>= 1
		}
		oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize))) // 获取key在旧桶的桶
		if !evacuated(oldb) { // 如果旧桶数据没有迁移新桶里面，那就在旧桶里面找
			b = oldb
		}
	}
	top := tophash(hash) // 计算出key的tophash
bucketloop:
	for ; b != nil; b = b.overflow(t) { // for循环实现功能是先从当前桶找，若未找到则当前桶的溢出桶b.overfolw(t)查找，直到溢出桶为nil
		for i := uintptr(0); i < bucketCnt; i++ { // 每个桶有8个单元，循环这8个单元，一个个找
			if b.tophash[i] != top { // 如果当前单元的tophash与key的tophash不一致，
				if b.tophash[i] == emptyRest { // 若单元tophash值是emptyRest，则直接跳出整个大循环，emptyRest表明当前单元和更高单元存储都为空，所以无需在继续查找下去了
					break bucketloop
				}
				continue // 继续查找桶其他的单元
			}

			// 此时已找到tophash等于key的tophash的桶单元，此时i记录这桶单元编号
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) // dataOffset是bmap.keys相对于bmap的偏移，k记录key存在bmap的位置
			if t.indirectkey() { // 若key是指针类型
				k = *((*unsafe.Pointer)(k))
			}
			if t.key.equal(key, k) {// 如果key和存放bmap里面的key相等则获取对应value值返回
				// value在bmap中的位置 = bmap.keys相对于bmap的偏移 + 8个key占用的空间(8 * keysize) + 该value在bmap.values中偏移(i * t.elemsize)
				e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
				if t.indirectelem() {
					e = *((*unsafe.Pointer)(e))
				}
				return e
			}
		}
	}
	return unsafe.Pointer(&zeroVal[0])
}

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
	if h == nil { // 对于nil map赋值操作直接panic。需要注意的是访问nil map返回的是value类型的零值
		panic(plainError("assignment to entry in nil map"))
	}
	if h.flags&hashWriting != 0 { // 有其他Goroutine正在写操作，则直接panic
		throw("concurrent map writes")
	}
	hash := t.hasher(key, uintptr(h.hash0)) // 计算出key的hash值
	h.flags ^= hashWriting // 将写标志位置为1

	if h.buckets == nil { // 惰性创建buckets，make创建map时候，并未初始buckets，等到mapassign时候在创建初始化
		h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
	}

again:
	bucket := hash & bucketMask(h.B) // bucket := hash & (2^h.B - 1)
	if h.growing() { // 如果当前map处于扩容过程中，则先进行扩容，将key所对应的旧桶先迁移过来
		growWork(t, h, bucket)
	}
	b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize))) // 获取key所在的桶
	top := tophash(hash) // 计算出key的tophash

	var inserti *uint8 // 指向key的tophash应该存放的位置，即bmap.tophash这个数组中某个位置
	var insertk unsafe.Pointer // 指向key应该存放的位置，即bmap.keys这个数组中某个位置
	var elem unsafe.Pointer // 指向value应该存放的位置，即bmap.values这个数组中某个位置
bucketloop:
	for {
		for i := uintptr(0); i < bucketCnt; i++ {
			if b.tophash[i] != top {
				if isEmpty(b.tophash[i]) && inserti == nil { // 当i单元的tophash值为空，那么说明该单元可以用来存放key-value。
					// 再加上inserti == nil条件就是inserti只找到第一个空闲的单元即可
					inserti = &b.tophash[i]
					insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
					elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
				}
				if b.tophash[i] == emptyRest { // 如果i单元的tophash值为emptyRest，那么剩下单元也不用继续找了，剩下单元一定都是空的
					break bucketloop
				}
				continue
			}

			// 上面代码是先找到第一个为空的桶单元，然后把该桶单元相关的tophash、key、value等位置信息记录在inserti，insertk，elem临时变量上。
			// 这样当key没有在map中情况下，可以拿inserti，insertk，elem这变量，将该key的信息写入到桶单元中，这种情况下key是一个新key，这种赋值操作属于新增操作。

			// 下面代码部分就是处理中map已存在key的情况，这时候，我们只需要找到key所在桶单元中value的位置，然后把value新值写入即可。
			// 这种情况下key是一个旧key，这种赋值操作属于更新操作。
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
			if t.indirectkey() {
				k = *((*unsafe.Pointer)(k))
			}
			if !t.key.equal(key, k) {
				continue
			}
			
			if t.needkeyupdate() {
				typedmemmove(t.key, k, key)
			}
			elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
			goto done
		}
		ovf := b.overflow(t) // 当前桶没有找到，继续在其溢出桶里面找，
		if ovf == nil { // 直到都没有找到，那么跳出循环，不在找了。
			break
		}
		b = ovf
	}

	// 当map未扩容中，那么就判断当前map是否需要扩容，扩容条件是以下两个条件符合任意之一即可：
	// 1. 是否达到负载因子的阈值6.5
	// 2. 溢出桶是否过多
	if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
		hashGrow(t, h)
		goto again // 跳到again标签处，再来一遍
	}

	// 如果上面两层for循环都没有找到空的桶单元，那说明所有桶单元都写满了，那么就得创建一个溢出桶了。
	// 然后将数据存放到该溢出桶的第一个单元上
	if inserti == nil {
		newb := h.newoverflow(t, b) // 创建一个溢出桶
		inserti = &newb.tophash[0]
		insertk = add(unsafe.Pointer(newb), dataOffset)
		elem = add(insertk, bucketCnt*uintptr(t.keysize))
	}

	// store new key/elem at insert position
	if t.indirectkey() {
		kmem := newobject(t.key)
		*(*unsafe.Pointer)(insertk) = kmem
		insertk = kmem
	}
	if t.indirectelem() {
		vmem := newobject(t.elem)
		*(*unsafe.Pointer)(elem) = vmem
	}
	typedmemmove(t.key, insertk, key)
	*inserti = top // 写入key的tophash值
	h.count++ // 更新map的元素计数

done:
	if h.flags&hashWriting == 0 {
		throw("concurrent map writes")
	}
	h.flags &^= hashWriting // 将map的写标志置为0，那么其他Gorountine可以进行写入操作了
	if t.indirectelem() {
		elem = *((*unsafe.Pointer)(elem))
	}
	return elem
}

func (h *hmap) newoverflow(t *maptype, b *bmap) *bmap {
	var ovf *bmap
	if h.extra != nil && h.extra.nextOverflow != nil {
		ovf = h.extra.nextOverflow // 从上面分析映射的创建过程代码中，我们知道创建map的buckets时候，有时候会顺便创建一些溢出桶，
		// h.extra.nextOverflow就是指向这些溢出桶
		if ovf.overflow(t) == nil { // ovf不是最后一个溢出桶
			h.extra.nextOverflow = (*bmap)(add(unsafe.Pointer(ovf), uintptr(t.bucketsize))) // extra.nextOverflow指向下一个溢出桶
		} else { // ovf是最后一个溢出桶
			ovf.setoverflow(t, nil) // 将ovf.overflow设置nil
			h.extra.nextOverflow = nil
		}
	} else {
		// 没有可用的预分配的溢出桶，则创建一个溢出桶
		ovf = (*bmap)(newobject(t.bucket))
	}
	h.incrnoverflow() // 更新溢出桶计数，这个溢出桶计数可用来是否进行rehash的依据
	if t.bucket.ptrdata == 0 { // 如果map中的key和value都不是指针类型，那么将溢出桶指针添加到extra.overflow这个切片中
		h.createOverflow()
		*h.extra.overflow = append(*h.extra.overflow, ovf)
	}
	b.setoverflow(t, ovf)
	return ovf
}

func (h *hmap) createOverflow() {
	if h.extra == nil {
		h.extra = new(mapextra)
	}
	if h.extra.overflow == nil {
		h.extra.overflow = new([]*bmap)
	}
}

func (b *bmap) overflow(t *maptype) *bmap {
	return *(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-sys.PtrSize))
}

func (b *bmap) setoverflow(t *maptype, ovf *bmap) {
	*(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-sys.PtrSize)) = ovf
}

func (h *hmap) incrnoverflow() {
	if h.B < 16 {
		h.noverflow++
		return
	}
	
	// 当h.B大于等于16时候，有1/(1<<(h.B-15))的概率会更新h.noverflow
	// 比如h.B == 18时，mask==7，那么fastrand & 7 == 0的概率就是1/8
	mask := uint32(1)<<(h.B-15) - 1
	if fastrand()&mask == 0 {
		h.noverflow++
	}
}

func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
	if h == nil || h.count == 0 { // 对nil map或者数量为0的map进行删除
		if t.hashMightPanic() {
			t.hasher(key, 0) // see issue 23734
		}
		return
	}
	if h.flags&hashWriting != 0 { // 有其他Goroutine正在写操作，则直接panic
		throw("concurrent map writes")
	}

	hash := t.hasher(key, uintptr(h.hash0))
	h.flags ^= hashWriting // 将写标志置为1，删除操作也是一种写操作

	bucket := hash & bucketMask(h.B)
	if h.growing() {
		growWork(t, h, bucket)
	}
	b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
	bOrig := b
	top := tophash(hash)
search:
	for ; b != nil; b = b.overflow(t) {
		for i := uintptr(0); i < bucketCnt; i++ {
			if b.tophash[i] != top {
				if b.tophash[i] == emptyRest {
					break search
				}
				continue
			}
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
			k2 := k
			if t.indirectkey() {
				k2 = *((*unsafe.Pointer)(k2))
			}
			if !t.key.equal(key, k2) {
				continue
			}
			
			// 清空key
			if t.indirectkey() {
				*(*unsafe.Pointer)(k) = nil
			} else if t.key.ptrdata != 0 {
				memclrHasPointers(k, t.key.size)
			}
			// 清空value
			e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
			if t.indirectelem() {
				*(*unsafe.Pointer)(e) = nil
			} else if t.elem.ptrdata != 0 {
				memclrHasPointers(e, t.elem.size)
			} else {
				memclrNoHeapPointers(e, t.elem.size)
			}
			b.tophash[i] = emptyOne // 将tophash置为emptyOne
			
			// 下面代码是将当前单元附近的emptyOne状态的单元都改成emptyRest状态
			if i == bucketCnt-1 {
				if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {
					goto notLast
				}
			} else {
				if b.tophash[i+1] != emptyRest {
					goto notLast
				}
			}
			for {
				b.tophash[i] = emptyRest
				if i == 0 {
					if b == bOrig {
						break
					}
					c := b
					for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {
					}
					i = bucketCnt - 1
				} else {
					i--
				}
				if b.tophash[i] != emptyOne {
					break
				}
			}
		notLast:
			h.count--
			break search
		}
	}

	if h.flags&hashWriting == 0 {
		throw("concurrent map writes")
	}
	h.flags &^= hashWriting
}

func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
	if B > 15 {
		B = 15
	}
	return noverflow >= uint16(1)<<(B&15)
}

func overLoadFactor(count int, B uint8) bool {
	return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}