go语言的hashmap
浏览数：28 /
时间：2015年06月10日
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，之后的内存无法得到有效的释放。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
