一、Redis字典：哈希表在内存数据库中的实战
说到哈希表在生产环境的应用，Redis的字典实现绝对是个绕不开的经典案例。我当年刚接触Redis源码时，第一反应是：这不就是个哈希表吗？但深入看下去才发现，里面藏着不少工程智慧。
Redis的字典，说白了就是一个高性能的键值对容器。它用哈希表作为底层数据结构，但做了很多针对内存数据库场景的优化。你想想看，Redis要处理每秒几十万的读写请求，哈希表的效率直接决定了整个数据库的性能。
1.1 字典的数据结构
Redis的字典定义在dict.h中，核心结构是这样的：
typedef struct dict {
dictType *type; // 类型特定函数
void *privdata; // 私有数据
dictht ht[2]; // 两个哈希表，用于渐进式rehash
long rehashidx; // rehash进度，-1表示未进行
int16_t pauserehash; // rehash是否暂停
} dict;这里有个有意思的设计——ht[2]。为什么需要两个哈希表？
嗯，这就是Redis实现渐进式rehash的关键。平时只用一个哈希表（ht[0]），当需要扩容或缩容时，ht[1]就会被分配空间，然后数据慢慢从ht[0]迁移到ht[1]。
每个哈希表的结构也很清晰：
typedef struct dictht {
dictEntry **table; // 哈希表数组
unsigned long size; // 哈希表大小
unsigned long sizemask; // 大小掩码，用于计算索引值
unsigned long used; // 已使用节点数
} dictht;我个人习惯把sizemask理解为"快速取模工具"。因为hash & sizemask比hash % size快得多，前提是size必须是2的幂。Redis就是这么干的。
1.2 哈希冲突的解决方式
Redis采用链地址法解决哈希冲突。每个哈希桶（bucket）指向一个链表，新节点插入到链表头部。
为什么是头插法？我记得在项目中做过测试，头插法在热点数据频繁访问的场景下，性能确实比尾插法好。因为最近插入的数据往往很快就会被再次访问，放在链表头部可以减少遍历次数。
节点结构长这样：
typedef struct dictEntry {
void *key; // 键
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v; // 值，支持多种类型
struct dictEntry *next; // 指向下一个节点
} dictEntry;注意这个union，Redis把值设计成联合体，可以直接存储整数或浮点数，省去了指针间接访问的开销。这种细节优化，在百万级QPS的场景下，效果非常明显。
核心要点：Redis字典采用双哈希表结构，支持渐进式rehash；使用链地址法解决冲突，头插法提升热点数据访问效率。
二、渐进式rehash：不停机扩容的艺术
哈希表扩容时，如果一次性把所有数据重新哈希到新表，那Redis就得"卡住"一会儿。对于线上服务来说，这简直是灾难。
Redis的解决方案是渐进式rehash。说白了，就是把一次大迁移，拆成多次小迁移，每次只搬一点点数据。
2.1 触发条件
什么时候开始rehash？Redis有两个关键指标：
- 负载因子 = used / size
- 当负载因子大于等于1时，触发扩容（如果正在执行BGSAVE或BGREWRITEAOF，阈值提高到5）
- 当负载因子小于0.1时，触发缩容
为什么BGSAVE期间要调高阈值？我曾经踩过这个坑。BGSAVE会fork子进程，采用写时复制技术。如果这时候扩容，父进程需要分配大量新内存，会导致写时复制的页表变大，内存消耗暴增，甚至OOM。
2.2 执行过程
渐进式rehash的流程，我画了张图帮你理解：
具体执行时，Redis会在每次增删改查操作中，顺带迁移一个桶的数据。比如你执行SET key value，Redis先查一下rehashidx，如果不是-1，就顺手把ht[0]中rehashidx指向的那个桶搬到ht[1]。
代码逻辑大致如下：
// 每次执行CRUD前，调用此函数
int dictRehash(dict *d, int n) {
int empty_visits = n * 10; // 最多跳过10n个空桶
while (n-- && d->ht[0].used != 0) {
dictEntry *de, *nextde;
// 跳过空桶
while (d->ht[0].table[d->rehashidx] == NULL) {
d->rehashidx++;
if (--empty_visits == 0) return 1;
}
// 迁移当前桶的所有节点
de = d->ht[0].table[d->rehashidx];
while (de) {
uint64_t h = dictHashKey(d, de->key) & d->ht[1].sizemask;
nextde = de->next;
de->next = d->ht[1].table[h];
d->ht[1].table[h] = de;
d->ht[0].used--;
d->ht[1].used++;
de = nextde;
}
d->ht[0].table[d->rehashidx] = NULL;
d->rehashidx++;
}
// 检查是否全部迁移完成
if (d->ht[0].used == 0) {
zfree(d->ht[0].table);
d->ht[0] = d->ht[1];
dictReset(&d->ht[1]);
d->rehashidx = -1;
return 0;
}
return 1;
}避坑指南：我曾经在生产环境遇到过一个问题——某个Redis实例的rehash一直没完成。排查后发现，是因为那个实例长时间没有读写操作，rehash进度卡住了。解决方案是配置了定时任务，定期执行SCAN 0命令，触发rehash推进。
2.3 查找时的策略
渐进式rehash期间，查找操作需要同时查两个表。先查ht[1]，如果没找到，再查ht[0]。为什么先查新表？因为大部分数据已经迁移到ht[1]了，先查新表命中率更高。
插入操作则只插入到ht[1]，这样能保证ht[0]的数据只减不增，最终全部迁移完成。
三、哈希表与过期策略
Redis的键过期功能，底层也依赖哈希表。每个数据库都有一个expires字典，专门存储键的过期时间。
3.1 过期字典的结构
expires字典的键指向数据库中的键对象，值是一个long long类型的毫秒级时间戳。说白了，就是记录"这个键什么时候该消失"。
// Redis数据库结构
typedef struct redisDb {
dict *dict; // 键空间，存储所有键值对
dict *expires; // 过期字典，存储键的过期时间
// ... 其他字段
} redisDb;3.2 过期删除策略
Redis用了三种策略的组合拳：
| 策略 | 原理 | 优缺点 |
|---|---|---|
| 惰性删除 | 访问键时检查是否过期，过期则删除 | 节省CPU，但可能占用内存 |
| 定期删除 | 每隔100ms随机抽查一批键，删除过期的 | 平衡CPU和内存 |
| 内存淘汰 | 内存不足时，按策略淘汰键 | 兜底策略，防止OOM |
定期删除的实现很有意思。它每次从expires字典中随机取20个键，删除其中过期的。如果过期比例超过25%，就再取20个，循环最多16次。这种设计既不会占用太多CPU，又能及时清理过期键。
注意：如果大量键同时过期，Redis可能会短暂卡顿。我建议你在业务中避免设置大量键在同一秒过期，可以加一个随机偏移量，比如EXPIRE key 3600 + random(0, 300)。
3.3 哈希表在过期检查中的角色
你想想看，如果没有哈希表，Redis怎么快速找到某个键的过期时间？
答案是：哈希表的O(1)查找。无论是惰性删除时的dictFind(expires, key)，还是定期删除时的随机采样，都依赖哈希表的高效性。
而且，expires字典和主键空间共用键对象，不额外存储键的副本，节省了内存。这种设计在存储上亿键时，能省下好几个GB的内存。
总结一下：Redis用哈希表实现了高性能的字典，用渐进式rehash解决了扩容时的服务中断问题，用过期字典配合多种删除策略，在内存和CPU之间找到了平衡点。这些设计思路，你在自己实现哈希表时完全可以借鉴。
好了，这一章的内容就到这里。哈希表在Redis中的应用远不止这些，比如哈希对象本身也用到了压缩列表和哈希表的转换，那是另一个有趣的话题了。
公众号:蓝海资料掘金营，微信deep3321