锐客网

  1. 首页 > 睿知 > it技术 > >

go语言可视化设计 golang可视化编程( 六 )

IT技术语言


通过汇编语言可以看到，向 map 中插入或者修改 key ， 最终调用的是mapassign函数 。
实际上插入或修改 key 的语法是一样的，只不过前者操作的 key 在 map 中不存在，而后者操作的 key 存在 map 中 。
mapassign 有一个系列的函数，根据 key 类型的不同，编译器会将其优化为相应的“快速函数” 。
我们只用研究最一般的赋值函数mapassign。
map的赋值会附带着map的扩容和迁移，map的扩容只是将底层数组扩大了一倍，并没有进行数据的转移，数据的转移是在扩容后逐步进行的，在迁移的过程中每进行一次赋值（access或者delete）会至少做一次迁移工作 。
1.判断map是否为nil
每一次进行赋值/删除操作时 ， 只要oldbuckets != nil 则认为正在扩容，会做一次迁移工作 ， 下面会详细说下迁移过程
根据上面查找过程，查找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）
【go语言可视化设计 golang可视化编程】 不难想像造成这种情况的原因：不停地插入、删除元素 。先插入很多元素，导致创建了很多 bucket，但是装载因子达不到第 1 点的临界值，未触发扩容来缓解这种情况 。之后 ， 删除元素降低元素总数量，再插入很多元素，导致创建很多的 overflow bucket，但就是不会触发第 1 点的规定，你能拿我怎么办？overflow bucket 数量太多，导致 key 会很分散，查找插入效率低得吓人 ， 因此出台第 2 点规定 。这就像是一座空城，房子很多，但是住户很少，都分散了 ， 找起人来很困难
对于条件 2 ， 其实元素没那么多，但是 overflow bucket 数特别多 ， 说明很多 bucket 都没装满 。解决办法就是开辟一个新 bucket 空间 ， 将老 bucket 中的元素移动到新 bucket，使得同一个 bucket 中的 key 排列地更紧密 。这样，原来 ， 在 overflow bucket 中的 key 可以移动到 bucket 中来 。结果是节省空间，提高 bucket 利用率，map 的查找和插入效率自然就会提升 。

推荐阅读


上一篇：怎么看显卡是否翻新货，显卡怎么查看是不是翻新的

下一篇：闪迪u盘手机u盘怎么用，闪迪手机u盘使用手册