go基础之map-删除(三)
共 5166字,需浏览 11分钟
·
2020-12-11 10:35
重点
在上篇文章《go基础之map-增和改(二)》已经非常详细的描述了定位key所在的桶以及它所在桶的位置,如果对上篇有所了解之后,该篇博客理解起来就会非常容易。总的来说map的删除主要做了2件事:
定位key所在的位置,并且删除key,清除value的内存数据;
尝试标记该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的内存地址。有几个地方分析下:
14-16行,可以看到只是把key的字符指针清除掉了,但是长度并没有被清除掉。为什么这么做呢?又知道的在下面留言探讨。我觉得这样并没有什么意义,对map的其他操作没任何影响。
17~23行,清除了value的内存,可以看到元素里面有指针和没指针完全是2种清理方式。
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。26~38行的意思是判断要不要去尝试标记该桶之前的数据为
emptyRest
。i == bucketCnt-1
表示这个key已经是桶的最后的数据了,就要去看看该桶的溢出桶是否是emptyRest
,如果是那么就可以标记当前槽为emptyRest
,并且向前尝试去标记前面的槽。如果不是最后一个桶,那么就判断该key后面一个数据是否是emptyRest
。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
推荐阅读