go基础之map-删除(三)

共 5166字,需浏览 11分钟

 ·

2020-12-11 10:35

重点

在上篇文章《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表示该槽已经被清空了。
    ③、evacuatedXevacuatedY表示该key已经被迁移过了。evacuatedX表示该桶的数据被迁移到序号低的桶,evacuatedY表示该桶被迁移到序号比较高的桶。具体可以看我在《go基础之map-增和改(二)》的分析。这个标记在迭代的时候会用到,后面序列博客会介绍。
    ④、evacuatedEmpty表示该tophash槽已经被迁移了,并且该tophash所在的桶也搬完了。
    ⑤、minTopHash表示最小的tophash值了,当一个key计算出来的tophash比这个还小的话就要加上minTopHash作为最终的tophash。

  4. 26~38行的意思是判断要不要去尝试标记该桶之前的数据为emptyResti == 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




推荐阅读


福利

我为大家整理了一份从入门到进阶的Go学习资料礼包,包含学习建议:入门看什么,进阶看什么。关注公众号 「polarisxu」,回复 ebook 获取;还可以回复「进群」,和数万 Gopher 交流学习。

浏览 16
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报