Golang——map-一一网

map数据结构

源码文件：/src/runtime/map.go
Go语言的map数据类型类似Java的HashMap，Python的Dictionary，我们可以统一称之为HashMap ；
Go语言的实现方式为哈希桶，根据key将数据分布到不同的桶中；
针对溢出和扩容情况也有对应的overflow和oldbuckets处理各自的情况。

1、哈希函数如何在map中应用的

通过哈希函数将key映射到不同的索引上

2、如何多个key经过”哈希函数“映射到一起怎么办？

如果多个key经过hash函数之后，映射到同一个索引上，称为哈希冲突

2.1、解决哈希冲突的方案

常见的解决方案是开放寻址法和拉链法

2.2、开放寻址方式

开放寻址法是一种在哈希表中解决哈希冲突的方法，这种方法的核心思想是依次探测和比较数组中的元素以判断目标键值对是否存在于哈希表中，如果我们使用开放寻址法来实现哈希表，那么实现哈希表底层的数据结构就是数组

开放寻址法中对性能影响最大的是”装载因子“，
装载因子：数组中元素的数量/数组大小；
随着装载因子的增加，探测的平均用时就会逐渐增加，也就会影响哈希表的读写性能。

2.3、拉链法

这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。
链地址法适用于经常进行插入和删除的情况。

2.4、拉链法和开放地址法比较

拉链法	开放寻址发
实现简单	实现复杂
需要额外空间存储链表的指针	直接存储具体的值，通过索引探测
链表上的节点空间是动态申请的，适合无法定长的场景
删除方便，只需要前后节点

3、数据结构

// 文件地址：go/src/runtime/map.go
type hmap struct {
        // 表示当前哈希表中的元素数量
	count     int // # live cells == size of map.  Must be first (used by len() builtin)
        // 标记读写状态，主要是做竞态检测，避免并发读写
	flags     uint8
        // 表示当前哈希表持有的buckets数量 len(buckets) == 2^B
	B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
        // 溢出的bucket个数
	noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
        // 哈希的种子，为哈希函数的结果引入随机性，在创建map是确定
	hash0     uint32 // hash seed
        // 指向数组buckets的指针
	buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
        // 哈希在扩容时用于保存之前buckets的字段
	oldbuckets unsafe.Pointer // 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
}
复制代码

每个bmap结构中定义一个是[8]uint8类型的数组，表示能够存储8个键值对，tophash存储了键哈希值的高8位

// 文件地址：go/src/runtime/map.go
// 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.
}

// 文件地址：src/cmd/compile/internal/reflectdata/reflect.go
通过MapBucketType()函数推断bucket中含有的元素
type XXX strcut{
    topbits  [8]uint8
    keys     [8]keytype
    elems    [8]elemtype
    overflow uintptr
}
复制代码

定义bmap中数组的容量

// 文件地址：go/src/runtime/map.go
const (
	// Maximum number of key/elem pairs a bucket can hold.
	bucketCntBits = 3
	bucketCnt     = 1 << bucketCntBits
        ...
)
复制代码

4、map初始化

创建map的函数

// 文件地址：go/src/runtime/map.go
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

	// allocate initial hash table
	// if B == 0, the buckets field is allocated lazily later (in mapassign)
	// If hint is large zeroing this memory could take a while.
	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
		}
	}

	return h
}
复制代码

4.1、获取一个随机的哈希种子

h.hash0 = fastrand()
复制代码

4.2、寻找合适的桶的数量

1、如果map中元素不超过8个，一个桶可以放下
2、如果数量超过8个，根据最大负载因子6.5，找到一个合适的B，满足2^B*13/2>count

// 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)
}
复制代码

4.3、分配一块连续的空间用于存储数据

根据makemap函数调用看makeBucketArray()函数返回值分别赋予了hmap.buckets和h.extra.nextOverflow 我们能确定在正常情况下，正常桶和溢出桶在内存中的存储空间是连续的，只是被hmap中的不同字段引用。

func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
	base := bucketShift(b)
	nbuckets := base
	if 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 {
		buckets = dirtyalloc
		size := t.bucket.size * nbuckets
		if t.bucket.ptrdata != 0 {
			memclrHasPointers(buckets, size)
		} else {
			memclrNoHeapPointers(buckets, size)
		}
	}

	if base != nbuckets {
		nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))
		last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))
		last.setoverflow(t, (*bmap)(buckets))
	}
	return buckets, nextOverflow
}
复制代码

5、访问

a := m[key], 其实现原型为mapaccess1()，返回一个值
a, ok := m[key], 返回两个值，其实现原型为mapaccess2()

5.1、确定key所在的桶

hash := t.hasher(key, uintptr(h.hash0))
m := bucketMask(h.B)
b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
复制代码

5.2、如果map正在扩容时从oldoverflow中找key所在的桶

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
    }
}
复制代码

5.3 、如果bmap中不存在则查找溢出桶

bucketloop:
	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 bucketloop
				}
				continue
			}
复制代码

5.4 遍历为何是乱序的？

Go语言针对map的遍历主要是使用mapiterinit()和mapiternext()
在开始遍历的时候，会调用fastrand()函数生成一个随机数，随机找到一个遍历桶的开始位置。

// decide where to start
r := uintptr(fastrand())
if h.B > 31-bucketCntBits {
    r += uintptr(fastrand()) << 31
}
it.startBucket = r & bucketMask(h.B)
it.offset = uint8(r >> h.B & (bucketCnt - 1))

// iterator state
it.bucket = it.startBucket
复制代码

6、赋值

m[a] = v1
m[b] = v2
在mapassign() 中，会完成已存在键则覆盖，未存在键则插入的过程；
赋值过程也是先根据key计算出哈希找到对应的桶。

6.1 桶溢出

当map进行插入新值时，可能会出现桶溢出（bucket overflow）和扩容（grow）现象；

if inserti == nil {
    // The current bucket and all the overflow buckets connected to it are full, allocate a new one.
    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)
复制代码

6.2 扩容

如果插入时出现以下两种情况会引发扩容：

装载因子已经超过 6.5；
哈希使用了太多溢出桶；

// If we hit the max load factor or we have too many overflow buckets,
// and we're not already in the middle of growing, start growing.
if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
    hashGrow(t, h)
    goto again // Growing the table invalidates everything, so try again
}
复制代码

总结

Go语言使用拉链法来解决哈希碰撞的问题实现了哈希表，它的访问、写入和删除等操作都在编译期间转换成了运行时的函数或者方法。
map是Go语言中很常见的数据类型，我们通过阅读源码可以很好的避免一些错误的用法，也能了解一些原理，比如为什么tophash选取key哈希值的前八位？遍历为何是乱序的？为什么存储指针类型的元素会影响GC？这些问题都可以在/src/runtime/map.go 文件中找到答案。