Java教程

散列冲突(哈希碰撞)的解决办法

本文主要是介绍散列冲突(哈希碰撞)的解决办法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

散列冲突(哈希碰撞)的解决办法

    相关概念

    哈希算法(散列函数)

    哈希算法(散列算法)是信息存储和查询所用的一项基本技术,它是一种基于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²,-q2 (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、建立公共溢出区

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

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

这篇关于散列冲突(哈希碰撞)的解决办法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!