济宁网站建设的公司,物流专线做网站,抖音自媒体平台注册,黄山旅游攻略住宿扩容
在 Go 语言中#xff0c;当 map 的元素数量达到一定阈值时#xff0c;会触发扩容操作以保持性能。这个过程称为 rehashing#xff0c;即重新散列所有的键值对到一个更大的哈希表中。
扩容的条件
源码#xff1a;
func mapassign(t *maptype, h *hmap, key unsafe.…扩容
在 Go 语言中当 map 的元素数量达到一定阈值时会触发扩容操作以保持性能。这个过程称为 rehashing即重新散列所有的键值对到一个更大的哈希表中。
扩容的条件
源码
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {// 省略代码...// Did not find mapping for key. Allocate new cell add entry.// If we hit the max load factor or we have too many overflow buckets,// and were not already in the middle of growing, start growing.if !h.growing() (overLoadFactor(h.count1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {hashGrow(t, h)goto again // Growing the table invalidates everything, so try again}// 省略代码...
}mapassign 函数会在以下两种情况发生时触发哈希的扩容
负载因子已经超过 6.5哈希使用了太多溢出桶
不过因为 Go 语言哈希的扩容不是一个原子的过程所以还需要判断当前哈希是否已经处于扩容状态避免二次扩容造成混乱即!h.growing()。
负载因子
默认负载因子Go 的 map 通常会在平均每个桶有超过6.5个元素时触发扩容。
也就是说当 map中数据总个数 / 桶个数 6.5 引发翻倍扩容。而6.5如何来的看源码 // Maximum average load of a bucket that triggers growth is bucketCnt*13/16 (about 80% full)// Because of minimum alignment rules, bucketCnt is known to be at least 8.// Represent as loadFactorNum/loadFactorDen, to allow integer math.loadFactorDen 2loadFactorNum loadFactorDen * abi.MapBucketCount * 13 / 16bucketCntabi.MapBucketCount bucketCnt 是每个桶bucket中可以存储的键值对数量。 在Go中这个值通常是8。源码 // Maximum number of key/elem pairs a bucket can hold.MapBucketCountBits 3 // log2 of number of elements in a bucket.MapBucketCount 1 MapBucketCountBits // 1左移三位就是二进制的1000 就是十进制的8负载因子Load Factor 负载因子决定了在何时需要对 map 进行扩容。最大平均负载被设定为桶容量的80%即每个桶大约80%满时会触发扩容。 loadFactorNum 和 loadFactorDen 使用分数形式来表示负载因子以便使用整数运算而不是浮点运算这样可以提高计算效率和精度。loadFactorDen 2 是分母用于简化整数运算。loadFactorNum loadFactorDen * abi.MapBucketCount * 13 / 16 是分子。
解读源码可以知道最大负载因子被设置为 loadFactorNum/loadFactorDen 13/2 6.5
扩容的方式
扩容方法hashGrow的源码
func hashGrow(t *maptype, h *hmap) {// If weve hit the load factor, get bigger.// Otherwise, there are too many overflow buckets,// so keep the same number of buckets and grow laterally.bigger : uint8(1)if !overLoadFactor(h.count1, h.B) {bigger 0h.flags | sameSizeGrow}oldbuckets : h.bucketsnewbuckets, nextOverflow : makeBucketArray(t, h.Bbigger, nil)...// commit the grow (atomic wrt gc)h.B bigger // 如果不是超过负载因子触发的扩容则bigger0即B不变容量不变属于等量扩容...
}map的扩容机制如下
增量扩容当负载因子超过阈值时map会进行增量扩容。在这种情况下新创建的哈希表的大小是旧哈希表的两倍即h.B会增加1表示桶的数量翻倍。这种扩容方式称为增量扩容因为每次只会扩大一倍而不是无限制地增加桶的数量。等量扩容当溢出桶的数量过多但负载因子没有超过阈值时map会进行等量扩容。这种情况下新创建的哈希表的大小与旧哈希表相同即h.B不会增加桶的数量保持不变。这种扩容方式实际上是对现有数据的重新分布目的是减少溢出桶的数量使数据分布更加均匀提高map的性能。
具体步骤
1、检测扩容条件
每次向 map 中插入新元素后都会检查是否要触发扩容。
负载因子当负载因子超过6.5时会触发扩容。溢出桶如果溢出桶数量过多也会进行扩容。
2、分配新桶数组
增量扩容时会为map分配一个新的、更大的bucket数组。新数组大小是当前大小的两倍即B增加1使得bucket数量变为原来的两倍。等量扩容时新旧bucket数组大小保持不变但元素会被重新分布以减少溢出。
3、初始化迁移状态
将旧bucket数组指针保存到oldbuckets字段。buckets指向新创建的桶新桶中暂时还没有数据更新map结构中的其他相关字段以支持增量迁移。
func hashGrow(t *maptype, h *hmap) {...// commit the grow (atomic wrt gc)h.B biggerh.flags flagsh.oldbuckets oldbuckets // 原本的桶设置为oldbucketsh.buckets newbuckets // 把新的桶设置为当前bucketsh.nevacuate 0 // nevacuate记录已经完成搬移的bucket数量初始化为0表示从第一个bucket开始进行增量迁移。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 // 将原来使用过的所有溢出桶引用保存到extra.oldoverflow, 这样可以在需要时访问这些老的数据结构以完成迁移操作。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().
}4、迁移数据
每次对map进行插入、删除或查找操作时都会调用evacuate函数来逐步搬移旧桶中的元素到新桶中。
func growWork(t *maptype, h *hmap, bucket uintptr) {// make sure we evacuate the oldbucket corresponding// to the bucket were about to use// 接下来的操作是为了确保将要使用的bucket对应的旧bucket已经被搬空。evacuate(t, h, bucketh.oldbucketmask())// bucket h.oldbucketmask() 计算出当前访问的新桶对应的旧桶编号。// 调用evacuate函数来处理这个旧桶将其元素搬到新结构中。// evacuate one more oldbucket to make progress on growing// 接下来会额外再处理一个旧桶以推进整个扩容过程。if h.growing() {evacuate(t, h, h.nevacuate)}
}5、搬移逻辑
**增量扩容**对于每个需要搬移的旧桶将其所有元素重新计算哈希并放置到新的对应位置上。 在进行扩容时因为 bucket 数量翻倍假设从 N 变为 2N原有每个 bucket 索引会映射到两个可能的索引上oldbucket和oldbucket N 假设原来有 8 个 buckets则 oldbuckets 的索引范围是 [0,7]。在扩容后buckets 数变为16则每个 oldbucket 对应两个 new buckets Bucket 0 映射到 New Bucket 0 和 New Bucket 8Bucket 1 映射到 New Bucket 1 和 New Bucket 9… 对于正在迁移中的每个 key, 再次计算其 hash 值根据hash值的 底B位 来决定将此键值对分流道那个新桶中。 例如如果有 16 (即 2 4 2^4 24 ) 个 buckets则需要最低的四位B4来确定 bucket 索引。 B的值在原来的基础上已加1也就意味着通过多1位来计算此键值对要分流到新桶位置 当新增的位的值为 0则数据会迁移到与旧桶编号一致的位置 oldbucket。当新增的位的值为 1则数据会迁移到翻倍后对应编号位置 oldbucket N。 **等量扩容**重新计算 Hash 对于每个 key使用相同或可能更新的 hash 函数再次计算其 hash 值。这可能涉及到使用新的随机种子 hash0 来确保更好地散列。由于 hash 函数或种子可能发生变化即使桶数没有增加key 的 hash 值也可能与之前不同。以确保旧桶数据能比之前更均匀的散列不同桶中
6、完成迁移
当所有旧桶都被处理完毕后即所有元素都已成功从旧结构移动到新结构将原来指向旧 hashtable 的指针指向新 hashtable此时可以释放旧bucket数组所占用的内存资源。
