go语言的hashmap

richmonkey · · 4275 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

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的过程中，同时还可以做插入和删除操作，这是很多其它语言不具备的特性。