1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func fastrand() uint32 {
	mp := getg().m
	// Implement xorshift64+: 2 32-bit xorshift sequences added together.
	// Shift triplet [17,7,16] was calculated as indicated in Marsaglia's
	// Xorshift paper: https://www.jstatsoft.org/article/view/v008i14/xorshift.pdf
	// This generator passes the SmallCrush suite, part of TestU01 framework:
	// http://simul.iro.umontreal.ca/testu01/tu01.html
	s1, s0 := mp.fastrand[0], mp.fastrand[1]
	s1 ^= s1 << 17
	s1 = s1 ^ s0 ^ s1>>7 ^ s0>>16
	mp.fastrand[0], mp.fastrand[1] = s0, s1
	return s0 + s1
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

// A header for a Go map.
type hmap struct {
	// Note: the format of the hmap is also encoded in cmd/compile/internal/gc/reflect.go.
	// Make sure this stays in sync with the compiler's definition.
	count     int //长度 # live cells == size of map.  Must be first (used by len() builtin)
	flags     uint8
	B         uint8  // buckets数量为2^B log_2 of # of buckets (can hold up to loadFactor * 2^B items)
	noverflow uint16 //溢出桶数量近似值。 approximate number of overflow buckets; see incrnoverflow for details
	hash0     uint32 // hash种子 hash seed

	buckets    unsafe.Pointer //长度为2^B的buckets数组 array of 2^B Buckets. may be nil if count==0.
	oldbuckets unsafe.Pointer //前一个桶数组，大小是现在的一半，只有在扩容过程中才不为nil  previous bucket array of half the size, non-nil only when growing
	nevacuate  uintptr        // 下一个要迁移桶的编号（顺序迁移）（小于此值的桶已被迁移） progress counter for evacuation (buckets less than this have been evacuated)

	extra *mapextra // optional fields
}
// 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 //下一个未使用的空桶
}

	// flags
	iterator     = 1 // there may be an iterator using buckets
	oldIterator  = 2 // there may be an iterator using oldbuckets
	hashWriting  = 4 // a goroutine is writing to the map
	sameSizeGrow = 8 // the current map growth is to a new map of the same size

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

// A bucket for a Go map.
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 {
    tophash  [8]uint8
    keys     [8]keytype
    values   [8]valuetype
    pad      uintptr
    overflow uintptr
}
	emptyRest      = 0 // this cell is empty, and there are no more non-empty cells at higher indexes or overflows.
	emptyOne       = 1 // this cell is empty
	evacuatedX     = 2 // key/elem is valid.  Entry has been evacuated to first half of larger table.
	evacuatedY     = 3 // same as above, but evacuated to second half of larger table.
	evacuatedEmpty = 4 // cell is empty, bucket is evacuated.
	minTopHash     = 5 // minimum tophash for a normal filled cell.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

// A hash iteration structure.
// If you modify hiter, also change cmd/compile/internal/gc/reflect.go to indicate
// the layout of this structure.
type hiter struct {
	key         unsafe.Pointer // 每次迭代结果的key Must be in first position.  Write nil to indicate iteration end (see cmd/compile/internal/gc/range.go).
	elem        unsafe.Pointer // 每次迭代结果的value Must be in second position (see cmd/compile/internal/gc/range.go).
	t           *maptype // map的类型
	h           *hmap   // map指针
	buckets     unsafe.Pointer // 初始化是指向的桶指针，bucket ptr at hash_iter initialization time
	bptr        *bmap          // 遍历当前桶，current bucket
	overflow    *[]*bmap       // 当前map溢出桶， keeps overflow buckets of hmap.buckets alive
	oldoverflow *[]*bmap       // 扩容之前map溢出桶， keeps overflow buckets of hmap.oldbuckets alive
	startBucket uintptr        // 开始桶偏移量，从这个桶开始遍历的， bucket iteration started at
	offset      uint8          // 桶内偏移量，表示第几个（key，value），intra-bucket offset to start from during iteration (should be big enough to hold bucketCnt-1)
	wrapped     bool           // 尾部已经遍历完成，开始折返从头开始遍历，already wrapped around from end of bucket array to beginning
	B           uint8          // h.B
	i           uint8          // 当前桶已经遍历数目，i=8时，bptr指向下一个
	bucket      uintptr        // 当前hash桶偏移量
	checkBucket uintptr        // 不为 noCheck(1<<(8*sys.PtrSize) - 1)的话，表示当前桶还没有搬迁到新 map，需要对旧桶检查跳过迁移到新扩容的hash桶的元素
}

1
2
3
4
5

hash := map[string]int{
	"1": 2,
	"3": 4,
	"5": 6,
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func maplit(n *Node, m *Node, init *Nodes) {
	a := nod(OMAKE, nil, nil)
	a.Esc = n.Esc
	a.List.Set2(typenod(n.Type), nodintconst(int64(n.List.Len())))
	litas(m, a, init)

	entries := n.List.Slice()
	if len(entries) > 25 {
	//	...
		return
	}
	// Build list of var[c] = expr.
	// Use temporaries so that mapassign1 can have addressable key, elem.
	// ...
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

for ; i < bucketCnt; i++ {
		offi := (i + it.offset) & (bucketCnt - 1) //offset开始遍历
		it.bucket = bucket
		if it.bptr != b { // avoid unnecessary write barrier; see issue 14921
			it.bptr = b
		}
		it.i = i + 1
		it.checkBucket = checkBucket
		return
	}