Go Map的底层原理解析之遍历流程和扩容流程

Go Map的底层原理解析之遍历流程和扩容流程

引用

CSDN

1.

https://m.blog.csdn.net/Ccccjjjj174/article/details/145691210

Go语言中的Map是一种非常常用的数据结构，它基于哈希表实现，提供了高效的键值对存储和访问。本文将深入解析Go Map的底层实现原理，重点介绍其遍历流程和扩容机制。

Map的随机遍历

在Go中，Map的遍历是通过迭代器（hiter）来实现的。迭代器结构体包含了遍历所需的各种信息：

type hiter struct {
    key         unsafe.Pointer // 指向遍历得到的key的指针
    elem        unsafe.Pointer // 指向遍历得到的value的指针
    t           *maptype       // map类型，包含key、value类型大小等信息
    h           *hmap          // map的指针
    buckets     unsafe.Pointer // map的桶数组
    bptr        *bmap          // 当前遍历到的桶
    overflow    *[]*bmap       // 新老桶数组对应的溢出桶
    oldoverflow *[]*bmap       // 旧桶数组的溢出桶
    startBucket uintptr        // 遍历起始位置的桶索引
    offset      uint8          // 遍历起始位置的key-value对索引
    wrapped     bool           // 遍历是否穿越桶数组尾端回到头部
    B           uint8          // 桶数组的长度指数
    i           uint8          // 当前遍历到的key-value对在桶中的索引
    bucket      uintptr        // 当前遍历到的桶
    checkBucket uintptr        // 因为扩容流程的存在，需要额外检查的桶
}

迭代器的初始化

迭代器的初始化过程主要通过mapiterinit函数完成：

func mapiterinit(t *maptype, h *hmap, it *hiter) {
    it.t = t
    if h == nil || h.count == 0 {
        return
    }
    it.h = h
    it.B = h.B
    it.buckets = h.buckets
    if t.bucket.ptrdata == 0 {
        h.createOverflow()
        it.overflow = h.extra.overflow
        it.oldoverflow = h.extra.oldoverflow
    }
    // 通过随机数决定遍历的起始位置
    var r uintptr
    r = uintptr(fastrand())
    it.startBucket = r & bucketMask(h.B)
    it.offset = uint8(r >> h.B & (bucketCnt - 1))
    // 记录迭代器状态
    it.bucket = it.startBucket
    // 确保没有并发写操作
    if old := h.flags; old&(iterator|oldIterator) != iterator|oldIterator {
        atomic.Or8(&h.flags, iterator|oldIterator)
    }
    mapiternext(it)
}

开始遍历

遍历过程主要通过mapiternext函数实现：

func mapiternext(it *hiter) {
    h := it.h
    if h.flags&hashWriting != 0 {
        fatal("concurrent map iteration and map write")
    }
    t := it.t
    bucket := it.bucket
    b := it.bptr
    i := it.i
    checkBucket := it.checkBucket
next:
    if b == nil {
        // 已经遍历结束
        if bucket == it.startBucket && it.wrapped {
            it.key = nil
            it.elem = nil
            return
        }
        // 如果正在扩容
        if h.growing() && it.B == h.B {
            oldbucket := bucket & it.h.oldbucketmask()
            b = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
            if !evacuated(b) {
                checkBucket = bucket
            } else {
                b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize)))
                checkBucket = noCheck
            }
        } else {
            b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize)))
            checkBucket = noCheck
        }
        // 去遍历下一个桶
        bucket++
        if bucket == bucketShift(it.B) {
            bucket = 0
            it.wrapped = true
        }
        i = 0
    }
    // 开始遍历每一个kv对
    for ; i < bucketCnt; i++ {
        offi := (i + it.offset) & (bucketCnt - 1)
        if isEmpty(b.tophash[offi]) || b.tophash[offi] == evacuatedEmpty {
            continue
        }
        k := add(unsafe.Pointer(b), dataOffset+uintptr(offi)*uintptr(t.keysize))
        if t.indirectkey() {
            k = *((*unsafe.Pointer)(k))
        }
        e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+uintptr(offi)*uintptr(t.elemsize))
        // 处理扩容情况下的遍历顺序
        if checkBucket != noCheck && !h.sameSizeGrow() {
            if checkBucket>>(it.B-1) != uintptr(b.tophash[offi]&1) {
                continue
            }
        }
        // 如果未被迁移
        if (b.tophash[offi] != evacuatedX && b.tophash[offi] != evacuatedY) ||
            !(t.reflexivekey() || t.key.equal(k, k)) {
            it.key = k
            if t.indirectelem() {
                e = *((*unsafe.Pointer)(e))
            }
            it.elem = e
        } else {
            // 如果被迁移了，重新读取kv对
            rk, re := mapaccessK(t, h, k)
            if rk == nil {
                continue // key has been deleted
            }
            it.key = rk
            it.elem = re
        }
        it.bucket = bucket
        if it.bptr != b { // avoid unnecessary write barrier; see issue 14921
            it.bptr = b
        }
        it.i = i + 1
        it.checkBucket = checkBucket
        return
    }
    // 准备遍历下一个溢出桶
    b = b.overflow(t)
    i = 0
    goto next
}

扩容流程

Go语言中的Map是基于哈希表实现的，当元素数量增加或删除频繁时，为了维持高效访问，会触发扩容机制。扩容分为增量扩容（正常扩容）和等量扩容（整理扩容）。

触发扩容的条件

扩容的触发条件主要通过负载因子来判断：

// loadFactor 装载因子，count 是map中元素的个数，(2^B)是 普通桶的数量
loadFactor := count / (2^B)

• 当元素数量超过负载因子（默认6.5）与当前桶数的乘积时触发增量扩容。此时，新桶数为原来的两倍（2×），以减少哈希冲突。
• 当溢出桶的数量过多时，触发等量扩容。这种情况通常由频繁插入和删除导致，桶内出现大量空闲槽位或长溢出链。此时桶数不变，但数据会被重新整理，减少溢出桶。

扩容流程

1. 分配新桶

• 增量扩容：新桶数为旧桶数的两倍（2^B → 2^(B+1)）。
• 等量扩容：新桶数与旧桶数相同（2^B保持不变）。

2. 渐进式扩容

   为了避免一次性迁移所有桶带来的性能瓶颈，Go的Map扩容采用了增量迁移（或称“懒迁移”）的策略：

• 在每次对Map进行查找、插入或删除操作时，运行时会顺带将一部分旧桶的数据迁移到新桶中。这意味着迁移工作分摊到了每个操作上，从而摊平了扩容的开销。
• 桶的迁移过程：对于旧桶中的每个键值对，都会重新计算其哈希值，然后根据新桶数组的大小确定新的桶索引。

3. 顺序迁移

• 逐步推进：每次Map操作都会迁移少量旧桶，运行时更新growIdx，直到整个旧桶数组的所有桶都被迁移完成。具体而言，growIdx从0开始，然后开始迁移hash值在0上面的kv对，最后growIdx++，去准备迁移下一个。
• 扩容完成：当growIdx达到旧桶数组的长度时，说明所有数据都已经迁移到新桶中，此时旧桶数组会被废弃，Map完全过渡到新的哈希表结构中。

通过上述机制，Go语言的Map能够在保持高性能的同时，灵活应对数据量的变化，确保了数据访问的效率和稳定性。