第4章 字典

为什么从“双表渐进rehash台”开始

第4章 字典的核心任务是追踪dict、dictht和dictEntry的哈希、冲突链、双表rehash与渐进迁移。命令返回值只暴露外层合同；实现解释还必须连接内存结构、写入与读取路径、事件顺序以及失败后的旧状态回收。双表渐进rehash台把这些关系放进同一条可复位轨迹。

先写预测：当负载状态由“触发扩缩”进入“正在迁移”时，哪个可观察状态最先变化？再规定什么结果会推翻当前解释。交互中的分数只表达透明因果方向，不冒充真实Redis测量。

来源、版次与独立重写边界

黄健宏作者读者服务页确认正式出版新版以Redis 3.0为源码基线，列出4部分、24章及完整小节，并链接Redis 3.0中文注释源码。本课程据此映射24个正式单元、145个目录节点，另设学习地图和总复习；未取得出版正文授权，目录只界定范围，不宣称复现原书正文。

本章字段与控制流由Redis官方3.0源码：dict.c和作者注释源码交叉核对；Redis当前持久化文档只用于辨认版本差异。中文解释、图示、交互、实验与答案均为独立教学重写，不把目录页或代码仓库许可证误报为原书许可证。

本章术语与源码合同

第4章 字典必须守住“迁移期间查找覆盖两张表，rehashidx单调推进，键只存在于正确位置且负载因子受控”。观察同时记录双表渐进rehash台一致率与访问动作分叉风险；只有结构快照、函数入口、运行结果和故障反例互相一致，才接受实现结论。

作者目录逐项深读

字典的实现

四级证据 1/7。 dict持有ht[0]、ht[1]与rehashidx；dictht保存桶数组、大小、掩码和已用节点数，dictEntry以链表解决冲突。本节点用“字典的实现”作观察点，执行rg 'dictRehash|_dictKeyIndex|dictFind' src/dict.c或等价源码探针，保存版本、输入、前后状态和能推翻解释的反例。

验证字典的实现时，先预测负载状态从“触发扩缩”切到“正在迁移”会改变哪个字段、偏移、文件或消息；再固定访问动作做一次对照。若故障注入没有破坏“迁移期间查找覆盖两张表，rehashidx单调推进，键只存在于正确位置且负载因子受控”，就撤回当前解释而不是补写故事。

哈希算法

四级证据 2/7。 哈希值与sizemask按位与得到桶索引；扩容后的掩码改变，所以迁移必须重新计算目标桶。本节点用“哈希算法”作观察点，执行rg 'dictRehash|_dictKeyIndex|dictFind' src/dict.c或等价源码探针，保存版本、输入、前后状态和能推翻解释的反例。

验证哈希算法时，先预测负载状态从“触发扩缩”切到“正在迁移”会改变哪个字段、偏移、文件或消息；再固定访问动作做一次对照。若故障注入没有破坏“迁移期间查找覆盖两张表，rehashidx单调推进，键只存在于正确位置且负载因子受控”，就撤回当前解释而不是补写故事。

解决键冲突

四级证据 3/7。 同桶键以链地址法连接，查找还要用类型回调比较键，不能只比较哈希值。本节点用“解决键冲突”作观察点，执行rg 'dictRehash|_dictKeyIndex|dictFind' src/dict.c或等价源码探针，保存版本、输入、前后状态和能推翻解释的反例。

验证解决键冲突时，先预测负载状态从“触发扩缩”切到“正在迁移”会改变哪个字段、偏移、文件或消息；再固定访问动作做一次对照。若故障注入没有破坏“迁移期间查找覆盖两张表，rehashidx单调推进，键只存在于正确位置且负载因子受控”，就撤回当前解释而不是补写故事。

rehash

四级证据 4/7。 rehash建立ht[1]并迁移ht[0]桶；完成后释放旧表、把ht[1]提升为ht[0]并把rehashidx复位为-1。本节点用“rehash”作观察点，执行rg 'dictRehash|_dictKeyIndex|dictFind' src/dict.c或等价源码探针，保存版本、输入、前后状态和能推翻解释的反例。

验证rehash时，先预测负载状态从“触发扩缩”切到“正在迁移”会改变哪个字段、偏移、文件或消息；再固定访问动作做一次对照。若故障注入没有破坏“迁移期间查找覆盖两张表，rehashidx单调推进，键只存在于正确位置且负载因子受控”，就撤回当前解释而不是补写故事。

渐进式rehash

四级证据 5/7。 普通字典操作顺带迁移有限桶；迁移期新增只写ht[1]，查找和删除需要覆盖两表。本节点用“渐进式rehash”作观察点，执行rg 'dictRehash|_dictKeyIndex|dictFind' src/dict.c或等价源码探针，保存版本、输入、前后状态和能推翻解释的反例。

验证渐进式rehash时，先预测负载状态从“触发扩缩”切到“正在迁移”会改变哪个字段、偏移、文件或消息；再固定访问动作做一次对照。若故障注入没有破坏“迁移期间查找覆盖两张表，rehashidx单调推进，键只存在于正确位置且负载因子受控”，就撤回当前解释而不是补写故事。

字典API

四级证据 6/7。 dictAdd、dictFind、dictDelete和迭代器共同受rehash状态约束，安全迭代器会阻止不兼容的迁移动作。本节点用“字典API”作观察点，执行rg 'dictRehash|_dictKeyIndex|dictFind' src/dict.c或等价源码探针，保存版本、输入、前后状态和能推翻解释的反例。

验证字典API时，先预测负载状态从“触发扩缩”切到“正在迁移”会改变哪个字段、偏移、文件或消息；再固定访问动作做一次对照。若故障注入没有破坏“迁移期间查找覆盖两张表，rehashidx单调推进，键只存在于正确位置且负载因子受控”，就撤回当前解释而不是补写故事。

重点回顾

四级证据 7/7。 第4章 字典的回顾要重新证明“迁移期间查找覆盖两张表，rehashidx单调推进，键只存在于正确位置且负载因子受控”，并用同一输入比较结构前态、变更轨迹、故障首错与恢复后态

验证重点回顾时，先预测负载状态从“触发扩缩”切到“正在迁移”会改变哪个字段、偏移、文件或消息；再固定访问动作做一次对照。若故障注入没有破坏“迁移期间查找覆盖两张表，rehashidx单调推进，键只存在于正确位置且负载因子受控”，就撤回当前解释而不是补写故事。

最小源码与运行切片

+git clone --branch 3.0 --depth 1 https://github.com/redis/redis.git redis-3.0
+cd redis-3.0
+rg 'dictRehash|_dictKeyIndex|dictFind' src/dict.c

该切片固定Redis 3.0分支、编译器、配置、数据集和命令序列；先保存结构或函数位置，再运行隔离实例。任何持久化损坏、断线、故障转移、大键或高流量实验都必须使用临时数据并规定CPU、内存、磁盘、延迟和停止上限。

unit: rdi-04-dictionary
source_file: dict.c
axis_a: "负载状态"
axis_b: "访问动作"
fault: "rehash期间只查询ht[0]，或一次迁移整表造成长停顿"
invariant: "迁移期间查找覆盖两张表，rehashidx单调推进，键只存在于正确位置且负载因子受控"
replay: same_version_same_input

三个必须主动触发的误区

误区 1

现象 → rehash 期间大量写入 原因 → 双表并存内存膨胀 修法 → 监控 rehash 状态，写入高峰避开

误区 2

现象 → 哈希键字段无上限 原因 → 单键过大拖垮操作 修法 → 限制单哈希字段数，必要拆键

误区 3

现象 → 以为哈希查找总是 O(1) 原因 → 冲突链过长退化为 O(N) 修法 → 关注负载因子与扩缩容阈值

小结

• 字典由两个哈希表组成便于 rehash
• 链地址法解决哈希冲突
• 渐进 rehash 分摊搬迁成本
• 负载因子触发扩缩容
• 字典是数据库与哈希键底座

练习、答案与节点验证

术语复核与本章回顾

完成第4章 字典意味着能从dict.c解释追踪dict、dictht和dictEntry的哈希、冲突链、双表rehash与渐进迁移，能运行章专属状态实验，能制造反例并在复位后证明旧状态没有残留。