哈希表冲突怎么解决,开放定址和链地址法区别

作者:SeekFlaw 求瑕 内容组 · 发布于 2026-11-19 · 更新于 2026-11-19

回答

哈希冲突指不同关键字映射到同一地址。常用解决办法分两类:开放定址法(线性探测、二次探测、双重哈希)把冲突元素放进表内别的空位;链地址法(拉链法)让每个地址挂一条链表。另有再哈希法、公共溢出区。线性探测实现简单但容易出现“聚集”;链地址法不聚集,装填因子可以大于 1,删除也方便。开放定址删除元素时不能直接置空,要打“已删除”标记,否则会截断其后元素的探测路径。装填因子 α = 元素数 / 表长,α 越大冲突越多、查找越慢。

例:表长 7,h(k) = k mod 7,线性探测,依次插入 15、22、29、8(已用程序核对):

  • 15 映射到地址 1,直接放入;22 也映射到 1,冲突,探测到 2 放入;
  • 29 映射到 1,探测 2、3,放入 3;8 映射到 1,探测 2、3、4,放入 4。
  • 结果表为 [空, 15, 22, 29, 8, 空, 空],查找 8 需比较 4 次。

依据:严蔚敏《数据结构》「查找」一章中哈希表(散列表)及处理冲突的方法。

用这个问题生成复习导图 打开官方导图,复制到我的空间

相关官方导图:数据结构期末 · 图、查找与排序

标签:数据结构哈希表冲突处理开放定址链地址法