今天我们来聊点不一样的。不再重复那些老生常谈的“Redis为什么快”，也不罗列数据类型。我们来直面一个更硬核的问题：如果现在让你打开编辑器，从第一行代码开始，实现Redis的哈希表，你能写得出来吗？
相信大多数人的回答是：不能。这很正常，因为“看懂”和“写出来”之间，隔着一条巨大的实践鸿沟。
一、一个真实的面试拷问
前段时间，有朋友分享了一次面试经历。面试官问：“Redis的哈希表扩容时，为什么不会卡顿？”
他答出了“渐进式rehash”，面试官点点头，接着追问：
“那rehash期间，读写操作怎么处理？rehashidx是什么意思？迁移是按什么顺序进行的？”
然后，他就卡壳了。
他说自己看过很多讲解，感觉都懂了，但被深挖细节时，才发现理解仅停留在表面。你是否也有过这种感受？看文章时恍然大悟，合上之后脑中一片空白。根本原因就在于：从未亲手实现过。
二、我的探索：从源码到实践
过去这段时间，我专注于两件事：一是深入研究 Redis 7.x 的核心源码（超9万行），二是将这些复杂晦涩的原理，转化为能让人真正动手学会的实践课程。
目前，在完成SDS和Adlist两个模块后，Dict哈希表和Intset整数集合这两个核心模块也已全部实现。我认为，它们是Redis数据结构中最具学习价值的：
- Dict：其渐进式rehash是Redis高性能与稳定性的基石，不理解它，对Redis的理解就是不完整的。
- Intset：虽然小巧，却极致体现了Redis对内存优化的追求，其编码升级机制非常精妙。
下面，我将为你拆解这两个模块的核心设计思想。
三、Dict：为什么需要两张哈希表？
首先思考：Redis的哈希表，与你大学数据结构课上学到的，最大的区别是什么？
答案是：Redis使用了两张哈希表，而非一张。
为什么？
3.1 单哈希表的扩容之痛
假设你有一张初始大小为16的哈希表。随着数据增多，到达负载因子阈值后必须扩容，比如扩到32。
扩容意味着什么？所有键值对都需要重新计算哈希值，并分配到新的槽位中。
如果你有100万个键，这个瞬间就要执行100万次操作。在此期间，Redis服务将完全卡住，无法响应请求。这对一个要求高可用的系统来说是灾难性的。
3.2 Redis的解决方案：双表渐进式迁移
Redis的解法聪明而优雅：双哈希表 + 渐进式迁移。
扩容前：
dict
ht[0] size=16 used=13 ← 正在使用的哈希表
ht[1] = NULL
rehashidx = -1 （未在rehash）
触发扩容后：
dict
ht[0] size=16 used=13 ← 旧表，数据逐步迁出
ht[1] size=32 used=0 ← 新表，数据逐步迁入
rehashidx = 0 （从第0个桶开始迁移）
核心机制：每次对字典进行增、删、改、查操作时，顺便将ht[0]中rehashidx索引指向的桶（bucket）内的所有条目迁移到ht[1]。
这样一来，100万次迁移操作被拆散到100万次用户请求中逐步完成，用户完全感知不到卡顿。这就是“渐进式rehash”的精髓。
3.3 Rehash期间的读写规则
这是一个重要的面试考点：
- 写操作：新数据只写入
ht[1]，绝不写入ht[0]。这保证了ht[0]的数据只减不增，迁移最终总会完成。
- 读操作：同时查找
ht[0]和ht[1]（先查ht[0]，未找到再查ht[1]）。
查找 key "name" 的流程（rehash进行中）：
step1: 在 ht[0] 中找 → 未找到（已迁移走）
↓
step2: 在 ht[1] 中找 → 找到！返回结果
说明：如果 rehashidx=5，意味着 ht[0] 的 0~4 号桶已迁完
这些桶里的 key 已经在 ht[1] 里了，ht[0] 里自然找不到
3.4 Dict模块：6天实现路径
- 第1天：基础哈希表 实现
dictEntry、链地址法解决冲突，完成基础增删改查，编写一个简化的哈希函数，跑通首个测试用例。
- 第2天：扩容机制 弄清负载因子计算与触发条件，先实现一次性全量rehash以理解原理。
- 第3天：渐进式Rehash（核心） 引入双表结构，实现
rehashidx标记与逐步迁移逻辑，将迁移嵌入日常操作。
- 第4天：迭代器与扫描 实现安全/非安全迭代器，重点攻克
dictScan的反向二进制位迭代算法，这是rehash期间遍历不遗漏的关键。
- 第5天：高级特性 实现无值模式、整数内联存储、两阶段删除等，体会Redis极致的性能优化哲学。
- 第6天：完整测试与评估 进行百万级数据压力测试，对比渐进式与一次性rehash性能，整理代码并交付。
最终成果：约1678行完整实现，附带详尽文档与测试用例。
四、Intset：三天读懂Redis的“内存抠门”艺术
如果说Dict是“大工程”，Intset就是“小心思”。它目标纯粹：高效存储一组整数。但Redis将其做到了极致。
4.1 为什么不用简单数组？
假设存储 [1, 2, 3, 100, 200]。如果用int32数组，每个占4字节，共20字节。
但如果只存[1, 2, 3]呢？用int32就浪费了，int16足矣。
Intset的设计正在于此：根据集合中最大整数的值，动态选择最节省空间的编码方式。
内存布局：
encoding(4B) length(4B) contents[]
──────────────────────────────────────────
│ 编码类型 │ 元素个数 │ 有序整数数组 │
──────────────────────────────────────────
encoding 的三种值：
INTSET_ENC_INT16 → 每个元素 2 字节，范围 -32768 ~ 32767
INTSET_ENC_INT32 → 每个元素 4 字节，范围约 ±21亿
INTSET_ENC_INT64 → 每个元素 8 字节，范围超大整数
关键点：数据在contents中是有序存储的，因此查找时可以使用二分搜索，达到 O(log n) 复杂度。
4.2 编码升级：精彩的“动态扩军”
假设当前intset为[1, 2, 3]，编码为INT16，占6字节。
现在要插入70000（超出INT16范围），必须将编码升级为INT32。
升级前（INT16，每元素2字节）：
contents: [1][2][3] 共6字节
升级步骤：
1. 重新分配内存：(3+1) × 4 = 16 字节
2. 从后往前迁移！（避免覆盖未迁移的数据）
先移动 3 → 放到新位置
再移动 2 → 放到新位置
再移动 1 → 放到新位置
最后插入 70000（因有序，大数必然在末尾）
升级后（INT32，每元素4字节）：
contents: [1][2][3][70000] 共16字节
重要特性：编码只能升级，不能降级。即使后续删除了70000，编码仍保持INT32。这是因为降级需要遍历检查所有元素，代价较高。Redis在此选择了以少许空间换取实现简洁与稳定，这是一种典型的工程权衡思维。
4.3 Intset模块：3天实现路径
- 第1天：基础建设 设计数据结构，厘清内存布局，实现字节序转换模块，完成创建、获取长度等基础API。
- 第2天：核心算法 实现二分查找
intsetSearch，完成最精彩的编码升级函数intsetUpgradeAndAdd，实现完整的增删逻辑。
- 第3天：收尾完善 实现随机获取元素、集合完整性校验等功能，编写完整测试套件，交付项目。
最终成果：约734行完整实现，附带详尽文档与测试用例。
五、实践出真知：看懂与实现的差距
一个真实的例子：有学员在学SDS前说：“这不就是个动态字符串嘛，挺简单。”实现之后他反馈：“原来之前理解全是错的。返回指针为什么指向buf而不是header？为什么有5种header？预分配为什么是翻倍？”。
看懂了以为懂了，动手写才发现不懂。 我的课程设计正是为了填补这个鸿沟：每天从最小可运行版本开始，增量编码，最终得到一个完整、可用、高性能的实现。你不是在复制粘贴，而是在理解每一行代码为何如此编写。
六、你能收获什么？
- Dict模块（6天，1678行）：你将真正吃透渐进式rehash，能在面试中清晰阐述rehashidx的作用、读写流程、以及
dictScan算法的奥秘，而非泛泛而谈。
- Intset模块（3天，734行）：你会掌握Redis极致内存优化的思路，理解编码升级背后的工程权衡。这种“按需分配、动态升级”的设计思想，适用于任何系统设计场景。
两个模块共计9天，代码量2412+行，配套完整文档与测试用例。
最后
学习Redis源码，目的不是为了夸夸其谈，而是为了在未来设计系统时，能自然而然地运用这些精妙的思想：“这里可以用渐进式迁移平滑扩容”，“这里可以用编码升级节省内存”。这才是深入源码的核心价值。
希望这篇对Redis Dict和Intset的拆解，能为你打开一扇从理解到实践的大门。如果你对这类深入底层、动手实学的技术内容感兴趣，欢迎在云栈社区与我们交流探讨。
发表于 11 小时前
|
查看: 8|
回复: 0
