Redis中dictht和dict的实现_Redis

dictht (字典哈希表)

dictht 是 “dictionary hash table” 的缩写，它代表一个最基础的哈希表结构。

它的定义如下（源码在 src/dict.h）：

typedef struct dictht {
    dictentry **table;      // 指向一个 bucket 数组（指针的指针）
    unsigned long size;     // 哈希表的大小（bucket 数组的长度）
    unsigned long sizemask; // 用于计算索引值的掩码，总是等于 size-1
    unsigned long used;     // 哈希表中已有节点的数量
} dictht;

对每个字段的解释：

table：这是一个数组指针，数组中的每个元素都是一个 dictentry *（指向键值对节点的指针）。这个数组就是哈希表的“buckets”（桶）。
size：table 数组的长度。这个值总是 2 的幂（例如 4, 8, 16, 32 …）。这是为了能使用高效的位运算 hash & sizemask 来代替取模运算 hash % size。
sizemask：掩码，其值恒等于 size - 1。计算键的索引时，用哈希值 & sizemask 得到的结果必定落在 [0, size-1] 的范围内，正好是数组的索引。
used：当前哈希表中实际存储了多少个键值对（dictentry 节点）。used/size 就是哈希表的负载因子（load factor），这个值是触发哈希表扩容或缩容的关键。

一个 dictht 的结构示意图：

        dictht
+------------------+
|      table       |----->  [dictentry*] -> [dictentry] -> [dictentry] -> null   (index 0)
|                  |        [dictentry*] -> null                                 (index 1)
|     size: 4      |        [dictentry*] -> [dictentry] -> null                  (index 2)
|  sizemask: 3     |        [dictentry*] -> [dictentry] -> [dictentry] -> null   (index 3)
|     used: 8      |
+------------------+

(上图展示了一个大小为 4 的哈希表，存储了 8 个元素，说明发生了哈希冲突，并用链表法解决)

2. 核心概念：dict (字典)

dict 是 redis 字典的主结构体，它封装了两个 dictht 和一些管理功能，使得哈希表能够平滑地扩容和缩容（rehashing）。

它的定义如下：

typedef struct dict {
    dicttype *type; // 类型特定函数，为实现多态而存在
    void *privdata; // 私有数据，传递给类型特定函数的可选参数
    dictht ht[2];   // 两个哈希表，为什么是两个？请看下面的解释
    long rehashidx; // rehashing 的进度，如果不是 -1 则表示正在进行 rehash
    int16_t pauserehash; // rehashing 暂停标志，>0 时表示 rehash 被暂停
} dict;

对每个字段的详细解释：

type 和 privdata：这两个成员是为了实现多态而存在的。dicttype 结构体包含了一系列函数指针（如哈希函数 hashfunction、键复制函数 keydup、值复制函数 valdup 等）。这使得 redis 的字典可以存储不同类型的键和值，只需为不同的用途设置不同的 dicttype 即可（例如用于存储数据库键值对的字典和用于存储键过期时间的字典，它们的函数指针不同）。
ht[2]：这是最关键的部分。一个 dict 结构包含了两个 dictht 哈希表。在通常情况下，所有的数据只存放在 ht[0] 中，ht[1] 为 null。只有在进行 rehashing（重新哈希）时，才会同时使用两个哈希表。
rehashidx：rehashing 的进度指示器。
- 当 rehashidx == -1 时，表示没有在进行 rehashing。
- 当 rehashidx >= 0 时，表示正在进行 rehashing，并且它的值表示 ht[0] 中当前正在被 rehash 的桶的索引（例如，rehashidx=3 表示 ht[0] 的索引 3 处的所有节点都已迁移到 ht[1]）。
pauserehash：表示 rehash 是否被暂停。大于 0 时表示暂停。这是为了在某些操作（如持久化 bgsave）时避免 rehash 带来过多的内存写入，保证性能。

3. dictht 和 dict 的关系与协作：rehashing

dictht 是静态的存储单元，而 dict 是动态的管理器。它们最精妙的协作体现在 rehashing（重新散列）过程中。

为什么需要 rehashing？

随着操作不断执行，哈希表的负载因子 used/size 会变得过大（冲突增多，效率下降）或过小（浪费内存）。为了维持高效性能，需要在适当的时候对哈希表进行扩容或缩容。

rehashing 的过程（渐进式重新散列）

触发：当满足一定条件时（如负载因子 > 1 且没有在进行 bgsave，或 > 5 等），触发扩容。为 ht[1] 分配空间，大小为第一个大于等于 ht[0].used * 2 的 2 的幂（例如 used=5，则新 size 为 16）。如果是缩容，则大小为第一个大于等于 ht[0].used 的 2 的幂（2的幂取模的时候直接与很方便）。
将 dict 的 rehashidx 从 -1 设置为 0，表示 rehashing 正式开始。
渐进式迁移：redis 不会一次性将 ht[0] 的所有键值对都迁移到 ht[1]（如果表很大，这会阻塞服务器很长时间）。而是采用分而治之的策略，将迁移工作分散到后续的每次增、删、改、查命令中。
- 每当对字典进行任何操作时，除了执行指定的操作，还会顺带将 ht[0] 在 rehashidx 索引上的整个 bucket 链表迁移到 ht[1] 中。
- 迁移完成后，将 rehashidx 的值加 1。
完成：当 rehashidx 递增到 ht[0].size 的值时，意味着 ht[0] 的所有数据都已迁移完毕。此时，释放 ht[0] 的空间，将 ht[1] 设置为新的 ht[0]，并为 ht[1] 创建一个新的空白哈希表以备下次使用。最后，将 rehashidx 重置为 -1。

在 rehashing 期间如何查找？
查找一个键时，会同时查找 ht[0] 和 ht[1] 两个表，先查 ht[0]，如果没找到再查 ht[1]。

总结与对比

特性	dictht (字典哈希表)	dict (字典)
角色	数据存储单元，一个静态的哈希表数组	字典管理器，一个动态的、封装好的字典对象
核心功能	存储键值对数据，处理哈希冲突（链表法）	管理两个 dictht，实现类型多态，控制 rehashing 流程
包含关系	被 dict 所包含	包含两个 dictht (ht[0] 和 ht[1])
rehashing	是 rehashing 操作的对象	是 rehashing 过程的控制器（通过 rehashidx）
类比	像是房子的毛坯房（只有房间结构）	像是房子的业主+装修队（负责管理、维护、扩建房子）