数据结构 - hashtable

@本文首发于 https://yeqown.github.io

背景

最近一直在看《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的详细过程。

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
}

总结：

1. rehashIdx 不仅用于标示hashtable是否在rehash过程中，也标示了rehash的进度；
2. rehash过程中，新增元素直接新增到1号bucket中；
3. 非rehash状态，则新增到0号bucket中；
4. 侧链新增元素过程，需比较key值是否存在，如果存在则更新并返回；
5. 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
}

总结：

1. 渐进rehash过程与SET中一致
2. 查询动作也需要根据rehash状而定：在rehash中则需要检查ht[0]和ht[1]；反之只需要检查rehash[0]即可；
3. 这里省略了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)
    }
}

总结：

1. 万变不离其宗，不管是SET，GET，DEL 都是先定位，再确定元素位置，再执行相应的动作；
2. 缩容判定中，填充率也等价于装载因子；
3. 代码中有个取巧：当使用率为0时则直接返回，避免了后续调用～

ITER

1. 此部分代码略去；
2. 遍历操作也需要视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

可见差距还是非常大的，这里大胆分析下导致这些差距的原因：

1. Key类型，通过pprof分析，在 hashtable.keyCompare 上花费了较多时间，虽然已经通过 strings.Compare 来加速orz；相比下golang内置的Map使用了 unsafe.Pointer pointer to unsafe.ArbitraryType (int) 作为key，并针对不同的key类型来设计哈希算法。
2. 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... ；
• 如果只是想要了解原理，参考资料中的 推荐 文档足以；
• 已经实现的版本还可以继续优化，并考虑并发安全问题～

参考资料

• https://en.wikipedia.org/wiki...
• http://redisbook.com/
• https://redisbook.readthedocs... 推荐
• https://github.com/cch123/gol... 推荐
• https://github.com/yeqown/has...