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

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

先选择正确的抽象

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

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

程序集合依赖相等性协议

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

下面的完整示例保存为 SetDemo.java，用 JDK 21 执行 javac SetDemo.java 和 java SetDemo，输出 true：

import java.util.HashSet;
import java.util.Set;

public class SetDemo {
    record UserId(String value) {}

    public static void main(String[] args) {
        Set<UserId> users = new HashSet<>();
        users.add(new UserId("u-17"));
        System.out.println(users.contains(new UserId("u-17"))); // true
    }
}

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

这里组件是不可变的 String。Record 不会递归冻结组件；若组件是可变列表，内容仍可能变化，若组件是数组，默认相等比较也不等于逐元素比较。树集合还要求比较器与所需的相等语义相容，不能靠换容器掩盖协议冲突。参见 Java Record 与 Set 合同。

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

复杂度要结合实现说

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

选择时比较：

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

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

SQL 默认常是 Bag 语义

以下 SQL 在一个新的 PostgreSQL 或 DuckDB 会话中顺序执行。先创建只存在于本次会话的合成表，后面的查询都使用这份数据：

CREATE TEMP TABLE user_roles(user_id VARCHAR, role VARCHAR);
INSERT INTO user_roles VALUES ('u1', 'viewer'), ('u2', 'viewer'), ('u2', 'admin');
CREATE TEMP TABLE team_a AS SELECT role FROM user_roles;
CREATE TEMP TABLE team_b(role VARCHAR);
INSERT INTO team_b VALUES ('viewer'), ('viewer');
CREATE TEMP TABLE users(id VARCHAR PRIMARY KEY);
INSERT INTO users VALUES ('u1'), ('u2'), ('u3');
CREATE TEMP TABLE purchases(user_id VARCHAR);
INSERT INTO purchases VALUES ('u1'), (NULL);

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

SELECT role FROM user_roles;

上面的查询返回三行，其中 viewer 出现两次。SELECT DISTINCT role FROM user_roles 才按角色去重，得到 viewer 和 admin 两个不同值；如需稳定输出顺序，还要显式 ORDER BY。

同样：

SELECT role FROM team_a
UNION
SELECT role FROM team_b;

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

本例 UNION 得到两个不同角色，改成 UNION ALL 则保留五行。DISTINCT/UNION 在去重时也会合并相同位置的 NULL，这不意味着比较表达式 NULL = NULL 为真。

内连接 INNER JOIN 可从笛卡尔积加谓词筛选理解：

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

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

外连接还会为未匹配的一侧补空值行，因此不能用上面的筛选式完整描述 LEFT JOIN。

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
);

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

在这份数据中，NOT IN 返回零行，NOT EXISTS 返回 u2 与 u3。主表 users.id 是非空主键；若左侧 ID 也允许 NULL，必须另定业务语义，不能认定这两种写法无条件等价。

用集合代数审查权限

定义：

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 允许假阳性：报告“可能存在”，实际不存在；在只插入、不删除且实现正确的假设下，不产生假阴性。

这个 Python 3 例子只用八个位和两个便于手算的位置函数，先制造假阳性，再演示为什么不能直接清位删除：

bits = [False] * 8

def positions(value):
    return (value % 8, (value // 8 + value) % 8)

def insert(value):
    for pos in positions(value):
        bits[pos] = True

def maybe_contains(value):
    return all(bits[pos] for pos in positions(value))

insert(1)
insert(2)
print(maybe_contains(1), maybe_contains(9), maybe_contains(3))
# True True False: 9 has not been inserted.

insert(9)
for pos in positions(1):
    bits[pos] = False  # Deliberately unsafe attempt to delete 1.
print(maybe_contains(9))  # False, although 9 was inserted. Do not delete this way.

1 使用位置 (1,1)，2 使用 (2,2)，尚未插入的 9 使用 (1,2)，因此它的两位恰好都已置位。之后真正插入 9，再清除 1 的位，会破坏共享位置并漏报 9。这些位置函数刻意简单且相关，不能据此估计生产误判率。

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

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

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

“没有假阴性”只针对已完整插入的元素。若主存储新增记录后过滤器还没更新，或重建时遗漏记录，系统仍可能把真实存在的数据挡掉。更新、恢复和版本切换必须保证覆盖关系；容量、误判目标与扩容也要按实际实现配置。接口语义可参考 Redis Bloom Filter 文档，本例不依赖 Redis 服务。

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

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

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

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

完成检查

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

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

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

参考资料

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