一、写在前面

现代编程语言一般都提供了hash表的容器, 比如c++的std::hash_map, golang的map底层都使用了hash table, 是什么魔法让hash table在编程中占有一席之地,下面的内容会慢慢揭晓这个答案。

二、hash表的组成

在聊hash表的实现,先问一个问题。对于数组的访问可以使用索引,array[0], 就可以取得0索引的值, 取值的效率是O(1), 如果对于字符串类型如果也能实现类似的访问, 那不是很完美,先字符串转数字, 再变成array[0]取值,那效率也是O(1)。

hash表的组成

上图中神秘黑魔法就是hash函数,那么hash函数这么牛逼,有没有什么问题? hash函数最大的问题就是hash冲突,如下图, 面对不同的字符串对映射到同一个槽位。

hash冲突

在工程实践中, 一般使用挂链的方式, 就是每个hash table里面的槽位都是链表,冲突之后就是把新节点加到链表的表尾。

解决hash冲突

三、redis是如何实现双hash表的

3.1 冲突挂链的效率优化

在一般hash table的实现中,聊到了使用挂链表的方式解决hash冲突。那有一个问题,随着数据越来越多, 冲突的概率也是越来越大。一个槽位里面挂1000个节点,还有啥效率可言。既然冲突不可避免, 那当槽位里面挂的节点超过一定比例, 就扩容一个新的hash table, 这个新旧同时存在的状态定为rehashing,更大的hash table,可以让冲突槽位的链表长度降低,从而提升效率。假如这个点可行, 后面无非是工程问题。

hash迁移示意图

3.2 扩容流程

上面已经想到用双hash表的方式提升数据扩容之后的访问效率,那现在讨论insert流程,访问的过程是先访问旧的hash table,然后再访问新的hash table,删除同理。

注意:

这里面有个优化点, 为了尽量避免rehashing对业务造成影响,需要平均操作的影响,每次get delete set操作,都迁移一些数据到新hash表中,这也是redis hashtable里面的实现。

来个流程图说明下。

扩容流程

3.3 收缩流程

收缩流程可以在hash table内部做,也可以在外部做。
hash table一般实现是指针数据,假如对一个hash table存入100w元素,再删除掉。

说明:

不支持内部自动收缩的hash table,一般会浪费7.6MB的空间(64位机器) 8 * 1000000 / 1024/1024.0 = 7.62890625,这里的8是64位机器一个指针的字节数,除以一个1024单位是KB,再除以一个1024就是MB。浪费空间也不大,现代手机都动不动8GB以上RAM。

如果还是极在意这个点,可以提供一个收缩函数给外部调用。

四、核心代码

如下为golang移值redis双hash表的核心代码,供参考。

// 元素
type entry[K comparable, V any] struct {
    key  K
    val  V
    next *entry[K, V]
}

type config struct {
    hashFunc func(str string) uint64
    cap      int
}

// hash 表头
type HashMap[K comparable, V any] struct {
    // 大多数情况, table[0]里就存在hash表元素的数据
    // 大小一尘不变hash随着数据的增强效率会降低, rhashmap的实现是超过某阈值时
    // table[1] 会先放新申请的hash表元素, 当table[0]都移动到table[1]时, table[1]赋值给table[0], 完成一次hash扩容
    // 移动的操作都分摊到Get, Set, Delete操作中, 每次移动一个槽位, 或者跳运100个空桶(TODO修改代码, 需要修改这边的注释)
    table   [2][]*entry[K, V] //hash table
    used    [2]uint64         // 记录每个table里面存在的元素个数
    sizeExp [2]int8           //记录exp

    rehashidx int // rehashid目前的槽位
    keySize   int //key的长度
    config
    isKeyStr bool //是string类型的key, 或者不是
    init     bool
}


// 返回索引值和entry
func (h *HashMap[K, V]) findIndexAndEntry(key K) (i uint64, e *entry[K, V], err error) {
    if err := h.expand(); err != nil {
        return 0, nil, err
    }

    hashCode := h.calHash(key)
    idx := uint64(0)
    for table := 0; table < 2; table++ {
        idx = hashCode & sizeMask(h.sizeExp[table])
        head := h.table[table][idx]
        for head != nil {
            if key == head.key {
                return idx, head, nil
            }

            head = head.next
        }

        if !h.isRehashing() {
            break
        }
    }

    return idx, nil, nil
} 
// 设置, 这里可以看下insert的流程
func (h *HashMap[K, V]) Set(k K, v V) error {
    h.lazyinit()
    if h.isRehashing() {
        h.rehash(1)
    }

    index, e, err := h.findIndexAndEntry(k)
    if err != nil {
        return err
    }

    idx := 0
    if h.isRehashing() {
    //如果在rehasing过程中, 如果这个key是第一次存入到hash table, 优先写入到新hash table中
        idx = 1 
    }

  // element存在, 这里是替换
    if e != nil {
        //e.key = k
        e.val = v
        return nil
    }

    e = &entry[K, V]{key: k, val: v}
    e.next = h.table[idx][index]
    h.table[idx][index] = e
    h.used[idx]++
    return nil
}

五、性能压测

如下为性能压测数据:

  • 读取速度比标准库快一倍
  • 写入速度较标准库每次慢0.018ns
goos: darwin
goarch: amd64
pkg: github.com/guonaihong/gstl/rhashmap
cpu: Intel(R) Core(TM) i7-1068NG7 CPU @ 2.30GHz
BenchmarkGet-8       1000000000          0.4066 ns/op
BenchmarkGetStd-8    1000000000          0.8333 ns/op
PASS
ok   github.com/guonaihong/gstl/rhashmap 130.007s.
比标准库快一倍.

goos: darwin
goarch: amd64
pkg: github.com/guonaihong/gstl/rhashmap
cpu: Intel(R) Core(TM) i7-1068NG7 CPU @ 2.30GHz
BenchmarkSet-8          1000000000           0.1690 ns/op
BenchmarkSetStd-8       1000000000           0.1470 ns/op
PASS
ok      github.com/guonaihong/gstl/rhashmap 3.970s

五百万数据的Get操作时间

六、完整代码

如果对其余部分也感兴趣, 可以查看如下网址, 包含Get、 Set、 Delete完整的实现。
https://github.com/guonaihong/gstl/tree/master/rhashmap

由于版权原因,本站共享资源只供云盘资源,版权均属于影片公司所有,请在下载后24小时删除,切勿用于商业用途。本站所有资源信息均从互联网搜索而来,本站不对显示的内容承担责任,如您认为本站页面信息侵犯了您的权益,请附上版权证明邮件并发送到[email protected]告知,我们会在收到邮件后72小时内删除。
想开点 » golang泛型实现——双hash表