数据结构 - hashtable

December 12, 2019

背景 #

最近一直在看《redis设计与实现》，其中讲了redis中使用到的数据结构如：sds, ziplist, skiplist, hashtable, intset, linkedlist等。读完第一部分之后，再结合github上的源码redis，本着好记性不如烂笔头的理念，便准备动手撸一遍。

redis中hashtable的特点 #

1. 链地址法解决hash冲突（除此以外，常见的冲突解决办法还有：再散列法/再哈希法/建立公共溢出区）
2. 使用了murmur2哈希函数。
3. 渐进式rehash，rehash过程并不是一步到位，而是在get/set/del 等操作中，穿插着完成。
4. 自动扩容和自动收缩，通过阀值来控制扩容和收缩。
5. 有2个bucket，其中0号bucket是最常用的，而1号只会在rehash过程中使用，一旦rehash完成，便不再使用。

解析和实现 #

hashtable：是根据Key直接访问在内存存储位置的数据结构。如何根据key得到内存中的位置，就需要使用hash函数来从旁协助了。

hash函数：是一种从任何一种数据中创建小的数字“指纹”的方法。简单的说：hash(input) = 1122334455。

这里选择了golang来实现；murmur3 hash算法；

数据结构 #

一图以蔽之：

// 对外暴露的hashtable
type LinkedDict struct {
	// 2个存储桶，0号正常使用，1号在rehash过程中使用；rehash完成之后，1号赋值给0号然后重置1号。
	ht [2]*hashtable
	// 初始值 -1，表示没有在rehash
	rehashIdx int
}

// 存储桶
type hashtable struct {
	// 底层“数组”
	table []*dictEntry
	size int
	sizemask int
	used int
}

// hashtable 元素定义
type dictEntry struct {
	key string
	value interface{}
	next *dictEntry
}

方法集 #

hashtable常用的方法有 GET/SET/DELETE/ITER，接下来会在SET和DEL中介绍rehash的详细过程。