go的hashmap实现

Disque中存储server相关的数据结构时,一般都使用dict.hz定义的hashmap,这个是作者直接从redis迁移过来。内部通过keyTypekey的数据类型,使用C中经常使用的union方法防止空间的浪费。存储采用类似指针数组,数组中的每个指针指向一个链表(链表用于解决hash冲突)。遇到存储空间不够(当总的元素数/指针数组的数量的几倍时,这代表hash查询的效率会下降,上述的几倍作者提供了一个经验值),采用rehash的方法,初始化时会有两个table,一个用作当前操作table,另一个在rehash时作为扩展后的table,rehash过程不是一次性完成,会在每次有操作时出发一步rehash,具体的rehash算法是每一步rehash会跳过10个空的slot后停止,防止会对正常的hash操作有影响,还有在rehash操作过程中,涉及到查询操作会同时查询两个table。

很久之前读过云风的一片blog,里面对比了golang中hashmap和lua中的实现,一头雾水。最近看了下hashmap.go的代码,这个整体的设计思路和dict一样,rehash都是重要的组成部分。但是细节上差异还是比较大的。首先,存储上,map采用bucket的概念,这个和dict一致,但是bucket内部结构不一样,map的bucket内部结构是数组,bmap+8k+8v+nextptr,bmap中的tophash存储hash中的前8位,用作bucket内部的进一步提升检索效率,如果当前bucket的key不匹配,会找到nextptr(dict中也是链表,写法非常直观),这个nextptr的寻找是通过golang内部指针运算得到的,指针运算主要使用unsafe.Pointeruintptr。rehash单位可能是cell,即每个kv。

	// Possible tophash values.  We reserve a few possibilities for special marks.
	// Each bucket (including its overflow buckets, if any) will have either all or none of its
	// entries in the evacuated* states (except during the evacuate() method, which only happens
	// during map writes and thus no one else can observe the map during that time).
	empty          = 0 // cell is empty
	evacuatedEmpty = 1 // cell is empty, bucket is evacuated.
	evacuatedX     = 2 // key/value is valid.  Entry has been evacuated to first half of larger table.
	evacuatedY     = 3 // same as above, but evacuated to second half of larger table.
	minTopHash     = 4 // minimum tophash for a normal filled cell.

上面这几个变量,如果是刚开始看可能有些迷惑,读不懂,其实这几个是预留的标识,存储在tophash中,标识当前k和v的状态:空,是否已经迁移,最小的tophash(这个可能是为了预留状态位设置的,因为小于4的都有特定的意义)。

上面的内容,是从mapaccess1得到的一些内容,未完待续。。。

删除操作mapdelete,和查找操作不同是,如果当前定位的bucket还没有迁移,需要调用growWork迁移,然后在新的bucket中查找并标记相应的cell为空。

赋值操作mapassign1,查找过程中会记录下当前bucket中的空cell位置,为后续插入做准备,如果没有找到空cell,则需要调用setoverflow增加链表元素。当查找不到时,还会检查当前map的负载,看是否需要扩容。

growWork在新旧bucket迁移时,保证某些bucket的迁移,然后在新的bucket中做操作。方法里还会多迁移一个bucket,这个理由,我个人觉得dict中的很像,就是这个操作代价不大,同时可以加快迁移过程。

evacuate具体的迁移操作,dict里面只需要计算hash,并映射到新的table中即可,但是这里,计算了xy两个位置,只在这两个位置上rehash。

  • 为什么能做到这样?rehash,旧bucket大小4,mask是3;新bucket大小8,mask是7;差别在于新bucket高位多1,所以在一个key当对应高位为0,只可能映射到原来的位置,对应位置为1则会映射到新位置。
  • 这样做的好处是?dict中rehash直接插入表头O(1)时间,evacuatebmap因为有上面的算法,只要保存2个指针就可以达到O(1)的顺序插入。至于为什么要不选择移动单个指针插入表头的方式,我个人还没想清楚,但两种方式都没什么问题。

hashmap中以指针和位操作为主,当你了解到下面这种写法的意义,基本可以读懂大部分代码

add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
go的hashmap实现
Share this