2.3 同一张哈希表：Set与Hash的共用引擎

2.3 同一张哈希表：Set与Hash的共用引擎

本节摘要：Set 和 Hash 底层共用 dict 这个渐进式 rehash 的哈希表：Set 是"值为空的 dict"，Hash 是"值非空的 dict"。搞懂一张表，两个类型一起通透，还能解释 SADD 与 HSET 为什么都是 O(1) 平均复杂度。

dict 长什么样

哈希表核心是两个数组（桶数组）加哈希函数。存入时算出哈希值，按桶数取模落到某个桶，冲突的元素在桶内串成链。

# Hash：field 到 value 的映射
> HSET user:1001 name li age 29
> HGET user:1001 name
"li"
# Set：成员到空的映射
> SADD online u1 u2 u3
> SISMEMBER online u2
(integer) 1
​

SISMEMBER 之所以 O(1)，因为查的是"u2 这个 key 在不在 dict 里"，与集合多大无关。

小数据还有一层节省：元素少时连 dict 都不建。亲手触发一次编码转换：

> HSET obj:1 name li age 29
> OBJECT ENCODING obj:1
"listpack"        # 小哈希：键值对紧排在一块连续内存里
# 继续加入 field，超过128个（默认阈值）……
> OBJECT ENCODING obj:1
"hashtable"       # 升级为真正的 dict
> SADD ids 1 2 3
> OBJECT ENCODING ids
"intset"          # 纯整数集合：排序整数数组，二分查找
> SADD ids "vip9"
> OBJECT ENCODING ids
"listpack"        # 混入字符串成员后立即整体换编码
​

两个解读。其一，转换是全量重建式的：listpack 放不下就整体升级，不存在"一半在紧凑结构一半在哈希表"的中间态。其二，intset 对"全是整数的集合"是意外之喜——有序数组让它还赠送了 O(logN) 的范围判断，但只要混进一个字符串成员，升级立刻发生，设计键的成员类型时保持纯粹是有内存回报的。

渐进式 rehash：最值得学的设计

元素越插越多，桶越来越挤，查找退化成链表扫描。常规做法是一次性扩容并把所有元素搬进新表——千万级元素时这一下能把服务卡死几秒，对单线程的 Redis 不可接受。

dict 的解法是同时持有两张表，搬迁摊牌：

渐进式 rehash 过程

搬迁期间的读写会同时查两张表，新增一律进新表。代价是过渡期内存双份、每次操作多一点搬迁开销，换来的是主线程永不被一次大搬迁卡住。

过渡期还有一个精巧细节：SCAN 在 rehash 进行时遍历，游标按"二进制位反转加一"前进，桶翻倍后新桶号只是在旧桶号最高位添一个 0 或 1——反序递增保证扩容缩容过程中已访问的桶不会被重复访问到漏键。所以 SCAN 才敢承诺"遍历开始到结束间存在的键至少返回一次"，代价是可能重复返回，调用方要自带去重。看似古怪的游标设计，背后正是对渐进式扩容的精确配合。

负载因子的两个触发线也值得记准：平时元素数超过桶数就扩容（因子 1）；有后台保存任务在跑时，阈值放宽到 5——因为此时大量扩容搬迁会连带写时复制的内存翻倍，宁可让桶挤一点。同一张表，两个时机两套阈值，把"内存紧张程度"这个上下文也纳入了决策。

💡 关键直觉：这个"把大动作摊成小步"的思路在 Redis 里反复出现——过期删除的惰性加定期（第 5 章）、删除大键的 UNLINK，本质都是同一个哲学。看懂一次，处处认得。

Set 的独门运算

Set 之所以不只是"没有值的 Hash"，在于它的命令直接映射到集合代数，而实现靠的都是哈希表查找：

> SDIFF followed:li followed:wang   # 差集：li 关注而 wang 没关注的
> SINTER followed:li followed:wang  # 交集：共同关注
> SUNION followed:li followed:wang  # 并集
> SADD tag:python u1 u2
> SRANDMEMBER tag:python 1          # 随机抽人：抽奖场景
> SPOP lucky:pool                   # 随机弹出
​

共同好友、共同标签、商品交叉推荐，这些需求在 SQL 里要写 JOIN，在 Set 里是一次多表桶遍历。交集实现是拿小集合逐个去大集合里 SISMEMBER，成本正比于小集合大小——求交时把小的放前面这句老经验，根源就在实现细节里。

Hash 的典型用法

# 存对象：比整块 JSON 好在哪
> HSET product:8521 title 手机 price 4999 stock 12
> HINCRBY product:8521 stock -1     # 只改库存一个字段
# 部分读取，不搬运整个对象
> HMGET product:8521 price stock
​

整块存 JSON 的问题是任何小改动都要整读整写；Hash 允许字段级读写与原子自增。反过来，如果字段极少且总被整取，String 加 JSON 反而更省——两三条 field 时 Hash 还可能退化用 listpack 存（编码转换在内存紧凑与查找效率间自动权衡）。

⚠️ 常见坑：十万元素的大 Set 做 SMEMBERS 会一次性吐出全部成员，响应体积与耗时双爆。遍历用 SSCAN 分批；同样道理大 Hash 用 HSCAN。

大键的分批遍历实际长这样，游标循环直到返回 0：

> HSCAN product:big 0 COUNT 200
1) "6144"                    # 下一轮的游标，返回0表示遍历结束
2) 1) "field:1"  2) "值1"    # 本批返回的键值对
   3) "field:2"  4) "值2"    # COUNT只是提示，实际条数可多可少
​

解读三点：游标是服务端状态的无符号数，客户端只管透传；COUNT 是每轮期望扫描的桶数而非精确返回条数；遍历期间有键写入或 rehash 进行中，个别键可能重复出现，调用方按 field 幂等处理即可。把 SMEMBERS、HGETALL 这类全量命令替换成游标循环，是第 8 章大键治理清单里收益最立竿见影的一项。

本节要点回顾

• Set 与 Hash 共用 dict，前者值恒为空，后者存 field 到 value
• 渐进式 rehash：双表并存、分批搬迁，主线程不被扩容卡死
• 集合运算是 Set 的灵魂，成本与较小集合的规模挂钩
• Hash 换来字段级操作，对象读改写比整块 JSON 精细
• 大集合全量命令是事故源，一律换 SCAN 家族