锐客网

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

go语言数组有序无序 golang有序集合( 五 )

IT技术Thrown


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 。
如果未迁移完毕 ， 赋值/删除的时候，扩容完毕后（预分配内存），不会马上就进行迁移 。而是采取 增量扩容 的方式 ， 当有访问到具体 bukcet 时，才会逐渐的进行迁移（将 oldbucket 迁移到 bucket）
nevacuate 标识的是当前的进度，如果都搬迁完，应该和2^B的长度是一样的
在evacuate 方法实现是把这个位置对应的bucket ， 以及其冲突链上的数据都转移到新的buckets上 。
转移的判断直接通过tophash 就可以，判断tophash中第一个hash值即可
遍历的过程，就是按顺序遍历 bucket，同时按顺序遍历 bucket 中的 key 。
map遍历是无序的，如果想实现有序遍历，可以先对key进行排序
为什么遍历 map 是无序的？

推荐阅读


上一篇：微信公众号全球搞笑视频，搞笑类微信公众号

下一篇：即时翻译挣钱游戏手机下载，即时翻译游戏的软件