哈希冲突和解决办法

哈希冲突

           哈希是对数据压缩，提高效率的一种方法。 

            但通过哈希函数产生的哈希值是有限的，而数据可能比较多，导致哈希处理后仍然有不同数据产生相同的值，这就是哈希冲突

填充因子

         也就是数组的长度，对装填因子进行取模

装载因子（也就是链表长度）

解决哈希冲突的方法

1.开放地址法

    （1）线性探测
         按顺序往后探测，如果某数据值存在，就在当前位置向后加一，直至不发生冲突

    （2）再平方探测

　　　按顺序决定值时，如果某数据的值已经存在，则在原来值的基础上先加1的平方个单位，若仍然存在则减1的平方个单位。随之是2的平方，3的平方等等。直至不发生哈希冲突。

   （3）伪随机探测

    按顺序探测时，如果值存在，那么通过随机函数生成一个数，在原来基础上加上随机值，直至不发生冲突

2.链地址法

   对于相同的值，通过链表将其连接

优点：

   （1）拉链法处理冲突简单，且无堆积现象，即非同义词绝不会冲突，因此平均查找长度较短；

   （2）由于拉链法中各链表上的节点空间是动态申请的，故它更适合于造表前无法确定表长的情况

   （3）开放地址法为减少冲突，要求装填因子（也就是取模的那个数）要小，故当节点规模较大时会浪费空间。

    （4）用拉链法构造的散列表中，删除节点的操作易于实现。只要删除链表上相应的节点即可

缺点：

   指针会占用较大空间，造成空间浪费，若空间用于增大散列表规模进而提高开放地址法的效率

3.建立公共溢出区

     公共溢出区存储 出现冲突的数据

4.再哈希法

  对于冲突的哈希值再次进行哈希处理，直至没有哈希冲突

缺点：每次冲突都要重新哈希，计算时间增加。