数据结构与底层编码深度解析

面试开场白

面试官：Redis 有哪些基本数据类型？底层是怎么存储的？

你：Redis 有五种基础类型：String、List、Hash、Set、ZSet。底层都采用多种编码方式，根据数据特征自动切换，比如 String 会根据内容在 int、embstr、raw 之间切换，Hash 在元素少时用压缩列表，多了用哈希表。

面试官：那你说说 Hash 什么时候从压缩列表切换到哈希表？切换后能降回去吗？

这个追问把很多人问住了。能说清编码切换阈值和不可逆性的候选人，才能真正脱颖而出。

---

链式追问一：String 类型的底层实现

Q1：Redis String 底层为什么用 SDS 而不是 C 字符串？必考

回答要点：

• C 字符串获取长度需 O(n) 遍历，SDS 直接读 len 字段 O(1)
• C 字符串追加可能溢出，SDS 自动扩容（预分配策略）
• C 字符串不二进制安全，遇 \0 截止；SDS 按 len 读取，完全二进制安全

SDS 结构：

SDS (Simple Dynamic String) 结构：
┌──────────┬──────────┬─────────────┬────┐
│ len (4B) │ free (4B)│ buf (data)  │ \0 │
└──────────┴──────────┴─────────────┴────┘
  已用长度    可用空间      数据缓冲    C兼容终止符

对比表格：

维度	C 字符串	SDS
获取长度	O(n) 遍历到 \0	O(1) 直接读 len
追加操作	可能缓冲区溢出	自动扩容 + 预分配
二进制安全	❌ 遇 \0 截断	✅ 按 len 读取
内存重分配	每次追加都 realloc	预分配减少次数
兼容性	-	可复用部分 C 字符串函数

代码示例：

// C 字符串追加（危险）
char *str = malloc(10);
strcpy(str, "hello");
strcat(str, "worldworld");  // 缓冲区溢出！

// SDS 追加（安全）
struct sdshdr {
    int len;
    int free;
    char buf[];
};
// 追加前检查 free，不足则扩容：
// new_len = len + add_len;
// if (free < add_len) realloc(new_len * 2);

本质一句话：SDS 用空间换时间，用 len/free 字段实现了 O(1) 长度获取、自动扩容和二进制安全。

---

Q2：String 类型的三种编码 int/embstr/raw 分别什么时候用？高频

关键细节：

三种编码对比：

编码	触发条件	内存结构	特点
int	整数值且范围在 long 内	直接存整数值	最省内存，无需 SDS
embstr	字符串长度 ≤ 44 字节	redisObject + SDS 连续分配	一次内存分配，缓存友好
raw	字符串长度 > 44 字节	redisObject 和 SDS 分开分配	两次内存分配，适合大字符串

ASCII 图表：

embstr 编码（连续内存）：
┌───────────────────┬──────────────────┐
│  redisObject      │   SDS            │
│  (16 字节)         │   (len+free+buf)│
└───────────────────┴──────────────────┘
一次 malloc 分配

raw 编码（分离内存）：
┌───────────────────┐      ┌──────────────────┐
│  redisObject      │ ───→ │   SDS            │
│  (16 字节)         │ ptr  │   (独立内存块)    │
└───────────────────┘      └──────────────────┘
两次 malloc 分配

为什么是 44 字节？

// Redis 分配内存使用 jemalloc，按 2^n 对齐
// redisObject (16B) + SDS header (4B+4B) + buf + \0 (1B)
// 16 + 9 + 44 + 1 = 70 字节，刚好适配 64 字节内存块（jemalloc 的 cache line）
// 超过 44 字节会浪费内存，不如用 raw 编码

面试陷阱

embstr 是只读的！任何修改操作（APPEND、SETRANGE）都会先转换为 raw 编码。因为 embstr 设计目标是小字符串快速分配，修改后通常超过 44 字节。

性能数据：

测试场景：SET key value，value 长度 10 字节
- int 编码（值为整数）：内存占用 16B（redisObject only）
- embstr 编码：内存占用 70B（redisObject + SDS）
- raw 编码：内存占用 80B+（两次分配有额外开销）

访问性能：embstr 比 raw 快约 15%（缓存局部性）

---

Q3：embstr 修改后会立即转 raw 吗？这样设计合理吗？中频

详细解析：

SET mykey "hello world hello world hello world"  -- 36 字节，embstr
APPEND mykey "!"  -- 37 字节，仍 ≤ 44，但已转为 raw
OBJECT ENCODING mykey  -- 返回 "raw"

为什么转 raw 而不是保持 embstr？

1. embstr 内存布局不可变：连续内存块，扩容需要 realloc + 可能的内存移动
2. 修改后大概率超限：实际业务中，能追加的小字符串通常会继续追加，很快就超 44 字节
3. 简化实现：统一转 raw，避免 embstr 扩容的复杂逻辑

这样设计合理吗？

优点：
  - 简化实现，减少代码复杂度
  - 避免频繁 realloc（embstr 扩容代价高）

缺点：
  - 小字符串修改后内存占用增加（embstr 70B → raw 80B+）
  - 性能略有下降（两次内存访问）

权衡：embstr 主要用于"写入一次，多次读取"的场景（如缓存 HTML 片段），
      修改频率低，转换开销可接受。

本质一句话：embstr 专为小字符串的一次性写入优化，修改后转 raw 是性能与实现的平衡。

---

链式追问二：List 类型的演进与 quicklist

Q4：Redis List 底层编码演进历程是怎样的？高频

回答要点：

编码演进时间线：

Redis 3.2 之前：
  ziplist  ← 元素 ≤ 128 且 单个 ≤ 64B
     ↓
  linkedlist ← 元素 > 128 或 单个 > 64B

Redis 3.2+：
  quicklist（统一） ← ziplist 节点组成的双向链表

Redis 7.0+：
  quicklist ← listpack 节点组成的双向链表
  （ziplist 被 listpack 取代）

quicklist 结构：

quicklist（快速列表）：
┌─────────────────────────────────────────┐
│  head ─→ [listpack] ←→ [listpack] ←→ [listpack] ←─ tail
│            8 元素        8 元素        5 元素
│           (紧凑)       (紧凑)       (紧凑)
└─────────────────────────────────────────┘
每个 listpack 节点最多 list-max-listpack-size 个元素（默认 -2，即 8KB）

对比表格：

编码	优点	缺点	适用场景
ziplist	内存紧凑，连续存储	插入/删除 O(n) 移动元素	小列表（< 512 元素）
linkedlist	插入/删除 O(1)	内存碎片大，每个节点 2 个指针	大列表
quicklist	兼顾内存紧凑和操作效率	实现复杂	所有列表（统一方案）

性能数据：

测试场景：LPUSH 10000 个元素
- linkedlist：内存占用 10000 × (value_size + 32B 指针开销)
- quicklist：内存占用 ≈ linkedlist × 0.6（压缩节点省内存）
- 插入性能：quicklist 比 linkedlist 快约 20%（缓存局部性更好）

测试场景：LINDEX 随机访问 10000 个元素
- linkedlist：O(n) 平均访问 5000 个节点，耗时约 5ms
- quicklist：O(n) 但节点数少 8 倍，耗时约 0.8ms

面试技巧

提到 Redis 版本演进是加分项。Redis 3.2 之前 List 有两种编码，运维需要调参；3.2 之后统一 quicklist，降低了运维复杂度。这体现了 Redis “用复杂实现换简单使用”的设计哲学。

---

Q5：为什么 Redis 7.0 用 listpack 取代 ziplist？实战

场景示例：

ziplist 的连锁更新问题：
初始状态：[entry1: 10B][entry2: 10B][entry3: 10B]...
            ↓ prev_len=1B
修改 entry1 为 300B：
  → entry1 长度从 10B 变为 300B
  → entry2 需要存储 entry1 的长度，从 1B 变为 5B
  → entry2 总长度增加 4B
  → entry3 需要存储 entry2 的新长度，也从 1B 变为 5B
  → 连锁扩容，最坏 O(n²)

ziplist 结构：

// ziplist 节点结构
struct ziplist_entry {
    previous_entry_length;  // 前一个节点长度（1B 或 5B）
    encoding;               // 编码类型
    content;                // 实际数据
};

// 问题：previous_entry_length 字段
// - 前一个节点 < 254B：用 1 字节存储
// - 前一个节点 ≥ 254B：用 5 字节存储
// 若某节点从小变大，触发后续节点连锁扩容

listpack 改进：

// listpack 节点结构
struct listpack_entry {
    encoding;               // 编码类型
    content;                // 实际数据
    backlen;                // 当前节点长度（自身长度，非前一个节点）
};

// 反向遍历：从当前节点末尾减去 backlen，定位到前一个节点
// 完全消除连锁更新，最坏 O(n)

性能对比：

测试场景：在 1000 个元素的 ziplist/listpack 中插入元素
- ziplist：最坏情况（触发连锁更新）耗时约 50ms
- listpack：稳定耗时约 0.1ms（无连锁更新）

实际影响：
  - Redis 7.0 之前，Hash/List/ZSet 的小规模编码都可能触发连锁更新
  - Redis 7.0 统一用 listpack，彻底解决该问题

本质一句话：listpack 将”存储前一节点长度”改为”存储自身长度”，用更简单的反向遍历逻辑彻底消除了 ziplist 的连锁更新问题。

---

链式追问三：Hash 类型的编码切换

Q6：Hash 什么时候从 listpack 升级为 hashtable？能降回去吗？必考

回答要点：

编码切换阈值：

编码	触发条件（满足任一即升级）	内存特点
listpack	字段数 ≤ hash-max-listpack-entries（默认 128） 且每个 key/value ≤ hash-max-listpack-value（默认 64B）	紧凑连续，省内存
hashtable	字段数 > 128 或任一 key/value > 64B	哈希表，O(1) 查找

切换过程：

HSET user:1001 name "Alice" age 30
OBJECT ENCODING user:1001  -- 返回 "listpack"（2 个字段）

HSET user:1001 field1 v1 field2 v2 ... field128 v128  -- 总字段数 130
OBJECT ENCODING user:1001  -- 返回 "hashtable"（超过 128 字段）

HDEL user:1001 field1 field2 ... field128  -- 删除到只剩 2 个字段
OBJECT ENCODING user:1001  -- 仍是 "hashtable"（不会降回 listpack）

为什么不能降回去？

原因：
1. 降级需要遍历所有字段，检查是否满足阈值，开销 O(n)
2. 实际业务中，字段数减少后通常还会再增加，频繁升降级浪费 CPU
3. hashtable 内存开销虽大，但访问性能更优（O(1)）

Redis 设计哲学：编码升级不可逆，避免频繁转换的开销

注意

即使删除所有字段只剩 1 个，hashtable 也不会降回 listpack。如果需要重置编码，只能 DEL key 后重新创建。

性能数据：

测试场景：HGET 100 个字段，各 10 字节 value
- listpack：线性扫描，耗时约 0.05ms（100 个元素遍历）
- hashtable：哈希查找，耗时约 0.01ms（O(1) 查找）

内存占用：
- listpack：约 1.2KB（紧凑存储）
- hashtable：约 3KB（哈希表结构 + 指针开销）

本质一句话：listpack 用时间换空间（省内存但查找慢），hashtable 用空间换时间（内存大但查找快），切换阈值是权衡的结果。

---

Q7：Hash 和 String 存储对象各有什么优劣？实战

场景示例：

-- 方案1：String 存储（序列化整个对象）
SET user:1001 '{"name":"Alice","age":30,"email":"alice@example.com"}'

-- 方案2：Hash 存储（按字段存储）
HSET user:1001 name "Alice" age 30 email "alice@example.com"

对比表格：

维度	String（序列化）	Hash
单字段更新	需读取整个对象，修改后写回	HSET 直接更新，只操作单个字段
内存占用	对象小（< 64B）时更省	对象大时更省（listpack 压缩）
过期时间	整个对象统一过期	整个 Hash 统一过期（不支持字段级 TTL）
访问方式	GET 整个对象或用 JSON 库提取	HGET 单字段或 HGETALL 全部
适用场景	读多写少，整体访问	频繁单字段更新，部分字段访问

代码示例：

# String 方案：更新年龄需要读取整个对象
user = json.loads(redis.get("user:1001"))
user["age"] = 31
redis.set("user:1001", json.dumps(user))

# Hash 方案：直接更新单个字段
redis.hset("user:1001", "age", 31)  # 只操作一个字段，更高效

性能对比：

测试场景：更新用户年龄字段
- String 方案：GET + 反序列化 + 修改 + 序列化 + SET，耗时约 0.5ms
- Hash 方案：HSET 单字段，耗时约 0.05ms，快 10 倍

测试场景：获取用户全部信息
- String 方案：GET 一次，耗时约 0.05ms
- Hash 方案：HGETALL，耗时约 0.08ms，略慢（需遍历字段）

面试技巧

这是经典的”如何设计缓存结构”问题。回答时强调：没有绝对优劣，要根据访问模式选择。高频单字段更新选 Hash，整体读写选 String。还可以提到 Redis Modules（如 RedisJSON）提供了更灵活的方案。

---

链式追问四：Set 和 ZSet 的编码

Q8：Set 的 intset 编码是什么？有什么限制？高频

回答要点：

intset 结构：

struct intset {
    uint32_t encoding;  // 编码方式：int16/int32/int64
    uint32_t length;    // 元素数量
    int8_t contents[];  // 有序整数数组（二分查找）
};

编码升级：

初始：所有元素为 int16（如 1, 2, 3）
插入元素 65535（超过 int16 范围）：
  → 整个数组升级为 int32
  → 所有元素重新编码（1, 2, 3, 65535 都用 4 字节存储）
  → 不可逆（即使删除 65535，仍是 int32 编码）

切换条件：

编码	触发条件
intset	全为整数 且 元素数 ≤ set-max-intset-entries（默认 512）
hashtable	含非整数 或 元素数 > 512

示例：

SADD myset 1 2 3
OBJECT ENCODING myset  -- 返回 "intset"

SADD myset "hello"  -- 加入非整数
OBJECT ENCODING myset  -- 返回 "hashtable"（立即升级）

SREM myset "hello"  -- 删除非整数
OBJECT ENCODING myset  -- 仍是 "hashtable"（不可逆）

性能数据：

测试场景：SISMEMBER 查询元素是否存在
- intset（100 个整数）：二分查找 O(log n)，耗时约 0.01ms
- hashtable（100 个元素）：哈希查找 O(1)，耗时约 0.005ms

内存占用：
- intset：100 个 int16 = 200 字节
- hashtable：100 个元素 × (指针 + SDS) ≈ 2KB
- intset 内存节省约 90%

本质一句话：intset 是极致省内存的有序整数数组，适合小规模整数集合，插入非整数或超限时升级为 hashtable。

---

Q9：ZSet 为什么同时维护 skiplist 和 dict？内存不会翻倍吗？必考

回答要点：

两种结构各司其职：

ZSet 内部结构：
┌─────────────────────────────────────┐
│  dict (哈希表)                      │
│  key: member                        │
│  value: score                       │
│  → 支持 ZSCORE O(1) 查询            │
└─────────────────────────────────────┘
         ↑ 共享 member 字符串指针
         ↓
┌─────────────────────────────────────┐
│  skiplist (跳表)                    │
│  按 score 有序存储                   │
│  → 支持 ZRANGE/ZRANK O(log n) 查询  │
└─────────────────────────────────────┘

为什么需要两个结构？

操作	只用 skiplist	只用 dict	两者结合
ZSCORE member	O(log n) 遍历查找	O(1) 哈希查找	O(1) ✅
ZRANGE start stop	O(log n + m)	O(n log n) 排序	O(log n + m) ✅
ZRANK member	O(log n)	❌ 不支持	O(log n) ✅

内存占用分析：

struct zset {
    dict *dict;       // member → score 映射
    zskiplist *zsl;   // 有序跳表
};

// 共享 member 字符串，不会完全翻倍
struct zskiplistNode {
    sds ele;              // member 字符串（指针，指向 dict 中的 key）
    double score;         // 分数
    struct zskiplistLevel *levels;  // 跳表索引层
};

// 实际内存增量：
// - 跳表节点：约 32B（ele 指针 + score + level 数组）
// - 哈希表节点：约 24B（key 指针 + value + next 指针）
// - member 字符串只存一份（共享指针）
// 总增量约 1.5 倍，不是 2 倍

面试陷阱

很多人以为 ZSet 会占用双倍内存，实际上 member 字符串是共享的（dict 和 skiplist 指向同一份数据），内存增量约 1.5 倍。这是典型的”空间换时间”权衡。

本质一句话：ZSet 用 dict 和 skiplist 互补，dict 负责 O(1) 点查询，skiplist 负责 O(log n) 范围查询，两者共享 member 字符串，内存开销可控。

---

链式追问五：跳表原理深挖

Q10：为什么 ZSet 用跳表不用红黑树？高频

回答要点：

对比表格：

维度	跳表	红黑树
实现复杂度	简单（约 200 行代码）	复杂（约 500+ 行，需处理旋转）
范围查询	找到起点后，沿 level-0 链表顺序遍历	需要中序遍历，涉及回溯
内存局部性	level-0 连续链表，缓存友好	节点分散，缓存不友好
平均时间复杂度	O(log n)	O(log n)
最坏时间复杂度	O(n)（概率极低）	O(log n)
支持逆序遍历	✅ 双向链表	⚠️ 需额外处理

范围查询优势：

场景：查询 score 在 [100, 200] 之间的元素

跳表：
  1. 从最高层找到第一个 score ≥ 100 的节点
  2. 沿 level-0 链表顺序遍历到 score > 200 停止
  3. 遍历过程是线性扫描，无需回溯

红黑树：
  1. 找到 score ≥ 100 的节点
  2. 中序遍历：左子树 → 当前节点 → 右子树
  3. 需要维护栈或父指针，回溯逻辑复杂

Redis 作者 Antirez 的理由：

1. 实现简单：跳表代码量远少于红黑树，易于维护和调试
2. 范围查询更快：ZRANGEBYSCORE 是 ZSet 高频操作，跳表优势明显
3. 内存友好：顺序遍历时缓存命中率高
4. 已被工程验证：跳表在多个系统中成功应用（如 LevelDB）

性能数据：

测试场景：ZRANGEBYSCORE 查询 1000 个元素
- 跳表：找到起点 O(log n) + 遍历 1000 个节点，耗时约 0.8ms
- 红黑树：找到起点 O(log n) + 中序遍历（频繁回溯），耗时约 1.2ms

测试场景：ZADD 插入 10000 个元素
- 跳表：O(log n) 平均查找 + 插入，耗时约 15ms
- 红黑树：O(log n) 查找 + 旋转，耗时约 14ms（性能接近）

本质一句话：跳表在实现简单、范围查询效率和内存局部性上优于红黑树，虽然理论最坏性能略差，但工程实践中表现优秀。

---

Q11：跳表的随机层数为什么用概率 1/4 而不是 1/2？加分

详细解析：

随机层数算法：

# Redis 跳表的层数生成
def random_level():
    level = 1
    while random() < 0.25 and level < 32:  # ZSKIPLIST_P = 0.25
        level += 1
    return level

不同概率的影响：

概率	平均层数/节点	索引节点总数	查询期望比较次数	内存开销
1/2	2 层	约 n 个	log₂(n)	100%（基准）
1/4	1.33 层	约 n/3 个	1.33×log₄(n) ≈ log₂(n)	33%
1/8	1.14 层	约 n/7 个	1.14×log₈(n) ≈ log₂(n)	14%

数学推导：

期望层数（概率 p）：
  E = 1 + p + p² + p³ + ... = 1/(1-p)

p = 1/2: E = 2 层
p = 1/4: E ≈ 1.33 层
p = 1/8: E ≈ 1.14 层

查询期望比较次数：
  C ≈ (1/p) × log_{1/p}(n)

p = 1/2: C ≈ 2 × log₂(n)
p = 1/4: C ≈ 4 × log₄(n) ≈ 2 × log₂(n)  （几乎相同）
p = 1/8: C ≈ 8 × log₈(n) ≈ 2.67 × log₂(n)  （略慢）

为什么选 1/4？

1/2 概率：
  - 内存开销大（每节点平均 2 层，索引节点 ≈ n）
  - 性能最优（比较次数最少）
  - 但内存浪费严重

1/4 概率（Redis 选择）：
  - 内存节省 67%（每节点平均 1.33 层）
  - 性能仅略低于 1/2（比较次数几乎相同）
  - 最佳平衡点

1/8 概率：
  - 内存最省（14%）
  - 但性能明显下降（比较次数增加 33%）
  - 过度节省

性能对比：

测试场景：查询 100 万个元素的 ZSet
- p=1/2：平均比较 40 次，内存占用 80MB
- p=1/4：平均比较 42 次，内存占用 40MB
- p=1/8：平均比较 53 次，内存占用 35MB

结论：p=1/4 在内存节省 50% 的前提下，性能仅下降 5%，是最优选择。

面试技巧

这题是高级面试的加分项。能说出概率推导和权衡分析的候选人，证明深入理解了跳表的设计哲学。可以补充：Redis 源码中 ZSKIPLIST_P 和 ZSKIPLIST_MAXLEVEL 都是可调参数，但默认值已经在工程实践中验证为最优。

本质一句话：概率 1/4 在查询性能几乎无损的前提下，将内存开销降低 67%，是 Redis 在性能与内存之间的最佳权衡。

---

链式追问六：高级数据类型

Q12：HyperLogLog 如何用 12KB 统计 2^64 个不同元素？实战

场景示例：

需求：统计日活 UV（独立访客数）
- 日活 1000 万用户
- Set 存储：每个用户 ID 平均 20 字节，总内存 200MB
- HyperLogLog：固定 12KB，误差 0.81%

HyperLogLog 原理：

1. 分桶：将元素哈希值分到 16384 个桶（2^14）
2. 统计最长前导零：每个桶记录该桶内元素哈希值的最长前导零长度
3. 基数估计：调和平均数计算基数

示例：
  元素 "user:1001" → hash → 0b00010110...（前导零个数 = 3）
  元素 "user:1002" → hash → 0b00101100...（前导零个数 = 2）
  元素 "user:1003" → hash → 0b00000101...（前导零个数 = 5）

  桶记录：max(前导零个数) = 5
  估计基数 ≈ 2^(max_zero + 1) = 2^6 = 64（实际元素约 3 个，误差大）

  实际用调和平均数和分桶，减小误差

内存结构：

HyperLogLog 结构：
┌─────────────────────────────────────┐
│  16384 个桶，每个桶 6 位（0~63）      │
│  总内存：16384 × 6 bit = 12KB        │
└─────────────────────────────────────┘

误差率：约 1.04 / sqrt(16384) ≈ 0.81%

代码示例：

PFADD uv:20240304 "user:1001" "user:1002" "user:1001"  -- 去重
PFCOUNT uv:20240304  -- 返回约 2

PFADD uv:20240305 "user:1003"
PFMERGE uv:total uv:20240304 uv:20240305  -- 合并多个 PPF
PFCOUNT uv:total  -- 返回约 3

性能对比：

方案	内存占用（1000 万用户）	误差	支持操作
Set	200MB	0%	精确计数、取元素
HyperLogLog	12KB	0.81%	仅计数，不可取元素

注意

HyperLogLog 只能统计基数（不同元素个数），不能取出具体元素。如果需要元素本身，用 Set 或 Bloom Filter。

本质一句话：HyperLogLog 用概率统计方法，牺牲精度和功能，换取极致的内存效率，适合大规模去重计数场景。

---

Q13：Bitmap 的底层原理是什么？如何实现签到功能？实战

场景示例：

需求：记录 1 亿用户一年内的签到状态
- 每个用户 365 位（1 年 365 天）
- 总内存：1 亿 × 365 bit ≈ 4.3GB

Bitmap 原理：

Bitmap 本质是 String 类型，按位操作：
  "签到:用户1001" → 二进制：00010110...
                      位置：  0 1 2 3...

SETBIT sign:uid:1001 0 1   -- 第 0 天签到，置第 0 位为 1
SETBIT sign:uid:1001 2 1   -- 第 2 天签到
BITCOUNT sign:uid:1001      -- 统计签到总天数
BITPOS sign:uid:1001 1      -- 找到第一个签到的天

性能数据：

操作时间复杂度：
- SETBIT/GETBIT：O(1)
- BITCOUNT：O(n)（n 为位图长度）
- BITOP（AND/OR/XOR）：O(n)

内存占用：
- 1 亿用户签到状态：1 亿 bit = 12.5MB（极省内存）
- 如果用 Set 存储：1 亿 × (用户ID + 指针开销) ≈ 几百 MB

代码示例：

# 用户 1001 在 2024 年 3 月的签到
SETBIT sign:1001:202403 0 1   -- 3 月 1 日签到
SETBIT sign:1001:202403 4 1   -- 3 月 5 日签到
SETBIT sign:1001:202403 10 1  -- 3 月 11 日签到

# 统计 3 月签到总天数
BITCOUNT sign:1001:202403  -- 返回 3

# 统计连续签到天数
BITPOS sign:1001:202403 0  -- 找到第一个未签到的位置

# 计算多个用户的共同签到天数
BITOP AND result sign:1001:202403 sign:1002:202403
BITCOUNT result  -- 返回两人都签到的天数

本质一句话：Bitmap 用 String 的位操作实现极致省内存的位图，适合布尔状态存储和位运算场景。

---

总结

核心要点回顾

1. String 三种编码：int（整数）、embstr（≤44B 小字符串）、raw（大字符串）
2. List 演进：ziplist → linkedlist → quicklist（统一方案）→ listpack（消除连锁更新）
3. Hash 编码切换：listpack（≤128 字段）→ hashtable，不可逆
4. Set 的 intset：有序整数数组，极致省内存，插入非整数或超限升级为 hashtable
5. ZSet 双结构：dict（O(1) 点查询）+ skiplist（O(log n) 范围查询），共享 member 指针
6. 跳表概率 1/4：内存节省 67%，性能几乎无损，最佳权衡
7. HyperLogLog：12KB 固定内存，误差 0.81%，适合大规模去重计数
8. Bitmap：String 的位操作，极省内存，适合布尔状态存储

面试高频考点

• <Badge text="必考" variant="danger" /> String 为什么用 SDS？三种编码何时切换？
• <Badge text="必考" variant="danger" /> Hash 编码切换阈值？为什么不可逆？
• <Badge text="必考" variant="danger" /> ZSet 为什么同时维护 dict 和 skiplist？
• <Badge text="高频" variant="tip" /> 为什么用跳表不用红黑树？
• <Badge text="高频" variant="tip" /> Set 的 intset 编码原理和限制？
• <Badge text="实战" variant="caution" /> Hash vs String 存储对象如何选择？
• <Badge text="实战" variant="caution" /> 如何实现签到功能（Bitmap）？
• <Badge text="加分" variant="success" /> 跳表为什么用概率 1/4？