Comments (3)
應該改成這樣 @mcrwayfun
搬迁的目的就是将老的 buckets 搬迁到新的 buckets。而通过前面的说明我们知道,应对条件 1[if !h.sameSizeGrow()],新的 buckets 数量和之前相等,应对条件 2,新的 buckets 数量是之前的一倍。
from go-questions.
对于条件 2,其实元素没那么多,但是 overflow bucket 数特别多,说明很多 bucket 都没装满。解决办法就是开辟一个新 bucket 空间,将老 bucket 中的元素移动到新 bucket,使得同一个 bucket 中的 key 排列地更紧密。这样,原来,在 overflow bucket 中的 key 可以移动到 bucket 中来。结果是节省空间,提高 bucket 利用率,map 的查找和插入效率自然就会提升。
关于map触发扩容这里的原因,我有些疑问。原文说在最初向map中写入数据,如果数据过于分散会导致空间利用率不高而开始重组。但是我感觉代码这里更像是为了应对一个kv极多的map,在删除大量kv后而产生大量较空的bucket而写的。感觉初始时候就遇到缩容重组的概率也太低了。那点内存也不太值得进行重组,也许后面还要继续增加呢。
from go-questions.
原文
搬迁的目的就是将老的 buckets 搬迁到新的 buckets。而通过前面的说明我们知道,应对条件 1,新的 buckets 数量是之前的一倍,应对条件 2,新的 buckets 数量和之前相等。
对于条件 1,从老的 buckets 搬迁到新的 buckets,由于 bucktes 数量不变,因此可以按序号来搬,比如原来在 0 号 bucktes,到新的地方后,仍然放在 0 号 buckets。
对于条件 2,就没这么简单了。要重新计算 key 的哈希,才能决定它到底落在哪个 bucket。例如,原来 B = 5,计算出 key 的哈希后,只用看它的低 5 位,就能决定它落在哪个 bucket。扩容后,B 变成了 6,因此需要多看一位,它的低 6 位决定 key 落在哪个 bucket。这称为 rehash。
条件1是buckets数量翻倍,条件2是sizeSameGrow,下面描述错误,与上下文不一致。
笔误。你可以提个 pr 成为 contributor^_^
from go-questions.
Related Issues (20)
- 第三章:数据容器3.1.2-Page22 HOT 1
- 切片作为函数参数这一章节,倒数第三段描述应该不准确 HOT 1
- 垃圾回收机制图片错误
- go-questions/content/channel/7-操作 channel 的情况总结.md 文章内容有误 HOT 3
- 关于279页贴的Go仓库Issue HOT 1
- 请问一个关于 m 和主线程绑定的问题。(顺便提个 typo)
- 关于 P 的状态流转
- 步调算法下界描述有误
- 有关优雅关闭channel的问题
- 纸质版印刷图片展示不友好
- 《如何实现字符串和byte切片的零拷贝转换》章节,在1.20版之后有变化了 HOT 1
- 《map的实现原理章节》关于slice的描述有点过时了
- 14.1.8 节
- 错误处理的As 和 Is 函数有误
- Page 288 (并发标记清除法的难点是什么)
- Page 289 关于写屏障 HOT 1
- go-questions/channel/graceful-close 文章内容疑似有误 HOT 1
- 1-map B=5时 bucket num 由 hash 的低 5 位决定
- 关于 Golang 内存分配机制 的延伸问题
- 《接口转换的原理》一节汇编过时
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from go-questions.