golang源码解读之map

liyeho

　　golang的map实现并不是像c++一样使用红黑树，而是使用了hashmap，用数组来实现。
　　详细的实现后续补充，这里先做个备忘。
　　在iterate整个map的时候，使用delete是安全的。这跟c++是不一样的，c++在delete的时候，会导致整棵树发生变化，所以不能在迭代的时候删除元素。
　　那为什么golang的map是安全的呢，从源码来看，golang的map使用了桶的概念，元素是被hash到桶存储，每个桶预设是存储八个kv,而且在头部有一个uint8 tophash[8]的结构，存储每个key的高八位（即hash(key) » (64 - 8)），如果该位置未被放置元素，则有一个特殊的标志Empty。在插入删除的时候，首先会比较该uint8跟hash(key)是否相等。当然，桶还利用了overflow指针，可以无限的增长，类似链表。
　　所以，for循环其实是对每个桶进行迭代，判断每个uint8位置，删除操作也并不是实际的memset，而是把对应的tophash的位置置为Empty.因此，在迭代golang的map过程中，使用delete是安全的。
　　

struct Hmap　　
{

　　
uintgo  count;        // # live cells ==>　　
uint32  flags;
　　
uint32  hash0;        // hash seed
　　
uint8   B;            // log_2 of # of buckets (can hold up to LOAD * 2^B items)

　　
uint8   keysize;      // key>
　　
uint8   valuesize;    // value>
　　
uint16  bucketsize;   // bucket>　　

　　
byte    *buckets;     // array of 2^B Buckets. may be nil if count==0.

　　
byte    *oldbuckets;  // previous bucket array of half the>　　
uintptr nevacuate;    // progress counter for evacuation (buckets less than this have been evacuated)
　　
};
　　

　　

　　

typedef struct Bucket Bucket;　　
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
　　
};