首页  思维导图  详情



 



解决Hash冲突的方法

2015-10-26 17:11:12   0  举报





仅支持查看

解决Hash冲突的方法

Hash冲突

模板推荐

作者其他创作

大纲/内容

当Hash函数对两个不同的数据产生了相同的Hash值时，冲突就产生了

为了提高Hash表查找性能，出了寻找合适的Hash表表长和完美的hash函数外，还必须考虑Hash表处理冲突的能力

处理方法

线性再散列法

简单的按顺序遍历Hash表，寻找下一个可用的槽

会产生拥挤区域

缺点

不能从表中删除元素（懒惰删除方法）

表被填满时性能下降明显

非线性再散列法

计算一个新的Hash值，跳转到表中不同部分（避免聚集现象）

缺点

不能从表中删除元素

当负载因子增大时，再散列所花费的时间也增加

再散列法适用

表负载较低

不太可能执行删除操作

外部拉链法

将Hash表中的每个槽当成具有相同hash值饿数据项所组成链表的头部，hash表将发生冲突的项添加到同一个链表中

查找时间：链表查找时间+1

原则

Hash表的大小和预料的个数差不多

定义

将Hash表看成一个链表数组，每个槽要么为空，要么指向Hash到该槽的表项的链表，通过把元素添加到链表中解决冲突，可以执行删除操作，不需要再散列。

缺点

时间和空间稍微多一点

 Collect

Get Started

聚类方法

 Collect

Get Started

PYRAMID-Oracle实施方法

 Collect

Get Started

hash

 Collect

Get Started

hash-overflow-cacheline





0 条评论

下一页