go语言的hashmap

richmonkey · · 4262 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

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,之后的内存无法得到有效的释放。


有疑问加站长微信联系(非本文作者)

本文来自:博客园

感谢作者:richmonkey

查看原文:go语言的hashmap

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

4262 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传