题目来源：改编自 LeetCode 705. 设计哈希集合。本 Lab 使用课程自定义输入输出协议和独立测试，不复制来源站点的代码或测试。

学习目标

• 手写一个基于链地址法的哈希集合：每个桶挂一条单链表，散列函数 $H(x)=xmodB$；
• 实现头插入、沿链查找与带前驱指针的摘链删除，保证头节点与中间节点都能正确摘除；
• 遵守集合语义：重复 add 无效果、同一值 add 两次后 remove 一次即视为删除；
• 与 Lab 09-E-05 的开放定址对照，说明装填因子、删除代价与冲突形态（链长 vs 探测链）的差异。

前置知识与环境

先阅读第 9.2 节 散列表的"链地址法"小节，并回看"装填因子"一节——链地址法允许装填因子超过 1，冲突全部表现为链表长度。

本题桶数 $B$ 被故意压得很小（3～97），平均链长可达数千：这考察的不是散列函数的均匀性，而是链表三个基本操作（插、查、删）的正确性。

在 Lab 目录执行 make doctor 检查环境；未安装 Make 时可在仓库根使用 pnpm 兜底命令（见下文"运行"）。

任务

设计一个哈希集合，支持三种操作：

• add x：把 x 加入集合；x 已存在时无任何效果；
• contains x：x 在集合中输出 1，否则输出 0；
• remove x：把 x 从集合中删除；x 不存在时无任何效果。

实现口径已钉死：链地址法。桶数组共 $B$ 个桶，每个桶是一条单链表；散列函数统一用 $H(x)=xmodB$。头插或尾插均可（输出不可见），但删除必须正确处理"被删节点是头节点"和"在链中间"两种情形。

输入格式

• 第一行：两个整数 B 和 n，分别为桶数与操作数；
• 接下来 n 行，每行一条指令，格式为 add x、contains x 或 remove x。

输出格式

对每条 contains 指令，输出一行一个整数 1 或 0。

数据范围与限制

项目	范围
桶数 B	3 ≤ B ≤ 97（故意压小，制造大量冲突）
操作数 n	1 ≤ n ≤ 2×10⁵
元素 x	0 ≤ x ≤ 10⁶
散列函数	$H(x)=xmodB$（课程统一约定）
时间复杂度要求	单次操作平均与链长成正比 $O(n/B)$；不做任何"整表扫描"式的捷径

正常、边界与错误情况

• 正常：add 后 contains 输出 1；remove 后 contains 输出 0；
• 集合语义：对同一值 add 两次，集合中只有一份，remove 一次后 contains 即为 0；
• 边界：对空集合 contains 与 remove；删除后再 add 同一值应重新可查到；x = 0 与 x = 10⁶ 两个端点值；B = 3 时几乎所有元素挤在同一条链上；
• 删除陷阱：摘除头节点时要同步更新桶的头指针，漏更新会出现"野指针"或死循环。

样例

样例 1

7 12
add 1
add 2
add 1
contains 1
contains 3
remove 2
contains 2
remove 5
add 1000000
contains 1000000
remove 1
contains 1

1
0
0
1
0

第二次 add 1 是重复插入，无效果，故 contains 1 输出 1；3 从未加入，输出 0；remove 2 后 contains 2 变为 0；remove 5 删除不存在的元素，无效果；1000000 加入后可查到；remove 1 之后 contains 1 归零。

样例 2

3 6
add 0
add 3
add 6
contains 3
remove 3
contains 3

1
0

$B=3$ 时 $0$、$3$、$6$ 的散列地址都是 $0$，三个元素串在同一条链上（装填因子为 3）。remove 3 摘掉的是链的中间节点，摘除后其余元素不受影响。

实现提示

• 节点结构：struct Node { long long key; Node* next; }，桶数组 std::vector<Node*> buckets(B, nullptr)；
• add(x)：先沿链查重（已存在直接返回），再头插新节点并更新桶头指针；
• remove(x)：沿链记录 prev，命中后 prev->next = cur->next；prev 为空说明删的是头节点，要同步把桶头指针改成 cur->next；
• 动态 new 出的节点在删除时 delete，程序结束前逐链释放（课程不强制，但写上是好习惯）；
• 想一想：为什么本题不需要 Lab 09-E-05 里的墓碑？链地址的删除只动一条链，不会截断别的元素的查找路径。

运行

make run
# 免 Make 兜底：在仓库根执行
pnpm lab:run -- labs/chapter-09/exercise/E-09-06-design-hash-set-chaining

需要单用例或严格评分时使用 make run CASE=006-stress-2e5 与 make score；也可用 pnpm lab:score -- labs/chapter-09/exercise/E-09-06-design-hash-set-chaining 兜底。

完成清单

• 样例 1、样例 2 与 make run 全部用例通过；
• 重复 add 只保留一份，add 两次 remove 一次后 contains 输出 0；
• 摘除头节点与摘除中间节点都正确，删除后再 add 同一值可重新查到；
• B = 3、上万个元素挤在 3 条链上时全部操作仍然正确；
• 压力用例（n = 2×10⁵）在时限内完成，能口述链地址与开放定址在删除上的差别。

思考与复盘

1. $B=3$、集合中有 ${10}^4$ 个元素时平均链长与装填因子各是多少？链地址法允许装填因子超过 1 的原因是什么？
2. 对照 Lab 09-E-05：为什么链地址删除不需要墓碑？如果本题改用开放定址，压小的 $B$ 会带来什么后果？
3. 头插法把新节点插在链头，最常被查到的元素却不一定在链头。若想在频繁 contains 的负载下缩短平均查找长度，可以做什么改进？代价是什么？