Redis作为高性能的内存数据库，其高效性很大程度上依赖于精心设计的数据结构。其中，字典（Hash Table） 是最核心的结构之一（如Hash类型的底层实现），而它的扩容和rehash机制则是保证Redis在海量数据下仍能高效运行的关键。本文将从基础数据结构讲起，深入剖析字典的扩容逻辑与rehash流程，并结合源码带你彻底搞懂这一核心机制。

一、Redis核心数据结构：不止于表面的"键值对"

Redis对外提供了String、Hash、List、Set、ZSet等数据类型，但这些都是"上层抽象"，底层由更基础的结构实现。其中，字典（Dictionary） 是最核心的底层结构（类似Java的HashMap），被广泛用于实现Hash类型、Redis数据库本身（存储所有键值对）等。

我们先快速了解Redis的基础数据结构，重点关注字典：

底层结构	用途举例	特点
简单动态字符串	实现String类型、存储键名	可动态扩容的字符串，兼容C字符串
双向链表	实现List类型（小数据量）	支持双向遍历，插入删除高效
字典（哈希表）	实现Hash类型、存储数据库键值对	键值对映射，O(1)查找效率
跳跃表	实现ZSet类型、集群节点信息	有序结构，支持快速范围查询
整数集合	实现Set类型（元素为整数且少量）	紧凑存储，避免内存浪费
压缩列表	实现List/Hash/ZSet（小数据量）	连续内存存储，节省空间

重点：字典的结构设计

字典的核心是哈希表，Redis的哈希表采用"数组+链表"的链地址法解决哈希冲突（和Java HashMap类似）。其结构定义如下（简化自Redis源码dict.h）：

// 哈希表节点：存储键值对
typedef struct dictEntry {
    void *key;                  // 键
    union {                     // 值（联合体，支持多类型）
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    struct dictEntry *next;     // 下一个节点，解决哈希冲突（链表）
} dictEntry;

// 哈希表
typedef struct dictht {
    dictEntry **table;          // 哈希表数组（存储指向节点的指针）
    unsigned long size;         // 数组容量（2^n）
    unsigned long sizemask;     // 掩码，用于计算索引（size-1）
    unsigned long used;         // 已存储的节点数量
} dictht;

// 字典
typedef struct dict {
    dictType *type;             // 类型特定函数（如哈希函数、比较函数）
    void *privdata;             // 私有数据，传给类型函数
    dictht ht[2];               // 两个哈希表！用于rehash
    long rehashidx;             // rehash索引（-1表示未在rehash）
    unsigned long iterators;    // 正在迭代的迭代器数量
} dict;

关键细节：

• 字典包含ht[0]和ht[1]两个哈希表，正常情况下只用ht[0]，ht[1]在rehash时使用。
• sizemask = size - 1，用于计算键的索引：index = hash(key) & sizemask（类似HashMap的取模运算，但更高效）。

二、为什么需要扩容？从"负载因子"说起

当哈希表中存储的元素越来越多，哈希冲突会加剧（链表变长），导致查询效率从O(1)退化到O(n)。为了维持高效查询，Redis会在合适的时机触发扩容（扩大哈希表容量），而扩容的判断依据是负载因子（load factor）。

1. 负载因子的计算

负载因子 = 哈希表已使用节点数 / 哈希表容量
即：load_factor = ht[0].used / ht[0].size

2. 扩容的触发条件

Redis规定，当满足以下任一条件时触发扩容：

• 服务器没有执行BGSAVE或BGREWRITEAOF（后台持久化），且负载因子 > 1。
• 服务器正在执行后台持久化，且负载因子 > 5。

为什么持久化时阈值更高？
因为后台持久化会fork子进程，此时Redis为了减少内存页的复制（Copy-On-Write机制），会暂时放宽扩容条件，避免不必要的内存分配。

三、rehash流程：哈希表的"平滑迁移"

扩容的核心是rehash（重新计算键的哈希值和索引，迁移数据到新哈希表）。但Redis是单线程模型，若直接一次性迁移大量数据，会阻塞主线程导致服务卡顿。因此，Redis采用渐进式rehash策略。

1. 全量rehash的问题

假设哈希表容量从4扩容到8，全量rehash需要：

1. 新建ht[1]，容量为ht[0].size * 2（保证是2的幂，方便计算索引）。
2. 遍历ht[0]的所有链表，将每个节点重新计算索引并迁移到ht[1]。
3. 迁移完成后，ht[0]清空，ht[1]变为新的ht[0]。

若ht[0]有百万级节点，全量迁移会导致Redis卡顿几十毫秒甚至秒级，这在高并发场景下是不可接受的。

2. 渐进式rehash："见缝插针"迁移数据

渐进式rehash的核心是将迁移工作分摊到每次字典操作中（如增删改查），避免一次性阻塞。步骤如下：

1. 初始化rehash：
   当触发扩容时，为ht[1]分配新容量（ht[0].size * 2），设置rehashidx = 0（表示开始rehash）。

2. 分步迁移：
   每次对字典执行操作时（如dictAdd、dictFind），除了正常处理操作，还会顺带迁移ht[0].table[rehashidx]链表的所有节点到ht[1]，然后rehashidx++。

3. 处理新操作：
   rehash期间，新添加的键会直接放入ht[1]，不影响ht[0]的迁移。

4. 完成rehash：
   当ht[0]的所有节点都迁移到ht[1]后，rehashidx设为-1，ht[0]指向ht[1]，ht[1]重置为空，扩容完成。

举例：渐进式rehash的过程

假设ht[0].size=4（容量4），ht[1].size=8（扩容后），rehashidx=0：

• 第一次操作字典：迁移ht[0].table[0]的所有节点到ht[1]，rehashidx=1。
• 第二次操作字典：迁移ht[0].table[1]的所有节点，rehashidx=2。
• 以此类推，直到rehashidx=4（超过ht[0].size-1），表示迁移完成。

四、源码分析：rehash的核心实现

我们结合Redis源码（dict.c），看渐进式rehash的关键逻辑。

1. 扩容触发函数：dictExpand

当需要扩容时，Redis会调用dictExpand函数初始化ht[1]：

int dictExpand(dict *d, unsigned long size) {
    // 已在rehash或新容量小于已使用节点数，不扩容
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;

    dictht n;  // 新哈希表
    unsigned long realsize = _dictNextPower(size);  // 计算下一个2的幂

    // 新容量等于当前容量，无需扩容
    if (realsize == d->ht[0].size)
        return DICT_ERR;

    // 初始化新哈希表
    n.size = realsize;
    n.sizemask = realsize - 1;
    n.table = zcalloc(realsize * sizeof(dictEntry*));  // 分配内存
    n.used = 0;

    // 如果ht[0]为空，直接用新表替换
    if (d->ht[0].table == NULL) {
        d->ht[0] = n;
        return DICT_OK;
    }

    // 否则，准备渐进式rehash：ht[1]设为新表，rehashidx=0
    d->ht[1] = n;
    d->rehashidx = 0;
    return DICT_OK;
}

关键逻辑：

• _dictNextPower确保新容量是"大于等于指定size的最小2的幂"（如传入5，返回8），保证sizemask能正确计算索引。
• 若ht[0]非空，设置rehashidx=0，标志着渐进式rehash开始。

2. 渐进式迁移函数：dictRehash

每次操作字典时，会调用dictRehash迁移部分数据（默认迁移100个桶）：

int dictRehash(dict *d, int n) {
    int empty_visits = n*10;  // 最多访问n*10个空桶
    if (!dictIsRehashing(d)) return 0;

    // 迁移n个桶，或直到ht[0]为空
    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];
        // 迁移该桶的所有节点到ht[1]
        while (de) {
            unsigned int h;
            nextde = de->next;

            // 计算在ht[1]中的索引
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            // 插入到ht[1]的链表头部
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;

            d->ht[0].used--;  // ht[0]计数减1
            d->ht[1].used++;  // ht[1]计数加1
            de = nextde;
        }
        // 迁移完成，清空当前桶
        d->ht[0].table[d->rehashidx] = NULL;
        d->rehashidx++;  // 下一个桶
    }

    // 如果ht[0]已空，完成rehash
    if (d->ht[0].used == 0) {
        zfree(d->ht[0].table);  // 释放旧表内存
        d->ht[0] = d->ht[1];    // ht[0]指向新表
        _dictReset(&d->ht[1]);  // 重置ht[1]
        d->rehashidx = -1;      // 标志rehash结束
        return 0;
    }

    // 还有数据未迁移，返回1
    return 1;
}

关键逻辑：

• 每次迁移n个桶（默认100），避免一次迁移过多。
• 跳过空桶，提高迁移效率。
• 迁移时将节点插入ht[1]的链表头部（头插法，O(1)操作）。
• 当ht[0].used == 0时，完成rehash，ht[0]切换到新表。

3. 操作时触发迁移：dictAdd示例

在添加键值对时，Redis会先检查是否在rehash，若是则触发部分迁移：

int dictAdd(dict *d, void *key, void *val) {
    dictEntry *entry = dictAddRaw(d, key, NULL);
    if (!entry) return DICT_ERR;
    dictSetVal(d, entry, val);
    return DICT_OK;
}

dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing) {
    // 若在rehash，先迁移一个桶（分摊工作）
    if (dictIsRehashing(d)) _dictRehashStep(d);

    // 计算键的索引
    unsigned int h, idx;
    dictEntry *entry;

    // 检查键是否已存在
    if ((entry = dictFind(d, key)) != NULL) {
        if (existing) *existing = entry;
        return NULL;
    }

    // 若ht[1]已初始化（rehash中），使用ht[1]；否则用ht[0]
    h = dictHashKey(d, key);
    if (dictIsRehashing(d)) {
        idx = h & d->ht[1].sizemask;
    } else {
        idx = h & d->ht[0].sizemask;
    }

    // 创建新节点并插入
    entry = zmalloc(sizeof(*entry));
    entry->next = d->ht[dictIsRehashing(d) ? 1 : 0].table[idx];
    d->ht[dictIsRehashing(d) ? 1 : 0].table[idx] = entry;
    d->ht[dictIsRehashing(d) ? 1 : 0].used++;

    return entry;
}

关键逻辑：

• _dictRehashStep(d)在每次添加前触发一次迁移（迁移1个桶）。
• rehash期间，新键直接添加到ht[1]，避免影响ht[0]的迁移。

Redis定时任务：主动 “加速” rehash 的数据迁移

Redis 虽然是单线程模型，但会在主线程中运行一个周期性的 “服务器 cron 任务”（默认每 100 毫秒执行一次），这个任务的其中一项职责就是：检查是否正在进行 rehash`，如果是，就批量迁移数据，避免 rehash 因 “操作触发” 频率低而迟迟无法完成。

1. 定时任务的核心逻辑：serverCron函数
   Redis 的主线程会不断循环处理请求，每次循环都会调用serverCron函数（定时任务的入口），其中与 rehash 相关的代码逻辑如下（简化自redis.c）：

int serverCron(struct aeEventLoop *eventLoop, long long id, void *clientData) {
    // ... 其他定时任务（如过期键删除、内存回收等） ...

    // 如果有字典正在进行rehash，执行批量迁移
    if (server.activerehashing) {
        // 每次定时任务迁移1000个桶（可配置，默认1000）
        for (int j = 0; j < server.dbnum; j++) {
            // 对每个数据库的字典（db->dict、db->expires）执行批量rehash
            if (dictIsRehashing(server.db[j].dict)) {
                dictRehash(server.db[j].dict, 1000);
                // 迁移后检查是否已完成rehash，避免重复迁移
                if (!dictIsRehashing(server.db[j].dict)) {
                    server.activerehashing--;
                }
            }
            if (dictIsRehashing(server.db[j].expires)) {
                dictRehash(server.db[j].expires, 1000);
                if (!dictIsRehashing(server.db[j].expires)) {
                    server.activerehashing--;
                }
            }
        }
    }

    // ... 其他逻辑 ...
    return 100;  // 下次执行定时任务的间隔（毫秒）
}

定时任务的作用：避免 rehash “卡壳”
场景举例：如果一个字典的哈希表有 10 万个桶，仅靠 “操作触发”（每次操作迁移 1 个桶），若后续对该字典的操作频率很低，rehash 可能需要几小时甚至更久才能完成，期间ht[0]和ht[1]会一直共存，占用额外内存。
定时任务的价值：每 100 毫秒批量迁移 1000 个桶，即使操作频率低，10 万个桶也能在 (10万 / 1000) * 100ms = 10秒 内完成迁移，大幅缩短 rehash 周期，减少内存占用。

两种迁移方式的对比：操作触发 vs 定时任务
两者相辅相成，共同构成 Redis 平滑的 rehash 机制，具体差异如下：

迁移方式	触发时机	迁移量	核心作用
操作触发	每次字典操作（增/删/改/查）	1 个桶	避免单次迁移量过大，保证操作响应速度（不阻塞）
定时任务触发	每 100 毫秒（serverCron 任务）	批量（默认 1000 个桶）	加速剩余数据迁移，避免 rehash 长期未完成

Redis 字典的扩容机制中，数据迁移的核心是渐进式 rehash，它通过两种方式分摊工作：
操作触发：每次字典操作顺带迁移 1 个桶，优先保证主线程不阻塞；
定时任务触发：每 100 毫秒批量迁移 1000 个桶，加速剩余数据迁移，避免 rehash “拖更”。

这两种方式结合，既解决了 “全量 rehash 阻塞主线程” 的问题，又避免了 “仅靠操作触发导致 rehash 过慢” 的隐患，是 Redis 在 “性能” 和 “效率” 之间的精妙平衡。

五、总结：Redis的"高效"秘诀

Redis字典的扩容和rehash机制，体现了其在"高性能"和"稳定性"之间的精妙平衡：

1. 负载因子动态阈值：根据是否在后台持久化调整扩容时机，避免不必要的性能损耗。
2. 渐进式rehash：将数据迁移分摊到每次操作中，避免单线程阻塞，保证服务响应速度。
3. 2的幂容量设计：通过sizemask = size - 1高效计算索引，同时方便扩容时翻倍容量。

理解这一机制，不仅能帮助你更好地使用Redis（如合理设计Hash类型的键值对数量），更能借鉴其"渐进式"思想，在自己的系统中处理大规模数据迁移问题。

由于Redis是通过C语言写的，建议不必苛求源码的深层次理解，只需要大概了解其扩容复制的原理即可

---

Redis的Set类型：为什么有时候有序有时候无序？

Redis的Set类型底层实现会根据元素类型自动切换：单独存数值时用「整数集合（intset）」（有序），加入字符串后会升级为「哈希表（hashtable）」（无序）——不是数值/字符串本身有序或无序，而是存储它们的「底层结构」决定了最终的顺序表现。

底层结构	适用条件（Set类型）	有序性	核心特点
整数集合（intset）	1. 所有元素都是整数；2. 元素数量 ≤ 512（默认配置）	✅ 有序	按数值升序存储，本质是有序数组
哈希表（hashtable）	1. 有非整数元素（如字符串）；2. 元素数量 > 512	❌ 无序	按哈希值存储，本质是哈希表（数组+链表）

二、为什么“单独存数值”会有序？——因为用了intset

当你往Set里只存数值（比如SADD myset 1 3 2），且数量不多时，Redis会用「整数集合（intset）」来存储。

1. intset的结构：天生有序的数组

intset本质是一个按数值升序排列的动态数组，源码定义（简化自intset.h）如下：

typedef struct intset {
    uint32_t encoding;  // 编码方式（存int16_t/int32_t/int64_t）
    uint32_t length;    // 元素个数
    int8_t contents[];  // 存储元素的数组（按升序排列）
} intset;

比如你存1、3、2，intset的contents数组会自动调整为[1,2,3]——插入时会通过二分查找找到“能保持升序”的位置，再插入元素，所以最终读取时（比如SMEMBERS myset）会按数值升序返回，看起来就是“有序”的。

2. 举个例子

# 1. 只存数值，底层是intset（有序）
127.0.0.1:6379> SADD numSet 5 2 8
(integer) 3
127.0.0.1:6379> SMEMBERS numSet  # 按数值升序返回
1) "2"
2) "5"
3) "8"

三、为什么“加入字符串”就无序？——因为升级成了hashtable

当你往原本存数值的Set里加入字符串（比如SADD myset "a"），此时元素不再全是整数，不符合intset的适用条件，Redis会自动把底层结构从「intset」升级为「hashtable」——而hashtable是无序的。

1. hashtable的结构：按哈希值存储，无顺序

hashtable的本质是“数组+链表”（和Java的HashMap类似），存储逻辑是：

• 对每个元素（不管是数值还是字符串）计算哈希值；
• 用哈希值取模得到数组索引，把元素放到对应索引的链表中；
• 读取时（SMEMBERS）会遍历数组和链表，顺序由哈希值和数组索引决定，和“数值大小”“插入顺序”都无关，所以看起来是“无序”的。

2. 举个例子

# 2. 加入字符串，底层升级为hashtable（无序）
127.0.0.1:6379> SADD numSet "a"  # 加入字符串
(integer) 1
127.0.0.1:6379> SMEMBERS numSet  # 顺序混乱，和哈希值相关
1) "a"
2) "2"
3) "8"
4) "5"

四、关键补充：不是所有“存数值”都有序

intset的有序是有条件的，一旦打破条件，也会升级为hashtable（变得无序）：

• 条件1：元素必须全是整数（如1、100、-5），只要有一个非整数（如"1"字符串、3.14浮点数），就升级；
• 条件2：元素数量 ≤ set-max-intset-entries（默认512），超过这个数量，即使全是整数，也会升级为hashtable。

比如：

# 3. 全是整数，但数量超过512，底层升级为hashtable（无序）
127.0.0.1:6379> CONFIG GET set-max-intset-entries
1) "set-max-intset-entries"
2) "512"
# 往Set里加513个整数，再SMEMBERS会发现顺序混乱

五、总结：核心是“底层结构的切换”

Redis的“有序/无序”不是由“数值”或“字符串”本身决定的，而是由存储它们的底层结构决定：

1. 只存整数+数量少 → 用「intset」（有序数组）→ 看起来有序；
2. 加字符串（非整数）/数量超阈值 → 升级为「hashtable」（哈希存储）→ 看起来无序。

如果想让“混合数值和字符串”也保持有序，可以用Redis的ZSet（有序集合），通过给每个元素设置“分数”来控制顺序，比如给数值和字符串分别设分数1、2、3。

要不要我帮你写一段**“Set类型底层切换”的实操示例代码**？可以直观看到intset升级为hashtable的过程，以及有序变无序的效果。

---

Studying will never be ending.

▲如有纰漏，烦请指正~~