目标
实现一个散列索引引擎，让链地址、线性探测、平方探测三种冲突策略共享同一套键值接口，并用探测次数观察冲突与堆积。本 Lab 是散列与索引这一章的收口工程，要求你把散列函数、冲突处理、删除墓碑、不变量检查和探测统计整合进同一个系统。
前置知识
- 第 8.5 节散列表的散列函数、链地址法、开放定址法、删除标记与装填因子；
- 第 8.4 节 B 树与 B+ 树的索引思想（用于理解"散列索引"与"有序索引"的分工）；
- 第 0 章时间复杂度与均摊分析；基本的 C++ 类、
std::vector与std::optional。
建议用时
300～420 分钟（5～7 小时），建议分 2～3 次提交：先做链地址，再做开放定址与墓碑，最后做探测统计与对比。
任务与评分
| Task | 类型 | 权重 | 依赖 | 交付物 |
|---|---|---|---|---|
index | stdio | 30 | 无 | 散列索引命令行驱动 |
engine | CTest | 50 | index | contracts/hash_index.hpp 的实现 |
report | manual | 20 | engine | ASL 对比、墓碑语义与复杂度报告 |
顶层评分会分别显示自动分和待人工分。任务依赖用于推荐顺序和定位，不会暗中把前置任务变成"一票否决"。
运行与评分
进入本目录后优先使用：
powershell
make doctor
make run
make run TASK=index CASE=001-chaining
make run TASK=engine
make scoreWindows 未安装 GNU Make 时，在仓库根使用免 Make 兜底：
powershell
pnpm lab:run -- labs/chapter-09/project/P-09-01-hash-index-engine
pnpm lab:run -- labs/chapter-09/project/P-09-01-hash-index-engine --task index --case 001-chaining
pnpm lab:score -- labs/chapter-09/project/P-09-01-hash-index-engine维护者可用 --target solution 验证参考实现自动部分满分。Project 使用 CMake ≥ 3.25 与 CTest；CMake 可选择当前平台的可用生成器，Ninja 只是可选加速项。所有构建产物只写入 .lab-cache/。
任务一：散列索引命令行
第一行读取模式与表长 m，随后逐行处理指令。散列函数固定为 h(k) = k mod m，键为非负整数。
| 指令 | 含义 | 输出 |
|---|---|---|
put k v | 写入键值（重复键覆盖值） | 无 |
get k | 取值 | 命中输出值，未命中输出 null |
erase k | 删除 | 成功 1，未找到 0 |
contains k | 判断是否存在 | 1 / 0 |
probes k | 查找比较/探测次数 | 整数（见任务二约定） |
size | 现存键数 | 整数 |
loadfactor | 装填因子 | 两位小数 |
任务二：散列索引引擎
实现 contracts/hash_index.hpp 中的 make_chaining 与 make_open_addressing。
| 策略 | 探测序列 |
|---|---|
| 链地址 | 每个槽一条链，同义词入同一链 |
| 线性探测 | (h + i) mod m，i = 0, 1, 2, … |
| 平方探测 | (h + i²) mod m，i = 0, 1, 2, … |
probes 约定：链地址返回被检查的链表结点个数（命中为链内位置，未命中为链长）；开放定址返回从 h(k) 起被检查的槽数，遇墓碑继续、遇空槽或命中停止。
删除墓碑：开放定址删除写墓碑标记而非清空，查找遇墓碑继续后移，遇从未使用的空槽才停止。要能解释为什么"墓碑不阻断查找、但可被插入复用"。
测试输入
- 链地址插入
1, 8, 15（同余），验证链长与probes位置； - 线性探测插入
1, 8, 15，观察聚集导致的探测次数递增； - 平方探测插入
1, 8, 15, 22，验证跳跃式探测； - 删除中间键后仍能查到其后键（墓碑语义）。
提交物
- 可运行代码；
make run TASK=index与make run TASK=engine的输出；- 设计说明（500～800 字），覆盖"复杂度分析要求"的 4 个问题；
- 报告模板
report/template.md的填写。
验收标准
复杂度分析要求
在说明文档里回答：
- 链地址与线性探测的成功/失败 ASL 随装填因子 α 如何变化？给出理论公式。
- 平方探测相比线性探测为什么更能抑制"堆积"？它又有什么覆盖不到的隐患？
- 表长取素数为什么通常优于取 2 的幂？给出一个具体的同余反例。
- 散列索引擅长"等值查询"却不擅长"范围查询"，B+ 树正好相反——数据库索引为什么常同时使用两者？
加分项
- 实现再散列（扩容），装填因子超阈值时搬到下一个更大的素数，并用均摊分析说明平均
O(1)； - 用加权和散列支持字符串键，重复实验对比整数键的分布质量；
- 把探测序列画成图，直观展示线性探测的堆积与平方探测的跳跃。
延伸思考
- 墓碑堆积过多会让失败查找变慢，工程上通常如何触发"整理/重建"？
- 如果键不是均匀分布的（如学号、身份证号），散列函数要怎样设计才能避免全挤进少数槽？
- 开放定址法在表满时
put会怎样？你的实现里表满的行为是什么？