散列冲突（哈希碰撞）的解决办法

散列冲突（哈希碰撞）的解决办法

    相关概念

    哈希算法（散列函数）

    哈希算法(散列算法)是信息存储和查询所用的一项基本技术，它是一种基于Hash函数的文件构造方法，可实现对记录的快速随机存取。它把给定的任意长关键字映射为一个固定长度的哈希值，一般用于鉴权、认证、加密、索引等。其主要优点是运算简单，预处理时间较短，内存消耗低，匹配查找速度比较快，便于维护和刷新，支持匹配规则数多等。

    什么是哈希碰撞（散列冲突）

    Hash算法并不完美，有可能两个不同的原始值在经过哈希运算后得到同样的结果， 这样就是哈希碰撞。

    解决办法

    1、开放定址法

    所谓的开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。

    fi(key)=（f（key）+di）MOD m (di=1，2，3,…，m-1)

    1）线性探测法

    di=1，2，3，…，m-1

   这种方法的特点是：冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。

   我们把这种解决冲突的开放地址法称为线性探测法。

    2）二次探测法

    fi(key)=（f（key）+di）MOD m (di=1²，-1²，2²，-2²，…，q²，-q² (q<=m/2 )

    这种方法的特点是：冲突发生时，在表的左右进行跳跃式探测，比较灵活。

    增加平方运算的目的是为了不让关键字都聚集在某一块区域。我们称这种方法为二次探测法。

    3）随机探测法

   还有一种方法是，在冲突时，对于位移量di采用随机函数计算得到，我们称之为随机探测法。

   fi(key)=（f（key）+di）MOD m (di是一个随机数列 )

   总之，开放定址法只要在散列表未填满时，总是能找到不发生冲突的地址，是我们常用的解决冲突的办法。

    2、再散列函数法

    事先准备多个散列函数:

    fi(key)=RHi（key）( i=1，2，…，k)

    当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。

    3、链地址法（拉链法）

    思路还可以再换一换，为什么有冲突就非要换地方呢，我们直接就在原地处理行不行呢？于是我们就有了链地址法。

    将所有关键字为同义词的记录存储在一个单链表中，我们称这种表为同义词子表，在散列表中只存储所有同义词子表的头指针。

    对于关键字集合{12,67,56,16,25,37, 22,29,15,47,48,34}，我们用前面同样的12为除数，进行除留余数法：

     

   此时，已经不存在什么冲突换址的问题，无论有多少个冲突，都只是在当前位置给单链表增加结点的问题。

   拉链法解决冲突的做法是：将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数组T[0..m-1]。凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。在拉链法中，装填因子α可以大于 1，但一般均取α≤1。

   链地址法对于可能会造成很多冲突的散列函数来说，提供了绝不会出现找不到地址的保障，当然，这也就带来了查找时需要遍历单链表的性能损耗。

   4、建立公共溢出区

    这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

    在查找时，对给定值通过散列函数计算出散列地址后，先与基本表的相应位置进行对比，如果相等，则查找成功；如果不相等，则到溢出表去进行顺序查找。如果相对于基本表而言，有冲突的数据很少的情况下，公共溢出区的结构对查找性能来说还是非常高的。