Golang Map 深度剖析：原理、实践与面试要点
嘿，小伙伴们！我是 k 哥。今天，咱们来聊聊 Map 。
在 Go 语言这个神奇的世界里，Map 这个有点神秘的数据结构一直都是开发者们特别关注的。
你是不是在用 Map 的时候，对它里面咋工作的感到好奇？是不是碰到复杂操作的时候，特别想弄明白它背后的原理？别着急，今天这篇文章就带你走进 Go 语言 Map 那个神秘的世界，帮你一层一层揭开它的面纱！
从底层的原理，到最佳实践，再到高频面试题的分析，这篇文章会从各个方面满足你的求知心。不管你是刚学的新手，还是经验丰富的老手，相信都能从这里得到宝贵的知识，受到启发。准备好跟我一起开始这场精彩的探索旅程了不？
1 原理
1.1 数据结构
Map 所涉及的核心数据结构包括两个，即 hmap 和 bmap ：
-
每当创建一个 map 对象时，在底层都会创建一个 hmap 结构，以用于存储 map 的长度、hash 种子、状态等基础信息。
-
hmap 指针类型的成员变量 buckets ，指向 bmap 数组。bmap 用于存储键值对。对于相同的键，每次进行 hash 操作后都会定位到 buckets 相同的索引位置进行访问。
-
每个 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 结构，其成员的含义如下：
-
count ：表示 map 中的数据个数，与 len() 函数相对应。
-
flags ：属于标记字段，用于标记是否正在进行读写操作，以便实现并发读写的检测。
-
B ：代表桶的数量，hash 桶 buckets 的数量为 2^B 个。
-
noverflow ：是溢出桶数量的近似值。
-
hash0 ：为 hash 种子，用于计算 key 的 hash 值。
-
buckets ：是指向由 2^B 个桶所组成的数组的指针。
-
oldbuckets ：指向扩容前的旧 buckets 数组，仅在 map 扩容时发挥作用。
-
nevacuate ：作为计数器，用于标示扩容后搬迁的进度，服务于渐进式迁移。
-
extra ：用于保存溢出桶和未使用溢出桶切片的首地址。
1.1.2 bmap
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 个成员变量分配内存）：
-
tophash 数组，用于存储每个 key hash 之后的高位 hash 值。
-
key 数组，用于存储 key。
-
value 数组，用于存储 value。
-
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)
}
}
-
对 nil map写入，会panic
-
对正在被访问的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().
}
扩容迁移最为关键的有以下三点：
-
渐进式 rehash。为了避免在扩容时一次性把大量数据复制到新的 buckets 中，从而引发性能方面的问题，golang 采用了渐进式 rehash 的方式，把数据迁移分散到每一次对 map 的写操作里，每次写操作都会触发迁移两个桶。
-
扩容时机的判断。每次进行写操作时，要是在 key 所对应的桶链表中找不到空位置来存放，如果 buckets 的负载过高（容易出现 hash 冲突）或者溢出桶太多（这样遍历链表的时间就会变长），就会触发扩容。
-
扩容 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
}
-
通过 hash 找到桶的位置。
-
对桶链表进行遍历，查找 key 相等的位置以及空位置。
-
倘若既不存在 key 相等的位置，也不存在空位置，那就申请溢出桶，将溢出桶中 index 为 0 的位置当作 key 的存放位置。
-
插入 key ，并把 value 的地址返回，在编译器进行编译时，会添加一段代码，向返回地址所在的内存空间写入 value 。
1.2.4 整体流程串联
// 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().
}
整体写入流程如下：
-
进行 hmap 是否为 nil 的检查。若为空，则触发 panic 。
-
进行并发读写的检查，倘若已经设置了并发读写标记，则抛出“concurrent map writes”异常。
-
处理桶迁移。如果正在扩容，把 key 所在旧桶的数据迁移到对应的新桶，同时迁移 index 为 h.nevacuate 的桶，迁移完成后 h.nevacuate 自增，更新迁移进度。若所有桶迁移完毕，则清除正在扩容的标记（使 h.oldbuckets 为 nil ）。
-
查找 key 所在的位置，并记录桶链表的第一个空闲位置（若此 key 之前不存在，则将该位置作为插入位置）。
-
若此 key 在桶链表中不存在，判断是否需要扩容，若溢出桶过多，则进行相同容量的扩容，否则进行双倍容量的扩容。
-
若桶链表没有空闲位置，则申请溢出桶来存放 key - value 对。
-
设置 key 和 tophash[i] 的值。
-
返回 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
}
删除的内部流程如下：
-
进行并发读写检查。若对正在被访问的 map 进行写入操作，会抛出“concurrent map writes”异常（并非 panic ），且该异常不能被 defer 捕获。
-
处理桶迁移。如果 map 处于正在扩容的状态，则迁移两个桶。
-
定位 key 所在的位置。
-
删除 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 底层的实现是无法保障顺序的：
-
Go 语言 map 的底层实现为哈希表，在进行插入操作时，会对 key 进行 hash 运算。这致使数据并非按顺序存储，遍历顺序与插入顺序不一致。（遍历顺序和插入顺序不一致）
-
map 在扩容后，会出现 key 的搬迁情况。原本落在同一个 bucket 中的 key，在搬迁后，有些 key 可能会去到其他 bucket 。而遍历的过程，即使按照顺序遍历 bucket，同时按顺序遍历 bucket 中的 key 。搬迁后，key 的位置发生了重大变化，有些 key 被迁移走了，有些 key 则保持原地不动。如此一来，前后两次遍历的顺序也会不一样。（两次遍历顺序不一致）
因此，为避免误用，在遍历 map 时，golang 并非固定地从 0 号 bucket 开始遍历，每次都是从一个随机值序号的 bucket 开始，并且是从这个 bucket 的一个随机序号的 cell 开始遍历。这样的实现方式，即便已经初始化好了一个 map ，并且不对这个 map 进行任何操作，即不会发生扩容，遍历顺序也是不固定的。
2 最佳实践
- 预分配容量。在初始化
map时，如果你知道大致的键值对数量，可以使用make函数预分配容量，以减少重新哈希的次数。预分配容量可以提高map的性能，特别是当插入大量元素时。
m := make(map[string]int, 2000) // 预分配容量为2000
-
优化键的选择。选择适合的键类型也可以影响性能。键类型应该是可比较的（支持
==操作），并且尽量选择结构简单的类型，比如整数或字符串。复杂的结构体类型作为键可能会影响性能。 -
使用并发安全的Map：如果需要在多个goroutine中并发访问Map，使用锁或分段锁。
-
避免频繁的内存分配。在Map的使用过程中，尽量避免频繁地增加和删除键值对，因为这可能导致频繁的内存分配和垃圾回收。
-
避免GC：内存需要使用Map缓存大量数据时，map的key和value避免存储指针类型且大小要小于128字节(可以使用开源库bigcache或freecache等)，避免因为gc扫描，引起接口延时抖动。
3 高频面试题
- map并发安全吗？
并发不安全
- 多个 goroutine 对同一个 map 写会 panic，异常是否可以用 defer 捕获？
不能被捕获
- map 循环是有序的还是无序的？
无序的，每次迭代都会从不同的桶，桶内不同位置开始。
- map 如何顺序读取？
如果希望按照特定顺序遍历 map，可以先将键或值存储到切片中，然后对切片进行排序，最后再遍历切片。
- map 中删除一个 key，它的内存会释放么？
伪删除，不会马上释放，等下次扩容数据迁移时会释放
- 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 中添加元素
- 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 采用了渐进式的数据迁移方式。
- map底层，hash冲突除了链地址法以外还可以使用什么数据结构解决？
可以借鉴Java，采用红黑树的方式解决hash冲突。Java中的HashMap在解决哈希冲突时，会随着冲突的增多而将链表转换为平衡树（红黑树），这种转换发生在链表长度超过某个阈值（默认为8）时，以提高搜索效率。这是因为当链表变得很长时，遍历链表的时间复杂度为O(n)，而平衡树的搜索时间复杂度为O(log n)，因此在包含大量元素且发生大量冲突的情况下，平衡树可以提供更快的操作速度。
- 怎么处理对 map 进行并发访问？有没有其他方案？区别是什么？
-
读写锁。对整个map加上读写锁sync.RWMutex，锁粒度过大。
-
分段锁。将一个map分成几个片，按片加锁，粒度比一把大锁粒度细，锁争抢相对小一些，读写性能会更高。
-
sync.Map写性能比较差，读性能相对较高，读多写少性能较好，否则并发性能很差。(原因后续出一篇文章单独介绍，sync.Map在实践中应用比较少)
原文链接：<<链接Golang Map 深度剖析：原理、实践与面试要点>>
#我的求职思考##牛客解忧铺##牛客在线求职答疑中心#golang语言核心功能、原理、实践和面试
#go#
投递百度等公司10个岗位 >
查看4道真题和解析
