题目来源：改编自 LeetCode 706. 设计哈希映射。本 Lab 使用课程自定义输入输出协议和独立测试，不复制来源站点的代码或测试。
学习目标
前置知识与环境
先阅读第 9.2 节 散列表的"开放定址法（线性探测）"与"开放定址删除：空槽与墓碑不同"两小节，再快速回顾"装填因子"与"堆积如何影响性能"，理解删除为什么不能一删了之。
在 Lab 目录执行 make doctor 检查环境；未安装 Make 时可在仓库根使用 pnpm 兜底命令（见下文"运行"）。
任务
设计一个哈希映射，支持三种操作：
put k v：把键k映射到值v；若k已存在，覆盖旧值；get k：输出键k对应的值；k不存在时输出-1（键与值的取值范围保证非负，-1不会与真实数据混淆）；remove k：删除键k；k不存在时无任何效果。
实现口径已钉死：开放定址 + 线性探测 + 墓碑删除。每个槽记录 {state, key, value}，state ∈ {EMPTY, USED, TOMBSTONE}；散列函数
删除的语义必须用墓碑标记：把被删槽标记为 TOMBSTONE，而不是清回 EMPTY。直接清空会截断探测链——在它之后落入的同义词从此查不到（见样例 2）。墓碑槽允许被后续 put 复用：探测时墓碑"看起来不存在"，落位时优先占用它，探测链保持完整。
数据保证全程不同键的个数 ≤ C−1：表里永远至少留一个空槽，探测不会绕表一整圈仍然找不到落脚点。
输入格式
- 第一行：两个整数
C和n，分别为桶数组容量与操作数； - 接下来
n行，每行一条指令，格式为put k v、get k或remove k。
输出格式
对每条 get 指令，输出一行一个整数：键存在时为其当前值，不存在时为 -1。
数据范围与限制
| 项目 | 范围 |
|---|---|
桶数组容量 C | 8 ≤ C ≤ 10⁴（不要求质数） |
操作数 n | 1 ≤ n ≤ 2×10⁵ |
键 k、值 v | 0 ≤ k, v ≤ 10⁶ |
| 不同键个数 | 全程 ≤ C−1（表内至少留一个空槽） |
| 时间复杂度要求 | 单次操作平均 |
| 输出上限 | 8 MB（get 行数最多 2×10⁵，判题器放宽了默认 1 MB 输出上限） |
正常、边界与错误情况
- 正常：
put覆盖已有键；get命中输出当前值；remove后get输出-1； - 边界：对空表
get；get/remove不存在的键；删除后重新put同散列地址的新键；表接近满（不同键数 = C−1）时所有操作仍正确； - 错误陷阱：删除聚集区中间的键后，必须仍能
get到落在它后面的同义词——把槽清回EMPTY的写法在这里直接出错；墓碑只对"查找"透明，put落位时可以且应该复用它。
样例
样例 1
16 11
put 1 10
put 2 20
put 2 99
get 1
get 2
get 3
remove 2
get 2
put 3 30
get 3
get 210
99
-1
-1
30
-1put 2 20 后再次 put 2 99 覆盖旧值，故 get 2 输出 99；remove 2 之后两次 get 2 都是 -1；get 3 在覆盖前查不到，put 3 30 之后输出 30。
样例 2
10 9
put 0 5
put 10 6
put 20 7
get 20
remove 0
get 20
get 10
remove 0
get 07
7
6
-10、10、20 散列地址都是 0，依次落进槽 0、1、2。remove 0 把槽 0 标成墓碑；此后 get 20 与 get 10 都要跳过墓碑继续探测才能找到答案（输出 7、6）。如果把槽 0 直接清回 EMPTY，get 20 会在槽 0 提前终止，错答 -1。最后的 remove 0 操作的对象已不存在，无效果，get 0 输出 -1。
实现提示
- 槽结构：
struct Slot { State state; long long key, value; }，State取EMPTY / USED / TOMBSTONE，初始全部EMPTY； get(k)：从USED且键相等即命中；TOMBSTONE跳过继续；EMPTY立即判定不存在；put(k, v)：探测途中记录首个墓碑槽下标；遇到同键USED槽就覆盖返回；遇到EMPTY说明键不存在，落位时优先复用记录的墓碑槽，没有墓碑才占用这个空槽；remove(k)：按get的方式定位，命中后把state改成TOMBSTONE即可，key/value无需清理；- 不要在
put里遇到第一个空槽就插入而不管墓碑——那样会让墓碑后面的探测链分叉吗？想清楚"查找跨墓碑、落位用墓碑"两件事的差别。
运行
make run
# 免 Make 兜底：在仓库根执行
pnpm lab:run -- labs/chapter-09/exercise/E-09-05-design-hash-map-probing需要单用例或严格评分时使用 make run CASE=006-stress-2e5 与 make score；也可用 pnpm lab:score -- labs/chapter-09/exercise/E-09-05-design-hash-map-probing 兜底。
完成清单
思考与复盘
- 样例 2 中如果把槽 0 清回
EMPTY，哪些get会出错？反过来，什么情况下"清空"又是安全的？（提示：确认它后面没有同义词时） - 当装填因子逼近 1 时，一次
get平均要走多少步？"不同键数 ≤ C−1"这条保证防住了哪一种最坏情况，又没防住哪一种？ - 墓碑会越积越多吗？如果允许
put复用墓碑槽，墓碑数量在什么操作模式下增长、什么模式下回落？