重点

在上篇文章《go基础之map-增和改（二）》已经非常详细的描述了定位key所在的桶以及它所在桶的位置，如果对上篇有所了解之后，该篇博客理解起来就会非常容易。总的来说map的删除主要做了2件事：

1. 定位key所在的位置，并且删除key，清除value的内存数据；

2. 尝试标记该key所在桶里面的元素为emptyRest，如果该桶处在逸出桶，那么就尝试向前遍历桶的元素为emptyRest。

如果想详细查看源码的注释，可以查看我的GitHub,欢迎批评指正。我的打算是把一些常用的数据结构都分析一遍，如果有志同道合的人，可以联系我。

详细解析

前面系列的文章如果有所了解的话，那这篇文章我就按照重点解析源码了，主要是思路。其实删除算是该map最简单的一个操作了。首先说明下map删除的底层代码是mapdelete_faststr方法，在runtime/map_faststr.go里面。话不多说上码。

func mapdelete_faststr(t *maptype, h *hmap, ky string) {    if raceenabled && h != nil {        callerpc := getcallerpc()        racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapdelete_faststr))    }    if h == nil || h.count == 0 {        return    }    if h.flags&hashWriting != 0 {        throw("concurrent map writes")    }
    key := stringStructOf(&ky)    hash := t.hasher(noescape(unsafe.Pointer(&ky)), uintptr(h.hash0))
    // Set hashWriting after calling t.hasher for consistency with mapdelete    h.flags ^= hashWriting
    bucket := hash & bucketMask(h.B)    // 顺便迁移    if h.growing() {        growWork_faststr(t, h, bucket)    }    // 找到key所在的桶    b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))    // 记录下刚开始key的所在的桶    bOrig := b    top := tophash(hash)    ....}

上面代码就是找到删除的key所在的桶的编号，然后还顺便尝试迁移一波。bOrig记录了这个bucket的序号，下面去标记tophash槽的状态有用。

...search:    // 外层循环该key所在的桶以及桶后面的逸出桶    for ; b != nil; b = b.overflow(t) {        // 遍历桶的数据        for i, kptr := uintptr(0), b.keys(); i < bucketCnt; i, kptr = i+1, add(kptr, 2*sys.PtrSize) {            k := (*stringStruct)(kptr)            if k.len != key.len || b.tophash[i] != top {                continue            }            if k.str != key.str && !memequal(k.str, key.str, uintptr(key.len)) {                continue            }            // Clear key's pointer.            // 清除key的字符，把长度留下            k.str = nil            e := add(unsafe.Pointer(b), dataOffset+bucketCnt*2*sys.PtrSize+i*uintptr(t.elemsize))            // 清除value的内存            if t.elem.ptrdata != 0 {                memclrHasPointers(e, t.elem.size)            } else {                memclrNoHeapPointers(e, t.elem.size)            }            // 标记为值已经被清除            b.tophash[i] = emptyOne            // If the bucket now ends in a bunch of emptyOne states,            // change those to emptyRest states.            // 判断该所在桶的key后面的key是否都已经被清空            // 或者如果该key已经是桶内的第8个key，那么就判断该桶的所有逸出桶是否已经被清空            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                }            }            // 往前面一直去试图标记桶的hash槽为emptyRest状态            // 当该槽的状态为emptyRest之后，那么就是该key之后所有的槽，以及该桶后面的逸出桶都是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--                }                // 如果是emptyOne，也就是被删除了，那么就标记为emptyRest                if b.tophash[i] != emptyOne {                    break                }            }        notLast:            h.count--            break search        }    }
    if h.flags&hashWriting == 0 {        throw("concurrent map writes")    }    h.flags &^= hashWriting

相信看了前面《go基础之map-增和改（二）》 之后，对上段代码的2个for循环相当熟悉，就是找到key和value的内存地址。有几个地方分析下:

1. 14-16行，可以看到只是把key的字符指针清除掉了，但是长度并没有被清除掉。为什么这么做呢？又知道的在下面留言探讨。我觉得这样并没有什么意义，对map的其他操作没任何影响。

2. 17~23行，清除了value的内存，可以看到元素里面有指针和没指针完全是2种清理方式。

3. 25行b.tophash[i] = emptyOne标记该tophash槽为emptyOne状态。这里说说tophash槽的几个状态:
   

   
   ①、emptyRest表示该槽之后的槽都没有key，并且该槽所在的桶后面的溢出桶也没有数据。
   ②、emptyOne表示该槽已经被清空了。
   ③、evacuatedX，evacuatedY表示该key已经被迁移过了。evacuatedX表示该桶的数据被迁移到序号低的桶，evacuatedY表示该桶被迁移到序号比较高的桶。具体可以看我在《go基础之map-增和改（二）》的分析。这个标记在迭代的时候会用到，后面序列博客会介绍。
   ④、evacuatedEmpty表示该tophash槽已经被迁移了，并且该tophash所在的桶也搬完了。
   ⑤、minTopHash表示最小的tophash值了，当一个key计算出来的tophash比这个还小的话就要加上minTopHash作为最终的tophash。

4. 26~38行的意思是判断要不要去尝试标记该桶之前的数据为emptyRest。i == bucketCnt-1表示这个key已经是桶的最后的数据了，就要去看看该桶的溢出桶是否是emptyRest,如果是那么就可以标记当前槽为emptyRest,并且向前尝试去标记前面的槽。如果不是最后一个桶，那么就判断该key后面一个数据是否是emptyRest。

5. 39~60行就是满足了上面的条件之后，就会来尝试标记桶的数据为emptyRest。这里就用到了上面提到的bOrig，不断的向前面找桶的key是否是emptyOne，如果是就标为emptyRest。第50行代码是防止删除的key在溢出桶的时候，就要顺着溢出桶往前面找所有的桶，尝试标记。

然后就完了？纳尼。当我写完这篇博客我才发现如此的简单，并且出现了一个疑问：当在扩容的时候，如果这个key在老桶上面，岂不是就不删除了？然后我回去再缕了下源码，发现了有段代码略过了:

 // 顺便迁移    if h.growing() {        growWork_faststr(t, h, bucket)    }

这里会去尝试迁移迁移的老桶，迁移完成之后接下来再去查找删除的key。好，疑问解决。

总结

删除比较简单，但是要完全能理明白的话或许要看《go基础之map-增和改（二）》打些基础。如有不足之处，请共同讨论学习。

References

[1] 我的GitHub: https://github.com/zhangshen023/zhangshen023-go_soucecode_analysis/tree/main/runtime