`

散列算法,冲突解决方法分析

阅读更多
哈希法又称散列法、杂凑法以及关键字地址计算法等,相应的表称为哈希表。这种方法的基本思想是:首先在元素的关键字k和元素的存储位置p之间建立一个对应关系f,使得p=f(k),f称为哈希函数。创建哈希表时,把关键字为k的元素直接存入地址为f(k)的单元;以后当查找关键字为k的元素时,再利用哈希函数计算出该元素的存储位置p=f(k),从而达到按关键字直接存取元素的目的。
   当关键字集合很大时,关键字值不同的元素可能会映象到哈希表的同一地址上,即 k1≠k2 ,但 H(k1)=H(k2),这种现象称为冲突,此时称k1和k2为同义词。实际中,冲突是不可避免的,只能通过改进哈希函数的性能来减少冲突。
综上所述,哈希法主要包括以下两方面的内容:
 1)如何构造哈希函数
 2)如何处理冲突。

一、如何构造哈希函数
构造哈希函数的原则是:①函数本身便于计算;②计算出来的地址分布均匀,即对任一关键字k,f(k) 对应不同地址的概率相等,目的是尽可能减少冲突。
下面介绍构造哈希函数常用的五种方法。
1、数字分析法  
   如果事先知道关键字集合,并且每个关键字的位数比哈希表的地址码位数多时,可以从关键字中选出分布较均匀的若干位,构成哈希地址。例如,有80个记录,关键字为8位十进制整数d1d2d3…d7d8,如哈希表长取100,则哈希表的地址空间为:00~99。假设经过分析,各关键字中 d4和d7的取值分布较均匀,则哈希函数为:h(key)=h(d1d2d3…d7d8)=d4d7。例如,h(81346532)=43,h(81301367)=06。相反,假设经过分析,各关键字中 d1和d8的取值分布极不均匀, d1 都等于5,d8 都等于2,此时,如果哈希函数为:h(key)=h(d1d2d3…d7d8)=d1d8,则所有关键字的地址码都是52,显然不可取。
2、平方取中法
   但无法确定关键字中哪几位分布均匀时,可以先求出关键字的平方值,然后按需要取平方值的中间几位做为哈希地址,这是因为:平方后中间几位和关键字中每一位都相关,故不同关键字会以较高的概率产生不同的哈希地址。
   例:我们把英文字母在字母表中的位置序号作为该英文字母的内部编码。例如K的内部编码为11,E的内部编码为05,Y的内部编码为25,A的内部编码为01, B的内部编码为02。由此组成关键字“KEYA”的内部代码为11052501,同理我们可以得到关键字“KYAB”、“AKEY”、“BKEY”的内部编码。之后对关键字进行平方运算后,取出第7到第9位作为该关键字哈希地址,如图8.23所示。
 
 
关键字
关键字内部编码内部编码的平方值H(k)关键字的哈希地址
KEYA11052501122157778355001778
KYAB11250102126564795010404795
AKEY01110525001233265775625265
BKEY02110525004454315775625315

图8.23平方取中法求得的哈希地址

3.分段叠加法
 这种方法是按哈希表地址位数将关键字分成位数相等的几部分(最后一部分可以较短),然后将这几部分相加,舍弃最高进位后的结果就是该关键字的哈希地址。具体方法有折叠法与移位法。移位法是将分割后的每部分低位对齐相加,折叠法是从一端向另一端沿分割界来回折叠(奇数段为正序,偶数段为倒序),然后将各段相加。例如:key=12360324711202065,哈希表长度为1000,则应把关键字分成3位一段,在此舍去最低的两位65,分别进行移位叠加和折叠叠加,求得哈希地址为105和907,如图8.24所示。

   1   2   3                    1   2   3
   6   0   3                    3   0   6
   2   4   7                    2   4   7
   1   1   2                    2   1   1
+)0   2   0                   +) 0   2   0
————————                     —————————
1 1   0   5                    9   0   7
 
(a)移位叠加                    (b) 折叠叠加
 
            图8.24 由叠加法求哈希地址

4. 除留余数法
假设哈希表长为m,p为小于等于m的最大素数,则哈希函数为
h(k)=k  %  p ,其中%为模p取余运算。
例如,已知待散列元素为(18,75,60,43,54,90,46),表长m=10,p=7,则有
    h(18)=18 % 7=4    h(75)=75 % 7=5    h(60)=60 % 7=4   
    h(43)=43 % 7=1    h(54)=54 % 7=5    h(90)=90 % 7=6   
    h(46)=46 % 7=4
此时冲突较多。为减少冲突,可取较大的m值和p值,如m=p=13,结果如下:
    h(18)=18 % 13=5    h(75)=75 % 13=10    h(60)=60 % 13=8    
    h(43)=43 % 13=4    h(54)=54 % 13=2    h(90)=90 % 13=12   
    h(46)=46 % 13=7
此时没有冲突。

采用一个伪随机函数做哈希函数,即h(key)=random(key)。
在实际应用中,应根据具体情况,灵活采用不同的方法,并用实际数据测试它的性能,以便做出正确判定。通常应考虑以下五个因素 :
  • 计算哈希函数所需时间(简单)。
  • 关键字的长度。
  • 哈希表大小。
  • 关键字分布情况。
  • 记录查找频率。
        

二、处理冲突的方法

1、开放定址法
   这种方法也称再散列法,其基本思想是:当关键字key的hash地址p=H(key)出现冲突时,以p为基础,产生另一个hash地址p1,如果p1依然冲突,那么以p1为基础,在产生一个hash地址p2,...,直到找出一个不冲突的hash地址pi,将相应元素存入其中。该方法的通用再散列函数式为:Hi=(H(key)+di)%m  0<i<m.其中H(key)是hash函数,m是表长,di是增量序列。根据增量序列的取值方式不同,相应的散列方式也不同。主要有一下三种:
●线性探测再散列
    di=1,2,3,…,m-1
这种方法的特点是:冲突发生时,顺序查看表中下一单元,直到找出一个空单元或查遍全表。
用线性探测法处理冲突,思路清晰,算法简单,但存在下列缺点:
① 处理溢出需另编程序。一般可另外设立一个溢出表,专门用来存放上述哈希表中放不下的记录。此溢出表最简单的结构是顺序表,查找方法可用顺序查找。
② 线性探测法很容易产生堆聚现象。所谓堆聚现象,就是存入哈希表的记录在表中连成一片。按照线性探测法处理冲突,如果生成哈希地址的连续序列愈长 ( 即不同关键字值的哈希地址相邻在一起愈长 ) ,则当新的记录加入该表时,与这个序列发生冲突的可能性愈大。因此,哈希地址的较长连续序列比较短连续序列生长得快,这就意味着,一旦出现堆聚 ( 伴随着冲突 ) ,就将引起进一步的堆聚。
●二次探测再散列
    di=1^2,-1^2,2^2,-2^2,…,k^2,-k^2    ( k<=m/2 ) 
 这种方法的特点是:冲突发生时,在表的左右进行跳跃式探测,比较灵活。
  例子:
  通过某一个散列函数对key的关键码进行计算,得到地址值,它是一个非负整数。
       Hi=hash(x)
  二次探测再散列在表中寻找下一个空桶的公式为:
       Hi=(H0+i²)%m,
       Hi=(H0-i²)%m,0<i<(m-1)/2
  公式中m是表的长度,在做H0-i²的运算时,如果H0-i²<0时,运算结果也是负数。
  实际算式可以改为
  if((j=(H0+i²)%m)<0)j+=m

●伪随机探测再散列
    di=伪随机数序列。
具体实现时,应建立一个伪随机数发生器,(如i=(i+p) % m),并给定一个随机数做起点。
例如,已知哈希表长度m=11,哈希函数为:H(key)= key  %  11,则H(47)=3,H(26)=4,H(60)=5,假设下一个关键字为69,则H(69)=3,与47冲突。如果用线性探测再散列处理冲突,下一个哈希地址为H1=(3 + 1)% 11 = 4,仍然冲突,再找下一个哈希地址为H2=(3 + 2)% 11 = 5,还是冲突,继续找下一个哈希地址为H3=(3 + 3)% 11 = 6,此时不再冲突,将69填入5号单元,参图8.26 (a)。如果用二次探测再散列处理冲突,下一个哈希地址为H1=(3 + 12)% 11 = 4,仍然冲突,再找下一个哈希地址为H2=(3 - 12)% 11 = 2,此时不再冲突,将69填入2号单元,参图8.26 (b)。如果用伪随机探测再散列处理冲突,且伪随机数序列为:2,5,9,……..,则下一个哈希地址为H1=(3 + 2)% 11 = 5,仍然冲突,再找下一个哈希地址为H2=(3 + 5)% 11 = 8,此时不再冲突,将69填入8号单元。
下图为图例:


从上述例子可以看出,线性探测再散列容易产生“二次聚集”,即在处理同义词的冲突时又导致非同义词的冲突。线性探测再散列的优点是:只要哈希表不满,就一定能找到一个不冲突的哈希地址,而二次探测再散列和伪随机探测再散列则不一定。

2、再哈希法
Hi=RH₁(key)  i=1,2,…,k
当哈希地址Hi=RH₁(key)发生冲突时,再计算Hi=RH₂(key)...,直到冲突不再产生。这种方法不容易产生聚焦,但是增加了计算时间。

3、链地址法
  这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表,并将单链表的头指针存在哈希表的第i个单元,因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。这也是jdk中的hashtable和hashMap所使用的冲突解决方案。

例如,已知一组关键字(32,40,36,53,16,46,71,27,42,24,49,64),哈希表长度为13,哈希函数为:H(key)= key % 13,则用链地址法处理冲突的结果如图8.27所示:


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

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

参考引用:
http://www.360doc.com/content/14/0721/09/16319846_395862328.shtml   
http://blog.csdn.net/willfcareer/article/details/6687117
http://blog.csdn.net/jnu_simba/article/details/9668369
  • 大小: 14 KB
  • 大小: 4.8 KB
分享到:
评论

相关推荐

    MD5(散列算法)加密

    Rivest开发出技术上更为趋近成熟的md5算法。它在MD4的基础上增加了"安全-带子"(safety-belts)的...Den boer和Bosselaers曾发现MD5算法中的假冲突(pseudo-collisions),但除此之外就没有其他被发现的加密后结果了

    哈希查找_数据结构实验报告

    要求:用除留余数法构造哈希函数,用二次探测再散列解决冲突。 需求分析 用户可以根据自己的需求输入一个顺序表(哈希表) 通过用除留余数法构造哈希函数,并用开放地址的二次探测再散列解决冲突。 在经过排序后显示...

    安全散列算法的FPGA实现与仿真.pdf

    安全散列算法(SHA-1)是一种常用的密码散列函数,属于安全散列算法系列中的一员,它被广泛应用于信息安全领域,如数据完整性验证、数字签名等场景中。SHA-1算法由美国国家安全局(NSA)设计,并由美国国家标准与...

    散列算法与散列码(实例讲解)

    在Java中,散列算法通常是通过hashCode()方法来实现的,该方法将对象转换为一个整数值,以便于存储和检索。然而,在使用散列算法时,需要注意重写hashCode()和equals()方法,以确保散列码的正确性。 在给定的例子中...

    用二次探测再散列法解决冲突建立哈希表并查找

    二次探测再散列法是一种解决哈希冲突的方法,当一个元素的哈希地址已经被其他元素占用时,我们不会立即跳到下一个地址,而是按照平方序列(如 1, 4, 9, ...)进行探测。在本例中,如果初始哈希地址是 `i`,冲突发生...

    散列法的实验研究

    散列法中,散列函数构造方法多种多样,同时对于同一散列函数解决冲突的方法也可以不同。两者是影响查询算法性能的关键因素。对于几种典型的散列函数构造方法,做实验观察,不同的解决冲突方法对查询性能的影响。

    算法导论中完全散列的C++代码实现

    其中,"完全散列"是一种高效的哈希表构造方法,旨在最大限度地减少哈希冲突,提高查找效率。在C++中实现完全散列,需要理解哈希函数的设计、装载因子、开放寻址法或链地址法等概念。 哈希表是一种数据结构,通过...

    数据结构C语言实现散列:创建、解决冲突、查找元素[文].pdf

    总的来说,这个实验旨在通过实际编程实践来理解散列的基本概念,包括散列函数的选择、冲突解决策略的实现以及查找算法的效率。通过对比不同散列函数和冲突解决方法,可以深入理解其性能差异,并学会如何在C语言中...

    数据结构算法\哈希表开放地址法解决冲突

    数据结构算法\哈希表开放地址法解决冲突

    哈希函数的应用(数据结构课程设计)

    在设计该系统时,我们使用了除留余数法构造哈希函数,然后使用线性探测再散列解决冲突。系统的实现语言为C++,运行环境为Windows XP Professional。 哈希函数是一种非常有用的数据结构技术,广泛应用于各种领域。...

    基于散列函数与半边数据结构的TIN拓扑重构算法.pdf

    散列函数与半边数据结构在TIN拓扑重构...这种方法提高了TIN模型处理大数据量的效率,并为地理信息系统(GIS)、数字矿山等领域提供了高效的数据结构支持,有助于在实际应用中解决复杂的地理空间分析和地质模拟问题。

    散列表---算法数据结构

    然而,由于不同键值可能会映射到相同的地址,产生冲突,所以设计好的散列函数和解决冲突的方法至关重要。 1. 散列函数构造法: - 数字分析法:适合于已知所有可能键值的情况,分析键值的每一位,选择分布均匀的...

    SHA:安全散列算法简析 附实例

    总的来说,SHA系列安全散列算法是网络安全中不可或缺的一部分,它们提供了一种有效的方法来验证数据的完整性和一致性。随着技术的发展,更安全的算法如SHA-3系列已经被提出,以应对不断增长的计算能力和潜在的攻击...

    两种方法实现Hash散列

    Hash散列是一种在计算机科学中广泛使用的数据结构和算法,用于快速访问和管理大量数据。在给定的标题和描述中,我们关注的是如何实现两种...通过分析和比较这两种方法,我们可以更好地理解Hash散列的原理和优化策略。

    sanlie.rar_散列

    在“www.pudn.com.txt”文件中,可能是关于散列算法的文档或示例代码,它可能详细解释了散列函数的实现、冲突解决策略以及上述操作的具体步骤。而“sanlie”文件可能是程序的源代码,包含了处理散列文件的实现细节。...

    散列的C语言实现知识汇总

    常见的解决冲突的方法有两种:开放寻址法和链地址法。开放寻址法包括线性探测、二次探测和双散列探测等,当某个位置被占用时,寻找下一个空闲位置。链地址法是将冲突的元素链接到同一个索引对应的链表中。 3. **...

    计算机算法设计与分析第3版 课后答案 王晓东

    《计算机算法设计与分析》是计算机科学领域的一本经典教材,由王晓东教授编写,旨在帮助读者深入理解和掌握算法的设计技巧及其分析方法。这本教材的第三版在前两版的基础上进行了更新和完善,包含了更多现代计算机...

    10散列法的实验研究

    10散列法的实验研究,散列法中,散列函数构造方法多种多样,同时对于同一散列函数解决冲突的方法也可以不同。两者是影响查询算法性能的关键因素。

Global site tag (gtag.js) - Google Analytics