深入了解Golang的map增量扩容

目录
  • 核心思想
  • 扩容方式
  • 源码分析

核心思想

以空间换时间,访问速度与填充因子有关

扩容hash表的时候每次都增大2倍,hash表大小始终为2的整数倍,有(hash mod 2^B) == (hash & (2^B-1)),方便于简化运算,避免取余操作

扩容前后的 hash mod 容量大小 是不等的,因此要重新计算每一项在hash表中的位置,扩容后需要将old pair重新hash到新的hash表上(就是一个evacuate的过程)。这个过程不是一次性完成的,在每次insert、remove的时候会搬移1-2个pair。就是使用的是增量扩容

每个旧桶的键值对都会分流到2个不同的新桶中

为什么要使用增量扩容?

主要是缩短map容器的响应时间。如果不用增量扩容,当一个map存储很多元素后进行扩容,会阻塞很长时间无法响应请求。增量扩容的本质其实就是将总的扩容时间分摊到了每一次hash操作上

在搬数据的时候,并不会把旧的bucket从oldbucket中删除,只是加上了一个已删除的标记

扩容期间一部分数据在oldbucket中,一部分在bucket中,会对hash表的insert,remove,lookup操作的处理逻辑产生影响,如耗时更长等

只有当oldbucket中所有bucket移动到新表后,才会将oldbucket释放掉

扩容方式

如果grow的太频繁,空间的利用率就会很低如果很久才grow,会形成很多的overflow buckets,查找速率会下降

map的填充因子是6.5

即当count / 2^B > 6.5时会触发一次grow.翻倍扩容

如果负载因子没有超标,但是使用的溢出桶较多,也会触发扩容。但是是等量扩容

原因是原桶中有太多的键值对被删除,等量扩容可以使得剩余的键值对排列更加紧凑,节省空间

	// Maximum average load of a bucket that triggers growth is 6.5.
	// Represent as loadFactorNum/loadFactorDen, to allow integer math.
	loadFactorNum = 13
	loadFactorDen = 2

这个6.5来源于作者的一个测试程序,取了一个相对适中的值

// Picking loadFactor: too large and we have lots of overflow
// buckets, too small and we waste a lot of space. I wrote
// a simple program to check some stats for different loads:
// (64-bit, 8 byte keys and elems)
//  loadFactor    %overflow  bytes/entry     hitprobe    missprobe
//        4.00         2.13        20.77         3.00         4.00
//        4.50         4.05        17.30         3.25         4.50
//        5.00         6.85        14.77         3.50         5.00
//        5.50        10.55        12.94         3.75         5.50
//        6.00        15.27        11.67         4.00         6.00
//        6.50        20.90        10.79         4.25         6.50
//        7.00        27.14        10.15         4.50         7.00
//        7.50        34.03         9.73         4.75         7.50
//        8.00        41.10         9.40         5.00         8.00
//
// %overflow   = percentage of buckets which have an overflow bucket
// bytes/entry = overhead bytes used per key/elem pair
// hitprobe    = # of entries to check when looking up a present key
// missprobe   = # of entries to check when looking up an absent key
//
// Keep in mind this data is for maximally loaded tables, i.e. just
// before the table grows. Typical tables will be somewhat less loaded.

源码分析

// 只是分配新的buckets,并将老的buckets挂到oldbuckets字段上
// 真正搬迁的动作在growWork()中
func hashGrow(t *maptype, h *hmap) {
	// If we've hit the load factor, get bigger.
	// Otherwise, there are too many overflow buckets,
	// so keep the same number of buckets and "grow" laterally.
    // B+1 相当于之前的2倍空间
	bigger := uint8(1)
    // 对应条件2
	if !overLoadFactor(h.count+1, h.B) {
        // 进行等量扩容,B不变
		bigger = 0
		h.flags |= sameSizeGrow
	}
    // 将oldbuckets挂到buckets上
	oldbuckets := h.buckets
    // 申请新的buckets空间
	newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)

    // 对标志位的处理
    // &^表示 按位置0
    // x=01010011
    // y=01010100
    // z=x&^y=00000011
    // 如果y的bit位为1,那么z相应的bit位就为0
    // 否则z对应的bit位就和x对应的bit位相同
    //
    // 其实就是将h.flags的iterator和oldItertor位置为0
    // 如果发现iterator位为1,那就把它转接到 oldIterator 位
    // 使得 oldIterator 标志位变成 1
    // bucket挂到了oldbuckets下,那么标志位也一样转移过去
	flags := h.flags &^ (iterator | oldIterator)
	if h.flags&iterator != 0 {
		flags |= oldIterator
	}

    // // 可能有迭代器使用 buckets
    // iterator     = 1
    // 可能有迭代器使用 oldbuckets
    // oldIterator  = 2
    // 有协程正在向 map 中写入 key
    // hashWriting  = 4
    // 等量扩容(对应条件 2)
    // sameSizeGrow = 8
    // 提交grow的动作
	// commit the grow (atomic wrt gc)
	h.B += bigger
	h.flags = flags
	h.oldbuckets = oldbuckets
	h.buckets = newbuckets
    // 搬迁进度为0
	h.nevacuate = 0
    // 溢出bucket数量为0
	h.noverflow = 0

	if h.extra != nil && h.extra.overflow != nil {
		// Promote current overflow buckets to the old generation.
		if h.extra.oldoverflow != nil {
			throw("oldoverflow is not nil")
		}
		h.extra.oldoverflow = h.extra.overflow
		h.extra.overflow = nil
	}
	if nextOverflow != nil {
		if h.extra == nil {
			h.extra = new(mapextra)
		}
		h.extra.nextOverflow = nextOverflow
	}

	// the actual copying of the hash table data is done incrementally
	// by growWork() and evacuate().
}

// growWork 真正执行搬迁工作的函数
// 调用其的动作在mapssign和mapdelete函数中,也就是插入、修改或删除的时候都会尝试进行搬迁
func growWork(t *maptype, h *hmap, bucket uintptr) {
	// make sure we evacuate the oldbucket corresponding
	// to the bucket we're about to use
    // 确保搬迁的老bucket对应的正在使用的新bucket
    // bucketmask 作用就是将key算出来的hash值与bucketmask相&,得到key应该落入的bucket
    // 只有hash值低B位决策key落入那个bucket
	evacuate(t, h, bucket&h.oldbucketmask())

	// evacuate one more oldbucket to make progress on growing
    // 再搬迁一个bucket,加快搬迁进度,这就是说为什么可能每次操作会搬迁1-2个bucket
	if h.growing() {
		evacuate(t, h, h.nevacuate)
	}
}

// 返回扩容前的bucketmask
//
// 所谓的bucketmask作用就是将 key 计算出来的哈希值与 bucketmask 相与
// 得到的结果就是 key 应该落入的桶
// 比如 B = 5,那么 bucketmask 的低 5 位是 11111,其余位是 0
// hash 值与其相与的意思是,只有 hash 值的低 5 位决策 key 到底落入哪个 bucket。
// oldbucketmask provides a mask that can be applied to calculate n % noldbuckets().
func (h *hmap) oldbucketmask() uintptr {
	return h.noldbuckets() - 1
}

// 检查oldbuckets是否搬迁完
// growing reports whether h is growing. The growth may be to the same size or bigger.
func (h *hmap) growing() bool {
	return h.oldbuckets != nil
}
// evacDst is an evacuation destination.
type evacDst struct {
    // 标识bucket移动的目标地址
	b *bmap          // current destination bucket
    // k-v的索引
	i int            // key/elem index into b
    // 指向k
	k unsafe.Pointer // pointer to current key storage
    // 指向v
	e unsafe.Pointer // pointer to current elem storage
}
// evacuate 核心搬迁函数
func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
    // 定位老的bucket的地址
	b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
	// 结果是2^B,进行计算 如 B = 5,结果为32
    newbit := h.noldbuckets()
    // 如果b没被搬迁过
	if !evacuated(b) {
		// TODO: reuse overflow buckets instead of using new ones, if there
		// is no iterator using the old buckets.  (If !oldIterator.)

		// xy contains the x and y (low and high) evacuation destinations.
        // xy包含了两个可能搬迁到的目的bucket地址
        // 默认是等量扩容的,用x来搬迁
		var xy [2]evacDst
		x := &xy[0]
		x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
		x.k = add(unsafe.Pointer(x.b), dataOffset)
		x.e = add(x.k, bucketCnt*uintptr(t.keysize))

        // 如果不是等量扩容,前后的bucket序号有变
        // 使用y来搬迁
		if !h.sameSizeGrow() {
			// Only calculate y pointers if we're growing bigger.
			// Otherwise GC can see bad pointers.
			y := &xy[1]
            // y代表的bucket序号增加了2^B
			y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
			y.k = add(unsafe.Pointer(y.b), dataOffset)
			y.e = add(y.k, bucketCnt*uintptr(t.keysize))
		}

        // 遍历所有的bucket,包括溢出bucket
        // b是老bucket的地址
		for ; b != nil; b = b.overflow(t) {
			k := add(unsafe.Pointer(b), dataOffset)
			e := add(k, bucketCnt*uintptr(t.keysize))

            // 遍历bucket里所有的cell
			for i := 0; i < bucketCnt; i, k, e = i+1, add(k, uintptr(t.keysize)), add(e, uintptr(t.elemsize)) {
				// 当前cell的tophash值
                top := b.tophash[i]
                // 如果cell为空,即没有key
                // 说明其被搬迁过,作标记然后继续下一个cell
				if isEmpty(top) {
					b.tophash[i] = evacuatedEmpty
					continue
				}

                // 一般不会出现这种情况
                // 未搬迁的cell只可能是empty或者正常的tophash
                // 不会小于minTopHash
				if top < minTopHash {
					throw("bad map state")
				}
                // 进行一次拷贝避免相同内存地址问题
				k2 := k
                // key如果是指针就进行解引用
				if t.indirectkey() {
					k2 = *((*unsafe.Pointer)(k2))
				}
                // 默认值为0标识默认是使用x,进行等量扩容
				var useY uint8
                // 增量扩容
				if !h.sameSizeGrow() {
					// Compute hash to make our evacuation decision (whether we need
					// to send this key/elem to bucket x or bucket y).
                    // 计算hash值,与第一次写入一样
					hash := t.hasher(k2, uintptr(h.hash0))

                    // 有协程在遍历map 且 出现相同的key,计算出的hash值不同
                    // 这里只会有一种情况,也就是float64的时候
                    // 每次hash出来都会是不同的hash值,这就意味着无法通过get去获取其key确切位置
                    // 因此采用取最低位位置来分辨
                    // 为下一个level重新计算一个随机的tophash
                    // 这些key将会在多次增长后均匀的分布在所有的存储桶中
					if h.flags&iterator != 0 && !t.reflexivekey() && !t.key.equal(k2, k2) {
						// If key != key (NaNs), then the hash could be (and probably
						// will be) entirely different from the old hash. Moreover,
						// it isn't reproducible. Reproducibility is required in the
						// presence of iterators, as our evacuation decision must
						// match whatever decision the iterator made.
						// Fortunately, we have the freedom to send these keys either
						// way. Also, tophash is meaningless for these kinds of keys.
						// We let the low bit of tophash drive the evacuation decision.
						// We recompute a new random tophash for the next level so
						// these keys will get evenly distributed across all buckets
						// after multiple grows.
                        // 第B位 置1
                        // 如果tophash最低位是0就分配到x part 否则分配到y part
						useY = top & 1
						top = tophash(hash)
					} else {
                        // 对于正常的key
                        // 第B位 置0
						if hash&newbit != 0 {
                            // 使用y部分
							useY = 1
						}
					}
				}

				if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY {
					throw("bad evacuatedN")
				}
                // 这里其实就是重新设置tophash值
                // 标记老的cell的tophash值,表示搬到useT部分(可能是x也可能是y,看具体取值)
				b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY
				// 选择目标bucket的内存起始部分
                dst := &xy[useY]                 // evacuation destination

                // 如果i=8说明要溢出了
				if dst.i == bucketCnt {
                    // 新建一个溢出bucket
					dst.b = h.newoverflow(t, dst.b)
                    // 从0开始计数
					dst.i = 0
                    // 标识key要移动到的位置
					dst.k = add(unsafe.Pointer(dst.b), dataOffset)
                    // 标识value要移动到的位置
					dst.e = add(dst.k, bucketCnt*uintptr(t.keysize))
				}
                // 重新设置tophash
				dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds check
				if t.indirectkey() {
                    // 将原key(指针类型)复制到新的位置
					*(*unsafe.Pointer)(dst.k) = k2 // copy pointer
				} else {
                    // 将原key(值类型)复制到新位置
					typedmemmove(t.key, dst.k, k) // copy elem
				}
                // 如果v是指针,操作同key
				if t.indirectelem() {
					*(*unsafe.Pointer)(dst.e) = *(*unsafe.Pointer)(e)
				} else {
					typedmemmove(t.elem, dst.e, e)
				}
                // 定位到下一个cell
				dst.i++
				// These updates might push these pointers past the end of the
				// key or elem arrays.  That's ok, as we have the overflow pointer
				// at the end of the bucket to protect against pointing past the
				// end of the bucket.
                // 两个溢出指针在bucket末尾用于保证 遍历到bucket末尾的指针
				dst.k = add(dst.k, uintptr(t.keysize))
				dst.e = add(dst.e, uintptr(t.elemsize))
			}
		}
        // 如果没有协程在用老的bucket,就将老的bucket清除,帮助gc
		// Unlink the overflow buckets & clear key/elem to help GC.
		if h.flags&oldIterator == 0 && t.bucket.ptrdata != 0 {
			b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))
			// Preserve b.tophash because the evacuation
			// state is maintained there.
			ptr := add(b, dataOffset)
			n := uintptr(t.bucketsize) - dataOffset
            // 只清除k-v部分,tophash用于标识搬迁状态
			memclrHasPointers(ptr, n)
		}
	}

    // 如果此次搬迁的bucket等于当前搬迁进度,更新搬迁进度
	if oldbucket == h.nevacuate {
		advanceEvacuationMark(h, t, newbit)
	}
}

// 更新搬迁进度
func advanceEvacuationMark(h *hmap, t *maptype, newbit uintptr) {
    // 进度+1
	h.nevacuate++
    // 尝试往后看1024个bucket,确保行为是O(1)的
	// Experiments suggest that 1024 is overkill by at least an order of magnitude.
	// Put it in there as a safeguard anyway, to ensure O(1) behavior.
	stop := h.nevacuate + 1024
	if stop > newbit {
		stop = newbit
	}
    // 寻找没有搬迁过的bucket
	for h.nevacuate != stop && bucketEvacuated(t, h, h.nevacuate) {
		h.nevacuate++
	}

    // 现在h.nevacuate之前的bucket都被搬迁完毕了

    // 如果所有bucket搬迁完毕
	if h.nevacuate == newbit { // newbit == # of oldbuckets
        // 清除oldbuckets,释放bucket array
		// Growing is all done. Free old main bucket array.
		h.oldbuckets = nil
        // 清除老的溢出bucket
        // [0]表示当前溢出bucket
        // [1]表示老的溢出bucket
		// Can discard old overflow buckets as well.
		// If they are still referenced by an iterator,
		// then the iterator holds a pointers to the slice.
		if h.extra != nil {
			h.extra.oldoverflow = nil
		}
        // 清除正在扩容的标志位
		h.flags &^= sameSizeGrow
	}
}

源码里提到 X, Y part,其实就是我们说的如果是扩容到原来的 2 倍,桶的数量是原来的 2 倍,前一半桶被称为 X part,后一半桶被称为 Y part。一个 bucket 中的 key 会分裂落到 2 个桶中。一个位于 X part,一个位于 Y part。所以在搬迁一个 cell 之前,需要知道这个 cell 中的 key 是落到哪个 Part。

其实很简单,重新计算 cell 中 key 的 hash,并向前“多看”一位,决定落入哪个 Part

设置 key 在原始 buckets 的 tophash 为 evacuatedX 或是 evacuatedY,表示已经搬迁到了新 map 的 x part 或是 y part。新 map 的 tophash 则正常取 key 哈希值的高 8 位。

对于增量扩容来说:某个 key 在搬迁前后 bucket 序号可能和原来相等,也可能是相比原来加上 2^B(原来的 B 值),取决于 hash 值 第 6 bit 位是 0 还是 1。

当搬迁碰到 math.NaN() 的 key 时,只通过 tophash 的最低位决定分配到 X part 还是 Y part(如果扩容后是原来 buckets 数量的 2 倍)。如果 tophash 的最低位是 0 ,分配到 X part;如果是 1 ,则分配到 Y part,已搬迁完的key的tophash值是一个状态值,表示key的搬迁去向

到此这篇关于深入了解Golang的map增量扩容的文章就介绍到这了,更多相关 Go增量扩容内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Golang Map实现赋值和扩容的示例代码

    golang map 操作,是map 实现中较复杂的逻辑.因为当赋值时,为了减少hash 冲突链的长度过长问题,会做map 的扩容以及数据的迁移.而map 的扩容以及数据的迁移也是关注的重点. 数据结构 首先,我们需要重新学习下map实现的数据结构: type hmap struct { count int flags uint8 B uint8 noverflow uint16 hash0 uint32 buckets unsafe.Pointer oldbuckets unsafe.Poin

  • 浅谈Golang 切片(slice)扩容机制的原理

    我们知道 Golang 切片(slice) 在容量不足的情况下会进行扩容,扩容的原理是怎样的呢?是不是每次扩一倍?下面我们结合源码来告诉你答案. 一.源码 Version : go1.15.6  src/runtime/slice.go //go1.15.6 源码 src/runtime/slice.go func growslice(et *_type, old slice, cap int) slice { //省略部分判断代码 //计算扩容部分 //其中,cap : 所需容量,newcap

  • golang切片扩容规则实现

    golang扩容规则 举个例子来演示下 package main import ( "fmt" ) func main() { arr1 := [4]int{1,2,3,4} //此时slice1为[1,2,3] 长度为3,容量为4 slice1 :=arr1[:3] fmt.Println(slice1,len(slice1),cap(slice1)) slice1 = append(slice1,5000,6000) fmt.Println(slice1,len(slice1),c

  • 浅谈Golang Slice切片如何扩容的实现

    目录 一.Slice数据结构是什么? 二.详细代码 1.数据结构 2.扩容原则 3.如何理解扩容规则一 1.当小于1024个元素时 2.当大于1024个元素时 4.如何理解扩容规则二 1.简单理解内存地址更换 总结 一.Slice数据结构是什么? 切片(slice)是 Golang 中一种比较特殊的数据结构,这种数据结构更便于使用和管理数据集合.切片是围绕动态数组的概念构建的,可以按需自动增长和缩小.切片(slice)是可以看做是一个长度可变的数组.切片(slice)自身并不是动态数组或者数组指

  • 深入了解Golang的map增量扩容

    目录 核心思想 扩容方式 源码分析 核心思想 以空间换时间,访问速度与填充因子有关 扩容hash表的时候每次都增大2倍,hash表大小始终为2的整数倍,有(hash mod 2^B) == (hash & (2^B-1)),方便于简化运算,避免取余操作 扩容前后的 hash mod 容量大小 是不等的,因此要重新计算每一项在hash表中的位置,扩容后需要将old pair重新hash到新的hash表上(就是一个evacuate的过程).这个过程不是一次性完成的,在每次insert.remove的

  • Golang中map的深入探究

    目录 简介 Map 的底层内存模型 Map 的存与取 底层代码 Map 的扩容 第一种情况 第二种情况 Map 的有序性 Map 的并发 总结 简介 本文主要通过探究在golang 中map的数据结构及源码实现来学习和了解map的特性,共包含map的模型探究.存取.扩容等内容.欢迎大家共同讨论. Map 的底层内存模型 在 golang 的源码中表示 map 的底层 struct 是 hmap,其是 hashmap 的缩写 type hmap struct { // map中存入元素的个数, g

  • Golang 语言map底层实现原理解析

    在开发过程中,map是必不可少的数据结构,在Golang中,使用map或多或少会遇到与其他语言不一样的体验,比如访问不存在的元素会返回其类型的空值.map的大小究竟是多少,为什么会报"cannot take the address of"错误,遍历map的随机性等等. 本文希望通过研究map的底层实现,以解答这些疑惑. 基于Golang 1.8.3 1. 数据结构及内存管理 hashmap的定义位于 src/runtime/hashmap.go 中,首先我们看下hashmap和buck

  • golang语言map全方位介绍

    目录 一.map 1.基本介绍 2.声明基本语法 二.map 的使用 2.map[string]map[string]string使用案例 三.map 的增删改查操作 1.map 增加和更新 2.map 删除 3.map 查找 四.map的其他操作 1.map 遍历: 2.map 的长度 3.map 切片 4.map 排序 五.map 使用细节 总结 一.map 1.基本介绍 map 是 key-value 数据结构,又称为字段或者关联数组.类似其它编程语言的集合, 在编程中是经常使用到 2.声

  • Golang中map数据类型的使用方法

    目录 前言 案例 map map定义 map声明 map的操作 总结 前言 今天咱们来学习一下golang中的map数据类型,单纯的总结一下基本语法和使用场景,也不具体深入底层.map类型是什么呢?做过PHP的,对于数组这种数据类型是一点也不陌生了.PHP中的数组分为索引数组和关联数组.例如下面的代码: // 索引数组[数组的key是一个数字, 从0,1,2开始递增] $array = [1, '张三', 12]; // 关联数组[数组的key是一个字符串,可以自定义key的名称] $array

  • 关于golang中map使用的几点注意事项总结(强烈推荐!)

    目录 前言 1 使用 map 记得初始化 2 map 的遍历是无序的 3 map 也可以是二维的 4 获取 map 的 key 最好使用这种方式 5 map 是并发不安全的 ,sync.Map 才是安全的 总结 前言 日常的开发工作中,map 这个数据结构相信大家并不陌生,在 golang 里面,当然也有 map 这种类型 关于 map 的使用,还是有蛮多注意事项的,如果不清楚,这些事项,关键时候可能会踩坑,我们一起来演练一下吧 1 使用 map 记得初始化 写一个 demo 定义一个 map[

  • golang针对map的判断,删除操作示例

    本文实例讲述了golang针对map的判断,删除操作.分享给大家供大家参考,具体如下: map是一种key-value的关系,一般都会使用make来初始化内存,有助于减少后续新增操作的内存分配次数.假如一开始定义了话,但没有用make来初始化,会报错的. 复制代码 代码如下: package main import ( "fmt" ) func main(){ var test =  map[string]string{"姓名":"李四",&qu

  • Golang 使用map需要注意的几个点

    1.简介 map 是 Golang 中的方便而强大的内建数据结构,是一个同种类型元素的无序组,元素通过另一类型唯一的键进行索引.其键可以是任何相等性操作符支持的类型, 如整数.浮点数.复数.字符串.指针.接口(只要其动态类型支持相等性判断).结构以及数组. 切片不能用作映射键,因为它们的相等性还未定义.与切片一样,映射也是引用类型. 若将映射传入函数中,并更改了该映射的内容,则此修改对调用者同样可见.未初始化的映射值为 nil. 使用示例如下: package main import "fmt&

  • golang映射Map的方法步骤

    map是key-value数据结构,又称为字段或者关联数组.类似其他编程语言的集合 一.基本语法 var 变量名 map[keytype]valuetype // map 使用前要make // map 的key不能重复,重复了,以最后的key-value为准 // map 的key-value 是无序的 var a map[string]string a = make(map[string]string, 10) a["n1"] = "a" a["n2&

  • Golang 空map和未初始化map的注意事项说明

    可以对未初始化的map进行取值,但取出来的东西是空: var m1 map[string]string fmt.Println(m1["1"]) 不能对未初始化的map进行赋值,这样将会抛出一个异常: panic: assignment to entry in nil map var m1 map[string]string m1["1"] = "1" 通过fmt打印map时,空map和nil map结果是一样的,都为map[].所以,这个时候别

随机推荐