根据上面查找过程,查找key所在位置,如果找到则更新,没找到则找空位插入即可
经过前面迭代寻找动作,若没有找到可插入的位置,意味着需要扩容进行插入,下面会详细说下扩容过程
通过汇编语言可以看到,向 map 中删除 key,最终调用的是mapdelete函数
删除的逻辑相对比较简单,大多函数在赋值操作中已经用到过,核心还是找到 key 的具体位置 。寻找过程都是类似的 , 在 bucket 中挨个 cell 寻找 。找到对应位置后 , 对 key 或者 value 进行“清零”操作 , 将 count 值减 1,将对应位置的 tophash 值置成Empty
再来说触发 map 扩容的时机:在向 map 插入新 key 的时候 , 会进行条件检测 , 符合下面这 2 个条件 , 就会触发扩容:
1、装载因子超过阈值
源码里定义的阈值是 6.5 (loadFactorNum/loadFactorDen),是经过测试后取出的一个比较合理的因子
我们知道,每个 bucket 有 8 个空位 , 在没有溢出,且所有的桶都装满了的情况下 , 装载因子算出来的结果是 8 。因此当装载因子超过 6.5 时,表明很多 bucket 都快要装满了,查找效率和插入效率都变低了 。在这个时候进行扩容是有必要的 。
对于条件 1,元素太多,而 bucket 数量太少,很简单:将 B 加 1,bucket 最大数量( 2^B )直接变成原来 bucket 数量的 2 倍 。于是,就有新老 bucket 了 。注意,这时候元素都在老 bucket 里,还没迁移到新的 bucket 来 。新 bucket 只是最大数量变为原来最大数量的 2 倍( 2^B * 2 )。
2、overflow 的 bucket 数量过多
在装载因子比较小的情况下 , 这时候 map 的查找和插入效率也很低,而第 1 点识别不出来这种情况 。表面现象就是计算装载因子的分子比较小 , 即 map 里元素总数少,但是 bucket 数量多(真实分配的 bucket 数量多,包括大量的 overflow bucket)
不难想像造成这种情况的原因:不停地插入、删除元素 。先插入很多元素,导致创建了很多 bucket , 但是装载因子达不到第 1 点的临界值,未触发扩容来缓解这种情况 。之后,删除元素降低元素总数量,再插入很多元素,导致创建很多的 overflow bucket,但就是不会触发第 1 点的规定 , 你能拿我怎么办?overflow bucket 数量太多,导致 key 会很分散,查找插入效率低得吓人,因此出台第 2 点规定 。这就像是一座空城,房子很多 , 但是住户很少,都分散了,找起人来很困难
对于条件 2,其实元素没那么多,但是 overflow bucket 数特别多,说明很多 bucket 都没装满 。解决办法就是开辟一个新 bucket 空间,将老 bucket 中的元素移动到新 bucket,使得同一个 bucket 中的 key 排列地更紧密 。这样 , 原来,在 overflow bucket 中的 key 可以移动到 bucket 中来 。结果是节省空间,提高 bucket 利用率 , map 的查找和插入效率自然就会提升 。
由于 map 扩容需要将原有的 key/value 重新搬迁到新的内存地址,如果有大量的 key/value 需要搬迁,会非常影响性能 。因此 Go map 的扩容采取了一种称为“渐进式”的方式,原有的 key 并不会一次性搬迁完毕,每次最多只会搬迁 2 个 bucket 。
上面说的hashGrow()函数实际上并没有真正地“搬迁”,它只是分配好了新的 buckets,并将老的 buckets 挂到了 oldbuckets 字段上 。真正搬迁 buckets 的动作在growWork()函数中,而调用growWork()函数的动作是在 mapassign 和 mapdelete 函数中 。也就是插入或修改、删除 key 的时候,都会尝试进行搬迁 buckets 的工作 。先检查 oldbuckets 是否搬迁完毕 , 具体来说就是检查 oldbuckets 是否为 nil 。
推荐阅读
- 几个截图怎么变成pdf,截图多张怎么能拼成一张
- js数据存本地文件,js数据存本地文件怎么存
- 好玩的解谜益智游戏,好玩的解谜益智游戏大全
- linux基础的命令,linux基本命令总结
- vb.net像素转换 vbnet imagelist
- 深圳go语言区块链课,go语言区块链开发实战
- html代码边框居中,html 边框
- ppt怎么吸引客户,ppt如何吸引人
- php高并发处理数据 php高并发三种解决方法