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 索引会映射到两个可能的索引上：oldbucket和oldbucket + 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$ ) 个 buckets，则需要最低的四位（B=4）来确定 bucket 索引。

  • B的值在原来的基础上已加1，也就意味着通过多1位来计算此键值对要分流到新桶位置：

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

6、完成迁移

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