哈希表冲突怎么解决,开放定址和链地址法区别
回答
哈希冲突指不同关键字映射到同一地址。常用解决办法分两类:开放定址法(线性探测、二次探测、双重哈希)把冲突元素放进表内别的空位;链地址法(拉链法)让每个地址挂一条链表。另有再哈希法、公共溢出区。线性探测实现简单但容易出现“聚集”;链地址法不聚集,装填因子可以大于 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 次。
依据:严蔚敏《数据结构》「查找」一章中哈希表(散列表)及处理冲突的方法。
相关官方导图:数据结构期末 · 图、查找与排序