对应的元素从哈希表中删除,无论是该键对应的值是否存在,这个内建的函数都不会返回任何的结果。
在编译期间,delete
关键字会被转换成操作为 ODELETE
的节点,而这个函数在最后会调用 mapdelete
函数簇中的一个,包括 mapdelete
、mapdelete_faststr
、mapdelete_fast32
和 mapdelete_fast64
:
func walkexpr(n *Node, init *Nodes) *Node {
switch n.Op {
case ODELETE:
init.AppendNodes(&n.Ninit)
map_ := n.List.First()
key := n.List.Second()
map_ = walkexpr(map_, init)
key = walkexpr(key, init)
t := map_.Type
fast := mapfast(t)
if fast == mapslow {
key = nod(OADDR, key, nil)
}
n = mkcall1(mapfndel(mapdelete[fast], t), nil, init, typename(t), map_, key)
}
}
这些函数的实现其实差不多,我们依然选择 mapdelete
作为分析的主要方法,如果在删除期间遇到了哈希表的扩容,就会对即将操作的桶进行分流,随后找到桶中的目标元素并根据数据的类型调用 memclrHasPointers
或者 memclrNoHeapPointers
函数完成键值对的删除。
func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
alg := t.key.alg
hash := alg.hash(key, uintptr(h.hash0))
bucket := hash & bucketMask(h.B)
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 !alg.equal(key, k2) {
continue
}
if t.indirectkey() {
*(*unsafe.Pointer)(k) = nil
} else if t.key.kind&kindNoPointers == 0 {
memclrHasPointers(k, t.key.size)
}
v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
if t.indirectvalue() {
*(*unsafe.Pointer)(v) = nil
} else if t.elem.kind&kindNoPointers == 0 {
memclrHasPointers(v, t.elem.size)
} else {
memclrNoHeapPointers(v, t.elem.size)
}
b.tophash[i] = emptyOne
}
// ...
}
}
}
哈希表的删除逻辑与写入逻辑非常相似,只是他的调用方式比较特殊,我们需要使用关键字来『调用』mapdelete
函数。
对于哈希表的删除逻辑,我们其实只需要知道 delete
关键字会先在 类型检查 阶段被转换成 ODELETE
操作,然后在 SSA 中间代码生成 时被转换成 mapdelete
函数簇就可以了。
总结
Go 语言中使用拉链法来解决哈希碰撞的问题实现了哈希表,访问、写入和删除等操作都在编译期间被转换成了对应的运行时函数或者方法。
哈希在每一个桶中存储键对应哈希的前 8 位,当对哈希进行操作时,这些 tophash
就成为了一级缓存帮助哈希快速遍历桶中元素,每一个桶都只能存储 8 个键值对,一旦当前哈希的某个桶超出 8 个,新的键值对就会被存储到哈希的溢出桶中。
随着键值对数量的增加,溢出桶的数量和哈希的装载因子也会逐渐升高,超过一定范围时就会触发扩容操作,扩容时会将桶的数量分配,元素再分配的过程也是在调用写操作时增量进行的,不会造成性能的瞬时巨大波动。
转载自:
理解Golang哈希表Map的元素