哈希表：线性探测
线性探测是开放寻址的一种：键直接保存在同一个数组里，冲突时逐格向后找空位，到末尾后回绕。哈希分布良好且有效占用率较低时，插入、查询、删除平均为 O(1)；表越满，聚集造成的探测成本越高。
把数组看成停车场，h(k) = k mod capacity 是指定车位。被占用后就向后寻找，下标到末尾再从 0 开始。
线性探测如何工作
每格有三种状态：空，从未使用；占用，保存键；墓碑，曾保存键但已删除。墓碑可复用，却不能终止搜索，因为同一探测序列的键可能还在后面。
三种操作都从 i = hash(k) 开始，按 i = (i + 1) mod capacity 推进，最多一圈。
get(k) 遇到相同键就返回索引；遇到真正空格就返回未找到；墓碑或不同键都继续。空格表示此前不存在跨过它插入的目标，删除不能伪造这项信息。
delete(k) 用相同搜索流程，命中后写墓碑。键已移除，但后续查询仍会越过它。
insert(k) 记住首个可复用位置 spot，通常是墓碑，否则是终止搜索的空格。遇到第一个墓碑不能立即写入，必须继续查重。找到相同键则不改状态；遇到空格或完成一圈仍无重复，才写到记住的位置。如果一圈中没有匹配键，也没有空格或墓碑，才抛出满表异常。固定数组就是全部存储，因此这是真实容量限制。
显示容量 5–11、键范围 1–99 则只是画布限制；满表处理适用于任意容量的固定开放寻址表。
逐步演示
默认容量 7，h(k) = k mod 7。每次先计算哈希，再逐格探测，最后提交变化。
insert(10)：10 mod 7 = 3，槽 3 为空，写入 10。insert(20)：h(20) = 6，槽 6 为空，写入 20。insert(17)：h(17) = 3，槽 3 是 10，继续到空槽 4，写入 17。insert(24)：h(24) = 3，越过槽 3 的 10、槽 4 的 17，在槽 5 写入 24。槽 3–5 形成连续聚集区。get(17)：从槽 3 开始，两次探测在索引 4 找到。delete(10)：槽 3 命中，将其设为墓碑，不是空格。- 再
get(17)：越过槽 3 的墓碑，在 4 找到。如果上一步清空槽 3，这里会提前停止并错报未找到。 insert(31)：31 mod 7 = 3。记住槽 3 的墓碑，再检查槽 4 的 17、槽 5 的 24、槽 6 的 20，回绕到空槽 0。确认无重复后，把 31 写到记住的槽 3，回收墓碑。
画布游标从哈希位置逐格推进，被检查格高亮。墓碑使用单独的淡色标记，区分可复用位置与可终止搜索的空位。
时间与空间复杂度
设 n 为有效键数，m 为容量。
| 操作 | 平均，低占用且分布良好 | 最坏 |
|---|---|---|
insert | O(1) | O(m)，最多一圈 |
get | O(1) | O(m)，最多一圈 |
delete | O(1) | O(m)，最多一圈 |
当 m 与 n 同阶时，常把最坏界写作 O(n)。墓碑较多时，要按容量计数，不能只看存活键数。空间为 O(m)，数组之外不需要逐条目的链接指针。
负载因子为 α = n / m。占用比例趋近 1 时，探测变长。成功和失败查询的期望成本不同，线性探测还存在主聚集，不能用一个 1 / (1 − α) 估计同时概括两者。
占用格连成区段，映射到区段内的新键要向后找位置，插入又把区段延长，大区段因此更容易继续增长。默认槽 3–5 就是例子。工程实现常在约 0.7–0.75 一类阈值附近扩容并重哈希，但阈值取决于探测方案和性能目标，不是通用常数。墓碑也应计入需要清理的占用。
边界情况
- 重复插入：探测命中后不写入，不覆盖，也不新增副本。
- 满表：一圈无空位、墓碑或匹配键，抛出上溢；可扩容实现通常提前扩容。
- 键不存在：遇到首个空格就停；没有空格时，m 次探测的一圈上限仍保证结束。
- 墓碑积累：频繁插删可能让有效键很少，但查询仍需穿过大量墓碑。重哈希只搬有效键，可同时清理墓碑。
常见错误
- 删除时清空。 会让查询在虚假的缺口终止，使后面的键不可达。
- 遇到首个墓碑就插入。 后方可能已有相同键。先记位置，完成查重，再写入。
- 忘记回绕。 使用
i = (i + 1) mod capacity，否则接近末尾的探测会越界。 - 插入不复用墓碑。 查询要越过墓碑，但插入应回收它；把墓碑永久当占用会泄漏位置。
- 从不扩容或清理。 高占用让聚集区合并，墓碑也拉长路径。监控占用并重哈希是保持预期性能的一部分。