文章目录
- 触发扩容操作
- 触发map扩容的条件
- 条件一:overLoadFactor
- 条件二:tooManyOverflowBuckets
- 何时会出现“溢出桶太多”的情况呢?
- 准备进行扩容
- 对 flag 的变动
- 扩容函数
- growWork
- evacuate
- noldbuckets
- evacuated & isEmpty
- evacDst
- indirectkey
- 小结
- 执行扩容
- 结论
Golang版本: 1.20.3
平台:Windows 11
Go语言,以其简单高效的编程理念和表现力强、性能优异的特性,迅速在开发者社区中取得了广泛的认可。尤其是在处理并发操作和网络编程方面,Go语言展现出了独特的优势。然而,尽管语言本身设计简洁,但其底层实现却巧妙而复杂,对此充满了好奇,我决定深入研究其中的一些关键组件——比如Go语言的Map。
Map,在许多编程语言中都是一个重要的数据结构,它为存储和检索键值对提供了方便。在计算机科学里,Map也被称为相关数组、符号表或者字典,是由一组 <key, value> 对组成的抽象数据结构,有两个关键点:Map是由key-value
对组成的;key只会出现一次。在Go语言中,Map更是引人注目,因为它既有强大的功能,又有丰富的优化。
在本篇博客中,我将分享我对Go语言1.20.3版本中Map扩容机制的探索过程和所得到的理解。我希望这些内容能够对正在学习Go语言,或者对Go语言底层实现感兴趣的读者提供一些帮助。这也是我写作本篇博客的主要动机。
首先,我们需要知道的是GO语言当中map文件的存放位置位于goSDK\src\runtime\map.go
当中,我们都知道map的扩容发生在新增元素的时候,接下来我将一点一点的去从头到尾展开讲解,如果说碰到某些概念对本文章的比较重要我会在本文章中解释,如果说不是特别重要的话,我会放在其他文章当中去讲。map的实现原理以及具体的细节我回来会单独出一篇文章,我们这次重点关注扩容。
触发扩容操作
在Go语言中,插入一个元素到hashmap
时,会出现以下两种情况:
- 如果元素已存在,那么将进行更新操作。
- 如果元素不存在,那么将进行插入操作。在插入之前,Go会先找到一个空位置以存放新插入的元素。
我们需要关注的是插入操作。在进行插入之前,Go会判断当前的map是否需要扩容,以及是否正在进行扩容操作。这是因为,如果map中的元素过多,迁移操作将会耗费大量的时间和内存。为了优化这一过程,Go采用了分批迁移的策略。下面是触发扩容操作的判断条件:
// 如果我们达到了最大负载因子,或者我们有太多的溢出桶,
// 并且我们还没有处于增长中,那么开始增长。
if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {hashGrow(t, h)goto again // 增长表格会使所有东西都失效,所以重新尝试
}// growing 报告 h 是否正在扩容。扩容可能是到相同的大小或更大。
// 通过判断oldbuckets是否为nil来判断是否扩容完成
func (h *hmap) growing() bool {return h.oldbuckets != nil
}
这段代码的含义是:如果当前的map的元素数量达到了最大负载因子的限制,或者溢出桶的数量过多,并且map并未处于扩容状态,那么就需要对map进行扩容操作(通过 hashGrow(t, h)
)。在扩容后,原有的map结构会发生改变(例如,元素的位置可能会变化),所以需要重新执行元素的查找或插入等操作,这就是 goto again
的作用。
触发map扩容的条件
接下来我们继续分析两个能触发map扩容的条件overLoadFactor
和tooManyOverflowBuckets
。我将要用到的函数以及变量都放在下面的代码中,并一并解释:
const (// 一个桶可以容纳的键/元素对的最大数量。bucketCntBits = 3bucketCnt = 1 << bucketCntBits // 相当于2^3 = 8// 触发增长的桶的最大平均负载是6.5。// 表示为 loadFactorNum/loadFactorDen,以允许使用整数数学运算。loadFactorNum = 13loadFactorDen = 2
)
// bucketShift 返回 1<<b,为了优化代码生成。
func bucketShift(b uint8) uintptr {// 通过掩码处理移位数量,可以省略溢出检查。return uintptr(1) << (b & (goarch.PtrSize*8 - 1))
}// overLoadFactor 报告将 count 个项放置在 1<<B 个桶中是否超过负载因子。
func overLoadFactor(count int, B uint8) bool {// 如果 count 大于每个桶能容纳的元素数量(bucketCnt),并且// count 大于负载因子允许的最大元素数量(loadFactorNum*(bucketShift(B)/loadFactorDen)),// 则返回 true,表示超过负载因子。return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}// tooManyOverflowBuckets 报告对于具有 1<<B 个桶的 map 而言,noverflow 个溢出桶是否太多。
// 注意这些溢出桶大部分必须在稀疏使用中;
// 如果使用密集,那么我们已经触发了常规的 map 增长。
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {// 如果阈值过低,我们会做额外的工作。// 如果阈值过高,那么增长和收缩的 map 可以保留大量未使用的内存。// “太多”意味着(大约)与常规桶一样多的溢出桶。// 有关更多详细信息,请参阅 incrnoverflow。if B > 15 {B = 15}// 编译器在这里看不到 B < 16;掩蔽 B 以生成更短的移位代码。return noverflow >= uint16(1)<<(B&15)
}
条件一:overLoadFactor
overLoadFactor
用于检查当前 map 中的元素数量是否已经超过了负载因子允许的最大元素数量。在overLoadFactor
函数中,首先会确认 map 中的元素数量是否超过了一个桶可以容纳的数量,即 bucketCnt
(8),这是触发扩容操作的一个基本条件。如果 map 的元素数量超过了这个值,并且也超过了负载因子(6.5)允许的最大元素数量,那么就需要对 map 进行扩容。
bucketShift
函数返回 1<<b
的值,这个函数主要用于计算具有 b
个桶的 map 可以容纳的元素数量。这个函数通过掩码处理移位数量,从而省略溢出检查,优化代码生成。
其中, goarch.PtrSize*8 - 1
是指针大小的位数减一。在 32 位系统上,goarch.PtrSize
为 4,而在 64 位系统上,goarch.PtrSize
为 8。因此,这个表达式在 32 位系统上等于 31,在 64 位系统上则等于 63。这样,移位数量 b
只能在 0 到 31(或 63)之间,从而避免了溢出。
条件二:tooManyOverflowBuckets
tooManyOverflowBuckets
函数检查当前 map 中的溢出桶数量是否过多。如果是,那也需要对 map 进行扩容。
在 Go 的 map 实现中,当一个桶存满后,会创建一个新的桶作为溢出桶来存储多出来的元素。溢出桶是通过链表的方式链接在原始桶后面的。如果一个 map 中的溢出桶数量过多,那么就需要对 map 进行扩容,以减少查找元素时需要遍历的溢出桶的数量。
在此函数中,首先判断了 B
(表示桶数量的对数)的值是否大于 15,如果大于 15,则将 B
设置为 15。这是因为,在实际的计算中,桶的数量不会超过 2^15
,即 32768。这样能防止后续的移位操作溢出。
然后,函数通过 1 << (B & 15)
计算出一个阈值,判断 noverflow
(当前溢出桶的数量)是否大于或等于这个阈值。如果是,那么就认为溢出桶的数量过多。B & 15
是为了确保移位的数量在 0 到 15 之间,避免溢出。
因此,“太多”溢出桶的意思是,溢出桶的数量大约与常规桶的数量相同。如果达到这个情况,那么就需要对 map 进行扩容。
何时会出现“溢出桶太多”的情况呢?
主要有两种可能:
- 数据插入不均匀:虽然 Go 的 map 在理论上可以通过哈希函数将数据均匀地分配到各个桶中,但在实际情况下,可能出现某个或某些桶的数据特别多,导致需要频繁生成溢出桶。这种情况可能由于哈希函数的选取不当,或者插入的数据分布特性导致。
- map 的容量设置过小:如果创建 map 时设置的容量过小,而实际插入的数据远超预设的容量,那么就会频繁地生成溢出桶,导致溢出桶数量增多。
当溢出桶的数量过多时,会影响 map 的性能。因为在查找一个键值对时,可能需要遍历多个溢出桶。因此,当 Go 检测到溢出桶过多时,会触发 map 的扩容操作,以减少溢出桶数量,提高操作效率。
准备进行扩容
func hashGrow(t *maptype, h *hmap) {// B的增长数量bigger := uint8(1)// 如果map里面元素的数量已经达到负载因子,变大。// 否则,溢出桶太多,所以保持同样数量的桶并“横向”增长(改变hash函数来实现元素重排)。if !overLoadFactor(h.count+1, h.B) {bigger = 0h.flags |= sameSizeGrow}oldbuckets := h.bucketsnewbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)flags := h.flags &^ (iterator | oldIterator)if h.flags&iterator != 0 {flags |= oldIterator}// 提交增长(对 GC 原子)h.B += biggerh.flags = flagsh.oldbuckets = oldbucketsh.buckets = newbucketsh.nevacuate = 0h.noverflow = 0if h.extra != nil && h.extra.overflow != nil {// 将当前溢出桶提升到旧一代。if h.extra.oldoverflow != nil {throw("oldoverflow is not nil")}h.extra.oldoverflow = h.extra.overflowh.extra.overflow = nil}if nextOverflow != nil {if h.extra == nil {h.extra = new(mapextra)}h.extra.nextOverflow = nextOverflow}
}
hashGrow
函数是 Go 里的 map 数据结构在需要扩容时的调用函数,它主要负责创建一个更大的新哈希表,并将旧哈希表的数据迁移到新的哈希表中。
在函数开始的地方,首先检查扩容的条件:如果已经达到负载因子,或者溢出桶的数量太多,那么就需要进行扩容。根据具体情况,扩容可能增大哈希表的大小,或者在哈希表大小不变的情况下进行元素重排。
在创建新的哈希表之后,函数会更新哈希表的相关属性,如桶的数量、标志位、旧桶的引用、新桶的引用等。
接着,如果有溢出桶存在,函数会将这些溢出桶移到旧的哈希表,并创建新的溢出桶。
至此,扩容的准备工作就完成了。实际的扩容工作,也就是哈希表数据的实际迁移,是通过 growWork()
和 evacuate()
函数逐步完成的。这意味着 hashGrow
函数的主要任务是创建新的哈希表和设置相关的属性,而真正的数据迁移工作在后续的 growWork()
和 evacuate()
函数中完成。
对 flag 的变动
flags := h.flags &^ (iterator | oldIterator)
if h.flags&iterator != 0 {flags |= oldIterator
}
以上代码段主要负责处理 hmap
结构体中 flags
字段的值。flags
字段用于保存一些标志位,这些标志位反映了当前哈希表的各种状态信息。
flags := h.flags &^ (iterator | oldIterator)
首先,这行代码使用位运算符 &^
来清除 h.flags
中的 iterator
和 oldIterator
标志位。在 Go 语言中,&^
是位清除运算符。对于 b
中的每一个二进制位,如果其值为 1,那么 a
对应的位将被清零,否则 a
对应的位保持不变。
if h.flags&iterator != 0 {flags |= oldIterator
}
然后,这个 if
语句检查 h.flags
的 iterator
标志位是否已被设置。如果 iterator
标志位被设置,那么就将 flags
的 oldIterator
标志位设为 1。|=
是位或赋值运算符,a |= b
相当于 a = a | b
,也就是对 a
和 b
进行位或运算,然后把结果赋值给 a
。
总的来说,这段代码的功能是,如果 iterator
标志位被设置,那么就清除 iterator
标志位,并同时设置 oldIterator
标志位。这是因为,在哈希表进行扩容操作过程中,原有的迭代器可能会失效,所以将 iterator
标志转变为 oldIterator
标志,以此来说明这个情况。
扩容函数
growWork
func growWork(t *maptype, h *hmap, bucket uintptr) {// 确保我们疏散对应于我们即将使用的桶的 oldbucketevacuate(t, h, bucket&h.oldbucketmask())// 疏散一个更多的 oldbucket 以在增长上取得进展if h.growing() {evacuate(t, h, h.nevacuate)}
}
它的主要任务是将旧哈希表的数据迁移至新创建的哈希表。这个函数一次处理两个桶的数据迁移。
-
第一个
evacuate
函数调用是为了处理我们即将在新的哈希表中使用的桶对应的旧桶的数据迁移。这是必须的,因为我们需要确保新桶中的数据是最新和完整的。 -
如果哈希表仍在扩容(由
h.growing()
函数检测),那么我们会调用第二个evacuate
函数来处理一个额外的旧桶的数据迁移。这是为了在扩容过程中取得进展,即每次都处理一部分数据迁移,而不是一次性处理所有数据,这样可以有效地分摊计算负载。h.nevacuate
就是下一个需要处理的旧桶的序号。
evacuate
evacuate
函数的任务就是将指定的旧桶的数据迁移至新的哈希表中。里面用到的辅助函数以及结构图都在下边有展示,或者通过Ctrl f
进行查找
func evacuate(t *maptype, h *hmap, oldbucket uintptr) {// 通过oldbuckets的起始位置和 oldbucket的指针,以及桶的长度来确定我们要操作的这个桶b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))// 计算出增长之前B的大小newbit := h.noldbuckets()//判断当前桶是否完成迁移if !evacuated(b) {// xy 包含了 x 和 y(低和高)的迁移目标位置。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))// 判断是不是扩容增长if !h.sameSizeGrow() {// 只有在我们要扩大规模时,我们才计算y指针。// 横向增长桶的数量没变,就不存在前一部分还是后一部分// 否则,GC可能会看到错误的指针。// y表示后半部分桶y := &xy[1]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))}// 以下的代码是迭代旧桶内的每一个元素,然后将它们根据 hash 值分别放到新的 x 或 y 桶中,//双重for循环第一层遍历当前桶以及溢出桶// 如果我们正在进行扩容操作(即,新的哈希表大小大于旧的哈希表大小),我们需要将元素分散到 x 和 y 两个桶中以保证平衡,// 如果我们正处于 "sameSizeGrow" 模式,那么我们只需要将元素移动到 x 桶即可。// 在迭代过程中,我们首先通过检查元素的 "tophash" 值来判断它是否已经被处理过,// 然后我们计算元素的哈希值,并根据哈希值的某个位来决定元素应该被放到 x 还是 y 桶中,// 最后我们把元素复制到新桶中的对应位置,然后更新 "tophash" 值以表示该元素已经被处理过。for ; b != nil; b = b.overflow(t) {k := add(unsafe.Pointer(b), dataOffset)e := add(k, bucketCnt*uintptr(t.keysize))for i := 0; i < bucketCnt; i, k, e = i+1, add(k, uintptr(t.keysize)), add(e, uintptr(t.elemsize)) {top := b.tophash[i]// 如果是空的说明已经迁移过该元素// 或者该元素已被删除if isEmpty(top) {b.tophash[i] = evacuatedEmptycontinue}if top < minTopHash {throw("bad map state")}k2 := k// 这段代码的目的是,如果哈希表的键是以指针形式存储的,// 那么获取到的键实际上是一个指向键的指针。// 因此,这段代码通过解引用这个指针 (*((*unsafe.Pointer)(k2))) 来获取真正的键的值。if t.indirectkey() {k2 = *((*unsafe.Pointer)(k2))}var useY uint8if !h.sameSizeGrow() {// 计算哈希以做出我们的疏散决定(是否需要将此键/元素发送到桶x或桶y)。hash := t.hasher(k2, uintptr(h.hash0))if h.flags&iterator != 0 && !t.reflexivekey() && !t.key.equal(k2, k2) {// 如果元素的键是 NaN(即,键不等于自身),那么元素的新哈希值可能会和旧的哈希值完全不同,且无法复制。// 在存在迭代器的情况下,需要可复制性,因为我们的疏散决策必须匹配迭代器做出的任何决策。// 幸运的是,我们可以任意选择将这些键发送的方向。同样,对这种类型的键来说,tophash 没有任何意义。// 我们通过 tophash 的低位来决定(useY = top & 1)// 同时,我们会为元素计算一个新的 tophash 值(top = tophash(hash))// 以保证在多次增长后,这种键将均匀地分布在所有桶中。useY = top & 1top = tophash(hash)} else {if hash&newbit != 0 {useY = 1}}}// 在哈希表的扩容过程中,evacuatedX 和 evacuatedY 是两个特殊的 tophash 值,// 它们被用来标记一个桶中的元素被疏散到新的桶(x 或 y)。// 这个断言的作用是确保 evacuatedX 和 evacuatedY 的值正确地反映了桶的疏散情况。// 具体地说,evacuatedY 应该是 evacuatedX 加 1,同时它们的异或运算结果也应该是 1,// 因为在二进制表示下,相邻的两个数的异或运算结果总是 1。// 如果这两个条件中的任何一个不满足,那么就会通过 throw 函数抛出一个错误。if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY {throw("bad evacuatedN")}b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedYdst := &xy[useY] // 迁移目标(新桶)// 数据迁移if dst.i == bucketCnt {dst.b = h.newoverflow(t, dst.b)dst.i = 0dst.k = add(unsafe.Pointer(dst.b), dataOffset)dst.e = add(dst.k, bucketCnt*uintptr(t.keysize))}dst.b.tophash[dst.i&(bucketCnt-1)] = top // 将 dst.i 作为优化掩码,以避免边界检查if t.indirectkey() {*(*unsafe.Pointer)(dst.k) = k2 // 拷贝指针} else {typedmemmove(t.key, dst.k, k) // 拷贝元素}if t.indirectelem() {*(*unsafe.Pointer)(dst.e) = *(*unsafe.Pointer)(e)} else {typedmemmove(t.elem, dst.e, e)}dst.i++// 这些更新可能会将这些指针推过 key 或 elem 数组的末尾。// 这是可以的,因为我们在桶的末尾有溢出指针来防止指向桶的末尾之后。dst.k = add(dst.k, uintptr(t.keysize))dst.e = add(dst.e, uintptr(t.elemsize))}}// 断开溢出桶的链接并清除键/值以帮助垃圾回收器。if h.flags&oldIterator == 0 && t.bucket.ptrdata != 0 {b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))// 保留 b.tophash ,因为疏散状态在那里维护。ptr := add(b, dataOffset)n := uintptr(t.bucketsize) - dataOffset// 内存清理memclrHasPointers(ptr, n)}}if oldbucket == h.nevacuate {advanceEvacuationMark(h, t, newbit)}
}
noldbuckets
// noldbuckets 计算桶增长之前B的数值并保存一下
func (h *hmap) noldbuckets() uintptr {oldB := h.Bif !h.sameSizeGrow() {oldB--}return bucketShift(oldB)
}
evacuated & isEmpty
const (// 可能的 tophash 值。我们为特别的标记保留了一些可能性。// 每一个桶(包括它的溢出桶,如果有的话)要么所有的条目都在 evacuated* 状态,要么都不在。// 除了在 evacuate() 方法中,这个方法只在 map 写入时发生,因此在这段时间内,没有其他人能观察到 map。emptyRest = 0 // 这个单元格是空的,并且从当前单元格往后没有元素。emptyOne = 1 // 这个单元格是空的,当前单元格位置后边还存在其他元素(一般指当前位置的元素被删除之后并且后边还有其他元素,会将当前的tophash,设置成emptyOne)// 在数据迁移的时候如果是增量迁移那么桶的数量扩充为之前的2倍// 如果说元素被迁移到前一半的桶则将tophash设置为evacuatedX否则设置为evacuatedYevacuatedX = 2 // key/elem 是有效的。条目已经被疏散到更大表的前半部分。evacuatedY = 3 // 与上面相同,但被疏散到更大表的后半部分。evacuatedEmpty = 4 // 单元格为空,桶已经迁移完成。minTopHash = 5 // 对于一个正常填充的单元格,tophash 的最小值。// 标志iterator = 1 // 可能有一个迭代器正在使用桶oldIterator = 2 // 可能有一个迭代器正在使用 oldbucketshashWriting = 4 // 一个 goroutine 正在写入 mapsameSizeGrow = 8 // 当前的 map 增长是到一个相同大小的新 map
)
// 检测当前桶是否已经完成迁移
func evacuated(b *bmap) bool {h := b.tophash[0]return h > emptyOne && h < minTopHash
}// isEmpty 报告给定的 tophash 数组条目是否表示一个空的桶条目。
func isEmpty(x uint8) bool {return x <= emptyOne
}
evacDst
// evacDst 是一个疏散目标。
type evacDst struct {b *bmap // 当前目标桶i int // 键/元素在 b 中的索引k unsafe.Pointer // 指向当前键存储的指针e unsafe.Pointer // 指向当前元素存储的指针
}
这个类型的主要作用是在哈希表的扩容过程中,记录元素的疏散目标。当我们需要将一个旧桶中的元素移动到新的桶中时,我们首先需要确定新的桶(即,疏散目标),然后再将元素复制到新桶中的对应位置。
这个类型有四个字段:
b
字段是一个指向新桶的指针。i
字段是元素在新桶中的索引(也就是元素应该被复制到新桶中的哪个位置)。k
字段是一个指向元素的键存储的指针(用于复制键值)。e
字段是一个指向元素的值存储的指针(用于复制元素值)。
indirectkey
// 注意: 标志值必须与在 ../cmd/compile/internal/reflectdata/reflect.go:writeType 中的 TMAP case 中使用的值相匹配。
func (mt *maptype) indirectkey() bool { // 存储指向键的指针,而不是键本身return mt.flags&1 != 0
}
这个函数的目标是检查给定的 map 类型是否存储的是键的指针,而不是键本身。在 Go 语言的哈希表实现中,可以选择存储键的值,也可以选择存储指向键的指针,这取决于键的类型及其大小。这个函数通过检查 map 类型的 flags
字段的第一位来判断存储方式,如果这一位是 1,那么就是存储指向键的指针。
这个函数的返回值可以用于在处理哈希表的元素时,正确地获取元素的键。比如,在查找元素时,我们需要使用元素的键进行比较,这时就需要知道元素的键是直接存储的,还是以指针形式存储的。
小结
在 Go 的 map 实现中,当 map 需要扩容时,为了避免一次性复制整个哈希表的数据导致的大量计算,Go 采用了分批(incrementally)复制的方式。具体来说,这个操作主要由 growWork()
和 evacuate()
这两个函数完成。
growWork()
函数的主要任务是创建一个新的、更大的哈希表,并将旧哈希表的数据移动到新的哈希表中。这个函数并不会把所有数据一次性全部移动过去,而是每次只处理一部分,也就是“分批处理”。evacuate()
函数的主要任务是将旧哈希表的一个桶的数据移动到新哈希表中。这个函数在growWork()
的每一次调用中都会被调用,进行实际的数据迁移工作。
通过这种方式,Go 的 map 扩容时可以平摊复制哈希表数据的计算量,避免了因为一次性处理大量数据导致的性能问题。
执行扩容
在Go语言中,Map的扩容过程非常关键,它决定了Map的性能和效率。一般来说,扩容会在以下几种情况中触发:
- 删除元素:当我们删除Map中的元素时,Go会检查是否正在进行扩容操作。如果是,那么扩容操作将针对被删除元素的bucket进行。
GO复制// 删除元素
func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {...
bucket := hash & bucketMask(h.B)if h.growing() {growWork(t, h, bucket)}...
}
- 插入或更新元素:当我们向Map中插入新元素或更新现有元素时,Go会进行类似的检查。此时,如果Map正在扩容,那么扩容操作将针对被插入或更新元素的bucket进行。
GO复制// 插入或更新元素
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {...
again:bucket := hash & bucketMask(h.B)if h.growing() {growWork(t, h, bucket)}...
if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {hashGrow(t, h)goto again // 增长表格会使所有东西都失效,所以重新尝试}
}
通过阅读源码,我们可以看到,如果Map正在扩容,那么在删除、插入或更新元素时都会执行一次迁移操作。这样可以确保扩容过程的平滑进行,而不会因为其他操作的干扰而中断。值得注意的是,查找元素并不会触发扩容操作。这是因为,查找操作只涉及到读取数据,而不会改变Map的结构,因此无需触发扩容。
结论
以上便是Go语言中的Map扩容机制的详细剖析。它以一种精细和高效的方式在插入元素时决定是否需要进行扩容。如果需要,它将执行扩容的预备工作,然后进行一次实际的扩容操作。此后,每次进行删除、插入或修改操作时,它都将执行扩容操作。
通过深入理解这些内在机制,我们能够更透彻地把握Go语言中Map的工作原理,并能更有效地利用这一强大的数据结构。这对于提高我们编程的效率,以及优化我们的代码性能,都有着重要的帮助。不仅如此,这也为我们提供了一个视角,去理解更多其他语言和框架中类似的数据结构和算法。总的来说,深入研究和理解这些底层原理,将对我们的编程技能提升有着积极的推动作用。
如果你在阅读过程中有任何疑问,欢迎在评论区提问,或者通过私信向我反馈。我很乐意进一步讨论这些主题,并努力解答你的疑问。记住,对知识的探求和分享是我们共同进步的重要途径。