map底层的一些理解

读 Draven的博客以及此文感觉了解了不少golang对map底层的一些实现，特此记录

底层结构

map的底层在绝大多数语言里面都是使用的数组加链表实现的，go也一样

其实map底层的链表本身就是为了解决hash冲突，每个链表里面最多放8个元素，满了就放到溢出桶里面去

装载因子超过 6.5

装载因子 = map的元素个数/桶个数
溢出桶过多（大于 1<<(B&15)）

B是用来计算桶个数的，桶个数=2^B
因为和15做了&运算，所以溢出桶数量永远不会超过31个
这个条件是golang发展一段时间后才加上的

map扩容后需要重新计算元素属于哪个新桶，这里注意，从旧桶迁移到新桶是慢慢进行的，不是一步到位

当进行写操作（增删改）时会触发nevacuate旧桶元素的重分配，若本身操作的就是旧桶中的元素，就会同时额外触发一个旧桶的迁移（即一次迁移两个），直至全部桶内元素迁移完成后，会把oldbuckets重置为nil

感谢Wbofeng大晚上陪我读源码

本作品采用《CC 协议》，转载必须注明作者和本文链接

247 声望

Go go go

讨论数量: 0

(=￣ω￣=)··· 暂无内容！

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容，与人为善，比聪明更重要！

帮助