一文读懂Redis的dict字典数据结构 _dict字典

概览redis 本质是 K-V 键值对数据库，底层通过字典 dict 存储键值映射关系，除此之外， dict 还作为 Redis hash 结构底层的实现之一。
讨论 Redis 的数据结构，可以从两个层面出发。
第一个层面从使用者角度出发，即 Redis 暴露给外部调用的 Api：
•string
•list
•hash
•set
•sorted set
第二个层面是 Redis 的内部实现角度出发，是更为底层的数据结构实现：
•dict
•sds
•ziplist
•quicklist
•skiplist
Redis 这么做的目的还是基于高性能的考虑，在不同的场景下使用不同的底层数据结构实现，最大程度提升内存操作的效率。
例如当 sorted set ， hash 存储的数据规模较小时，底层都是通过 ziplist 实现，而当数据规模达到一定量时， sorted set 会转换成 dict + skiplist 的底层实现， hash 会转换成 dict 的底层实现。
本文主要讨论是 Redis 关于 dict 这一底层数据结构的实现原理。
实现dict 的实现与 JAVA jdk 中 hashmap 的实现有许多相似之处：
•关于哈希映射， key 的索引计算公式为 hash & (n - 1) ，其中 hash 为 key 对应的 hash 值（Redis 通过 MurmurHash 算法计算得出）， n 为哈希数组的大小•关于哈希冲突， Redis 同样也是采用链地址法解决冲突
dict 在扩缩容的情况下，采用的是渐进式的 rehash 方式，这是它的特殊之处，下文会主要讲到。
dict 的数据结构如下：
•type属性是一个指向dictType结构的指针，每个dictType结构保存了一簇用于操作特定类型键值对的函数， Redis会为用途不同的字典设置不同的类型特定函数
•privdata属性则保存了需要传给那些类型特定函数的可选参数
•ht[2] 数组中存放了两张哈希表，只有在 rehash 的过程中， ht[0] ht[1] 才都有效；正常情况下只有 ht[0] 有效， ht[1] 中没有任何数据
•rehashidx 用来表示 rehash 过程到了哪一个索引位置，正常情况下 rehashidx = -1 ，表示当前没有进行 rehash

文章插图

dictht 的数据结构如下：
•dictEntry 数组，用来存放键值对
•size 表示当前 dictEntry 数组的大小
•sizemask ，值为 size - 1 ，在计算 key 的索引位置时用到， index = hash & sizemask
•used 记录现有 dict 的数据个数

文章插图
【一文读懂Redis的dict字典数据结构】
正常情况下， dict 整体的数据结构如下图所示：

文章插图

rehash随着操作不断执行，哈希表中的键值对会逐渐增加或减少，为了让哈希表的负载因子（负载因子 = 已保存节点数量/哈希表大小）维持在一个合理的范围内，当哈希表中节点数量过多或者过少时， Redis 会对哈希表进行相应的扩容或缩容，这一过程称为 rehash 。
在 rehash 操作开始前，首先要为哈希表 ht[1] 分配内存， ht[1] 之前一直是空闲状态，终于要派上用场了，具体内存分配策略如下：
•如果是扩容操作， ht[1]的大小为第一个大于等于ht[0].used*2的2^n（2的n次方幂），举个例子 ht[0].used = 5 ，触发了扩容操作，即 ht[1].size = 5 * 2 = 10 ，但 10 不符合 2^n 要求，则继续往下找到第一个符合要求的数 16 ，即 ht[1].size = 16
•如果是缩容操作， ht[1]的大小为第一个大于等于ht[0].used的2^n（2的n次方幂），举个例子 ht[0].used = 5 ，触发了缩容操作，则 ht[1].size = 8
ht[1] 分配完内存之后，接着进行如下操作：
•将 ht[0] 的中的节点重新计算哈希值和索引值，映射到 ht[1] 上
•当ht[0]包含的所有键值对都迁移到了ht[1]之后（ht[0]变为空表），释放ht[0] ，将ht[1]设置为ht[0] ，并在ht[1]新创建一个空白哈希表，为下一次rehash做准备