hash 与 zset 空间占用对比分析

一、问题背景

Redis 中相同数量的数据，使用 hash 与 zset 存储时空间占用差异究竟有多大？这是面试中常见的高频考点，核心考察点在于ziplist vs skiplist vs dict三种底层数据结构的空间复杂度。

二、数据结构选择规则

Redis 根据节点数量动态选择底层数据结构，具体阈值如下：

核心结论：

• 节点数 <= 128 时，hash 和 zset 均使用 ziplist，空间占用相同
• 节点数 129~512 时，hash 使用 ziplist，zset 使用 skiplist
• 节点数 > 512 时，hash 使用 dict，zset 使用 skiplist + dict

三、hash 内部数据结构

3.1 ziplist（压缩列表）

当 hash 节点数 <= 512 时采用，本质是一段连续的内存块：

+----------+----------+----------+----------+----------+ | prevlen | encoding | data | prevlen | ... | +----------+----------+----------+----------+----------+

空间占用特点：

• 紧凑存储，无额外指针开销
• prevlen 字段使用变长编码（1-5字节）
• 新增/删除操作可能触发级联更新

3.2 dict（字典）

当 hash 节点数 > 512 时采用，本质是哈希表：

struct dict { dictht table[2]; // 两个哈希表，支持渐进式 rehash long rehashidx; // rehash 进度，-1 表示未进行 long iterators; // 当前迭代器数量 };

空间占用特点：

• 每个 key-value 对额外占用一个 dictEntry 指针
• 负载因子 > 1 时触发扩容，空间换时间
• 存在指针开销，约 16-24 字节/条目

四、zset 内部数据结构

4.1 ziplist（压缩列表）

当 zset 节点数 <= 128 时采用，有序存储：

+----------+----------+----------+----------+----------+ | score | member | score | member | ... | +----------+----------+----------+----------+----------+

空间占用特点：

• score 和 member 交替存储
• 紧凑无指针开销
• 查询需要遍历，时间复杂度 O(n)

4.2 skiplist + dict（跳跃表 + 字典）

当 zset 节点数 > 128 时采用，这是zset 的核心结构：

struct zset { dict *dict; // member -> score 字典，O(1) 查询 skiplist *zsl; // 跳跃表，按 score 有序 };

为什么需要 dict？

• skiplist 查询 member 需要 O(n)，加入 dict 后可直接 O(1) 获取 score
• dict 和 skiplist 同时存储 member，数据冗余

五、skiplist 空间占用详解

5.1 数据结构定义

structskipListNode{doublescore;// 分数，8字节robj*obj;// 成员对象指针，8字节intbackward;// 后退指针，4字节（压缩指针）structskipListLevel{skipListNode*forward;// 前向指针，8字节unsignedintspan;// 跨度，4字节}level[];// 柔性数组，层数随机};

5.2 层数计算公式

节点层数根据以下规则随机生成：

// Redis 源码中的层高计算intrandomLevel(void){intlevel=1;while(random()<(1/4))// 1/4 概率继续增加层数level++;returnlevel;}

层数期望推导：

期望层数 E = 1 + 1/4 + 1/16 + 1/64 + … =4/3 层

即平均层数约为 1.33 层

5.3 空间占用公式

对于 n 个节点的 skiplist：

节点总空间 = n × (基础字段 + 指针开销)

基础字段（每个节点固定）：

• score: 8 字节
• obj 指针: 8 字节
• backward 指针: 4 字节

每层开销（平均 1.33 层）：

• forward 指针: 8 字节 × 1.33 ≈ 10.64 字节
• span: 4 字节 × 1.33 ≈ 5.32 字节

总计：约 32-36 字节/节点（不含 dict）

六、空间对比分析

6.1 阈值区间对比

6.2 定量空间估算

假设存储 1000 个节点（key + value 各 16 字节）：

关键结论：zset 在使用 skiplist + dict 时，空间占用约为 hash 的 1.5~2 倍

七、面试追问 FAQ

八、相关题目

九、总结

核心结论：zset 在数据量大时空间占用显著高于 hash，根源在于 skiplist 的多层索引结构 + dict 冗余存储。这是典型的空间换时间设计权衡。

根据零声教育教学写作https://github.com/0voice