Redis 源码硬核解析系列专题 - 第三篇：核心数据结构之字典（Dict）

第三篇：核心数据结构之字典（Dict）

1. 引言

字典（Dict）是Redis的核心数据结构之一，用于实现键值存储（Redis数据库的核心）和内部元数据管理（如客户端状态）。Redis的字典基于哈希表实现，支持高效的增删改查操作。本篇将深入剖析其源码实现，包括哈希表结构、冲突解决和渐进式rehash机制。

2. 字典的结构体定义

字典的定义在src/dict.h和src/dict.c中。以下是核心结构：

代码片段（dict.h）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
typedef struct dictEntry {
    void *key;               // 键
    union {
        void *val;           // 值
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;  // 链表，解决哈希冲突
} dictEntry;

typedef struct dictht {
    dictEntry **table;       // 哈希表数组
    unsigned long size;      // 哈希表大小
    unsigned long sizemask;  // 大小掩码，用于计算索引
    unsigned long used;      // 已使用槽数
} dictht;

typedef struct dict {
    dictType *type;          // 类型特定函数（如自定义哈希）
    void *privdata;          // 私有数据
    dictht ht[2];            // 两个哈希表，用于rehash
    long rehashidx;          // rehash进度，-1表示未进行
} dict;

硬核解析：

dictEntry：键值对节点，next指针形成链表解决冲突。
dictht：哈希表，size是2的幂次，sizemask = size - 1。
dict：包含两个哈希表ht[0]和ht[1]，支持渐进式rehash。

Mermaid结构图：

classDiagram
    class dict {
        -type: dictType*
        -privdata: void*
        -ht[2]: dictht
        -rehashidx: long
    }
    class dictht {
        -table: dictEntry**
        -size: ulong
        -sizemask: ulong
        -used: ulong
    }
    class dictEntry {
        -key: void*
        -v: union
        -next: dictEntry*
    }
    dict o--> "2" dictht
    dictht o--> "n" dictEntry
    dictEntry o--> "1" dictEntry : "next"

3. 核心操作解析

3.1 添加键值对（`dictAdd()`）

代码片段（dict.c）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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) {
    if (dictIsRehashing(d)) _dictRehashStep(d); // 单步rehash
    int index = dictHashKey(d, key) & d->ht[0].sizemask;
    dictEntry *entry = zmalloc(sizeof(*entry));
    entry->next = d->ht[0].table[index];
    d->ht[0].table[index] = entry;
    d->ht[0].used++;
    dictSetKey(d, entry, key);
    return entry;
}

硬核解析：

哈希计算：dictHashKey()调用自定义哈希函数，默认是MurmurHash2。
索引计算：key_hash & sizemask，快速定位槽。
冲突处理：链地址法，插入到链表头部。

3.2 查找键（`dictFind()`）

代码片段（dict.c）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
dictEntry *dictFind(dict *d, const void *key) {
    if (d->ht[0].used + d->ht[1].used == 0) return NULL;
    if (dictIsRehashing(d)) _dictRehashStep(d);
    unsigned long hash = dictHashKey(d, key);
    for (int i = 0; i <= 1; i++) {
        unsigned long idx = hash & d->ht[i].sizemask;
        dictEntry *he = d->ht[i].table[idx];
        while (he) {
            if (dictCompareKeys(d, key, he->key)) return he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;
    }
    return NULL;
}

硬核解析：

检查ht[0]和ht[1]（rehash期间需两表查找）。
链表遍历对比键，dictCompareKeys()支持自定义比较。

3.3 渐进式rehash

触发条件：

负载因子（used/size）超过阈值（默认1，或更高若有AOF写入）。
通过_dictExpand()分配新表ht[1]。

代码片段（_dictRehashStep()）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
static void _dictRehashStep(dict *d) {
    if (d->rehashidx == -1) return;
    while (d->rehashidx < d->ht[0].size && d->ht[0].table[d->rehashidx] == NULL)
        d->rehashidx++;
    if (d->rehashidx < d->ht[0].size) {
        dictEntry *he = d->ht[0].table[d->rehashidx];
        while (he) {
            dictEntry *next = he->next;
            unsigned long idx = dictHashKey(d, he->key) & d->ht[1].sizemask;
            he->next = d->ht[1].table[idx];
            d->ht[1].table[idx] = he;
            he = next;
        }
        d->ht[0].table[d->rehashidx] = NULL;
        d->rehashidx++;
    }
}

硬核解析：

渐进式迁移：每次操作只迁移一个桶（rehashidx）。
时间分摊：避免一次性rehash阻塞主线程。
完成标志：rehashidx >= ht[0].size时，释放ht[0]，ht[1]变为ht[0]。

Mermaid rehash流程：

graph TD
    A["dictAdd/dictFind"] --> B["dictIsRehashing()"]
    B -->|Yes| C["_dictRehashStep()"]
    C --> D{"rehashidx < size?"}
    D -->|Yes| E["迁移当前桶"]
    E --> F["rehashidx++"]
    F --> D
    D -->|No| G["rehash完成"]

4. 哈希冲突与扩容缩容

冲突解决：链地址法，next指针形成链表。
扩容：used/size > 1时，size翻倍（_dictExpand()）。
缩容：used/size < 0.1时，size减半（_dictContract()）。

5. 总结与调试建议

收获：理解Redis字典的哈希表实现与rehash优化。
调试技巧：用gdb打印ht[0].table（如p d->ht[0].table[0]），观察链表结构。
下一步：探索跳表（Skip List）在ZSET中的应用。

Redis 源码硬核解析系列专题 - 第三篇：核心数据结构之字典（Dict）

相关文章：