Golang Map 深度剖析:原理、实践与面试要点

嘿,小伙伴们!我是 k 哥。今天,咱们来聊聊 Map 。

在 Go 语言这个神奇的世界里,Map 这个有点神秘的数据结构一直都是开发者们特别关注的。

你是不是在用 Map 的时候,对它里面咋工作的感到好奇?是不是碰到复杂操作的时候,特别想弄明白它背后的原理?别着急,今天这篇文章就带你走进 Go 语言 Map 那个神秘的世界,帮你一层一层揭开它的面纱!

从底层的原理,到最佳实践,再到高频面试题的分析,这篇文章会从各个方面满足你的求知心。不管你是刚学的新手,还是经验丰富的老手,相信都能从这里得到宝贵的知识,受到启发。准备好跟我一起开始这场精彩的探索旅程了不?

1 原理

1.1 数据结构

alt

Map 所涉及的核心数据结构包括两个,即 hmap 和 bmap :

  1. 每当创建一个 map 对象时,在底层都会创建一个 hmap 结构,以用于存储 map 的长度、hash 种子、状态等基础信息。

  2. hmap 指针类型的成员变量 buckets ,指向 bmap 数组。bmap 用于存储键值对。对于相同的键,每次进行 hash 操作后都会定位到 buckets 相同的索引位置进行访问。

  3. 每个 bmap 能够存储 8 个键值对,并且,每个 bmap 设有一个指针,当某个 bmap 存满时,就会申请新的 bmap 进行存储,并与前一个 bmap 构成链表。(通过链地址法解决冲突)

1.1.1 hmap

const (
    // Maximum average load of a bucket that triggers growth is 6.5.
    // Represent as loadFactorNum/loadFactorDen, to allow integer math.
    loadFactorNum = 13
    loadFactorDen = 2
 )

// A header for a Go map.
type hmap struct {
    // Note: the format of the hmap is also encoded in cmd/compile/internal/reflectdata/reflect.go.
    // Make sure this stays in sync with the compiler's definition.
    count     int // # live cells == size of map.  Must be first (used by len() builtin)
    flags     uint8
    B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
    noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
    hash0     uint32 // hash seed

    buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
    oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
    nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)

    extra *mapextra // optional fields
}

// mapextra holds fields that are not present on all maps.
type mapextra struct {
    // If both key and elem do not contain pointers and are inline, then we mark bucket
    // type as containing no pointers. This avoids scanning such maps.
    // However, bmap.overflow is a pointer. In order to keep overflow buckets
    // alive, we store pointers to all overflow buckets in hmap.extra.overflow and hmap.extra.oldoverflow.
    // overflow and oldoverflow are only used if key and elem do not contain pointers.
    // overflow contains overflow buckets for hmap.buckets.
    // oldoverflow contains overflow buckets for hmap.oldbuckets.
    // The indirection allows to store a pointer to the slice in hiter.
    overflow    *[]*bmap // 溢出桶数组指针
    oldoverflow *[]*bmap // 迁移过程中,旧溢出桶数组指针

    // nextOverflow holds a pointer to a free overflow bucket.
    nextOverflow *bmap // 还未使用的,提前分配的溢出桶链表
}



每创建一个 map 对象,在 Go 语言底层都会创建 hmap 结构,其成员的含义如下:

  1. count :表示 map 中的数据个数,与 len() 函数相对应。

  2. flags :属于标记字段,用于标记是否正在进行读写操作,以便实现并发读写的检测。

  3. B :代表桶的数量,hash 桶 buckets 的数量为 2^B 个。

  4. noverflow :是溢出桶数量的近似值。

  5. hash0 :为 hash 种子,用于计算 key 的 hash 值。

  6. buckets :是指向由 2^B 个桶所组成的数组的指针。

  7. oldbuckets :指向扩容前的旧 buckets 数组,仅在 map 扩容时发挥作用。

  8. nevacuate :作为计数器,用于标示扩容后搬迁的进度,服务于渐进式迁移。

  9. extra :用于保存溢出桶和未使用溢出桶切片的首地址。 

1.1.2 bmap

alt

const (
    // Maximum number of key/elem pairs a bucket can hold.
    bucketCntBits = 3
    bucketCnt     = 1 << bucketCntBits
)

// A bucket for a Go map.
type bmap struct {
    // tophash generally contains the top byte of the hash value
    // for each key in this bucket. If tophash[0] < minTopHash,
    // tophash[0] is a bucket evacuation state instead.
    tophash [bucketCnt]uint8
    // Followed by bucketCnt keys and then bucketCnt elems.
    
    // Followed by an overflow pointer.
}

bmap 主要用于存储 key-value 对,每个 bmap 能够存储 8 个 key-value 对。bmap 包含 4 个成员变量(尽管在源码中只有一个成员变量 tophash,但实际上在申请内存时,Go 语言会依据 key、value 的具体类型,额外为另外 3 个成员变量分配内存):

  1. tophash 数组,用于存储每个 key hash 之后的高位 hash 值。

  2. key 数组,用于存储 key。

  3. value 数组,用于存储 value。

  4. overflow 溢出指针,指向了下一个 bmap 的地址。

bmap 有个溢出桶指针能指向溢出桶,那 extra 里为啥还得用 *[]*bmap 结构来存所有的溢出桶呢?

这主要是因为 gc 的原因。在早前的 Go 语言版本里,gc 会把 buckets 里的所有对象都扫一遍。要是 map 存的 key-value 对特别多,gc 能花上几百毫秒到好几秒,这就会让一些用 Go 语言开发的服务,接口超时超得厉害。

为了处理这个情况,Go 语言官方改了 map 的实现。要是 map 满足下面这两个条件,那 bmap 里除了 overflow ,就没别的指针了,而且会被 gc 标记成不用扫描:

  • key 和 value 不是指针类型,里面也不含指针(int 类型行,string 类型不行,因为 string 底层的数据结构里有指针)。

  • key 和 value 的大小得小于 128 字节。

但是 bmap.overflow 是指针类型,如果 gc 不扫 buckets ,溢出桶就可能被 gc 错误地回收掉。为了不让这种情况发生,就在 extra 里用 *[]*bmap 来存溢出桶,这样 gc 就能通过 []*bmap 扫到溢出桶(不用扫桶里面的东西),也就不会把溢出桶错误回收了。

1.2 插入或更新

1.2.1 2种异常情况处理

// Like mapaccess, but allocates a slot for the key if it is not present in the map.
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    // 为nil则panic
    if h == nil {
        panic(plainError("assignment to entry in nil map"))
    }
    // 并发读写会抛异常,且不能被defer捕获
    if h.flags&hashWriting != 0 {
        throw("concurrent map writes")
    }
    // 计算key对应的hash值
    hash := t.hasher(key, uintptr(h.hash0))

    // 设置正在写标记
    h.flags ^= hashWriting
    // 初始化,但是桶为空的,会自动创建桶数组,读写不会panic
    if h.buckets == nil {
        h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
    }
}
  1. 对 nil map写入,会panic

  2. 对正在被访问的map写入,抛concurrent map writes异常(非panic),且不能被defer捕获。

1.2.2 扩容处理

// Like mapaccess, but allocates a slot for the key if it is not present in the map.
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {

again:
    // 根据hash值定位桶
    bucket := hash & bucketMask(h.B)
    // 渐进式rehash。如果正在扩容,将oldbuckets对应的桶数据迁移到buckets对应的桶,同时迁移index为h.nevacuate的桶,迁完h.nevacuate++
    if h.growing() {
        growWork(t, h, bucket) 
    }

    // 查找对应key应该插入或更新位置。
    ...

    // 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.
    // 扩容时机判断。是否进行扩容判断。如果map负载太高或者溢出桶太多,则触发扩容。
    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
    }
}

// growing reports whether h is growing. The growth may be to the same size or bigger.
func (h *hmap) growing() bool {
    return h.oldbuckets != nil
}

// 桶迁移
func growWork(t *maptype, h *hmap, bucket uintptr) {
    // make sure we evacuate the oldbucket corresponding
    // to the bucket we're about to use
    evacuate(t, h, bucket&h.oldbucketmask())

    // evacuate one more oldbucket to make progress on growing
    if h.growing() {
        evacuate(t, h, h.nevacuate)
    }
}

// 扩容设置,包括新容量设定
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.
    // 如果负载太高,则桶数组双倍扩容,否则桶数组不扩容,只做重新rehash,重新rehash会移除被删除的key
    bigger := uint8(1)
    // 溢出桶过多,容量不变
    if !overLoadFactor(h.count+1, h.B) {
        bigger = 0
        h.flags |= sameSizeGrow
    }
    oldbuckets := h.buckets
    newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)

    flags := h.flags &^ (iterator | oldIterator)
    if h.flags&iterator != 0 {
        flags |= oldIterator
    }
    // commit the grow (atomic wrt gc)
    h.B += bigger
    h.flags = flags
    h.oldbuckets = oldbuckets
    h.buckets = newbuckets
    h.nevacuate = 0
    h.noverflow = 0
    // the actual copying of the hash table data is done incrementally
    // by growWork() and evacuate().
}

扩容迁移最为关键的有以下三点:

  1. 渐进式 rehash。为了避免在扩容时一次性把大量数据复制到新的 buckets 中,从而引发性能方面的问题,golang 采用了渐进式 rehash 的方式,把数据迁移分散到每一次对 map 的写操作里,每次写操作都会触发迁移两个桶。

  2. 扩容时机的判断。每次进行写操作时,要是在 key 所对应的桶链表中找不到空位置来存放,如果 buckets 的负载过高(容易出现 hash 冲突)或者溢出桶太多(这样遍历链表的时间就会变长),就会触发扩容。

  3. 扩容 buckets 容量大小的设定。要是因为溢出桶过多而触发的迁移,那么新的 buckets 数组和 oldbuckets 的长度会保持一致,原因在于 hash 函数均匀的情况下,只可能是删除操作导致了溢出桶过多,重新进行 rehash ,会把被删除的 key 所占的空间释放出来,进而减少溢出桶的数量;要是因为负载过高而触发的扩容,那么新的 buckets 数组等于 2 倍的 oldbuckets ,以此来减少 hash 冲突。 

1.2.3 定位key和value位置

// Like mapaccess, but allocates a slot for the key if it is not present in the map.
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {

again:
    // 根据hash值定位桶
    bucket := hash & bucketMask(h.B)
    // 桶地址
    b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
    // hash值的高位用于定位桶内位置
    top := tophash(hash)

    var inserti *uint8
    var insertk unsafe.Pointer
    var elem unsafe.Pointer
bucketloop:
    // 查找插入或更新位置。外层循环是桶和溢出桶构成的链表迭代,内层循环是桶内迭代
    for {
        for i := uintptr(0); i < bucketCnt; i++ {
            if b.tophash[i] != top {
                // 桶内找到的第一个空位置,先记下来,后续如果没找到和传入的key相等的数据,则在此位置是插入位置
                // 否则,找到之前已经存在的key位置更新。
                if isEmpty(b.tophash[i]) && inserti == nil {
                    inserti = &b.tophash[i]
                    insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
                    elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
                }
                // 桶和溢出桶构成的链表遍历完成,此位置之后没有数据,跳出循环。
                if b.tophash[i] == emptyRest {
                    break bucketloop
                }
                // 此位置已经有数据且高位hash值不相等(意味着key也不相等),继续往下找
                continue
            }
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            if t.indirectkey() {
                k = *((*unsafe.Pointer)(k))
            }
            // key不相等,继续往下找
            if !t.key.equal(key, k) {
                continue
            }
            // 此key已经存在
            // already have a mapping for key. Update it.
            if t.needkeyupdate() {
                typedmemmove(t.key, k, key)
            }
            elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
            // 已经找到插入value位置,直接跳到函数末尾返回
            goto done
        }
        // 继续遍历溢出桶查找
        ovf := b.overflow(t)
        if ovf == nil {
            break
        }
        b = ovf
    }

    // Did not find mapping for key. Allocate new cell & add entry.
    if inserti == nil {
        // The current bucket and all the overflow buckets connected to it are full, allocate a new one.
        // 申请溢出桶
        newb := h.newoverflow(t, b)
        inserti = &newb.tophash[0]
        insertk = add(unsafe.Pointer(newb), dataOffset)
        elem = add(insertk, bucketCnt*uintptr(t.keysize))
    }

    // store new key/elem at insert position
    if t.indirectkey() {
        kmem := newobject(t.key)
        *(*unsafe.Pointer)(insertk) = kmem
        insertk = kmem
    }
    if t.indirectelem() {
        vmem := newobject(t.elem)
        *(*unsafe.Pointer)(elem) = vmem
    }
    typedmemmove(t.key, insertk, key)
    *inserti = top
    h.count++

done:
    if h.flags&hashWriting == 0 {
        throw("concurrent map writes")
    }
    h.flags &^= hashWriting
    if t.indirectelem() {
        elem = *((*unsafe.Pointer)(elem))
    }
    // 返回value应该插入的地址
    return elem
}
  1. 通过 hash 找到桶的位置。

  2. 对桶链表进行遍历,查找 key 相等的位置以及空位置。

  3. 倘若既不存在 key 相等的位置,也不存在空位置,那就申请溢出桶,将溢出桶中 index 为 0 的位置当作 key 的存放位置。

  4. 插入 key ,并把 value 的地址返回,在编译器进行编译时,会添加一段代码,向返回地址所在的内存空间写入 value 。

1.2.4 整体流程串联

alt

// Like mapaccess, but allocates a slot for the key if it is not present in the map.
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    // 1.hmap为nil检查,为空则panic
    if h == nil {
        panic(plainError("assignment to entry in nil map"))
    }
    // 2.并发读写会抛异常,且不能被defer捕获
    if h.flags&hashWriting != 0 {
        throw("concurrent map writes")
    }
    // 计算key对应的hash值
    hash := t.hasher(key, uintptr(h.hash0))

    // Set hashWriting after calling t.hasher, since t.hasher may panic,
    // in which case we have not actually done a write.
    // 设置正在写标记
    h.flags ^= hashWriting
    // 初始化,但是桶为空的,会自动创建桶数组,读写不会panic
    if h.buckets == nil {
        h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
    }

again:
    // 根据hash值定位桶
    bucket := hash & bucketMask(h.B)
    
    // 3.桶迁移。如果正在扩容,将oldbuckets对应的桶数据迁移到buckets对应的桶,同时迁移index为h.nevacuate的桶,迁完h.nevacuate++
    if h.growing() {
        growWork(t, h, bucket) 
    }
    // 桶地址
    b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
    // hash值的高位用于定位桶内位置
    top := tophash(hash)

    var inserti *uint8
    var insertk unsafe.Pointer
    var elem unsafe.Pointer
bucketloop:
    // 4.查找key所在位置。外层循环是桶和溢出桶构成的链表迭代,内层循环是桶内迭代
    for {
        for i := uintptr(0); i < bucketCnt; i++ {
            if b.tophash[i] != top {
                // 桶内找到的第一个空位置,先记下来,后续如果没找到和传入的key相等的数据,则在此位置是插入位置
                // 否则,找到之前已经存在的key位置更新。
                if isEmpty(b.tophash[i]) && inserti == nil {
                    inserti = &b.tophash[i]
                    insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
                    elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
                }
                // 桶和溢出桶构成的链表遍历完成,此位置之后没有数据,跳出循环。
                if b.tophash[i] == emptyRest {
                    break bucketloop
                }
                // 此位置已经有数据且高位hash值不相等(意味着key也不相等),继续往下找
                continue
            }
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            if t.indirectkey() {
                k = *((*unsafe.Pointer)(k))
            }
            // key不相等,继续往下找
            if !t.key.equal(key, k) {
                continue
            }
            // 此key已经存在
            // already have a mapping for key. Update it.
            if t.needkeyupdate() {
                typedmemmove(t.key, k, key)
            }
            elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
            // 已经找到插入value位置,直接跳到函数末尾返回
            goto done
        }
        // 继续遍历溢出桶查找
        ovf := b.overflow(t)
        if ovf == nil {
            break
        }
        b = ovf
    }

    // 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.
    // 5.扩容判断和容量设置。是否进行扩容判断。如果map负载太高或者溢出桶太多,则触发扩容。
    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
    }
    // 6.申请溢出桶。
    if inserti == nil {
        // The current bucket and all the overflow buckets connected to it are full, allocate a new one.
        // 当前桶及溢出桶构成的链表已满,分配一个新溢出桶
        newb := h.newoverflow(t, b)
        inserti = &newb.tophash[0]
        insertk = add(unsafe.Pointer(newb), dataOffset)
        elem = add(insertk, bucketCnt*uintptr(t.keysize))
    }
    // 7.设置key和tophash[i]的值
    // store new key/elem at insert position
    if t.indirectkey() {
        kmem := newobject(t.key)
        *(*unsafe.Pointer)(insertk) = kmem
        insertk = kmem
    }
    if t.indirectelem() {
        vmem := newobject(t.elem)
        *(*unsafe.Pointer)(elem) = vmem
    }
    typedmemmove(t.key, insertk, key)
    *inserti = top
    h.count++

done:
    if h.flags&hashWriting == 0 {
        throw("concurrent map writes")
    }
    h.flags &^= hashWriting
    if t.indirectelem() {
        elem = *((*unsafe.Pointer)(elem))
    }
    // 8.返回value应该插入的地址,会在此地址插入value
    return elem
}

// growing reports whether h is growing. The growth may be to the same size or bigger.
func (h *hmap) growing() bool {
    return h.oldbuckets != nil
}

// 桶迁移
func growWork(t *maptype, h *hmap, bucket uintptr) {
    // make sure we evacuate the oldbucket corresponding
    // to the bucket we're about to use
    evacuate(t, h, bucket&h.oldbucketmask())

    // evacuate one more oldbucket to make progress on growing
    if h.growing() {
        evacuate(t, h, h.nevacuate)
    }
}

// bucketShift returns 1<<b, optimized for code generation.
func bucketShift(b uint8) uintptr {
    // Masking the shift amount allows overflow checks to be elided.
    return uintptr(1) << (b & (sys.PtrSize*8 - 1))
}

// bucketMask returns 1<<b - 1, optimized for code generation.
func bucketMask(b uint8) uintptr {
    return bucketShift(b) - 1
}

// noldbuckets calculates the number of buckets prior to the current map growth.
func (h *hmap) noldbuckets() uintptr {
    oldB := h.B
    if !h.sameSizeGrow() {
        oldB--
    }
    return bucketShift(oldB)
}

// sameSizeGrow reports whether the current growth is to a map of the same size.
func (h *hmap) sameSizeGrow() bool {
    return h.flags&sameSizeGrow != 0
}
// oldbucketmask provides a mask that can be applied to calculate n % noldbuckets().
func (h *hmap) oldbucketmask() uintptr {
    return h.noldbuckets() - 1
}

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 = 0
        h.flags |= sameSizeGrow
    }
    oldbuckets := h.buckets
    newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)

    flags := h.flags &^ (iterator | oldIterator)
    if h.flags&iterator != 0 {
        flags |= oldIterator
    }
    // commit the grow (atomic wrt gc)
    h.B += bigger
    h.flags = flags
    h.oldbuckets = oldbuckets
    h.buckets = newbuckets
    h.nevacuate = 0
    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
        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().
}

整体写入流程如下:

  1. 进行 hmap 是否为 nil 的检查。若为空,则触发 panic 。

  2. 进行并发读写的检查,倘若已经设置了并发读写标记,则抛出“concurrent map writes”异常。

  3. 处理桶迁移。如果正在扩容,把 key 所在旧桶的数据迁移到对应的新桶,同时迁移 index 为 h.nevacuate 的桶,迁移完成后 h.nevacuate 自增,更新迁移进度。若所有桶迁移完毕,则清除正在扩容的标记(使 h.oldbuckets 为 nil )。

  4. 查找 key 所在的位置,并记录桶链表的第一个空闲位置(若此 key 之前不存在,则将该位置作为插入位置)。

  5. 若此 key 在桶链表中不存在,判断是否需要扩容,若溢出桶过多,则进行相同容量的扩容,否则进行双倍容量的扩容。

  6. 若桶链表没有空闲位置,则申请溢出桶来存放 key - value 对。

  7. 设置 key 和 tophash[i] 的值。

  8. 返回 value 的地址。

1.3 删除

func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
    // 并发读写检查
    if h.flags&hashWriting != 0 {
        throw("concurrent map writes")
    }

    hash := t.hasher(key, uintptr(h.hash0))

    // Set hashWriting after calling t.hasher, since t.hasher may panic,
    // in which case we have not actually done a write (delete).
    h.flags ^= hashWriting

    bucket := hash & bucketMask(h.B)
    // 桶迁移。如果正在扩容,将oldbuckets对应的桶数据迁移到buckets对应的桶,同时迁移index为h.nevacuate的桶,迁完h.nevacuate++
    if h.growing() {
        growWork(t, h, bucket)
    }
    b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
    bOrig := b
    top := tophash(hash)
search:
    // 定位要删除的位置
    for ; b != nil; b = b.overflow(t) {
        for i := uintptr(0); i < bucketCnt; i++ {
            if b.tophash[i] != top {
                if b.tophash[i] == emptyRest {
                    break search
                }
                continue
            }
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            k2 := k
            if t.indirectkey() {
                k2 = *((*unsafe.Pointer)(k2))
            }
            if !t.key.equal(key, k2) {
                continue
            }
            // Only clear key if there are pointers in it.
            if t.indirectkey() {
                *(*unsafe.Pointer)(k) = nil
            } else if t.key.ptrdata != 0 {
                memclrHasPointers(k, t.key.size)
            }
            e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
            if t.indirectelem() {
                *(*unsafe.Pointer)(e) = nil
            } else if t.elem.ptrdata != 0 {
                memclrHasPointers(e, t.elem.size)
            } else {
                memclrNoHeapPointers(e, t.elem.size)
            }
            // 将要删除的位置i标记为emptyOne
            b.tophash[i] = emptyOne
            // If the bucket now ends in a bunch of emptyOne states,
            // change those to emptyRest states.
            // It would be nice to make this a separate function, but
            // for loops are not currently inlineable.
            if i == bucketCnt-1 {
                if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {
                    goto notLast
                }
            } else {
                if b.tophash[i+1] != emptyRest {
                    goto notLast
                }
            }
            // 此位置之后为emptyRest(即后面为空位置),则从此位置往前遍历,将emptyOne都设置为emptyRest
            for {
                b.tophash[i] = emptyRest
                if i == 0 {
                    if b == bOrig {
                        break // beginning of initial bucket, we're done.
                    }
                    // Find previous bucket, continue at its last entry.
                    c := b
                    for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {
                    }
                    i = bucketCnt - 1
                } else {
                    i--
                }
                if b.tophash[i] != emptyOne {
                    break
                }
            }
        notLast:
            h.count--
            // Reset the hash seed to make it more difficult for attackers to
            // repeatedly trigger hash collisions. See issue 25237.
            if h.count == 0 {
                h.hash0 = fastrand()
            }
            break search
        }
    }

    if h.flags&hashWriting == 0 {
        throw("concurrent map writes")
    }
    h.flags &^= hashWriting
}

删除的内部流程如下:

  1. 进行并发读写检查。若对正在被访问的 map 进行写入操作,会抛出“concurrent map writes”异常(并非 panic ),且该异常不能被 defer 捕获。

  2. 处理桶迁移。如果 map 处于正在扩容的状态,则迁移两个桶。

  3. 定位 key 所在的位置。

  4. 删除 key - value 对的占用。这里的删除实际上属于伪删除。只有在下次扩容时,被删除的key所占用的桶空间才会得到释放。

  • map 首先会将对应位置的 tophash[i] 设置为 emptyOne ,表示该位置已被删除。

  • 倘若 tophash[i] 后面还有有效的节点,则仅设置 emptyOne 标志,这意味着此节点后面仍存在有效的 key - value 对,后续在查找某个 key 时,此节点之后仍需继续查找。

  • 要是 tophash[i] 是桶链表的最后一个有效节点,则从此节点往前遍历,将链表最后面所有标志为 emptyOne 的位置,都设置为 emptyRest 。在查找某个 key 时,emptyRest 之后的节点无需继续查找。

  • 这种删除方式,通过少量的空间来避免桶链表和桶内数据的移动。

1.4 range迭代

// mapiterinit initializes the hiter struct used for ranging over maps.
// The hiter struct pointed to by 'it' is allocated on the stack
// by the compilers order pass or on the heap by reflect_mapiterinit.
// Both need to have zeroed hiter since the struct contains pointers.
func mapiterinit(t *maptype, h *hmap, it *hiter) {
    it.t = t
    it.h = h
    // grab snapshot of bucket state
    it.B = h.B
    it.buckets = h.buckets
   
    // decide where to start
    // 随机数r决定了从哪个桶,桶内的哪个位置迭代
    r := uintptr(fastrand())
    if h.B > 31-bucketCntBits {
        r += uintptr(fastrand()) << 31
    }
    // 随机桶开始迭代
    it.startBucket = r & bucketMask(h.B)
    // 桶内的随机位置开始迭代
    it.offset = uint8(r >> h.B & (bucketCnt - 1))
    // iterator state
    it.bucket = it.startBucket

    mapiternext(it)
}

在每次对 map 进行循环时,会调用 mapiterinit 函数,以确定迭代从哪个桶以及桶内的哪个位置起始。由于 mapiterinit 内部是通过随机数来决定起始位置的,所以 map 循环是无序的,每次循环所返回的 key - value 对的顺序都各不相同。

为何 golang 要从随机位置开始遍历桶,而非从0号桶开始顺序遍历呢?

主要原因在于担心开发人员在开发过程中依赖稳定的遍历顺序,然而 golang 底层的实现是无法保障顺序的:

  1. Go 语言 map 的底层实现为哈希表,在进行插入操作时,会对 key 进行 hash 运算。这致使数据并非按顺序存储,遍历顺序与插入顺序不一致。(遍历顺序和插入顺序不一致

  2. map 在扩容后,会出现 key 的搬迁情况。原本落在同一个 bucket 中的 key,在搬迁后,有些 key 可能会去到其他 bucket 。而遍历的过程,即使按照顺序遍历 bucket,同时按顺序遍历 bucket 中的 key 。搬迁后,key 的位置发生了重大变化,有些 key 被迁移走了,有些 key 则保持原地不动。如此一来,前后两次遍历的顺序也会不一样。(两次遍历顺序不一致

因此,为避免误用,在遍历 map 时,golang 并非固定地从 0 号 bucket 开始遍历,每次都是从一个随机值序号的 bucket 开始,并且是从这个 bucket 的一个随机序号的 cell 开始遍历。这样的实现方式,即便已经初始化好了一个 map ,并且不对这个 map 进行任何操作,即不会发生扩容,遍历顺序也是不固定的。 

2 最佳实践

  1. 预分配容量。在初始化map时,如果你知道大致的键值对数量,可以使用make函数预分配容量,以减少重新哈希的次数。预分配容量可以提高map的性能,特别是当插入大量元素时。
m := make(map[string]int, 2000) // 预分配容量为2000
  1. 优化键的选择。选择适合的键类型也可以影响性能。键类型应该是可比较的(支持==操作),并且尽量选择结构简单的类型,比如整数或字符串。复杂的结构体类型作为键可能会影响性能。

  2. 使用并发安全的Map:如果需要在多个goroutine中并发访问Map,使用锁或分段锁。

  3. 避免频繁的内存分配。在Map的使用过程中,尽量避免频繁地增加和删除键值对,因为这可能导致频繁的内存分配和垃圾回收。

  4. 避免GC:内存需要使用Map缓存大量数据时,map的key和value避免存储指针类型且大小要小于128字节(可以使用开源库bigcache或freecache等),避免因为gc扫描,引起接口延时抖动。

3 高频面试题

  1. map并发安全吗?

并发不安全

  1. 多个 goroutine 对同一个 map 写会 panic,异常是否可以用 defer 捕获?

不能被捕获

  1. map 循环是有序的还是无序的?

无序的,每次迭代都会从不同的桶,桶内不同位置开始。

  1. map 如何顺序读取?

如果希望按照特定顺序遍历 map,可以先将键或值存储到切片中,然后对切片进行排序,最后再遍历切片。

  1. map 中删除一个 key,它的内存会释放么?

伪删除,不会马上释放,等下次扩容数据迁移时会释放

  1. nil map 和空 map 有何不同?

nil map 是一个未初始化的 map,其值为nil(hmap是nil)。你不能向nil map 添加任何元素,否则会panic。但是,你可以从 nil map 中获取元素,这不会引发运行时错误,但总是返回元素类型的零值。

空 map 是一个已经初始化但没有包含任何元素的 map(构建了hmap,但成员变量buckets数组指针为空)。你可以向空 map 添加元素,也可以从空 map 中获取元素。

var m map[string]int // m 是一个 nil mapm["key"] = 1 // 运行时错误:panic: assignment to entry in nil mapm := make(map[string]int) // m 是一个空 mapm["key"] = 1 // 正常运行,向空 map 中添加元素

  1. map 的数据结构是什么?是怎么实现扩容的?

Go map 的底层实现是一种哈希表(数组 + 链表)结构,通过拉链法来消除哈希冲突。

扩容时机:

在每次有 key - value 对插入时,会判断是否需要扩容,满足以下两个条件之一即可扩容。

  • 当 Go map 中每个 bucket 桶存储的平均元素个数大于加载因子 loadFactor = 6.5(此为判断扩容的条件)时,map 底层会创建一个容量大小为原来两倍的新 buckets 数组。

  • 当 map 中的数据较少,但 overflow 指向的溢出桶 bucket 数量过多时,会致使溢出桶中的记录存储十分稀疏,排列不够紧凑,从而大量空间被浪费。此时就需要进行等量扩容/缩容(通常出现在之前数据被大量删除的场景下)。

如何扩容:

Golang 采用渐进式的数据迁移方式,每次对 map 进行写入和删除操作时,会将两个 bucket 的数据迁移到新的 buckets 中(一个是当前访问 key 所在的 bucket ,然后再多迁移一个 bucket )。其原因在于一次性迁移全部数据,所涉及的 CPU 资源和内存资源占用相对较多,在数据量较大时,会产生较大的延时,影响正常的业务逻辑,所以 Go 采用了渐进式的数据迁移方式。

  1. map底层,hash冲突除了链地址法以外还可以使用什么数据结构解决?

可以借鉴Java,采用红黑树的方式解决hash冲突。Java中的HashMap在解决哈希冲突时,会随着冲突的增多而将链表转换为平衡树(红黑树),这种转换发生在链表长度超过某个阈值(默认为8)时,以提高搜索效率。这是因为当链表变得很长时,遍历链表的时间复杂度为O(n),而平衡树的搜索时间复杂度为O(log n),因此在包含大量元素且发生大量冲突的情况下,平衡树可以提供更快的操作速度。

  1. 怎么处理对 map 进行并发访问?有没有其他方案?区别是什么?
  • 读写锁。对整个map加上读写锁sync.RWMutex,锁粒度过大。

  • 分段锁。将一个map分成几个片,按片加锁,粒度比一把大锁粒度细,锁争抢相对小一些,读写性能会更高。

  • sync.Map写性能比较差,读性能相对较高,读多写少性能较好,否则并发性能很差。(原因后续出一篇文章单独介绍,sync.Map在实践中应用比较少)

原文链接:<<链接Golang Map 深度剖析:原理、实践与面试要点>>

#我的求职思考##牛客解忧铺##牛客在线求职答疑中心#
Golang面试核心考点 文章被收录于专栏

golang语言核心功能、原理、实践和面试

全部评论
分享给大家一篇不错的文章,对Golang map写得很透彻#go#
点赞 回复 分享
发布于 08-17 21:51 北京
希望对大家有所帮助
点赞 回复 分享
发布于 08-18 09:03 广东

相关推荐

2 9 评论
分享
牛客网
牛客企业服务