当前位置: 首页 > news >正文

10 go语言(golang) - 数据类型:哈希表(map)及原理(二)

扩容

在 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 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}// 省略代码...
}

mapassign 函数会在以下两种情况发生时触发哈希的扩容:

  1. 负载因子已经超过 6.5;
  2. 哈希使用了太多溢出桶;

不过因为 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 / 16
  1. bucketCnt(abi.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
      
  2. 负载因子(Load Factor)

    • 负载因子决定了在何时需要对 map 进行扩容。
    • 最大平均负载被设定为桶容量的80%(即每个桶大约80%满时会触发扩容)。
  3. loadFactorNum 和 loadFactorDen

    • 使用分数形式来表示负载因子,以便使用整数运算而不是浮点运算,这样可以提高计算效率和精度。
    • loadFactorDen = 2 是分母,用于简化整数运算。
    • loadFactorNum = loadFactorDen * abi.MapBucketCount * 13 / 16 是分子。

解读源码可以知道:最大负载因子被设置为 loadFactorNum/loadFactorDen = 13/2 = 6.5

扩容的方式

扩容方法hashGrow的源码:

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.bigger := uint8(1)if !overLoadFactor(h.count+1, h.B) {bigger = 0h.flags |= sameSizeGrow}oldbuckets := h.bucketsnewbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)...// commit the grow (atomic wrt gc)h.B += bigger // 如果不是超过负载因子触发的扩容,则bigger=0,即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 we're about to use// 接下来的操作是为了确保将要使用的bucket对应的旧bucket已经被搬空。evacuate(t, h, bucket&h.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 索引会映射到两个可能的索引上:oldbucketoldbucket + N

      • 假设原来有 8 个 buckets,则 oldbuckets 的索引范围是 [0,7]。在扩容后,buckets 数变为16,则每个 oldbucket 对应两个 new buckets:
        • Bucket 0 映射到 New Bucket 0 和 New Bucket 8
        • Bucket 1 映射到 New Bucket 1 和 New Bucket 9
    • 对于正在迁移中的每个 key, 再次计算其 hash 值,根据hash值的 底B位 来决定将此键值对分流道那个新桶中。

      • 例如,如果有 16 (即 2 4 2^4 24 ) 个 buckets,则需要最低的四位(B=4)来确定 bucket 索引。
    • B的值在原来的基础上已加1,也就意味着通过多1位来计算此键值对要分流到新桶位置:

      • 当新增的位的值为 0,则数据会迁移到与旧桶编号一致的位置 :oldbucket。
      • 当新增的位的值为 1,则数据会迁移到翻倍后对应编号位置 :oldbucket + N。
  • **等量扩容:**重新计算 Hash
    • 对于每个 key,使用相同或可能更新的 hash 函数再次计算其 hash 值。这可能涉及到使用新的随机种子 hash0 来确保更好地散列。
    • 由于 hash 函数或种子可能发生变化,即使桶数没有增加,key 的 hash 值也可能与之前不同。以确保旧桶数据能比之前更均匀的散列不同桶中

6、完成迁移

  • 当所有旧桶都被处理完毕后,即所有元素都已成功从旧结构移动到新结构(将原来指向旧 hashtable 的指针指向新 hashtable),此时可以释放旧bucket数组所占用的内存资源。

http://www.mrgr.cn/news/62843.html

相关文章:

  • 从此告别文献混乱:Zotero必装的40个插件
  • 详细分析与梳理Java基础中的重点知识:String类 ,Java字符串String类入门,剖析String类底层机制
  • 2023高等代数下【南昌大学】
  • ubuntu22.04安装向日葵
  • 【大模型开发指南】llamaindex配置deepseek、jina embedding及chromadb实现本地RAG及知识库(win系统、CPU适配)
  • iOS静态库(.a)及资源文件的生成与使用详解(OC版本)
  • LoRA微调大模型 - 从主元 pivot 的角度看矩阵的秩
  • 前端如何解决浏览器input输入框密码自动填充的问题
  • 【C/C++】字符/字符串函数(1)——由string.h提供
  • DBeaver如何插入一行新数据或者复制一行新数据,真方便
  • selenium无头浏览器截图并以邮件发送
  • 【设计模式】如何用C++实现依赖倒置
  • AcWing 1069 凸多边形的划分 区间dp + 高精度
  • 普通人的核心竞争力
  • Vim的配置
  • 杭州E类人才认定流程
  • C++设计模式结构型模式———桥接模式
  • 排序
  • 第十五章数据管理成熟度评估
  • 新160个crackme - 088-[KFC]fish‘s CrackMe
  • Telegram bot教程:通过BotFather设置Telegram bot的命令菜单
  • Java Executor ScheduledThreadPoolExecutor 总结
  • DBeaver如何查看ER图
  • Python定义与调用函数
  • 【AI时代】普通程序员想投身AI大模型行业,该如何快速入局
  • DAY67WEB 攻防-Java 安全JNDIRMILDAP五大不安全组件RCE 执行不出网