什么是哈希冲突?常见的冲突解决方法有哪些?

核心考点

散列表基本思想、冲突产生原因及常用冲突处理策略，重点掌握开放定址法与链地址法的区别。

参考答案(答题要点)

1.哈希冲突：哈希函数将关键字映射到散列表地址时，不同关键字映射到同一地址的现象。冲突不可避免，只能尽量减少并处理。

2.开放定址法：冲突时按某种探测序列寻找下一个空闲单元。常见有线性探测法、平方探测法、双散列法。线性探测法依次向后找空位，易产生堆积;平方探测法按1^2、-1^2、2^2、-2^2……探测，可减少堆积;双散列法用第二个散列函数确定探测步长。

3.链地址法(拉链法)：同一地址的关键字组织成链表，冲突元素挂到对应链表上。删除方便，适合冲突较多的情况。

4.再散列法：发生冲突时再用另一个散列函数计算新地址，直到不冲突。

5.建立公共溢出区：基本表外另设溢出区，冲突元素统一放入溢出区。

6.总结：开放定址法数据存放在表内，易堆积且删除需标记;链地址法额外设链，插入删除灵活。装填因子越大，冲突概率越高。

易错提醒

哈希冲突不是哈希函数写错了，而是映射多对一导致的正常现象。开放定址法删除元素不能直接置空，否则会截断探测链，通常设删除标记。链地址法平均查找长度与装填因子有关，但不要求装填因子小于1。

今日小测

开放定址法删除元素时，为什么不能直接把该单元置为空?

答案：直接置空会截断后续元素的探测链，导致原本可查找到的元素查找失败，通常应设置删除标记。