线性探测法因聚集导致检索延迟，需监控装载因子、选用优质散列函数、删除后标记伪空；α≥0.75应扩容，聚集严重时换二次探测或拉链法。

线性探测法本身不叫“线性补偿探测”，“补偿”不是标准术语——这里实际指用线性探测解决冲突时，因聚集（clustering）引发的检索延迟问题。核心不在“补偿”，而在**识别聚集、控制负载、调整策略**，从而把平均查找长度（ASL）维持在合理水平。

什么是聚集？它为什么拖慢检索

聚集是线性探测最典型的副作用：一旦某几个键映射到相近位置，后续冲突项会不断向后“挤占”相邻槽位，形成一段连续被占的区域。查找时哪怕目标键本该落在开头，也可能要遍历整个簇才能确认存在与否或定位失败。

比如散列表长13，插入序列{29, 7, 84}，散列函数h(key) = key % 13：

• 29 → h=3，填入位置3
• 7 → h=7，填入位置7
• 84 → h=7，冲突 → 探测8 → 占用8

此时若再插入11（h=11），没问题；但若插入20（h=7），就得一路探到9、10、11……直到空位。查找20也要走同样长路径——这就是一次由聚集放大的延迟。

实战中控制聚集的三个关键动作

• 监控装载因子α：α = 已存元素数 / 表长。α超过0.7后，聚集增长明显加快。建议α ≥ 0.75时触发扩容（如扩大为原大小的1.5–2倍，并重哈希）
• 选用优质散列函数：优先用除留余数法 + 素数模数（如表长取1009而非1000），避免因模数与数据分布共振加剧同义词冲突
• 删除操作后做标记，不直接清空：若简单置空被删位置，会截断后续探测链，导致“本该存在却查不到”。应设为DELETED伪空状态，插入时可复用，查找时仍需跳过继续探

什么时候该换方法？线性探测的适用边界

线性探测适合内存紧凑、读多写少、且能接受一定ASL波动的场景（如嵌入式缓存、编译器符号表）。但它不适合：

• 动态增删频繁、α长期 > 0.8 的系统
• 对最坏查找延迟敏感的应用（如实时风控判定）
• 键分布高度偏斜（如大量key以同一数字结尾）

此时建议切换为二次探测（步长为1², 2², 3²…，减少线性堆积）或拉链法（每个槽挂链表，聚集影响仅限局部）。

快速验证你是否受聚集影响

运行一次简单诊断：

• 统计当前所有元素的“探测长度”（即插入时尝试了多少次才找到空位）
• 计算平均值，若明显高于1.5（例如>2.2），且最长探测长度 ≥ 8，基本可判定聚集已显著影响性能
• 可视化散列表填充图：用字符‘X’表示占用，‘.’表示空，一眼可见大片连续X区

不复杂但容易忽略。