解决Hash冲突的方法
2015-10-26 17:11:12 0 举报AI智能生成
解决Hash冲突的方法
作者其他创作
大纲/内容
当Hash函数对两个不同的数据产生了相同的Hash值时，冲突就产生了
为了提高Hash表查找性能，出了寻找合适的Hash表表长和完美的hash函数外，还必须考虑Hash表处理冲突的能力
处理方法
线性再散列法
简单的按顺序遍历Hash表，寻找下一个可用的槽
会产生拥挤区域
缺点
不能从表中删除元素（懒惰删除方法）
表被填满时性能下降明显
非线性再散列法
计算一个新的Hash值，跳转到表中不同部分（避免聚集现象）
缺点
不能从表中删除元素
当负载因子增大时，再散列所花费的时间也增加
再散列法适用
表负载较低
不太可能执行删除操作
外部拉链法
将Hash表中的每个槽当成具有相同hash值饿数据项所组成链表的头部，hash表将发生冲突的项添加到同一个链表中
查找时间：链表查找时间+1
原则
Hash表的大小和预料的个数差不多
定义
将Hash表看成一个链表数组，每个槽要么为空，要么指向Hash到该槽的表项的链表，通过把元素添加到链表中解决冲突，可以执行删除操作，不需要再散列。
缺点
时间和空间稍微多一点
0 条评论
下一页
