hash碰撞的解决办法

2019-03-26 本文已影响0人 whupenger

hash : 翻译为“散列”，就是把任意长度的输入，通过散列算法，变成固定长度的输出，该输出就是散列值。

开放地址法

当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。这种方法有一个通用的再散列函数形式：
$H_i=p_i \ mod \ m (i=1，2，…，n)$
其中 $p_i = H(Key)+d_i$

其中 $H(key)$ 为哈希函数， $m$ 为表长， $d_i$ 称为增量序列。增量序列的取值方式不同，相应的再散列方式也不同。主要有以下三种：

线性探测法：冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表
$d_i = 1,2,3,...,n$
二次探测法：冲突发生时，在表的左右进行跳跃式探测，比较灵活。
$d_i = 1^2 ，－ 1^2 ， 2^2 ，－ 2^2 ，....， k^2， -k^2$
伪随机探测：应建立一个伪随机数发生器，（如 $i=(i+p) \% m）$ ，并给定一个随机数做起点。
$d_i = 伪随机序列$

对于利用开放地址法处理冲突所产生的哈希表中删除一个元素时需要谨慎，不能直接地删除，因为这样将会截断其他具有相同哈希地址的元素的查找地址，所以，通常采用设定一个特殊的标志以示该元素已被删除。

再哈希法

这种方法是同时构造多个不同的哈希函数：
$H_i=RH_i(key), i=1，2，…，k$
当哈希地址 $Hi=RH_1（key）$ 发生冲突时，再计算 $H_i=RH_2（key）$ ……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。

链地址法(拉链法)

为每个 Hash 值建立一个单链表，当发生冲突时，将记录插入到链表中

建立公共溢出区

将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表

拉链法的优缺点：

优点：

① 拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
② 由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
③ 开放地址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
④ 在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。

缺点：

指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。