对于条件 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 是无序的?
如果发生过迁移 , key 的位置发生了重大的变化,有些 key 飞上高枝,有些 key 则原地不动 。这样,遍历 map 的结果就不可能按原来的顺序了 。
如果就一个写死的 map,不会向 map 进行插入删除的操作,按理说每次遍历这样的 map 都会返回一个固定顺序的 key/value 序列吧 。但是 Go 杜绝了这种做法,因为这样会给新手程序员带来误解,以为这是一定会发生的事情,在某些情况下,可能会酿成大错 。
Go 做得更绝,当我们在遍历 map 时,并不是固定地从 0 号 bucket 开始遍历 , 每次都是从一个**随机值序号的 bucket开始遍历,并且是从这个 bucket 的一个 随机序号的 cell **开始遍历 。这样 , 即使你是一个写死的 map,仅仅只是遍历它 , 也不太可能会返回一个固定序列的 key/value 对了 。
关于go语言map固定顺序和go语言map底层实现原理的介绍到此就结束了,不知道你从中找到你需要的信息了吗 ?如果你还想了解更多这方面的信息,记得收藏关注本站 。
推荐阅读
- 关于chatGPT,关于ChatGPT的论文
- chatgpt替代软件,chatter软件
- 冒险闯关手机游戏,冒险类闯关游戏
- 滁州钉钉直播,钉钉直播全攻略
- java运算结果代码 java 运算
- mongodb通过数组查询表,mongo 数组查询
- oracle临时表怎么查询数据,如何查看oracle的临时表空间名称以及大小
- 快排代码Java 快排代码408
- postgresql9.5contrib的简单介绍