2.3 软件系统中的集合：数据结构、SQL 与近似成员查询

数学集合只有成员资格，没有顺序和重复。程序中的 List、Set、数据库结果集和缓存过滤器却各有自己的语义。把它们都叫“集合”会掩盖重复、空值、相等性和误判问题。

先选择正确的抽象

抽象	顺序	重复	典型问题
Set	不作为语义的一部分	不保留	某元素是否属于集合
Sequence / List	保留	保留	第几个元素是什么
Multiset / Bag	通常不关心	记录次数	某值出现多少次
Map	键到值的映射	键唯一	某键对应什么值

订单中的商品行通常是序列或多重集合，而不是普通集合：买两件同款商品不能因为去重只剩一件。用户拥有的权限若只关心“是否拥有”，则适合集合。

程序集合依赖相等性协议

数学中元素相等由模型给定。哈希集合还需要实现层面的协议：相等元素必须产生一致哈希值，且作为键期间影响相等与哈希的字段不应变化。

record UserId(String value) {}

Set<UserId> users = new HashSet<>();
users.add(new UserId("u-17"));

boolean found = users.contains(new UserId("u-17")); // true

Java record 根据组件生成值相等语义，适合这类标识符。若使用可变对象作为 HashSet 元素，加入后再修改参与 equals/hashCode 的字段，元素可能仍在桶里却无法按新值或旧值正常找到。

“集合元素必须可哈希”也不是跨语言的数学规则。树集合可以依赖全序比较，位集合依赖整数索引，线性实现甚至只需要相等判断。数据结构的要求来自实现策略。

复杂度要结合实现说

典型哈希集合在分布良好并正确扩容时，成员查询平均接近常数时间；最坏情况和具体保证取决于实现。平衡树集合通常提供对数级查询并维持排序。位图在紧凑整数域中能以位运算快速完成并交差。

选择时比较：

• 元素数量和键分布；
• 是否需要稳定顺序或范围查询；
• 内存上限；
• 相等与哈希成本；
• 并发读写协议；
• 是否需要持久化或跨进程序列化。

不要只因为 API 名为 Set 就假定所有操作都是 O(1)。

SQL 默认常是 Bag 语义

关系模型以集合为基础，但 SQL 查询结果通常允许重复行：

SELECT role FROM user_roles;

若十个用户都有 viewer，结果可能出现十行 viewer。DISTINCT 才显式去重。

同样：

SELECT role FROM team_a
UNION
SELECT role FROM team_b;

UNION 去重，而 UNION ALL 保留重复。保留重复往往省去排序或哈希去重成本，若业务不需要集合语义，应优先表达真实需求。

JOIN 可从笛卡尔积加谓词筛选理解：

R ⋈_condition S = {pair ∈ R×S | condition(pair)}

但在 SQL 中，重复行和 NULL 会使结果计数与纯集合直觉不同。关系代数是理解查询的模型，不应当抹平 SQL 的实际语义。

NOT IN 与 NULL 的陷阱

目标：找出没有购买记录的用户。

SELECT u.id
FROM users u
WHERE u.id NOT IN (SELECT p.user_id FROM purchases p);

若子查询可能产生 NULL，SQL 三值逻辑会让比较结果变成 UNKNOWN，最终可能一行也不返回。通常更稳妥的是相关的 NOT EXISTS：

SELECT u.id
FROM users u
WHERE NOT EXISTS (
  SELECT 1
  FROM purchases p
  WHERE p.user_id = u.id
);

具体执行计划仍应由数据库优化器和索引决定；语义正确是优化之前的前提。

用集合代数审查权限

定义：

Direct(u)       用户直接权限
Roles(u)        用户角色集合
Granted(role)   角色授予权限
Denied(u)       显式拒绝权限

一种策略是：

Effective(u)
= (Direct(u) ∪ ⋃_{r∈Roles(u)} Granted(r)) \ Denied(u)

这个公式明确“拒绝优先”。若系统还有资源范围、条件授权和临时有效期，单纯集合已不足够，可能需要关系或带属性的决策模型。不要把复杂 ABAC 策略强行压成字符串权限集合。

Bloom Filter 表示的是近似成员关系

当集合巨大且主要想快速判断“肯定不存在”时，可以使用 Bloom Filter。插入元素时，用多个哈希函数设置位数组中的位置；查询时检查相同位置：

任一位为 0  -> 元素一定未插入
所有位为 1  -> 元素可能已插入

标准 Bloom Filter 允许假阳性：报告“可能存在”，实际不存在；在只插入、不删除且实现正确的假设下，不产生假阴性。

它不是数学集合的精确替代品：

• 不能枚举全部元素；
• 普通版本不支持安全删除；
• 误判率取决于位数组大小、哈希数量和插入元素数；
• 哈希或持久化版本不一致会破坏保证。

缓存穿透防护可先查 Bloom Filter，但“可能存在”后仍要查询真实存储。把近似结构当授权来源会错误地放行用户，因此不适合安全决策。

类型可以用集合语义理解，但不是全部

把类型解释成一组允许的值很有帮助：整数类型对应某个值域，子类型关系类似集合包含，联合类型类似并集。但真实语言还涉及：

• 操作和行为，而不只值集合；
• null、异常、非终止等语义；
• 可变性与型变；
• 名义类型身份；
• 运行时表示和未定义行为。

因此“类型就是集合”是一种语义模型，不是所有类型系统细节的完整定义。

完成检查

为以下数据选择 Set、List、Multiset、Map 或近似结构，并说明原因：

1. 购物车商品行；
2. 用户权限；
3. 日志事件顺序；
4. 单词出现频率；
5. 十亿个已爬取 URL 的预过滤；
6. 按时间范围查询的唯一任务 ID。

再写一条 SQL，返回“属于项目但未被冻结的用户”，并说明重复行和 NULL 是否会影响结果。

参考资料

• PostgreSQL：Combining Queries
• PostgreSQL：Comparison Functions and Operators