数据结构 – hashtable
2014 年 11 月 24 日
@本文首发于 https://yeqown.github.io
背景
最近一直在看《redis设计与实现》,其中讲了redis中使用到的数据结构如: sds
, ziplist
, skiplist
, hashtable
, intset
, linkedlist
等。读完第一部分之后,再结合 github上 的源码 redis ,本着好记性不如烂笔头的理念,便准备动手撸一遍。
redis中hashtable的特点
- 链地址法解决hash冲突(除此以外,常见的冲突解决办法还有:再散列法/再哈希法/建立公共溢出区)
- 使用了
murmur2
哈希函数。 - 渐进式
rehash
,rehash
过程并不是一步到位,而是在 get/set/del 等操作中,穿插着完成。 - 自动扩容和自动收缩,通过阀值来控制扩容和收缩。
- 有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的详细过程。
SET
func (d *LinkedDict) Set(key string, value interface{}) { if d.ht[0].table == nil { d.ht[0].init(InitTableSize) } // isRehashing 判定:`rehashIdx != -1` // needRehash 判定: 装载因子 used / size > 1.0 时触发扩容rehash if !d.isRehashing() && d.needRehash() { // rehashGrowup 表示本次rehash是需要扩容,在配置ht[1].table时会扩展为当前的2倍 // 反之则会缩减内存空间 // startrehash 会设置 rehashIdx = 0, 标志rehash的进度 d.startrehash(rehashGrowup) } if d.isRehashing() { // 如果在rehash过程中,则完成一部分任务: // 根据rehash的进度rehashIdx,选择搬移 d.ht[0].table[rehashIdx]部分的数据,添加到d.ht[1]中 d.steprehash() } // 上述工作完成之后,就可以考虑新增数据了 hashkey := d.hashkey(key) if d.isRehashing() { // 如果在rehash过程中,毋庸考虑,直接新增到d.ht[1]中 d.ht[1].insert(hashkey, newDictEntry(key, value, nil)) return } // 反之,不在rehash过程中,则直接新增到d.ht[0]中 d.ht[0].insert(hashkey, newDictEntry(key, value, nil)) return } // 渐进式rehash,根据rehashIdx确定,要搬移那一部分的数据。 func (d *LinkedDict) steprehash() { entry := d.ht[0].table[d.rehashIdx] // 如果rehashIdx指向的侧链为空,则rehashIdx自增,直到找到有数据的侧链或者数据均搬移完成 for entry == nil { d.rehashIdx++ if d.rehashIdx > d.ht[0].sizemask { d.finishrehash() return } entry = d.ht[0].table[d.rehashIdx] } // 开始搬移动作 // 遍历链表,将所有数据,新增到d.ht[1]中 next := entry.next for entry != nil { entry.next = nil d.ht[1].insert(d.hashkey(entry.key), entry) if next == nil { break } entry = next next = next.next } // 释放d.ht[0].table[rehashIdx]链表:避免干扰查询;释放内存 d.ht[0].table[d.rehashIdx] = nil d.rehashIdx++ if d.rehashIdx > d.ht[0].sizemask { // 是否已经结束,如果结束则: // d.ht[0] = d.ht[1] // d.ht[1] = newHashTable() // rehashIdx = -1 d.finishrehash() } } // 新增一个元素到到存储桶: // 根据hash函数的结果(hashkey)对存储桶大小(size)取模得到结果(pos);ht.table[pos]完成对链表的新增工作。 func (ht *hashtable) insert(hashkey uint64, item *dictEntry) { pos := hashkey % uint64(ht.size) entry := ht.table[pos] last := entry if entry == nil { ht.used++ ht.table[pos] = item return } for entry != nil { if ht.keyCompare(entry.key, item.key) { // 如果key已经存在则覆盖旧值 entry.value = item.value return } last = entry entry = entry.next } ht.used++ last.next = item }
总结:
- rehashIdx 不仅用于标示hashtable是否在rehash过程中,也标示了rehash的进度;
- rehash过程中,新增元素直接新增到1号bucket中;
- 非rehash状态,则新增到0号bucket中;
- 侧链新增元素过程,需比较key值是否存在,如果存在则更新并返回;
- rehash过程中,rehashIdx不是只会增加1单位,而是根据侧链情况来更新;
GET
func (d *LinkedDict) Get(key string) (v interface{}, ok bool) { // 同上SET,不过多赘述 if d.isRehashing() { d.steprehash() } hashkey := d.hashkey(key) v, ok = d.ht[0].lookup(hashkey, key) if !d.isRehashing() { // 如果不在rehash过程中 d.ht[0]中检索的结果便是最终结果 return } else if ok { // 如果在rehash过程中且命中,也返回结果 return v, ok } // 反之 rehash过程中,但在d.ht[0]中没找到,却不代表该key真的不存在, 还需要在d.ht[1]中确定 v, ok = d.ht[1].lookup(hashkey, key) return }
总结:
- 渐进rehash过程与SET中一致
- 查询动作也需要根据rehash状而定:在rehash中则需要检查ht[0]和ht[1];反之只需要检查rehash[0]即可;
- 这里省略了lookup部分的代码,是因为查询和新增在原理上是一致的: 定位 -> 遍历检查 -> 比较key -> 动作 。
DEL
// Del to delete an item in hashtable. func (d *LinkedDict) Del(key string) { if d.ht[0].used == 0 && d.ht[1].used == 0 { return } // 这里相比Set,区别在于:判定的内容不是是否需要扩容而是缩容 // 缩容判定:d.ht[0]的内存空间大于初始值4且“填充率”少于 10% // d.ht[0].size > 4 && (d.ht[0].used*100/d.ht[0].size) < 10 if !d.isRehashing() && d.needShrink() { d.startrehash(rehashShrink) } if d.isRehashing() { d.steprehash() } hashkey := d.hashkey(key) d.ht[0].del(hashkey, key) if d.isRehashing() { d.ht[1].del(hashkey, key) } }
总结:
- 万变不离其宗,不管是SET,GET,DEL 都是先定位,再确定元素位置,再执行相应的动作;
- 缩容判定中,填充率也等价于装载因子;
- 代码中有个取巧:当使用率为0时则直接返回,避免了后续调用~
ITER
- 此部分代码略去;
- 遍历操作也需要视rehash情况而定;
测试
这里我使用了golang内置的Map做了对比测试,结果如下:
builtinMap_1000 cost: 0ms builtinLinkedDict_1000 cost: 0ms getMap_1000 cost: 0ms getLinkedDict_1000 cost: 0ms builtinMap_10000 cost: 4ms builtinLinkedDict_10000 cost: 6ms getMap_10000 cost: 2ms getLinkedDict_10000 cost: 5ms builtinMap_100000 cost: 76ms builtinLinkedDict_100000 cost: 108ms getMap_100000 cost: 56ms getLinkedDict_100000 cost: 131ms builtinMap_1000000 cost: 1053ms builtinLinkedDict_1000000 cost: 1230ms getMap_1000000 cost: 581ms getLinkedDict_1000000 cost: 915ms builtinMap_10000000 cost: 13520ms builtinLinkedDict_10000000 cost: 17137ms getMap_10000000 cost: 8663ms getLinkedDict_10000000 cost: 14271ms
可见差距还是非常大的,这里大胆分析下导致这些差距的原因:
- Key类型,通过pprof分析,在
hashtable.keyCompare
上花费了较多时间,虽然已经通过strings.Compare
来加速orz;相比下golang内置的Map使用了unsafe.Pointer
pointer to unsafe.ArbitraryType (int) 作为key,并针对不同的key类型来设计哈希算法。 - bucket(数据结构)的使用:在我的实现中只使用了2个bucket,常用的只有1个bucket,在定位上:hash后的结果使用取模的方法定位;相比之下,map采用了多个bucket,每个bucket只存放8个元素,在定位上:hash后用
low bits & bucketMask
定位buckets和high 8bits
找到对应的位置,效率更高;
总结
- 实现一个hashtable并不难,难点在于:hash算法的选用(均匀分布);如何降低hash冲突(rehash时机);
- 当完成上述工作的时候,我再去阅读go内置的
map
的实现会容易很多orz,仅相似部分;map比上述hashtable的实现要复杂得多; - 文中所有代码均在 https://github.com/yeqown/has… ;
- 如果只是想要了解原理,参考资料中的 推荐 文档足以;
- 已经实现的版本还可以继续优化,并考虑并发安全问题~