精华内容
下载资源
问答
  • 另外,当关键字的实际取值大于哈希表的长度时,而且表中已装满了记录,如果插入一个新记录,不仅发生冲突,而且还会发生溢出。因此,处理冲突和溢出是 哈希技术中的两个重要问题。1、开放定址法 用开放定址法解决...

    虽然我们不希望发生冲突,但实际上发生冲突的可能性仍是存在的。当关键字值域远大于哈希表的长度,而且事先并不知道关键字的具体取值时。冲突就难免会发 生。另外,当关键字的实际取值大于哈希表的长度时,而且表中已装满了记录,如果插入一个新记录,不仅发生冲突,而且还会发生溢出。因此,处理冲突和溢出是 哈希技术中的两个重要问题。
    1、开放定址法
         用开放定址法解决冲突的做法是:当冲突发生时,使用某种探查(亦称探测)技术在散列表中形成一个探查(测)序列。沿此序列逐个单元地查找,直到找到给定 的关键字,或者碰到一个开放的地址(即该地址单元为空)为止(若要插入,在探查到开放的地址,则可将待插入的新结点存人该地址单元)。查找时探查到开放的 地址则表明表中无待查的关键字,即查找失败。
    注意:
    ①用开放定址法建立散列表时,建表前须将表中所有单元(更严格地说,是指单元中存储的关键字)置空。
    ②空单元的表示与具体的应用相关。
         按照形成探查序列的方法不同,可将开放定址法区分为线性探查法、线性补偿探测法、随机探测等。
    (1)线性探查法(Linear Probing)
    该方法的基本思想是:
        将散列表T[0..m-1]看成是一个循环向量,若初始探查的地址为d(即h(key)=d),则最长的探查序列为:
            d,d+l,d+2,…,m-1,0,1,…,d-1
         即:探查时从地址d开始,首先探查T[d],然后依次探查T[d+1],…,直到T[m-1],此后又循环到T[0],T[1],…,直到探查到T[d-1]为止。
    探查过程终止于三种情况:
         (1)若当前探查的单元为空,则表示查找失败(若是插入则将key写入其中);
        (2)若当前探查的单元中含有key,则查找成功,但对于插入意味着失败;
         (3)若探查到T[d-1]时仍未发现空单元也未找到key,则无论是查找还是插入均意味着失败(此时表满)。
    利用开放地址法的一般形式,线性探查法的探查序列为:
            hi=(h(key)+i)%m 0≤i≤m-1 //即di=i
    用线性探测法处理冲突,思路清晰,算法简单,但存在下列缺点:
    ① 处理溢出需另编程序。一般可另外设立一个溢出表,专门用来存放上述哈希表中放不下的记录。此溢出表最简单的结构是顺序表,查找方法可用顺序查找。
    ② 按上述算法建立起来的哈希表,删除工作非常困难。假如要从哈希表 HT 中删除一个记录,按理应将这个记录所在位置置为空,但我们不能这样做,而只能标上已被删除的标记,否则,将会影响以后的查找。
    ③ 线性探测法很容易产生堆聚现象。所谓堆聚现象,就是存入哈希表的记录在表中连成一片。按照线性探测法处理冲突,如果生成哈希地址的连续序列愈长 ( 即不同关键字值的哈希地址相邻在一起愈长 ) ,则当新的记录加入该表时,与这个序列发生冲突的可能性愈大。因此,哈希地址的较长连续序列比较短连续序列生长得快,这就意味着,一旦出现堆聚 ( 伴随着冲突 ) ,就将引起进一步的堆聚。
    (2)线性补偿探测法 
    线性补偿探测法的基本思想是:
    将线性探测的步长从 1 改为 Q ,即将上述算法中的 j = (j + 1) % m 改为: j = (j + Q) % m ,而且要求 Q 与 m 是互质的,以便能探测到哈希表中的所有单元。
    【例】 PDP-11 小型计算机中的汇编程序所用的符合表,就采用此方法来解决冲突,所用表长 m = 1321 ,选用 Q = 25 。

    (3)随机探测 
    随机探测的基本思想是:
    将线性探测的步长从常数改为随机数,即令: j = (j + RN) % m ,其中 RN 是一个随机数。在实际程序中应预先用随机数发生器产生一个随机序列,将此序列作为依次探测的步长。这样就能使不同的关键字具有不同的探测次序,从而可以避 免或减少堆聚。基于与线性探测法相同的理由,在线性补偿探测法和随机探测法中,删除一个记录后也要打上删除标记。

    2、拉链法
    (1)拉链法解决冲突的方法
         拉链法解决冲突的做法是:将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为m,则可将散列表定义为一个由m个头指针组成的指针数 组T[0..m-1]。凡是散列地址为i的结点,均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。在拉链法中,装填因子α可以大于 1,但一般均取α≤1。
    【例】设有 m = 5 , H(K) = K mod 5 ,关键字值序例 5 , 21 , 17 , 9 , 15 , 36 , 41 , 24 ,按外链地址法所建立的哈希表如下图所示:


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

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

    http://hi.baidu.com/zkheartboy/blog/item/b181470f301b79296159f3d0.html

     

     

    直接定址法

    例如:有一个从1到100岁的人口数字统计表,其中,年龄作为关键字,哈希函数取关键字自身。

    数字分析法

    有学生的生日数据如下:

    年.月.日

    75.10.03

    75.11.23

    76.03.02

    76.07.12

    75.04.21

    76.02.15

    ...

    经分析,第一位,第二位,第三位重复的可能性大,取这三位造成冲突的机会增加,所以尽量不取前三位,取后三位比较好。

    平方取中法

    取关键字平方后的中间几位为哈希地址。

    折叠法

    将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位)作为哈希地址,这方法称为折叠法。

    例如:每一种西文图书都有一个国际标准图书编号,它是一个10位的十进制数字,若要以它作关键字建立一个哈希表,当馆藏书种类不到10,000时,可采用此法构造一个四位数的哈希函数。

    除留余数法

    取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。

    H(key)=key MOD p (p<=m)

    随机数法

    选择一个随机函数,取关键字的随机函数值为它的哈希地址,即

    H(key)=random(key),其中random为随机函数。通常用于关键字长度不等时采用此法。

    若已知哈希函数及冲突处理方法,哈希表的建立步骤如下:

    Step1. 取出一个数据元素的关键字key,计算其在哈希表中的存储地址D=H(key)。若存储地址为D的存储空间还没有被占用,则将该数据元素存入;否则发生冲突,执行Step2。

    Step2. 根据规定的冲突处理方法,计算关键字为key的数据元素之下一个存储地址。若该存储地址的存储空间没有被占用,则存入;否则继续执行Step2,直到找出一个存储空间没有被占用的存储地址为止。

    冲突

    无论哈希函数设计有多么精细,都会产生冲突现象,也就是2个关键字处理函数的结果映射在了同一位置上,因此,有一些方法可以避免冲突。

    拉链法

    拉出一个动态链表代替静态顺序存储结构,可以避免哈希函数的冲突,不过缺点就是链表的设计过于麻烦,增加了编程复杂度。此法可以完全避免哈希函数的冲突。

    多哈希法

    设计二种甚至多种哈希函数,可以避免冲突,但是冲突几率还是有的,函数设计的越好或越多都可以将几率降到最低(除非人品太差,否则几乎不可能冲突)。

    开放地址法

    开放地址法有一个公式:Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1)

    其中,m为哈希表的表长。di 是产生冲突的时候的增量序列。如果di值可能为1,2,3,...m-1,称线性探测再散列。

    如果di取1,则每次冲突之后,向后移动1个位置.如果di取值可能为1,-1,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2)

    称二次探测再散列。如果di取值可能为伪随机数列。称伪随机探测再散列。

    建域法

    假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表,另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。

     

     

    例题1

    已知一个线性表(38,25,74,63,52,48),假定采用散列函数h(key) = key%7 计算散列地址,并散列存储在散列表A【0....6】中,若采用线性探测方法解决冲突,则在该散列表上进行等概率成功查找的平均查找长度为

     

    依次进行取模运算求出哈希地址:(关键是这个图)
     
    74 应该放在下标为4 的位置,由于25 已经放在这个地方,所以74往后移动,放在了下标 为5的位置上了。 由于是等概率查找,所以结果为:1/6*(1+3+1+1+2+4)= 2.0

     

    例题2

    一道哈希表用二次探测再散列法解决冲突的问题
    设哈希表长为14,哈希函数是H(key)=key%11,表中已有数据的关键字为15,38,61,84共四个,现要将关键字为49的结点加到表中,用二次探测再散列法解决冲突,则放入的位置是( ) 【南京理工大学 2001 一、15 (1.5分)】

    A.8 B.3 C.5 D.9
    答案为A,为什么我计算出来是D呢?
    我的计算步骤如下:
    15,38,61,84用哈希函数H(key)=key%11计算后得地址:4,5,6,7
    49计算后为5,发生冲突.
    二次探测再散列法解决冲突:
    1:(key+1^2)%11=(49+1)%11=6,仍然发生冲突.
    2:(key-1^2)%11=(49-1)%11=4,仍然发生冲突.
    3:(key+2^2)%11=(49+4)%11=9,不再发生冲突.
    得出结果为D

    ------解决方案--------------------
    答案A是正确的
    (key+1^2)%14=(49+1)%14=8,不再发生冲突..
    Hi=(H(key) + di) MOD m, i=1,2,…, k(k<=m-1),其中H(key)为散列函数,m为散列表长,di为增量序列
    这里m=14 不是11 

    展开全文
  • 而本节所介绍的哈希表可以通过关键字直接找到数据的存储位置,不需要进行任何的比较,其查找的效率相较于前面所介绍的查找算法是更高的。 哈希表的构建 在初中的数学课本中学习过函数的相关知识,给定一个 x,通过...

    前面介绍了静态查找表以及动态查找表中的一些查找方法,其查找的过程都无法避免同查找表中的数据进行比较,查找算法的效率很大程度取决于同表中数据的查找次数。

    而本节所介绍的哈希表可以通过关键字直接找到数据的存储位置,不需要进行任何的比较,其查找的效率相较于前面所介绍的查找算法是更高的。

    哈希表的构建

    在初中的数学课本中学习过函数的相关知识,给定一个 x,通过一个数学公式,只需要将 x 的值带入公式就可以求出一个新的值 y。

    哈希表的建立同函数类似,把函数中的 x 用查找记录时使用的关键字来代替,然后将关键字的值带入一个精心设计的公式中,就可以求出一个值,用这个值来表示记录存储的哈希地址。即:

    数据的哈希地址=f(关键字的值)

    哈希地址只是表示在查找表中的存储位置,而不是实际的物理存储位置。f()是一个函数,通过这个函数可以快速求出该关键字对应的的数据的哈希地址,称之为“哈希函数”。

    例如,这里有一个电话簿(查找表),电话簿中有 4 个人的联系方式:

    张三 13912345678
    李四 15823457890
    王五 13409872338
    赵六 13805834722

    假如想查找李四的电话号码,对于一般的查找方式最先想到的是从头遍历,一一比较。而如果将电话簿构建成一张哈希表,可以直接通过名字“李四”直接找到电话号码在表中的位置。

    在构建哈希表时,最重要的是哈希函数的设计。例如设计电话簿案例中的哈希函数为:每个名字的姓的首字母

    展开全文
  • 哈希表及哈希冲突解决办法

    千次阅读 2019-07-17 22:04:11
    哈希表及哈希冲突解决办法 目录 什么是哈希表哈希表的数据结构 哈希冲突 哈希冲突解决办法 1. 什么是哈希表哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而...

    哈希表及哈希冲突解决办法


    目录

    1. 什么是哈希表?

    2. 哈希表的数据结构

    3. 哈希冲突

    4. 哈希冲突解决办法


    1. 什么是哈希表?

    哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

    hash就是找到一种数据内容和数据存放地址之间的映射关系。

    当使用哈希表hashtable(key,value) 进行查询的时候,就是使用哈希函数将关键码key转换为对应的数组下标,并定位到该空间获取value,如此一来,就可以充分利用到数组的定位性能进行数据定位。


    2. 哈希表的数据结构

    数组的特点是:寻址容易,插入和删除困难;
    而链表的特点是:寻址困难,插入和删除容易。

    那么我们能不能综合两者的特性,做出一种寻址容易,插入删除也容易的数据结构?答案是肯定的,这就是我们要提起的哈希表,哈希表有多种不同的实现方法,我接下来解释的是最常用的一种方法——拉链法,我们可以理解为“链表的数组”,如图:在这里插入图片描述

    左边很明显是个数组,数组的每个成员包括一个指针,指向一个链表的头,当然这个链表可能为空,也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去,也是根据这些特征,找到正确的链表,再从链表中找出这个元素。


    3. 哈希冲突

    1. 哈希冲突:即不同key值产生相同的地址,即发生了哈希冲突。一般来说,哈希冲突是无法避免的,所以就有了解决方案。

    4. 哈希冲突解决办法

    (一)链地址法

    1. HashMap,HashSet其实都是采用的拉链法来解决哈希冲突的,就是在每个位桶实现的时候,我们采用链表(jdk1.8之后采用链表+红黑树)的数据结构来去存取发生哈希冲突的输入域的关键字(也就是被哈希函数映射到同一个位桶上的关键字)。首先来看使用拉链法解决哈希冲突的几个操作:
      1. 插入操作:在发生哈希冲突的时候,我们输入域的关键字去映射到位桶(实际上是实现位桶的这个数据结构,链表或者红黑树)中去的时候,我们先检查带插入元素x是否出现在表中,很明显,这个查找所用的次数不会超过装载因子(n/m:n为输入域的关键字个数,m为位桶的数目),它是个常数,所以插入操作的最坏时间复杂度为O(1)的。

      2. 查询操作:和插入操作一样,在发生哈希冲突的时候,我们去检索的时间复杂度不会超过装载因子,也就是检索数据的时间复杂度也是O(1)的

      3. 删除操作:如果在拉链法中我们想要使用链表这种数据结构来实现位桶,在删除一个元素x的时候,需要更改x的前驱元素的next指针的属性,把x从链表中删除。这个操作的时间复杂度也是O(1)的。

    在这里插入图片描述

    1. 与开放定址法相比,拉链法有如下几个优点:
      ①拉链法处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短;

      ②由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况;

      ③开放定址法为减少冲突,要求装填因子α较小,故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1,且结点较大时,拉链法中增加的指针域可忽略不计,因此节省空间;

      ④在用拉链法构造的散列表中,删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。

    2. 拉链法的缺点

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

      使用例子:HashMap

    (二)开发地址法

    开发地址法的做法是,当冲突发生时,使用某种探测算法在散列表中寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到。按照探测序列的方法,一般将开放地址法区分为线性探查法、二次探查法、双重散列法等。

    这里为了更好的展示三种方法的效果,我们用以一个模为8的哈希表为例,采用除留余数法,往表中插入三个关键字分别为26,35,36的记录,分别除8取模后,在表中的位置如下:
    在这里插入图片描述
    这个时候插入42,那么正常应该在地址为2的位置里,但因为关键字26已经占据了位置,所以就需要解决这个地址冲突的情况,接下来就介绍三种探测方法的原理,并展示效果图。

    1) 线性探查法:

    fi=(f(key)+i) % m ,0 ≤ i ≤ m-1

    探查时从地址 d 开始,首先探查 T[d],然后依次探查 T[d+1],…,直到 T[m-1],此后又循环到 T[0],T[1],…,直到探查到有空余的地址或者到 T[d-1]为止。

    插入42时,探查到地址2的位置已经被占据,接着下一个地址3,地址4,直到空位置的地址5,所以42应放入地址为5的位置。
    在这里插入图片描述

    缺点:需要不断处理冲突,无论是存入还是査找效率都会大大降低。

    2) 二次探查法

    fi=(f(key)+di) % m,0 ≤ i ≤ m-1

    探查时从地址 d 开始,首先探查 T[d],然后依次探查 T[d+di],di 为增量序列1^2 , -1^2, 2^2, -2^2,……, q^2, -q^2 且q≤1/2 (m-1) ,直到探查到 有空余地址或者到 T[d-1]为止。

    缺点:无法探查到整个散列空间。

    所以插入42时,探查到地址2被占据,就会探查T[2+1^2]也就是地址3的位置,被占据后接着探查到地址7,然后插入。(文章说是地址7位置上,但是照上面运算我觉得是T(2±1=1)),是1位置上添加。
    在这里插入图片描述

    3) 伪随机探测
    di=伪随机数序列;具体实现时,应建立一个伪随机数发生器,(如i=(i+p) % m),生成一个位随机序列,并给定一个随机数做起点,每次去加上这个伪随机数++就可以了。

    (三)再散列法

    fi=(f(key)+i*g(key)) % m (i=1,2,……,m-1)

    其中,f(key) 和 g(key) 是两个不同的哈希函数,m为哈希表的长度

    步骤:

    1. 双哈希函数探测法,先用第一个函数 f(key) 对关键码计算哈希地址,一旦产生地址冲突,再用第二个函数 g(key) 确定移动的步长因子,最后通过步长因子序列由探测函数寻找空的哈希地址。

    2. 比如,f(key)=a 时产生地址冲突,就计算g(key)=b,则探测的地址序列为 f1=(a+b) mod m,f2=(a+2b) mod m,……,fm-1=(a+(m-1)b) % m,假设 b 为 3,那么关键字42应放在 “5” 的位置。


    文章内容引用博客:
    数据结构:哈希表以及哈希冲突的解决方案: https://blog.csdn.net/yeyazhishang/article/details/82533211
    解决hash冲突的三种方法:https://www.cnblogs.com/kaleidoscope/p/9588151.html

    展开全文
  • 哈希表以及解决冲突方法

    千次阅读 2014-03-16 19:27:48
    哈希法又称散列法、杂凑法以及关键字地址计算法等,相应的表称为哈希表。这种方法的基本思想是:首先在元素的关键字k和元素的存储位置p之间建立一个对应关系f,使得p=f(k),f称为哈希函数。创建哈希表时,把关键字为...

    哈希法又称散列法、杂凑法以及关键字地址计算法等,相应的表称为哈希表。这种方法的基本思想是:首先在元素的关键字k和元素的存储位置p之间建立一个对应关系f,使得p=f(k)f称为哈希函数。创建哈希表时,把关键字为k的元素直接存入地址为f(k)的单元;以后当查找关键字为k的元素时,再利用哈希函数计算出该元素的存储位置p=f(k),从而达到按关键字直接存取元素的目的。

       当关键字集合很大时,关键字值不同的元素可能会映象到哈希表的同一地址上,即 k1k2 ,但 Hk1=Hk2),这种现象称为冲突,此时称k1k2为同义词。实际中,冲突是不可避免的,只能通过改进哈希函数的性能来减少冲突。

    综上所述,哈希法主要包括以下两方面的内容:

     1)如何构造哈希函数

     2)如何处理冲突。

    8.4.1   哈希函数的构造方法

        构造哈希函数的原则是:函数本身便于计算;计算出来的地址分布均匀,即对任一关键字kf(k) 对应不同地址的概率相等,目的是尽可能减少冲突。

    下面介绍构造哈希函数常用的五种方法。

    1 数字分析法

          如果事先知道关键字集合,并且每个关键字的位数比哈希表的地址码位数多时,可以从关键字中选出分布较均匀的若干位,构成哈希地址。例如,有80个记录,关键字为8位十进制整数d1d2d3…d7d8,如哈希表长取100,则哈希表的地址空间为:00~99。假设经过分析,各关键字中 d4d7的取值分布较均匀,则哈希函数为:h(key)=h(d1d2d3…d7d8)=d4d7。例如,h(81346532)=43h(81301367)=06。相反,假设经过分析,各关键字中 d1d8的取值分布极不均匀, d都等于5d都等于2,此时,如果哈希函数为:h(key)=h(d1d2d3…d7d8)=d1d8,则所有关键字的地址码都是52,显然不可取。

    2 平方取中法

    当无法确定关键字中哪几位分布较均匀时,可以先求出关键字的平方值,然后按需要取平方值的中间几位作为哈希地址。这是因为:平方后中间几位和关键字中每一位都相关,故不同关键字会以较高的概率产生不同的哈希地址。

    例:我们把英文字母在字母表中的位置序号作为该英文字母的内部编码。例如K的内部编码为11E的内部编码为05Y的内部编码为25A的内部编码为01, B的内部编码为02。由此组成关键字“KEYA”的内部代码为11052501,同理我们可以得到关键字“KYAB”、“AKEY”、“BKEY”的内部编码。之后对关键字进行平方运算后,取出第7到第9位作为该关键字哈希地址,如图8.23所示。

     

     

    关键字

    内部编码

    内部编码的平方值

    H(k)关键字的哈希地址

    KEYA

    11050201

    122157778355001

    778

    KYAB

    11250102

    126564795010404

    795

    AKEY

    01110525

    001233265775625

    265

    BKEY

    02110525

    004454315775625

    315

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

    3 分段叠加法

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

     

     

      2   3                    1   2   3

      0   3                    3   0   6

      4   7                    2   4   7

      1   2                    2   1   1

    +   0   2   0               +  0   2   0

            ————————            —————————

            1   1   0   5                    9   0   7

     

    a)移位叠加                    (b) 折叠叠加

     

                          8.24 由叠加法求哈希地址

     

    4 除留余数法

    假设哈希表长为mp为小于等于m的最大素数,则哈希函数为

    hk=k  %  p ,其中%为模p取余运算。

    例如,已知待散列元素为(18756043549046),表长m=10p=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

    此时没有冲突,如图8.25所示。

     

         1      2     3     4     5      6     7     8     9     10     11    12

     

     

     

    54

     

    43

    18

     

    46

    60

     

    75

     

    90

                          8.25  除留余数法求哈希地址

     

    5 伪随机数法

        采用一个伪随机函数做哈希函数,即h(key)=random(key)

    在实际应用中,应根据具体情况,灵活采用不同的方法,并用实际数据测试它的性能,以便做出正确判定。通常应考虑以下五个因素 

    l         计算哈希函数所需时间 (简单)。

    l         关键字的长度。

    l         哈希表大小。

    l         关键字分布情况。

    l         记录查找频率

    8.4.2   处理冲突的方法

       通过构造性能良好的哈希函数,可以减少冲突,但一般不可能完全避免冲突,因此解决冲突是哈希法的另一个关键问题。创建哈希表和查找哈希表都会遇到冲突,两种情况下解决冲突的方法应该一致。下面以创建哈希表为例,说明解决冲突的方法。常用的解决冲突方法有以下四种:

    1.         开放定址法

    这种方法也称再散列法其基本思想是:当关键字key的哈希地址p=Hkey)出现冲突时,以p为基础,产生另一个哈希地址p1,如果p1仍然冲突,再以p为基础,产生另一个哈希地址p2,直到找出一个不冲突的哈希地址pi 将相应元素存入其中。这种方法有一个通用的再散列函数形式:

              Hi=Hkey+di% m   i=12…,n

        其中Hkey)为哈希函数,为表长,di称为增量序列。增量序列的取值方式不同,相应的再散列方式也不同。主要有以下三种:

    l         线性探测再散列

        dii=123m-1

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

    l         二次探测再散列

        di=12-1222-22k2-k2    ( k<=m/2 )

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

    l         伪随机探测再散列

        di=伪随机数序列。

    具体实现时,应建立一个伪随机数发生器,(如i=(i+p) % m),并给定一个随机数做起点。

    例如,已知哈希表长度m=11,哈希函数为:Hkey= key  %  11,则H47=3H26=4H60=5,假设下一个关键字为69,则H69=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)。如果用伪随机探测再散列处理冲突,且伪随机数序列为:259……..,则下一个哈希地址为H1=3 + 2% 11 = 5,仍然冲突,再找下一个哈希地址为H2=3 + 5% 11 = 8,此时不再冲突,将69填入8号单元,参图8.26 (c)

     

     

                                                           10    

     

     

     

     

    47

    26

    60

    69

     

     

     

     

             a 用线性探测再散列处理冲突

     

     

                                                           10    

     

     

     

    69

    47

    26

    60

     

     

     

     

     

             b 用二次探测再散列处理冲突

     

     

                                                           10    

     

     

     

     

    47

    26

    60

     

     

    69

     

     

             c 用伪随机探测再散列处理冲突

     

                          8.26开放地址法处理冲突

    从上述例子可以看出,线性探测再散列容易产生“二次聚集”,即在处理同义词的冲突时又导致非同义词的冲突。例如,当表中i, i+1 ,i+2三个单元已满时,下一个哈希地址为i, i+1 ,i+2,或i+3的元素,都将填入i+3这同一个单元,而这四个元素并非同义词。线性探测再散列的优点是:只要哈希表不满,就一定能找到一个不冲突的哈希地址,而二次探测再散列和伪随机探测再散列则不一定。

    2.         再哈希法

        这种方法是同时构造多个不同的哈希函数:

        Hi=RH1key  i=12k

    当哈希地址Hi=RH1key)发生冲突时,再计算Hi=RH2key)……,直到冲突不再产生。这种方法不易产生聚集,但增加了计算时间。

    3.         链地址法

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

    例如,已知一组关键字(324036531646712742244964),哈希表长度为13,哈希函数为:Hkey= key % 13,则用链地址法处理冲突的结果如图8.27所示:

     



    哈希表及处理冲突的方法(转) - 另一片天空 - 仰望天空
     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

    展开全文
  • 哈希表及处理冲突方法
  • 哈希表处理冲突方法

    千次阅读 2018-10-08 16:20:59
    哈希表,也叫散列表,是根据关键字而直接进行访问的数据结构。也就是说,它将关键字通过某种规则映射到数组中某个位置,以加快查找的速度。这个映射规则称为哈希函数(散列函数),存放记录的数组称为哈希表哈希表...
  •  散列表(Hash table,也叫哈希表),是根据关键码值(Key-Value)而直接进行访问的数据结构。 也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的...
  • 主要有:常用的字符串Hash函数还有ELFHash,APHash等等,都是十分简单有效的方法。这些函数使用位运算使得每一个字符都对最后的函数值产生影响。另外还有以MD5和SHA1为代表的杂凑函数,这些函数几乎不可能找到碰撞。...
  • 哈希表冲突及处理冲突的方法

    万次阅读 多人点赞 2018-07-06 20:31:30
    哈希法又称散列法、杂凑法以及关键字地址计算法等,相应的表成为哈希表。 基本思想:首先在元素的关键字K和元素的位置P之间建立一个对应关系f,使得P=f(K),其中f成为哈希函数。 创建哈希表时,把关键字K的元素直接...
  • 按这个思想建立的表为哈希表。 2.哈希函数的构造方法 2.1 直接定址法 取关键字或关键字的某个线性函数值为哈希地址。即: H(key) = key 或 H(key) = a · key + b 2.2 数字分析法 假设关键字是以r为基的数(如:以10...
  • 哈希表冲突解决

    千次阅读 2013-09-03 12:38:12
    这个方法的基本思想是:当发生地址冲突时,按照某种方法继续探测哈希表中的其他存储单元,直到找到空位置为止。这个过程可用下式描述:  H i ( key ) = ( H ( key )+ d i ) mod m ( i = 1,2,…… , k ( k ≤ m – ...
  • 哈希表:通过关键码来映射到值的一个数据结构; 哈希函数:键与值映射的一个映射关系; 哈希函数的构建: 常用方法: 1、直接寻址法:f(x) = kx+b (k、b都是常数) ,一旦确定了哈希函数,那么添加、获取元素都需要...
  • 哈希表及处理冲突方法

    千次阅读 2018-11-20 13:08:14
    哈希法又称***散列法、杂凑法以及关键字地址计算法***等,相应的表称为哈希表。 这种方法的基本思想是:首先在元素的关键字k和元素的存储位置p之间建立一个对应关系f,使得p=f(k),f称为哈希函数。 创建哈希表...
  • 文章目录Java哈希表概念冲突避免冲突哈希函数的设计方法常见哈希函数负载因子调节解决哈希冲突两种常见的方法是:闭散列和开散列哈希表和 java 类集的关系 Java哈希表 概念 顺序结构以及平衡树中,元素关键码与其...
  • 哈希冲突解决方法

    2020-08-06 08:59:45
    开放地址方法 ...(3)伪随机探测:按顺序决定哈希值时,如果某数据已经存在,通过随机函数随机生成一个数,在原来哈希值的基础上加上随机数,直至不发生哈希冲突。 链式地址法(HashMap的哈希冲突解.
  • 解决哈希冲突方法

    2019-09-04 01:06:21
    创建哈希表和查找哈希表都会遇到冲突,两种情况下解决冲突方法应该一致。下面以创建哈希表为例,说明解决冲突方法。常用的解决冲突方法有以下四种: 开放定址法 这种方法也称再散列法,其基本思想是:当关键字...
  • 1 开放地址法 这个方法的基本思想是:当发生地址冲突时,按照某种方法继续探测哈希表中的其他存储单元,直到找到空位置为止。这个过程可用下式描述: H i ( key ) = ( H ( key )+ d i ) mod m ( i = 1,2,…… , k ...
  • 为什么会有冲突? 当关键字集合很大时,...处理冲突是指对于一个待插入哈希表的数据元素,若按给定的哈希函数求得的哈希地址已被占用,则按一定规则求下一哈希地址,如此重复,直至找到一个可用的地址以保存该元...
  • 1. 哈希表就是数组+哈希函数,其核心思想是利用数组可以按照下标索引随机访问数据的特性。 2. 哈希冲突的原因:数组的有界,哈希函数的计算,哈希值的映射。 3. 解决哈希冲突方法:数组扩容,设计优秀的哈希函数,...
  • 文章目录哈希表和哈希函数的概念哈希函数的构造直接定址法数字分析法平方取中法折叠法除留余数法(常用)随机数法哈希函数的选择处理冲突方法开放定址法再哈希法链地址法建立一个公共溢出区代码实现 哈希表和哈希...
  • 哈希法又称散列法、杂凑法以及关键字地址计算法等,相应的表成为哈希表。 基本思想:首先在元素的关键字K和元素的位置P之间建立一个对应关系f,使得P=f(K),其中f成为哈希函数。 创建哈希表时,把关键字K的元素直接...
  • 哈希表 哈希函数:记录的存储位置和它的关键字之间建立一个确定的对应关系。 冲突:对不同的关键字可能得到同一哈希地址,这种现象称为冲突。 哈希函数构造方法 1.直接定址法 取关键字或关键字的某个线性函数值...
  • 哈希法又称散列法、杂凑法以及关键字地址计算法等,相应的表称为哈希表。这种方法的基本思想是:首先在元素的关键字k和元素的存储位置p之间建立一个对应关系f,使得p=f(k),f称为哈希函数。创建哈希表时,把关键字为...
  • 哈希表之三冲突解决

    2017-07-01 20:07:00
    前的部分分析了,哈希表中的冲突时难以避免的,冲突是很正常的,所以就要知道如何解决冲突。 我觉得冲突是有两种解决方法: 1、横向的解决 2、纵向的解决 所谓横向解决:指的是对冲突的键,会在哈希表上另外找...
  • 哈希 一般指哈希算法。英文Hash,一般翻译做"散列",也有直接音译为"哈希"的,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 32,437
精华内容 12,974
关键字:

哈希表解决冲突的方法随机