Redis 源码手撕实录:我用9天时间,从0写出了Dict哈希表和Intset整数集合

大家好，我是小康。

今天这篇文章，我想换一种方式聊Redis。

不聊「Redis为什么快」，不聊「Redis有哪些数据类型」——这些你随便搜都能找到一堆。

我想聊一个更硬核的问题：

如果让你现在打开编辑器，从第一行代码开始，把Redis的哈希表写出来，你能写吗？

大多数人的答案是：不能。

不是因为你不聪明，而是因为看懂和写出来，是两件完全不同的事。

一、一个让我印象深刻的面试现场

前段时间，一个粉丝朋友私信我，说他去面某大厂，面试官问了这样一个问题：

“Redis的哈希表扩容时，为什么不会卡顿？”

他回答了「渐进式rehash」，面试官点点头，继续追问：

“那rehash期间，读写操作怎么处理？rehashidx是什么意思？迁移是按什么顺序进行的？”

然后就卡住了。

他说自己在网上看过很多渐进式rehash的讲解，感觉都懂了，但面试官一深挖，发现全是皮毛。

这种感觉你熟悉吗？

看文章的时候觉得懂了，闭上眼睛什么都不剩。

根本原因在于：你从来没有自己实现过。

二、我最近做了什么

过去这段时间，我把精力集中在了两个方向：

一是研究Redis 7.x的核心源码（9万行+），二是把这些内容转化成能让人真正学会的课程。

目前，继SDS和Adlist两个模块之后，Dict哈希表和Intset整数集合这两个核心模块已经完成制作。

这两个模块，我认为是Redis数据结构里最有学习价值的：

• Dict：渐进式rehash是整个Redis性能稳定性的基石，不理解它，你对Redis的理解就是残缺的
• Intset：小而精，展示了Redis在内存优化上的极致追求，编码升级机制非常精妙

今天这篇文章，我想把这两个模块的核心设计思想完整讲给你听。

三、Dict：一张哈希表为什么不够用？

先从一个问题开始思考：

Redis的哈希表，和你在数据结构课上学的哈希表，最大的区别是什么？

答案是：Redis用了两张哈希表，而不是一张。

为什么？

3.1 单哈希表的致命问题

想象你有一张哈希表，初始16个槽位，随着数据越来越多，到了某个临界点，Redis必须扩容——比如扩到32个槽位。

扩容意味着什么？所有的key都要重新计算哈希值，重新分配位置。

如果你有100万个key，扩容瞬间要做100万次操作。在这期间，Redis完全卡住，无法响应任何请求。

这对于一个「每秒10万请求」的系统来说，是不可接受的。

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个桶开始迁移）

每次对dict的增删改查操作，顺便把ht[0]的一个桶迁移到ht[1]。

100万个key的迁移，被拆分成100万次微小操作，分散在日常请求里完成——用户感知不到任何卡顿。

这就是「渐进式rehash」的精髓。

3.3 rehash期间的读写规则

这里有个细节很重要，也是面试常考的：

写操作：新数据只写入ht[1]，不写ht[0]。这样ht[0]的数据只减不增，迁移终会完成。

读操作：先查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 链地址法冲突解决，完成基础增删改查，写一个 SipHash 简化版哈希函数，跑通第一个测试用例。

第2天：扩容机制 搞清楚负载因子怎么算、扩容在什么条件下触发，先实现一次性 rehash 版本，把原理摸透再引入渐进式。

第3天：渐进式 Rehash（最核心） 引入双哈希表结构，实现 rehashidx 标记机制，让每次增删改查都顺带推进一步迁移，直到 ht[0] 清空为止。

第4天：迭代器与扫描 实现安全迭代器和非安全迭代器，重点吃透 dictScan 的反向位递增算法——这是 rehash 期间遍历不漏 key 的核心秘密。

第5天：高级特性 实现 no_value 模式（只存 key 节省内存）、整数值直接存储优化、两阶段删除机制，理解 Redis 为性能抠到极致的工程哲学。

第6天：完整测试 + 性能评估 百万级数据压力测试，渐进式 rehash 与一次性 rehash 性能对比，代码整理，项目交付。

完整实现代码量：1678 行，配套详细文档和完整测试用例。

四、Intset：三天搞定Redis最精妙的「小心思」

如果说Dict是Redis的「大工程」，那Intset就是Redis的「小心思」。

它只做一件事：高效存储一组整数。

但就是这么简单的需求，Redis做到了极致。

4.1 为什么不用普通数组？

假设你有一组整数：1, 2, 3, 100, 200

如果用 int32 数组存，每个元素4字节，总共20字节，没问题。

但如果你只有 1, 2, 3 这三个小数字呢？用 int32 完全是浪费——int16 就够了，能省一半空间。

Redis 的 Intset 正是这样设计的：根据当前数据集里最大的数，动态选择编码方式。

内存布局： encoding(4B)   length(4B)    contents[] ────────────────────────────────────────── │   编码类型  │  元素个数  │  有序整数数组  │ ──────────────────────────────────────────encoding 的三种值：  INTSET_ENC_INT16 → 每个元素 2 字节，能存 -32768 ~ 32767  INTSET_ENC_INT32 → 每个元素 4 字节，能存 ±21亿  INTSET_ENC_INT64 → 每个元素 8 字节，能存超大整数

数据是有序存储的！ 这样查找时可以用二分搜索，O(log n) 直接搞定。

4.2 编码升级：最精彩的「扩编制」机制

假设你的 intset 里现在存着 [1, 2, 3]，编码是 INT16，占6字节。

现在要插入一个数：70000（超过 INT16 的范围）

怎么办？必须把编码从 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，编码也不会降回 INT16。

为什么？因为降级需要遍历所有数据重新校验，代价不低，Redis选择牺牲一点空间换取实现的简洁性——这背后是非常典型的工程权衡思维。

4.3 Intset 3天实现路径

第1天：打地基 设计数据结构，画清楚内存布局，实现 endianconv 字节序模块（大端/小端转换），完成 intsetNew、intsetLen、底层读写函数，跑通基础冒烟测试。

第2天：核心算法 实现 intsetSearch 二分查找，实现编码升级的核心函数 intsetUpgradeAndAdd（最精彩的部分），完成 intsetAdd 和 intsetRemove 的完整增删逻辑，覆盖所有边界 case。

第3天：完善收尾 实现 intsetRandom 随机采样（Redis 的 Set 命令需要它），实现 intsetValidateIntegrity 完整性校验，编写完整测试套件，代码整理、注释完善，项目交付。

完整实现代码量：734 行，配套详细文档和完整测试用例。

五、光看不练，永远是门外汉

我想跟你说一件真实的事。

有个学员，学SDS之前跟我说：「小康哥，我感觉SDS挺简单的，就是个动态字符串嘛。」

学完之后他发消息给我：「原来我之前对SDS的理解全是错的。为什么返回的指针指向buf而不是header？为什么有5种不同的header类型？为什么预分配策略是翻倍而不是固定增量？这些细节我之前完全没想过。」

看懂了感觉懂了，动手写才知道自己不懂。

我的课程设计思路是这样的：每天都从最小可运行版本出发，一点点增量实现，到最后一天交付完整的、可用的、性能优秀的实现。

不是一上来就给你完整代码——那样你只是个复制粘贴机器。

而是带着你一步步写，每一行代码都知道为什么这么写。

六、两个模块，能学到什么？

Dict模块（6天，源码1678行）：

你会真正理解渐进式rehash，而不是只会背定义。面试官问你rehash期间读写怎么处理、dictScan为什么用反向位递增算法，你能详细讲清楚每一个细节，而不是说「好像是……」。

Intset模块（3天，源码734行）：

你会理解Redis是怎么用最少的内存存最多的数据的，编码升级机制背后的工程权衡是什么。这套「按需分配、动态升级」的思路，在你以后设计任何系统时都会受用。

两个模块合计9天，代码量合计2412行+，配套详细文档和完整测试用例。

七、课程定价

Dict + Intset 两模块合集：200元

包含：

• Dict模块（6天）：完整源码（1678行）+ 详细文档 + 测试用例
• Intset模块（3天）：完整源码（734行）+ 详细文档 + 测试用例
• 专属学习群：技术答疑 + 代码 Review

八、想系统学完整个Redis？现在是最好的时机

Redis 7.x 源码实战完整版（16+个核心模块），当前报名价 1500元。

课程涵盖：

• 基础数据结构篇（6个）：SDS、Adlist、Dict、Skiplist、Intset、Ziplist

• 核心对象系统（2个）：Object、Database

• 网络与事件驱动（3个）：AE、Networking、Server

• 分布式特性（3个）：Replication、Sentinel、Cluster

• 性能优化（2个）：内存优化、生产级特性

• 等等其他核心模块

这里我需要说清楚一件事：这门课的价格一直在涨，而且是真涨。

最早一批学员以 1200 元报名，后来调整到了现在的 1500 元。根据目前的课程制作进度，预计一周左右价格会上调到 1800 元。

课程内容还在持续制作中，等到全部16+个模块完成交付，定价大概率会到 2500 元以上。

所以，你现在报名 1500 元，就是当前能拿到的最低价。等你犹豫完，价格可能就不一样了。

Redis项目实战课程详情可以看这篇文章：Redis 7.x 源码实战课程来了！从0到1手写Redis核心模块

九、这门课适合你吗？

以下任意一条符合，这门课就值得你认真考虑：

• 想在面试时把「渐进式rehash」讲得比面试官还清楚的——适合。
• 在校生，想要一个有说服力的 C 语言实战项目写进简历的——适合。
• 工作了好几年，一直在用 Redis 但从没搞清楚底层到底怎么跑的——适合。
• 准备跳槽，想在技术深度上拉开和竞争者差距的——适合。
• 想系统啃一遍经典开源项目源码、提升自己架构设计感觉的——更适合。

如果你已经在这个行业里摸爬滚打了一段时间，你会知道：真正能把底层讲清楚的人，在团队里是不一样的存在。

这门课，就是帮你成为那种人的。

十、如何报名

三步搞定：

1. 扫下方二维码，添加小康微信（或微信搜索：jkfwdkf）
2. 备注「 Dict 」
3. 告知选择版本（200元两模块 / 1500元完整版），确认后 微信/支付宝 付款

付款后当天进群，立即获取全部学习资料。

扫码加小康微信：

最后说一句话：

学Redis源码，不是为了能在饭桌上吹牛。

是为了有一天你设计系统的时候，脑子里自然而然会想到：

「这里可以用渐进式迁移，这里可以用编码升级来节省内存，这里可以用反向位算法来保证遍历不漏……」

这才是啃源码真正的价值。

我是小康，我们课程里见。👋

💬 你觉得Dict的渐进式rehash和Intset的编码升级，哪个设计更让你惊艳？评论区聊聊！

十一、对C++项目更感兴趣？这里还有18个硬核项目等你

从去年7月到现在，我陆续完成了18个C++硬核项目实战课程，已经带领 350+ 同学从零开始实现这些项目。这些同学中有985、211的，也有普通本科的，大家都收获满满。

课程覆盖三大方向：

基础设施：线程池、高性能内存池、MySQL连接池、高性能日志库MiniSpdlog、无锁异步日志库ZephyrLog、内存泄漏检测器、死锁检测工具

高性能组件：事件驱动组件ReactorX、无锁栈、无锁队列SPSC、无锁队列MPMC、工业级智能指针shared_ptr

综合实战：高性能网络库NetCore、FlashHTTP高性能服务器(性能超过大部分开源httpserver项目)、协程库CoroForge、多线程下载工具FastDL、HTTP压测工具(类似于wrk)

每一个项目都是增量式教学，从第一行代码带你写到最终交付，每天都能编译运行，每天都有成就感。

👉 感兴趣的朋友点这里查看完整课程介绍：为什么同样是”学过C++”，有人面试碾压，有人开口就怂？差距在这18个C++硬核项目

• 对C++项目实战课程感兴趣的朋友，可以扫下方二维码添加小康微信
• 备注「 项目实战 」