分享
go语言的hashmap
richmonkey · · 4930 次点击 · · 开始浏览这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。
go语言中map的数据结构,以下只摘取了关键的几个属性:
struct Bucket
{
uint8 tophash[BUCKETSIZE]; // top 8 bits of hash of each entry (0 = empty)
Bucket *overflow; // overflow bucket, if any
byte data[1]; // BUCKETSIZE keys followed by BUCKETSIZE values
};
struct Hmap
{
uint8 B; // log_2 of # of buckets (can hold up to LOAD * 2^B items)
byte *buckets; // array of 2^B Buckets. may be nil if count==0.
byte *oldbuckets; // previous bucket array of half the size, non-nil only when growing
};key的hash值的低位部分决定了key在buckets中的索引位置。
当相应bucket溢出时,通过Bucket中的overflow来插入新项。
Grow Bucket
当整个Hmap中的元素个数超过Bucket数目的65%之后,会分配2倍的bucket,之后将每个bucket中的元素分裂到新的bucket中。
将旧的bucket中的元素移到新的bucket中是一个渐进的过程,同时会保留旧有的bucket,此种实现方式,带来了遍历map的过程中,同时还可以做插入和删除操作,这是很多其它语言不具备的特性。
Shrink Bucket
Hmap还不支持bucket的shrink,这会导致某些程序在很短的时间内使用的超大数目的map,之后的内存无法得到有效的释放。
有疑问加站长微信联系(非本文作者)
入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889
关注微信4930 次点击
上一篇:go语言的chan
下一篇:Go 语言的手工内存管理
添加一条新回复
(您需要 后才能回复 没有账号 ?)
- 请尽量让自己的回复能够对别人有帮助
- 支持 Markdown 格式, **粗体**、~~删除线~~、
`单行代码` - 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
- 图片支持拖拽、截图粘贴等方式上传
收入到我管理的专栏 新建专栏
go语言中map的数据结构,以下只摘取了关键的几个属性:
struct Bucket
{
uint8 tophash[BUCKETSIZE]; // top 8 bits of hash of each entry (0 = empty)
Bucket *overflow; // overflow bucket, if any
byte data[1]; // BUCKETSIZE keys followed by BUCKETSIZE values
};
struct Hmap
{
uint8 B; // log_2 of # of buckets (can hold up to LOAD * 2^B items)
byte *buckets; // array of 2^B Buckets. may be nil if count==0.
byte *oldbuckets; // previous bucket array of half the size, non-nil only when growing
};key的hash值的低位部分决定了key在buckets中的索引位置。
当相应bucket溢出时,通过Bucket中的overflow来插入新项。
Grow Bucket
当整个Hmap中的元素个数超过Bucket数目的65%之后,会分配2倍的bucket,之后将每个bucket中的元素分裂到新的bucket中。
将旧的bucket中的元素移到新的bucket中是一个渐进的过程,同时会保留旧有的bucket,此种实现方式,带来了遍历map的过程中,同时还可以做插入和删除操作,这是很多其它语言不具备的特性。
Shrink Bucket
Hmap还不支持bucket的shrink,这会导致某些程序在很短的时间内使用的超大数目的map,之后的内存无法得到有效的释放。