golang源码解读之map

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

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 == size of map.  Must be first (used by len() builtin)
	uint32  flags;
	uint32  hash0;        // hash seed
	uint8   B;            // log_2 of # of buckets (can hold up to LOAD * 2^B items)
	uint8   keysize;      // key size in bytes
	uint8   valuesize;    // value size in bytes
	uint16  bucketsize;   // bucket size in bytes

	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
	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
};

  

本文来自:博客园

感谢作者:weijiaen

查看原文:golang源码解读之map

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