dict字典的实现

dict的用途

dict是一种用于保存键值对的抽象数据结构,在redis中使用非常广泛,比如数据库、哈希结构的底层。

当执行下面这个命令:

以及使用哈希结构,如:

都会使用到dict作为底层数据结构的实现。

结构的定义

先看看字典以及相关数据结构体的定义:

字典

哈希表

哈希表节点

dictType

把上面的结构定义串起来,得到下面的字典数据结构:

根据数据结构定义,把关联图画出来后,看代码的时候就更加清晰。

从图中也可以看出来,字典的哈希表里,使用了链表解决键冲突的情况,称为链式地址法。

rehash(重新散列)

当操作越来越多,比如不断的向哈希表添加元素,此时哈希表需要分配了更多的空间,如果接下来的操作是不断地删除哈希表的元素,那么哈希表的大小就会发生变化,更重要的是,现在的哈希表不再需要那么大的空间了,在redis的实现中,为了保证哈希表的负载因子维持在一个合理范围内,当哈希表保存的键值对太多或者太少时,redis对哈希表大小进行相应的扩展和收缩,称为rehash(重新散列)。

执行rehash的流程图

负载因子解释

负载因子 = 哈希表已保存节点数量 / 哈希表大小

负载因子越大,意味着哈希表越满,越容易导致冲突,性能也就越低。因此,一般来说,当负载因子大于某个常数(可能是 1,或者 0.75 等)时,哈希表将自动扩容。

渐进式rehash

在上面的rehash流程图里面,rehash的操作不是一次性就完成了的,而是分多次,渐进式地完成。

原因是,如果需要rehash的键值对较多,会对服务器造成性能影响,渐进式地rehash避免了对服务器的影响。

渐进式的rehash使用了dict结构体中的rehashidx属性辅助完成。当渐进式哈希开始时,rehashidx会被设置为0,表示从dictEntry[0]开始进行rehash,每完成一次,就将rehashidx加1。直到ht[0]中的所有节点都被rehash到ht[1],rehashidx被设置为-1,此时表示rehash结束。

结合代码再深入理解

在渐进式rehash期间,所有对字典的操作,包括:添加、查找、更新等等,程序除了执行指定的操作之外,还会顺带将ht[0]哈希表索引的所有键值对rehash到ht[1]。比如添加:

总结

使用一个标记值标记某项操作正在执行是编程中常用的手段,比如本文提到的rehashidx,多利用此手段可以解决很多问题。

我在github有对Redis源码更详细的注解。感兴趣的可以围观一下,给个star。Redis4.0源码注解。可以通过commit记录查看已添加的注解。

原创文章,文笔有限,才疏学浅,文中若有不正之处,万望告知。

  • 发表于:
  • 原文链接:http://kuaibao.qq.com/s/20180108G09TRZ00?refer=cp_1026

扫码关注云+社区