数据结构

Redis 支持丰富的数据结构，这是它区别于 Memcached 等其他键值存储的最大特点。本文将详细介绍 Redis 的各种数据结构、底层实现原理、应用场景和常见面试题。

数据结构概览

数据类型	底层编码	时间复杂度	适用场景
String	int、embstr、raw	O(1)	缓存、计数器、分布式锁
Hash	ziplist、hashtable	O(1)	对象存储、购物车
List	quicklist、linkedlist	O(N)	消息队列、时间线
Set	intset、hashtable	O(1)	标签、共同好友、抽奖
ZSet	ziplist、skiplist+hashtable	O(log N)	排行榜、优先级队列
Bitmap	string（按位操作）	O(1)	签到、在线用户、布隆过滤器
HyperLogLog	string（基数统计）	O(1)	UV 统计、去重计数
GEO	ziplist、skiplist	O(log N)	附近的人、地理位置
Stream	radixtree+list	O(1)	消息队列、事件溯源

一、String（字符串）

1.1 基本概念

String 是 Redis 最基本的数据类型，它是二进制安全的，可以存储任何类型的数据（字符串、数字、图片、序列化对象等）。

最大容量：512 MB

1.2 底层实现

Redis 的 String 有三种编码方式：

1. int 编码

条件：存储的是整数值，且可以用 long 类型表示
示例：SET count 100
结构：直接将 value 赋值给 RedisObject 的 ptr 指针

// 伪代码
struct RedisObject {
    type = REDIS_STRING;
    encoding = REDIS_ENCODING_INT;
    ptr = 100;  // 直接存储整数值
}

2. embstr 编码（Embedded String）

条件：字符串长度 ≤ 39 字节（Redis 3.2 之前是 39 字节，之后是 44 字节）
特点：RedisObject 和 SDS 存放在连续内存中
优势：一次内存分配，内存连续，缓存友好

// 伪代码
struct RedisObject {
    type = REDIS_STRING;
    encoding = REDIS_ENCODING_EMBSTR;
    ptr = "hello";  // 指向连续的 SDS
}

3. raw 编码

条件：字符串长度 > 39/44 字节
特点：RedisObject 和 SDS 分开分配内存
优势：可以存储大字符串，修改时不需要重新分配整个对象

// 伪代码
struct RedisObject {
    type = REDIS_STRING;
    encoding = REDIS_ENCODING_RAW;
    ptr = pointer_to_SDS;  // 指向 SDS 的指针
}

1.3 SDS（Simple Dynamic String）

Redis 没有直接使用 C 语言的字符串，而是实现了 SDS：

struct sdshdr {
    int len;        // 字符串长度
    int free;       // 未使用空间
    char buf[];     // 字节数组
};

SDS 相比 C 字符串的优势：

O(1) 获取长度：len 属性直接存储长度
防止缓冲区溢出：修改前检查空间是否足够
减少内存重分配：空间预分配和惰性释放
二进制安全：可以存储任意二进制数据
兼容 C 字符串：buf 末尾保留 \0

1.4 常用命令

# ============ 基本操作 ============

# 设置键值
SET key value
SET key value EX 60        # 设置过期时间（秒）
SET key value PX 60000     # 设置过期时间（毫秒）
SET key value NX           # 仅当键不存在时设置
SET key value XX           # 仅当键存在时设置

# 获取值
GET key

# 批量设置/获取
MSET key1 value1 key2 value2
MGET key1 key2 key3

# ============ 数值操作 ============

# 自增（必须为数字）
INCR key
INCRBY key increment
INCRBYFLOAT key increment

# 自减
DECR key
DECRBY key decrement

# ============ 字符串操作 ============

# 追加字符串
APPEND key value

# 获取子串
GETRANGE key 0 4
SETRANGE key 6 "Redis"      # 从索引 6 开始替换

# 获取字符串长度
STRLEN key

# ============ 分布式锁相关 ============

# SETNX（仅当键不存在时设置，等价于 SET key value NX）
SETNX lock:value true

# 设置值并返回旧值
GETSET key newvalue

1.5 应用场景

1. 缓存

# 缓存用户信息
SET user:1001 '{"id":1001,"name":"张三","age":25}'
GET user:1001

# 缓存文章内容
SET article:1001:content "文章内容..." EX 3600

缓存更新策略：

# Cache-Aside 模式（旁路缓存）
# 读：
GET cache:key
if (not exists) {
    data = db.query()
    SET cache:key data EX 3600
}

# 写：
db.update(data)
DEL cache:key

2. 计数器

# 文章点赞数
INCR article:1001:likes

# 视频播放量
INCRBY video:1001:views 1

# 限流计数器
INCR api:limit:user:1001
EXPIRE api:limit:user:1001 60

3. 分布式锁

# 获取锁
SET lock:order:1001 "uuid" NX EX 10

# 释放锁（Lua 脚本保证原子性）
if redis.call("get", KEYS[1]) == ARGV[1] then
    return redis.call("del", KEYS[1])
else
    return 0
end

4. Session 共享

# 用户登录后存储 Session
SET session:abc123 '{"userId":1001,"loginTime":"2024-01-01"}' EX 1800

5. 限流

# 固定窗口限流
MULTI
INCR limit:api:user:1001
EXPIRE limit:api:user:1001 60
EXEC

# 判断是否超限
if GET limit:api:user:1001 > 100:
    return "Rate limit exceeded"

1.6 面试题

Q1：Redis 的 String 为什么是二进制安全的？

答案：

Redis 使用 SDS（Simple Dynamic String）存储字符串，而不是 C 语言的字符串。

C 字符串：以 \0（空字符）标识字符串结束，不能包含 \0
SDS：通过 len 属性记录长度，不依赖 \0，可以存储任意二进制数据

// C 字符串：读取到 \0 就停止
char *str = "hello\0world";  // 只能读到 "hello"

// SDS：通过 len 判断长度
struct sdshdr {
    int len = 11;  // 可以正确读取 "hello\0world"
    char buf[] = "hello\0world";
};

Q2：String 的 embstr 和 raw 编码有什么区别？

答案：

特性	embstr	raw
内存分配次数	1 次	2 次
内存释放次数	1 次	2 次
内存布局	连续	分散
适用场景	≤ 39/44 字节	> 39/44 字节
优势	缓存友好，分配/释放快	可存储大字符串，修改时不需要重新分配整个对象

embstr：RedisObject 和 SDS 在一块连续内存中，只分配一次内存 raw：RedisObject 和 SDS 分开分配，需要两次内存分配

Q3：为什么使用 SDS 而不是 C 字符串？

答案：

O(1) 获取长度：C 字符串需要 O(N) 遍历，SDS 直接读取 len 属性
防止缓冲区溢出：SDS 修改前会检查空间，C 字符串可能溢出
减少内存重分配：
- 空间预分配：扩展时预留额外空间
- 惰性释放：缩短时不立即释放内存
二进制安全：可以存储任意数据，包括 \0
兼容 C 字符串：buf 末尾保留 \0，可以使用 C 字符串函数

Q4：实现一个分布式锁？

答案：

# 获取锁
SET lock:resource unique_uuid NX EX 10

# 业务逻辑执行
# ...

# 释放锁（Lua 脚本）
if redis.call("get", KEYS[1]) == ARGV[1] then
    return redis.call("del", KEYS[1])
else
    return 0
end

关键点：

NX：保证只有一个客户端能设置成功
EX：设置过期时间，防止死锁
唯一值：保证只有锁的持有者能释放锁
Lua 脚本：保证获取和删除的原子性

Q5：如何实现限流？

答案：

# 方式一：固定窗口
INCR limit:api:user:1001
EXPIRE limit:api:user:1001 60  # 第一次需要设置过期时间

if redis.call("get", "limit:api:user:1001") > 100:
    return "超过限制"

# 方式二：滑动窗口（使用 List）
# 每次请求记录时间戳
LPUSH limit:api:user:1001 timestamp
# 删除 60 秒之前的数据
LTRIM limit:api:user:1001 0 -1
# 检查数量
if LLEN limit:api:user:1001 > 100:
    return "超过限制"

# 方式三：令牌桶（更平滑）
# 使用 Redis Cell 模块或 ZSet 实现

Q6：SET 命令的 NX、XX 参数有什么用？

答案：

NX（Not Exist）：仅当键不存在时设置
- 应用：分布式锁、幂等性控制
- 示例：SET lock:key value NX EX 10
XX：仅当键存在时设置
- 应用：更新已存在的键
- 示例：SET session:key value XX EX 1800

# NX 实现
SETNX key value  # 等价于 SET key value NX

# 使用场景
if (SET lock resource NX EX 10 == "OK") {
    // 获取锁成功
    execute()
    DEL lock
}

二、Hash（哈希）

2.1 基本概念

Hash 是一个键值对集合，特别适合存储对象。

结构：Hash Key → {Field1: Value1, Field2: Value2, ...}

示例：

user:1001 → {
    name: "张三",
    age: 25,
    email: "zhangsan@example.com"
}

2.2 底层实现

1. ziplist（压缩列表）

使用条件（同时满足）：

所有键值对的键和值的字符串长度都 ≤ 64 字节（默认 hash-max-ziplist-value）
键值对数量 < 512 个（默认 hash-max-ziplist-entries）

特点：

紧凑的连续内存存储
节省内存，但不利于修改

2. hashtable（哈希表）

使用条件（满足任一）：

键或值的字符串长度 > 64 字节
键值对数量 ≥ 512

特点：

使用链地址法解决冲突
时间复杂度 O(1)
负载因子 > 1 时扩容

// 伪代码
struct dictht {
    dictEntry **table;  // 哈希表数组
    unsigned long size;  // 哈希表大小
    unsigned long sizemask;  // 哈希表大小掩码，用于计算索引
    unsigned long used;  // 已有节点数量
};

struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    struct dictEntry *next;  // 链表，解决冲突
};

2.3 渐进式 rehash

当哈希表需要扩容或缩容时，Redis 不会一次性完成 rehash，而是渐进式 rehash：

为 dict[1] 分配新哈希表
将 rehashidx 设置为 0，表示开始 rehash
每次增删改查时，将 dict[0] 中 rehashidx 位置的数据迁移到 dict[1]
rehashidx++
直到 dict[0] 全部迁移完成，将 dict[1] 设置为 dict[0]，释放旧表

优点：避免一次性 rehash 导致的阻塞

2.4 常用命令

# ============ 设置操作 ============

# 设置单个字段
HSET key field value
HSETNX key field value  # 仅当字段不存在时设置

# 设置多个字段
HMSET key field1 value1 field2 value2

# ============ 获取操作 ============

# 获取单个字段
HGET key field

# 获取多个字段
HMGET key field1 field2 field3

# 获取所有字段和值
HGETALL key

# 获取所有字段
HKEYS key

# 获取所有值
HVALS key

# ============ 判断与删除 ============

# 判断字段是否存在
HEXISTS key field

# 删除字段（可删除多个）
HDEL key field1 field2

# ============ 计数操作 ============

# 字段值自增
HINCRBY key field increment
HINCRBYFLOAT key field increment

# ============ 其他操作 ============

# 获取字段数量
HLEN key

# 获取字符串长度
HSTRLEN key field

2.5 应用场景

1. 对象存储

# 存储 user:1001 的信息
HSET user:1001 name "张三"
HSET user:1001 age 25
HSET user:1001 email "zhangsan@example.com"

# 获取用户信息
HGET user:1001 name
HMGET user:1001 name age email

# 获取所有信息
HGETALL user:1001

对比 String 存储：

# ❌ String JSON 存储
SET user:1001 '{"name":"张三","age":25,"email":"zhangsan@example.com"}'
GET user:1001  # 需要反序列化

# ✅ Hash 存储
HSET user:1001 name "张三"
HGET user:1001 name  # 直接获取，无需反序列化

2. 购物车

# 添加商品
HSET cart:user:1001 product:1001 2
HSET cart:user:1001 product:1002 1

# 增加商品数量
HINCRBY cart:user:1001 product:1001 1

# 获取购物车
HGETALL cart:user:1001

# 删除商品
HDEL cart:user:1001 product:1001

3. 文章点赞

# 点赞（存储用户 ID 和时间戳）
HSET article:1001:likes user:1001 1704067200

# 取消点赞
HDEL article:1001:likes user:1001

# 判断是否点赞
HEXISTS article:1001:likes user:1001

# 获取点赞数
HLEN article:1001:likes

4. 计数器（多维）

# 统计文章的各种指标
HINCRBY article:1001:stats views 1
HINCRBY article:1001:stats likes 1
HINCRBY article:1001:stats comments 1

# 获取所有统计
HGETALL article:1001:stats

2.6 面试题

Q1：Hash 和 String 存储对象的区别？

答案：

特性	Hash	String (JSON)
存储方式	字段分开存储	JSON 序列化存储
修改单个字段	O(1) 直接修改	O(N) 需要读取全部，修改，再写入
内存占用	ziplist 时更省内存	序列化后有额外开销
部分获取	HGET 单个字段	GET 全部再解析
复杂查询	不支持复杂查询	不支持
适用场景	字段经常修改	字段不常修改

选择建议：

字段经常独立修改：使用 Hash
整体不常修改，总是整体读取：使用 String
字段数量多（> 512）：使用 Hash
需要嵌套结构：使用 String (JSON)

Q2：什么是渐进式 rehash？为什么要这样设计？

答案：

Redis 的 Hash 在扩容或缩容时，采用渐进式 rehash：

过程：

为 dict[1] 分配新的哈希表（通常是旧表的 2 倍）
维护 rehashidx 索引，初始为 0
每次增删改查操作时，顺带将 dict[0].table[rehashidx] 的数据迁移到 dict[1]
rehashidx++
直到全部迁移完成，释放 dict[0]

优点：

避免阻塞：不会一次性迁移大量数据导致服务阻塞
分摊成本：将 rehash 的成本分摊到多次操作中

缺点：

rehash 期间需要维护两个哈希表，内存占用增加

Q3：ziplist 和 hashtable 的转换条件？

答案：

配置参数：

hash-max-ziplist-entries 512    # 键值对数量阈值
hash-max-ziplist-value 64      # 键或值长度阈值

转换规则：

** hashtable → ziplist**：不转换（只从小到大）
ziplist → hashtable：满足任一条件即转换
- 键值对数量 ≥ 512
- 键或值的字符串长度 > 64 字节

查看编码：

OBJECT ENCODING key

Q4：HGETALL 有什么问题？如何优化？

答案：

问题：

如果 Hash 字段很多（如百万级），HGETALL 会返回所有数据，可能导致：
- 网络阻塞
- 内存占用过高
- 阻塞其他命令

优化方案：

分批获取（使用 HSCAN）

HSCAN key 0 COUNT 100

只获取需要的字段

HMGET key field1 field2 field3

限制字段数量

# 业务层控制 Hash 的字段数量
# 如购物车限制最多 100 件商品

Q5：实现一个购物车功能？

答案：

# 添加商品
HSET cart:user:1001 product:1001 2
HSET cart:user:1001 product:1002 1

# 修改商品数量
HINCRBY cart:user:1001 product:1001 1

# 获取购物车
HGETALL cart:user:1001

# 删除商品
HDEL cart:user:1001 product:1001

# 获取商品数量
HLEN cart:user:1001

# 判断商品是否在购物车
HEXISTS cart:user:1001 product:1001

优化：

超时清理：给购物车设置过期时间
数量限制：检查商品数量是否超过上限
原子操作：使用 Lua 脚本保证库存扣减的原子性

三、List（列表）

3.1 基本概念

List 是一个有序的字符串列表，可以在列表两端高效地添加和删除元素。

特点：

有序
可重复
双向操作（头尾）

3.2 底层实现

1. quicklist（快速列表，Redis 3.2+）

结构：双向链表 + ziplist

quicklist
├── ziplist node → [elem1, elem2, elem3]
├── ziplist node → [elem4, elem5, elem6]
└── ziplist node → [elem7, elem8]

特点：

每个节点是一个 ziplist
结合了链表和 ziplist 的优点
节省内存，且支持快速的两端操作

配置参数：

list-max-ziplist-size -2    # 每个节点的 ziplist 大小
# -2: 8KB
# -1: 4KB
# -5: 64KB
# 正数: 元素个数

list-compress-depth 0       # 压缩深度（0 表示不压缩）

2. linkedlist（双向链表，Redis 3.2 之前）

结构：

struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
};

struct list {
    listNode *head;
    listNode *tail;
    unsigned long len;
};

缺点：

每个节点都有指针开销
内存不连续，缓存不友好

3. ziplist（压缩列表，元素少时）

使用条件：元素数量少且每个元素小

3.3 常用命令

# ============ 左右操作 ============

# 左侧插入（头插）
LPUSH key value1 value2
LPUSHX key value  # 仅当列表存在时插入

# 右侧插入（尾插）
RPUSH key value1 value2
RPUSHX key value

# 左侧弹出
LPOP key
BLPOP key timeout  # 阻塞式弹出

# 右侧弹出
RPOP key
BRPOP key timeout

# ============ 查询操作 ============

# 获取列表指定范围元素
LRANGE key 0 -1      # 获取所有
LRANGE key 0 9       # 获取前 10 个

# 获取列表长度
LLEN key

# 获取指定索引的元素
LINDEX key 0

# ============ 修改操作 ============

# 设置指定索引的元素
LSET key index value

# 插入到指定元素前后
LINSERT key BEFORE|AFTER pivot value

# ============ 删除操作 ============

# 删除指定值的元素（可删除多个）
LREM key count value
# count > 0: 从头到尾删除 count 个
# count < 0: 从尾到头删除 |count| 个
# count = 0: 删除所有

# 保留指定范围
LTRIM key 0 99  # 只保留前 100 个

# ============ 阻塞操作 ============

# 阻塞式弹出（实现消息队列）
BLPOP queue1 queue2 0      # 永久阻塞
BRPOP queue1 queue2 10     # 阻塞 10 秒

# ============ 其他操作 ============

# 弹出最后一个元素并插入到另一个列表（原子操作）
RPOPLPUSH source destination
BRPOPLPUSH source destination timeout

3.4 应用场景

1. 消息队列（FIFO）

# 生产者
LPUSH queue:task "task1"
LPUSH queue:task "task2"

# 消费者
RPOP queue:task

# 阻塞式消费（推荐）
BRPOP queue:task 0  # 永久阻塞直到有消息

2. 栈（LIFO）

# 压栈
LPUSH stack:task "task1"

# 出栈
LPOP stack:task

3. 最新列表

# 添加最新文章
LPUSH latest:articles article:1001
LTRIM latest:articles 0 9  # 只保留最新 10 篇

# 获取最新文章列表
LRANGE latest:articles 0 9

4. 时间线

# 用户发布动态
LPUSH timeline:user:1001 "post:1001"

# 获取时间线
LRANGE timeline:user:1001 0 19

5. 优先级队列

# 高优先级队列
LPUSH queue:high "task1"
# 普通队列
LPUSH queue:normal "task2"

# 消费时先处理高优先级
BRPOP queue:high queue:normal 0

3.5 面试题

Q1：Redis 的 List 为什么不使用跳表？

答案：

List 的使用场景主要是两端操作（LPUSH/RPOP），quicklist 优化了这些场景：

两端操作：O(1)
范围查询：O(N)，但实际使用中通常是获取头部或全部

如果需要中间访问或范围查询，应该使用 ZSet（底层使用跳表，O(log N)）。

Q2：如何实现消息队列？有什么问题？

答案：

# 简单实现
LPUSH queue:task "task1"
RPOP queue:task

# 阻塞式实现
BRPOP queue:task 0

问题：

消息丢失：消费者宕机，消息未处理就丢失
- 解决：使用 BRPOPLPUSH 备份到 processing 队列
不支持消息确认：无法知道消息是否被正确处理
- 解决：使用 Stream（Redis 5.0+）
不支持广播：一条消息只能被一个消费者消费
- 解决：使用 Pub/Sub 或 Stream
不支持消息回溯：已消费的消息无法重新消费
- 解决：使用 Stream

更好的方案：

Redis 5.0 之前：使用 List + 备份队列
Redis 5.0+：使用 Stream

Q3：LRANGE 为什么性能差？如何优化？

答案：

问题：

LRANGE 0 -1 获取所有元素，时间复杂度 O(N)
如果 List 很大，会导致：
- 阻塞 Redis
- 网络传输慢
- 内存占用高

优化方案：

分页查询

LRANGE key 0 9    # 第一页
LRANGE key 10 19  # 第二页

限制 List 长度

# 固定长度列表
LPUSH key value
LTRIM key 0 99

使用 HSCAN 替代 KEYS + LRANGE

# 如果需要查找特定元素，考虑其他数据结构

Q4：实现一个轻量级的消息队列？

答案：

# ============ 生产者 ============
LPUSH queue:task "task1"

# ============ 消费者 ============
# 使用 RPOPLPUSH 实现消息备份
RPOPLPUSH queue:task queue:processing

# 处理消息...
# 处理成功后删除
LREM queue:processing 1 "task1"

# ============ 监控未处理消息 ============
LLEN queue:task

# ============ 死信队列 ============
# 处理失败的消息
LPUSH queue:dead "task1"

使用 BRPOPLPUP 的优势：

原子操作：弹出和压入是原子的
消息备份：防止消息丢失
可恢复：可以从 processing 队列恢复

Q5：quicklist 的设计思想？

答案：

quicklist 结合了 双向链表和 ziplist 的优点：

双向链表：

优点：两端操作快 O(1)
缺点：每个节点都有指针开销，内存不连续

ziplist：

优点：内存紧凑，连续存储
缺点：插入删除可能需要重新分配内存

quicklist：

每个 quicklist 节点是一个 ziplist
多个 ziplist 节点通过双向链表连接
平衡了内存和性能

配置参数：

# 每个 ziplist 节点的大小
list-max-ziplist-size -2    # 8KB，平衡内存和性能

# 压缩深度
list-compress-depth 1       # 压缩除首尾外的节点

四、Set（集合）

4.1 基本概念

Set 是无序、唯一的字符串集合。

特点：

无序（不保证顺序）
唯一（自动去重）
支持集合运算（交集、并集、差集）

4.2 底层实现

1. intset（整数集合）

使用条件：

所有元素都是整数值
元素数量 ≤ 512 个（默认 set-max-intset-entries）

结构：

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

特点：

有序数组（从小到大）
支持二分查找
升级但不降级

2. hashtable（哈希表）

使用条件：

元素是字符串
元素数量 > 512

特点：

value 固定为 NULL
O(1) 添加、删除、查找

4.3 常用命令

# ============ 基本操作 ============

# 添加元素（可添加多个）
SADD key member1 member2

# 获取所有元素
SMEMBERS key

# 删除元素（可删除多个）
SREM key member1 member2

# 判断元素是否存在
SISMEMBER key member

# 获取集合元素个数
SCARD key

# 随机获取元素
SRANDMEMBER key [count]

# 随机弹出元素
SPOP key [count]

# ============ 集合运算 ============

# 交集
SINTER key1 key2
SINTERSTORE dest key1 key2

# 并集
SUNION key1 key2
SUNIONSTORE dest key1 key2

# 差集（key1 - key2）
SDIFF key1 key2
SDIFFSTORE dest key1 key2

# ============ 其他操作 ============

# 随机获取指定数量元素
SRANDMEMBER key 10   # 不删除
SPOP key 10          # 删除

# 将元素从一个集合移动到另一个集合
SMOVE source dest member

4.4 应用场景

1. 标签系统

# 添加文章标签
SADD article:1001:tags "Redis" "数据库" "NoSQL"

# 获取文章标签
SMEMBERS article:1001:tags

# 删除标签
SREM article:1001:tags "NoSQL"

2. 共同好友

# 用户的好友列表
SADD user:1001:friends "user:1002" "user:1003" "user:1004"
SADD user:1002:friends "user:1003" "user:1004" "user:1005"

# 查找共同好友
SINTER user:1001:friends user:1002:friends
# 返回: user:1003, user:1004

3. 点赞/收藏

# 用户点赞文章
SADD article:1001:liked "user:1001"

# 取消点赞
SREM article:1001:liked "user:1001"

# 判断是否点赞
SISMEMBER article:1001:liked "user:1001"

# 获取点赞数
SCARD article:1001:liked

# 获取所有点赞用户
SMEMBERS article:1001:liked

4. 抽奖系统

# 参与抽奖
SADD lottery:participants "user:1001" "user:1002" "user:1003"

# 随机抽取中奖者（不删除）
SRANDMEMBER lottery:participants 3

# 随机抽取并删除（真正的抽奖）
SPOP lottery:participants 1

5. 去重

# 日志去重
SADD logs:unique "log_id_1001"
# 如果已存在，不会重复添加

# 统计 UV（独立访客）
SADD uv:20240101 "user:1001"
SCARD uv:20240101

4.5 面试题

Q1：Set 和 List 的区别？

答案：

特性	Set	List
有序性	无序	有序
唯一性	唯一，自动去重	可重复
索引访问	不支持	支持（LINDEX）
集合运算	支持（交集、并集、差集）	不支持
应用场景	标签、好友、去重	消息队列、时间线

选择建议：

需要去重：Set
需要顺序：List
需要集合运算：Set
需要索引访问：List

Q2：如何实现共同好友功能？

答案：

# 添加好友
SADD user:1001:friends "user:1002" "user:1003" "user:1004"
SADD user:1002:friends "user:1003" "user:1004" "user:1005"

# 查找共同好友（交集）
SINTER user:1001:friends user:1002:friends

# 查找 user:1001 的独有好友（差集）
SDIFF user:1001:friends user:1002:friends

# 查找所有好友（并集）
SUNION user:1001:friends user:1002:friends

# 推荐可能认识的人（二度好友）
SDIFF (SUNION user:1002:friends) user:1001:friends

Q3：intset 的升级机制？

答案：

intset 根据数值大小自动升级编码：

int16 → int32 → int64

示例：

SADD numbers 1 2 3          # int16
SADD numbers 40000          # 超过 int16 范围，升级到 int32
SADD numbers 5000000000     # 超过 int32 范围，升级到 int64

特点：

只升级不降级：升级后不会降级，即使删除大数值
重新分配内存：升级时需要重新分配内存并复制数据

配置：

set-max-intset-entries 512  # 超过 512 个元素后使用 hashtable

Q4：SMEMBERS 有什么性能问题？如何优化？

答案：

问题：

SMEMBERS 返回所有元素，时间复杂度 O(N)
如果 Set 很大（百万级），会导致：
- 网络传输慢
- 内存占用高
- 阻塞 Redis

优化方案：

使用 SSCAN 遍历

SSCAN key 0 COUNT 100

分页处理

# 如果需要随机元素
SRANDMEMBER key 100

业务层限制

# 控制集合大小
SCARD key
# 如果超过阈值，不再添加或清理旧数据

Q5：实现一个抽奖系统？

答案：

# ============ 用户参与抽奖 ============
SADD lottery:draw:20240101 "user:1001"
SADD lottery:draw:20240101 "user:1002"

# ============ 抽取中奖者 ============
# 方式一：随机抽取但不删除（用于展示）
SRANDMEMBER lottery:draw:20240101 10

# 方式二：随机抽取并删除（真实抽奖）
SPOP lottery:draw:20240101 3

# ============ 防止重复抽奖 ============
SADD lottery:draw:20240101 "user:1001"
# 如果已参与，返回 0

# ============ 查看参与人数 ============
SCARD lottery:draw:20240101

高级功能：

# 权重抽奖（使用 ZSet）
ZADD lottery:weighted 10 "user:1001"
ZADD lottery:weighted 5 "user:1002"

# 根据权重抽取（实现较复杂，需要 Lua 脚本）

五、ZSet（有序集合）

5.1 基本概念

ZSet 是有序、唯一的字符串集合，每个元素关联一个 score（分数）。

特点：

有序（按 score 排序）
唯一（member 唯一）
支持范围查询

5.2 底层实现

1. ziplist（压缩列表）

使用条件（同时满足）：

元素数量 < 128 个（默认 zset-max-ziplist-entries）
元素长度 < 64 字节（默认 zset-max-ziplist-value）

结构：

[member1, score1, member2, score2, ...]

2. skiplist + hashtable（跳表 + 哈希表）

使用条件（满足任一）：

元素数量 ≥ 128
元素长度 ≥ 64 字节

skiplist（跳表）结构：

struct zskiplistNode {
    sds ele;                      // 成员
    double score;                 // 分数
    struct zskiplistNode *backward; // 后退指针
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 前进指针
        unsigned long span;       // 跨度
    } level[];                    // 层
};

struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
};

为什么同时使用 skiplist 和 hashtable？

skiplist：支持范围查询、排名查询，O(log N)
hashtable：支持 O(1) 查找 member 对应的 score

5.3 跳表（Skip List）

跳表是一种概率数据结构，用于替代平衡树。

结构示例：

Level 3:  1 → 7
Level 2:  1 → 4 → 7
Level 1:  1 → 3 → 4 → 6 → 7
Level 0:  1 → 2 → 3 → 4 → 5 → 6 → 7

时间复杂度：

查找、插入、删除：平均 O(log N)，最坏 O(N)
空间复杂度：O(N)

对比平衡树：

跳表实现简单
不需要旋转操作
范围查询更高效

5.4 常用命令

# ============ 添加操作 ============

# 添加元素
ZADD key score member
ZADD key score1 member1 score2 member2

# ============ 查询操作 ============

# 获取指定范围元素（按 score 排序）
ZRANGE key 0 -1          # 升序
ZRANGE key 0 9 WITHSCORES
ZREVRANGE key 0 -1       # 降序

# 按 score 范围查询
ZRANGEBYSCORE key 60 100 WITHSCORES
ZREVRANGEBYSCORE key 100 60

# 按排名范围查询
ZRANGE key 0 9

# ============ 获取分数和排名 ============

# 获取元素分数
ZSCORE key member

# 获取元素排名（升序）
ZRANK key member

# 获取元素排名（降序）
ZREVRANK key member

# ============ 删除操作 ============

# 删除元素
ZREM key member

# 按排名删除
ZREMRANGEBYRANK key 0 9

# 按 score 范围删除
ZREMRANGEBYSCORE key 0 60

# ============ 计数操作 ============

# 获取集合元素个数
ZCARD key

# 获取 score 范围内的元素个数
ZCOUNT key 60 100

# ============ 增减分数 ============

# 增加分数
ZINCRBY key increment member

5.5 应用场景

1. 排行榜

# 添加分数
ZADD rank:game 1000 "player1"
ZADD rank:game 1200 "player2"
ZADD rank:game 1150 "player3"

# 获取前 10 名
ZREVRANGE rank:game 0 9 WITHSCORES

# 查看玩家排名
ZREVRANK rank:game "player2"

# 增加分数
ZINCRBY rank:game 50 "player1"

# 获取指定分数范围的玩家
ZRANGEBYSCORE rank:game 1000 1200

2. 优先级队列

# 添加任务（score 为优先级）
ZADD queue:priority 1 "low_task"
ZADD queue:priority 10 "high_task"
ZADD queue:priority 5 "medium_task"

# 获取最高优先级任务
ZREVRANGE queue:priority 0 0

# 弹出最高优先级任务
ZPOPMAX queue:priority

3. 延迟队列

# score 为执行时间戳
ZADD queue:delayed 1704153600 "task1"
ZADD queue:delayed 1704157200 "task2"

# 获取到期任务
ZRANGEBYSCORE queue:delayed 0 1704153600

4. 范围查询

# 查找指定分数范围的用户
ZRANGEBYSCORE scores:math 80 100

# 查找指定排名范围的用户
ZRANGE scores:math 0 9

5.6 面试题

Q1：ZSet 为什么使用跳表而不是平衡树？

答案：

对比项	跳表	平衡树（红黑树、AVL）
实现复杂度	简单	复杂（需要旋转）
查找效率	O(log N)	O(log N)
插入删除	O(log N)	O(log N)
范围查询	高效（顺序访问）	需要中序遍历
内存占用	稍高（多级索引）	较低

跳表的优势：

实现简单，不需要复杂的旋转操作
范围查询更高效（按顺序访问即可）
并发友好（不需要重平衡）

Q2：ZSet 的 skiplist 和 hashtable 是如何配合的？

答案：

双索引结构：

skiplist：按 score 排序，支持范围查询、排名查询
hashtable：member → score 映射，支持 O(1) 查找分数

示例：

ZADD myzset 10 "player1"

操作：

hashtable 存储："player1" → 10
skiplist 插入：("player1", 10) 到合适位置

查询：

# 查找分数（O(1)）
ZSCORE myzset "player1"
# 使用 hashtable

# 查找排名（O(log N)）
ZRANK myzset "player1"
# 使用 skiplist

Q3：实现一个实时排行榜？

答案：

# ============ 用户得分 ============
ZINCRBY rank:game score user_id

# ============ 获取 Top 10 ============
ZREVRANGE rank:game 0 9 WITHSCORES

# ============ 获取用户排名 ============
ZREVRANK rank:game user_id

# ============ 获取用户分数 ============
ZSCORE rank:game user_id

# ============ 分页查询 ============
# 第 1 页（0-9）
ZREVRANGE rank:game 0 9 WITHSCORES
# 第 2 页（10-19）
ZREVRANGE rank:game 10 19 WITHSCORES

# ============ 按分数范围查询 ============
# 查找分数在 1000-2000 之间的用户
ZRANGEBYSCORE rank:game 1000 2000 WITHSCORES LIMIT 0 10

# ============ 定时清理 ============
# 只保留前 1000 名
ZREMRANGEBYRANK rank:game 1000 -1

Q4：ZRangeByScore 的实现原理？

答案：

ZRANGEBYSCORE key min max 的实现：

跳表查找：从最高层开始，找到第一个 ≥ min 的节点
顺序遍历：从找到的节点开始，按第 0 层的指针遍历
条件判断：返回 score ≤ max 的节点

时间复杂度：

查找起点：O(log N)
遍历结果：O(M)，M 为结果数量

优化：

# 使用 LIMIT 限制结果数量
ZRANGEBYSCORE key min max WITHSCORES LIMIT 0 100

Q5：实现一个延迟队列？

答案：

# ============ 添加延迟任务 ============
# score = 执行时间戳
ZADD queue:delayed 1704153600 "task1_data"
ZADD queue:delayed 1704157200 "task2_data"

# ============ 消费者轮询 ============
# 获取当前时间之前到期的任务
ZRANGEBYSCORE queue:delayed 0 (current_timestamp) LIMIT 0 10

# ============ 处理任务 ============
for task in tasks:
    # 处理任务...
    # 删除已处理的任务
    ZREM queue:delayed task

# ============ 使用 ZPOPMIN（Redis 6.2+） ============
while true:
    task = ZPOPMIN queue:delayed
    if task and task.score <= current_timestamp:
        process(task)
    else:
        # 未到期，重新放回
        ZADD queue:delayed task.score task.member
        sleep(1)

优化：

使用 Redis Keyspace Notifications 通知到期
或使用 Redis 模块（如 RedisTimeSeries）

六、Bitmap（位图）

6.1 基本概念

Bitmap 不是独立的数据类型，而是基于 String 的按位操作。

特点：

节省空间（1 MB = 800 万位）
支持位运算

6.2 常用命令

# 设置位
SETBIT key offset value
# offset: 0-based
# value: 0 或 1

# 获取位
GETBIT key offset

# 统计为 1 的位数
BITCOUNT key
BITCOUNT key 0 100  # 统计指定范围

# 位运算
BITOP AND dest key1 key2      # 交集
BITOP OR dest key1 key2       # 并集
BITOP XOR dest key1 key2      # 异或
BITOP NOT dest key            # 取反

# 查找第一个为 1/0 的位
BITPOS key 1
BITPOS key 0

6.3 应用场景

1. 用户签到

# 2024 年第 1 天签到
SETBIT checkin:user:1001:2024 0 1

# 第 10 天签到
SETBIT checkin:user:1001:2024 9 1

# 检查是否签到
GETBIT checkin:user:1001:2024 9

# 统计签到天数
BITCOUNT checkin:user:1001:2024

# 获取连续签到天数
# 需要编程实现

2. 在线用户

# 用户上线
SETBIT online:users 1001 1

# 用户下线
SETBIT online:users 1001 0

# 统计在线用户数
BITCOUNT online:users

# 检查用户是否在线
GETBIT online:users 1001

3. 布隆过滤器

# 添加元素（使用多个哈希函数）
SETBIT bloom:filter hash1 1
SETBIT bloom:filter hash2 1
SETBIT bloom:filter hash3 1

# 检查元素是否存在
if (GETBIT bloom:filter hash1 == 1 &&
    GETBIT bloom:filter hash2 == 1 &&
    GETBIT bloom:filter hash3 == 1) {
    // 可能存在
} else {
    // 一定不存在
}

6.4 面试题

Q1：Bitmap 为什么节省空间？

答案：

对比：

String 存储 "10000001"：8 字节
Bitmap 存储：1 字节（8 位）

计算：

1 位存储 0 或 1
1 字节 = 8 位
1 MB = 8,000,000 位

示例：

# 存储 1000 万用户的签到状态
# String：需要 1000 万个 key，每个至少几十字节
# Bitmap：一个 key，1.25 MB

Q2：实现用户签到功能？

答案：

# ============ 签到 ============
SETBIT checkin:user:1001:2024 (day_of_year - 1) 1

# ============ 检查签到 ============
GETBIT checkin:user:1001:2024 (day_of_year - 1)

# ============ 统计签到天数 ============
BITCOUNT checkin:user:1001:2024

# ============ 获取连续签到天数 ============
# 需要客户端实现
# 从最后一天往前遍历，统计连续为 1 的位数

# ============ 统计某天活跃用户数 ============
# 将所有用户的位做 OR 运算
BITOP OR active:day:100 user:1 user:2 user:3 ...
BITCOUNT active:day:100

Q3：布隆过滤器的原理和实现？

答案：

原理：

使用多个哈希函数将元素映射到位
判断时，检查所有对应的位是否都为 1

特点：

不存在一定不存在
存在可能不存在（误判）

实现：

# ============ 添加元素 ============
# 假设 3 个哈希函数
hash1 = murmurhash3(x) % 10000
hash2 = md5(x) % 10000
hash3 = sha1(x) % 10000

SETBIT bloom:filter hash1 1
SETBIT bloom:filter hash2 1
SETBIT bloom:filter hash3 1

# ============ 检查元素 ============
if (GETBIT bloom:filter hash1 == 1 &&
    GETBIT bloom:filter hash2 == 1 &&
    GETBIT bloom:filter hash3 == 1) {
    return "可能存在"
} else {
    return "一定不存在"
}

优化：

使用更大的 Bitmap 降低误判率
增加哈希函数数量

七、HyperLogLog（基数统计）

7.1 基本概念

HyperLogLog 用于基数统计（统计不重复元素个数）。

特点：

空间固定（12 KB）
有误差（0.81%）
适合海量数据

7.2 常用命令

# 添加元素
PFADD key element1 element2

# 统计基数
PFCOUNT key

# 合并多个 HyperLogLog
PFMERGE dest key1 key2

7.3 应用场景

1. UV 统计

# 记录访问
PFADD uv:20240101 "user:1001"
PFADD uv:20240101 "user:1002"

# 统计 UV
PFCOUNT uv:20240101

# 合并多天 UV
PFMERGE uv:total uv:20240101 uv:20240102

7.4 面试题

Q1：HyperLogLog 的原理？

答案：

核心思想：通过伯努利试验估算基数。

步骤：

将元素哈希为二进制串
找到第一个 1 的位置（低位开始）
记录最大位置（例如：00101 → 第 3 位）
根据最大位置估算基数

公式：

基数 ≈ 1.39 * m * (0.5)^max

优化：分桶平均，降低误差

Q2：HyperLogLog vs Set vs Bitmap？

答案：

特性	HyperLogLog	Set	Bitmap
空间占用	固定 12 KB	O(N)	依赖 ID 范围
精确度	有误差（0.81%）	精确	精确
适用场景	海量数据	小数据	ID 连续

选择建议：

海量数据、可接受误差：HyperLogLog
小数据、精确统计：Set
ID 连续（如用户 ID）：Bitmap

八、GEO（地理位置）

8.1 基本概念

GEO 存储地理位置信息，底层使用 ZSet 实现。

8.2 常用命令

# 添加位置
GEOADD key longitude latitude member

# 获取位置
GEOPOS key member

# 计算距离
GEODIST key member1 member2 [km|m|mi|ft]

# 范围查询
GEORADIUS key longitude latitude radius km|...
GEORADIUSBYMEMBER key member radius km|...

8.3 应用场景

1. 附近的人

# 添加用户位置
GEOADD locations 116.404 39.915 "user1"

# 查找附近 10km 内的用户
GEORADIUS locations 116.404 39.915 10 km

# 返回距离
GEORADIUS locations 116.404 39.915 10 km WITHDIST

8.4 面试题

Q1：GEO 的底层实现？

答案：

GEO 底层使用 ZSet：

// member: 用户 ID
// score: 经纬度的 52 位 geohash
ZADD locations geohash "user1"

geohash：

将经纬度编码为字符串
相近的位置 geohash 也相近

九、Stream（流）

9.1 基本概念

Stream 是 Redis 5.0 新增的消息队列数据类型。

特点：

支持消息持久化
支持消费者组
支持消息确认（ACK）

9.2 常用命令

# 添加消息
XADD stream * key value

# 读取消息
XREAD STREAMS stream $

# 消费者组
XGROUP CREATE stream group1 0
XREADGROUP GROUP group1 consumer1 STREAMS stream 0

# 确认消息
XACK stream group1 message_id

9.3 面试题

Q1：Stream vs List 作为消息队列？

答案：

特性	Stream	List
消息持久化	支持	不支持
消费者组	支持	不支持
消息确认	支持	不支持
消息回溯	支持	不支持
复杂度	较高	简单

选择建议：

简单场景：List
可靠性要求高：Stream

总结

本文详细介绍了 Redis 的 9 种数据结构：

String：最基本的数据类型，用于缓存、计数器、分布式锁
Hash：存储对象，如用户信息、购物车
List：有序列表，用于消息队列、时间线
Set：无序唯一集合，用于标签、共同好友、抽奖
ZSet：有序集合，用于排行榜、优先级队列
Bitmap：位图，用于签到、在线用户
HyperLogLog：基数统计，用于 UV 统计
GEO：地理位置，用于附近的人
Stream：消息队列，用于可靠消息传递

面试要点：

每种数据类型的底层实现
编码转换条件
时间复杂度
应用场景
常见问题和优化方案

掌握这些内容，就能应对大部分 Redis 数据结构相关的面试题！

数据结构概览​

一、String（字符串）​

1.1 基本概念​

1.2 底层实现​

1. int 编码​

2. embstr 编码（Embedded String）​

3. raw 编码​

1.3 SDS（Simple Dynamic String）​

1.4 常用命令​

1.5 应用场景​

1. 缓存​

2. 计数器​

3. 分布式锁​

4. Session 共享​

5. 限流​

1.6 面试题​

Q1：Redis 的 String 为什么是二进制安全的？​

Q2：String 的 embstr 和 raw 编码有什么区别？​

Q3：为什么使用 SDS 而不是 C 字符串？​

Q4：实现一个分布式锁？​

Q5：如何实现限流？​

Q6：SET 命令的 NX、XX 参数有什么用？​

二、Hash（哈希）​

2.1 基本概念​

2.2 底层实现​

1. ziplist（压缩列表）​

2. hashtable（哈希表）​

2.3 渐进式 rehash​

2.4 常用命令​

2.5 应用场景​

1. 对象存储​

2. 购物车​

3. 文章点赞​

4. 计数器（多维）​

2.6 面试题​

Q1：Hash 和 String 存储对象的区别？​

Q2：什么是渐进式 rehash？为什么要这样设计？​

Q3：ziplist 和 hashtable 的转换条件？​

Q4：HGETALL 有什么问题？如何优化？​

Q5：实现一个购物车功能？​

三、List（列表）​

3.1 基本概念​

3.2 底层实现​

1. quicklist（快速列表，Redis 3.2+）​

2. linkedlist（双向链表，Redis 3.2 之前）​

3. ziplist（压缩列表，元素少时）​

3.3 常用命令​

3.4 应用场景​

1. 消息队列（FIFO）​

2. 栈（LIFO）​

3. 最新列表​

4. 时间线​

5. 优先级队列​

3.5 面试题​

Q1：Redis 的 List 为什么不使用跳表？​

Q2：如何实现消息队列？有什么问题？​

Q3：LRANGE 为什么性能差？如何优化？​

Q4：实现一个轻量级的消息队列？​

Q5：quicklist 的设计思想？​

四、Set（集合）​

4.1 基本概念​

4.2 底层实现​

1. intset（整数集合）​

2. hashtable（哈希表）​

4.3 常用命令​

4.4 应用场景​

1. 标签系统​

2. 共同好友​

3. 点赞/收藏​

4. 抽奖系统​

5. 去重​

4.5 面试题​

Q1：Set 和 List 的区别？​

Q2：如何实现共同好友功能？​

Q3：intset 的升级机制？​

Q4：SMEMBERS 有什么性能问题？如何优化？​

Q5：实现一个抽奖系统？​

五、ZSet（有序集合）​

5.1 基本概念​

5.2 底层实现​

数据结构概览

一、String（字符串）

1.1 基本概念

1.2 底层实现

1. int 编码

2. embstr 编码（Embedded String）

3. raw 编码

1.3 SDS（Simple Dynamic String）

1.4 常用命令

1.5 应用场景

1. 缓存

2. 计数器

3. 分布式锁

4. Session 共享

5. 限流

1.6 面试题

Q1：Redis 的 String 为什么是二进制安全的？

Q2：String 的 embstr 和 raw 编码有什么区别？

Q3：为什么使用 SDS 而不是 C 字符串？

Q4：实现一个分布式锁？

Q5：如何实现限流？

Q6：SET 命令的 NX、XX 参数有什么用？

二、Hash（哈希）

2.1 基本概念

2.2 底层实现

1. ziplist（压缩列表）

2. hashtable（哈希表）

2.3 渐进式 rehash

2.4 常用命令

2.5 应用场景

1. 对象存储

2. 购物车

3. 文章点赞

4. 计数器（多维）

2.6 面试题

Q1：Hash 和 String 存储对象的区别？

Q2：什么是渐进式 rehash？为什么要这样设计？

Q3：ziplist 和 hashtable 的转换条件？

Q4：HGETALL 有什么问题？如何优化？

Q5：实现一个购物车功能？

三、List（列表）

3.1 基本概念

3.2 底层实现

1. quicklist（快速列表，Redis 3.2+）

2. linkedlist（双向链表，Redis 3.2 之前）

3. ziplist（压缩列表，元素少时）

3.3 常用命令

3.4 应用场景

1. 消息队列（FIFO）

2. 栈（LIFO）

3. 最新列表

4. 时间线

5. 优先级队列

3.5 面试题

Q1：Redis 的 List 为什么不使用跳表？

Q2：如何实现消息队列？有什么问题？

Q3：LRANGE 为什么性能差？如何优化？

Q4：实现一个轻量级的消息队列？

Q5：quicklist 的设计思想？

四、Set（集合）

4.1 基本概念

4.2 底层实现

1. intset（整数集合）

2. hashtable（哈希表）

4.3 常用命令

4.4 应用场景

1. 标签系统

2. 共同好友

3. 点赞/收藏

4. 抽奖系统

5. 去重

4.5 面试题

Q1：Set 和 List 的区别？

Q2：如何实现共同好友功能？

Q3：intset 的升级机制？

Q4：SMEMBERS 有什么性能问题？如何优化？

Q5：实现一个抽奖系统？

五、ZSet（有序集合）

5.1 基本概念

5.2 底层实现