Golang中的map实现

type hmap struct {
	count     int // 键值对个数
	flags     uint8
	B         uint8  // 2^B = 桶数量
	noverflow uint16 // 溢出桶的个数
	hash0     uint32 // hash seed

	buckets    unsafe.Pointer // 哈希桶
	oldbuckets unsafe.Pointer // 原哈希桶，扩容时为非空
	nevacuate  uintptr        // 扩容进度，地址小于它的桶已被迁移了

	extra *mapextra // optional fields
}

type bmap struct {
	// tophash数组可以看做键值对的索引
	tophash [bucketCnt]uint8
	// 实际上编译器会动态添加下述属性
  // keys     [8]keytype
  // values   [8]valuetype
  // padding  uinptr
  // overflow uinptr
}

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
	...
	alg := t.key.alg
	hash := alg.hash(key, uintptr(h.hash0))
	m := bucketMask(h.B)
	// 计算得到桶的位置bucket-k
	b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
  // 若正在扩容，老buckets则为非空
	// 若bucket-k在老的buckets数组中，未被迁移，则使用老的
	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
		}
		oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
		if !evacuated(oldb) {
			b = oldb
		}
	}
	// 根据tophash(hash), 在bucket-k中的tophash中查找key
	top := tophash(hash)
  // 找到对应的bucket后，遍历查找对应的key/value
bucketloop:
	for ; b != nil; b = b.overflow(t) {
		for i := uintptr(0); i < bucketCnt; i++ {
			...
			// 计算第i个位置的key的地址
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
			if t.indirectkey() {
				k = *((*unsafe.Pointer)(k))
			}
			// 比较tophash[i]上的k是否与目标key相等
			if alg.equal(key, k) {
        // 计算value的地址
				v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
				if t.indirectvalue() {
					v = *((*unsafe.Pointer)(v))
				}
				return v
			}
		}
	}
	// 若最终还是没找到，则返回nil
	return unsafe.Pointer(&zeroVal[0])
}