当前位置：首页 > news >正文

Redis 哈希表结构详解

news 来源：原创 2025/7/6 4:59:42

Redis 哈希表结构详解

相关链接
redis中 hashtable的 sizemask理解

一、核心结构体定义与作用

Redis 的哈希表实现基于 链表法解决冲突，并采用 渐进式 rehash 策略。其核心结构体包括 dictEntry、dictht 和 dict，三者协作实现高效的键值对存储。

二、结构体逐层解析

1. `dictEntry`：哈希表节点

typedef struct dictEntry {void *key;          // 键（如 SDS 字符串）union {             // 值（支持多种类型）void *val;      // 普通值（指向 redisObject）uint64_t u64;   // 存储无符号整数int64_t s64;    // 存储有符号整数} v;struct dictEntry *next; // 指向下一个节点的指针（解决哈希冲突）
} dictEntry;

• 作用：存储一个键值对。
• 字段说明：
• key：键的指针，通常为字符串（如 user:1001:name）。
• v：联合体，支持多种值类型（如字符串、整数）。
• next：指向下一个节点的指针，形成链表解决哈希冲突。

示意图：

dictEntry             dictEntry
+----------------+    +----------------+
| key: "name"    |    | key: "age"     |
| v.val: "Alice" |    | v.s64: 30      |
| next: ------------> | next: NULL      |
+----------------+    +----------------+

2. `dictht`：哈希表

typedef struct dictht {dictEntry **table;      // 哈希桶数组（每个桶是链表头节点）unsigned long size;     // 哈希表大小（桶的数量，2^n）unsigned long sizemask; // 哈希掩码（size-1，用于计算桶索引）unsigned long used;     // 已存储的节点数量
} dictht;

• 作用：管理一个哈希表的所有桶。
• 字段说明：
• table：指向 dictEntry 指针数组，每个元素是一个链表的头节点。
• size：哈希表的总容量（桶的数量），必须是 2 的幂（如 4、8、16）。
• sizemask：值为 size-1，用于通过按位与（&）快速计算键的桶索引（替代取模运算）。
• used：当前哈希表中存储的键值对数量。

哈希计算示例：

// 计算键的哈希值（伪代码）
hash = hashFunction(key);
// 通过 sizemask 确定桶索引
index = hash & dictht.sizemask;

3. `dict`：字典（主结构）

typedef struct dict {dictht ht[2];        // 两个哈希表（用于渐进式 rehash）long rehashidx;       // rehash 进度索引（-1 表示未进行）int iterators;       // 正在运行的迭代器数量
} dict;

• 作用：管理整个哈希表结构，支持渐进式 rehash。
• 字段说明：
• ht[2]：两个哈希表，默认使用 ht[0]，ht[1] 仅在 rehash 时使用。
• rehashidx：
◦ -1：未进行 rehash。
◦ ≥0：表示当前 rehash 的进度（已迁移 ht[0].table[0..rehashidx] 的桶）。
• iterators：记录当前活跃的迭代器数量，rehash 时会暂停以避免数据不一致。

三、哈希表操作流程

1. 插入键值对（`SET key value`）

计算键的哈希值：

hash = hashFunction(key); // 如使用 SipHash 算法

确定桶索引：

index = hash & dict->ht[0].sizemask; // 若未 rehash，否则需检查两个表

处理哈希冲突：
• 遍历链表，检查键是否存在：
◦ 存在：更新值。
◦ 不存在：创建新节点，插入链表头部（时间复杂度 O(1)）。
触发 rehash 检查：
• 若哈希表负载因子（used/size）超过阈值（默认 5），启动渐进式 rehash。

插入示意图：

哈希表 ht[0]
table[3]: dictEntry("city" -> "Beijing") → NULL
插入 ("name" -> "Alice")：计算 index = 1table[1]: NULL → 新建节点插入
结果：
table[1]: dictEntry("name" -> "Alice") → NULL

2. 查找键值对（`GET key`）

若未 rehash：只在 ht[0] 中查找。
若正在 rehash：依次查找 ht[0] 和 ht[1]。
遍历链表：通过 key 对比找到目标节点。

查找示例：

// 计算哈希和索引
hash = hashFunction("name");
index = hash & ht[0].sizemask;
// 遍历链表
entry = ht[0].table[index];
while (entry) {if (strcmp(entry->key, "name") == 0) {return entry->v.val; // 返回 "Alice"}entry = entry->next;
}

3. 删除键值对（`DEL key`）

查找节点：流程同查找。
删除节点：调整链表指针，跳过被删节点。
更新统计信息：used 减 1。

四、渐进式 rehash 机制

1. 触发条件

• 扩容：当 负载因子 = used / size > 5。
• 缩容：当 负载因子 < 0.1（需开启 activerehashing 配置）。

2. rehash 流程

准备阶段：
• 分配 ht[1] 的内存，大小为第一个大于等于 ht[0].used * 2 的 2^n。
渐进迁移：
• 每次执行增删改查操作时，顺带迁移 ht[0].table[rehashidx] 的整个桶到 ht[1]。
• rehashidx 递增，直到所有桶迁移完成。
收尾阶段：
• 释放 ht[0] 内存，将 ht[1] 设为 ht[0]，重置 ht[1]。
• rehashidx 置为 -1。

rehash 示意图：

初始状态：
ht[0].table[0]: entryA → entryB → NULL
ht[0].table[1]: entryC → NULL
rehashidx = 0迁移第一个桶（index=0）到 ht[1]:
ht[1].table[new_index]: entryA → entryB → NULL
更新 rehashidx = 1后续操作：
所有新插入的键值对直接写入 ht[1]。
查找时同时检查 ht[0] 和 ht[1]。

3. 为什么需要渐进式 rehash？

• 避免单次阻塞：大哈希表迁移会阻塞 Redis 主线程。
• 分摊成本：将迁移成本分散到多次操作中，保证服务可用性。

五、各结构体内存布局示例

// dict 实例
dict {ht[0]: {table: [dictEntry*, dictEntry*, ...], // 桶数组size: 4,sizemask: 3,used: 3},ht[1]: {table: NULL,size: 0,sizemask: 0,used: 0},rehashidx: -1,iterators: 0
}// 哈希表 ht[0] 的 table 数组
table[0]: NULL
table[1]: dictEntry("name" -> "Alice") → NULL
table[2]: dictEntry("age" -> 30) → dictEntry("city" -> "Beijing") → NULL
table[3]: NULL

六、总结

结构体	核心作用	关键字段
`dictEntry`	存储键值对，解决哈希冲突	`key`, `v`, `next`
`dictht`	管理哈希桶数组和统计信息	`table`, `size`, `sizemask`
`dict`	控制渐进式 rehash 和多表协作	`ht[2]`, `rehashidx`

• 哈希计算：通过 hash & sizemask 快速定位桶。
• 冲突解决：链表法，同一桶内节点用 next 指针连接。
• 渐进式 rehash：通过双哈希表逐步迁移数据，避免阻塞。

通过这种设计，Redis 的哈希表在保证高效操作的同时，支持动态扩容缩容，并能平滑处理大规模数据迁移。

Redis 哈希表结构详解

一、核心结构体定义与作用

二、结构体逐层解析

1. dictEntry：哈希表节点

2. dictht：哈希表

3. dict：字典（主结构）

三、哈希表操作流程

1. 插入键值对（SET key value）

2. 查找键值对（GET key）

3. 删除键值对（DEL key）

四、渐进式 rehash 机制

1. 触发条件

2. rehash 流程

3. 为什么需要渐进式 rehash？

五、各结构体内存布局示例

六、总结

相关文章：

1. `dictEntry`：哈希表节点

2. `dictht`：哈希表

3. `dict`：字典（主结构）

1. 插入键值对（`SET key value`）

2. 查找键值对（`GET key`）

3. 删除键值对（`DEL key`）