01

60 秒回答模板

开放地址法发生哈希冲突时，不再挂链表，而是在表内继续探测其他槽位。伪随机探测会根据 key 的哈希值和固定随机序列生成 h(key, 0), h(key, 1)...。插入时按序列找第一个空槽或可复用删除槽；查找时必须按同样序列查，直到找到目标 key，遇到从未使用过的空槽才可判定不存在。删除通常用 tombstone 标记，不能直接清空，否则会截断后续查找链。负载因子过高时探测变长，需要扩容。

考点 同一序列
难度 真实面经题
回答目标 讲清方法、边界和追问
02

深入解析

01

先说明开放地址法

开放地址法把所有元素都放在哈希表数组里。冲突后不使用外部链表，而是按某种探测规则寻找另一个槽位，因此表的空位分布和负载因子会直接影响查询成本。

02

伪随机探测序列

伪随机开放地址法不是每次真正随机，而是为同一个 key 生成可复现的探测序列。插入和查找必须走完全一致的序列，否则已经写入表中的元素会沿另一条路径被跳过。

03

插入流程

先计算初始哈希槽，如果被其他 key 占用，就依次尝试伪随机序列中的下一个槽位，直到遇到空槽或可复用的删除标记。插入成功后，key、value 和槽位状态要一起写入。

04

查找流程

查找时也按同样序列探测。找到相同 key 就返回；遇到 tombstone 不能停止；只有遇到从未占用过的空槽，才说明目标不存在。

05

删除和扩容

删除一般放 tombstone，避免破坏查找路径。随着负载因子升高，探测次数增加，需要扩容并重新哈希，保持查询性能，同时清理过多删除标记。

03

易错点

  • 不要把伪随机理解成查找时重新随机，那样无法复现插入路径。
  • 不要删除时直接清空槽位，应使用删除标记或重排探测链。
  • 不要忽略负载因子，开放地址法在高负载下性能会快速下降。
04

面试官追问

开放地址法和链地址法有什么区别？

开放地址法冲突后仍在数组内探测，链地址法在桶后挂链表或其他结构；前者缓存友好但对负载因子更敏感。

删除为什么不能直接置空？

直接置空会让查找在该槽位提前停止，导致后面通过冲突探测插入的元素无法被找到。

伪随机探测有什么风险？

如果探测序列覆盖不好或负载因子过高，仍可能聚集和退化，需要设计序列并控制扩容。