哈希游戏- 哈希游戏平台- 哈希游戏官方网站

　　第二十五讲 哈 希 表 查 找;8.3.1 哈希表的概念 在前面讲过的几种查找方法中，都是在结 构中查找记录时需要进行一系列和关键字的比 较。查找的效率依赖于查找过程中所进行的比 较次数。; 理想的情况是希望不经过任何比较，一次 存取便能够得到所查记录，那就必须在记录的 存储位置上和它的关键字之间建立一个确定的 对应关系f，使每个关键字和结构中一个唯一 的存储位置相对应。因而在查找时，只要根据;这个对应关系f找到给定值k的的映像f(k)。若 结构中存在关键字和k相等的记录，则必定在 f(k)的存储位置上，由此，不需要进行比较便 可直接取得所查记录。在此，我们称这个对应 关系f为哈希函数，按这个思想建立的表为哈 希表。 ;而使用哈希表进行查找的方法称为哈希查找。 因此，其查找时间与计算地址的函数有关。 假设table是一个包含n个元素的线性表，Ri 为表中的某个元素（1=i=n），keyi是其关键 字值，若在关键字值keyi与元素Ri的地址（即 在线性表中的位置）之间建立某种函数关系，;则可以通过这个函数，把关键字值转换成相应 元素在表中的地址，即 Addr(Ri)=H(keyi) 其中，Addr(Ri)为Ri的地址，函数 H 称为哈希 （Hash）函数（散列函数）， 称H(keyi) 的值为哈希地址（散列地址）。 ;哈希查找的基本思想： 确定将关键字值转换成存储位置的函数 H，以记录中关键字值K为自变量，对应的函 数值H（K）作为其记录的存储地址将其存到 相应的位置中。查找时，通过函数H计算得到 待查找记录的存储位置。; 在进行查找之前，我们先来了解如何构造哈希表。例如：假定一个线} 将其存储到数组H[13]中，如下图所示：; 若哈希函数定义为H（key）=key%13,则查找 过程就是一个求H（key）的值的过程，如查找 75，则H（75）=75%13=10，说明H[10]存放着 75。若查找90， H（90）=90%13=12，说明 H[12]存放着90。; 若根据哈希函数，把元素存放到线性表中相 应的位置上，这样形成的表便称为哈希表，又 叫散列表。哈希表的查找是以同样的方式进行 的。 若某个哈希函数对于不同的关键字值key1和 key2，得到相同的散列地址，;即H（key1）= H（key2），这种现象称为冲 突。例如：H（54）=H（67）=2，说明54和 67在存放时发生冲突，即54和67都要存放到 H[2]中，这就需要有办法来处理冲突，发生 冲突的关键字对该哈希函数H（key）来说称 为是同义词。 ;; 综上所述，哈希表是根据设定的哈希函 数和解决冲突的方法，为一组元素建立一张 表，每个元素在表中的位置依赖于设定的哈 希函数和解决冲突的方法。 ; 8.3.2 哈希函数的构造方法 构造哈希函数的方法很多，在讲述各种 方法之前，首先需要明确什么是“好”的哈希 函数。 若对于关键字集合中的任一个关键字， 经哈希函数映像到地址集合中任何一个地址 的概率是相等的，则称此类哈希函数为均匀;的（Uniform）哈希函数。换句话说，就是使 关键字经过哈希函数得到一个“随机的地址”， 以便使一组关键字的哈希地址均匀分布在整个 地址空间中，从而减少冲突。 ;1、直接地址法（这种哈希函数叫做自身函数） 哈希函数H对于关键字是数字类型的元素， 直接利用关键字求得哈希地址。 H（key）=key 或 H（key）=a×key+b 在使用时，为了使哈希地址与存储空间吻合，可以调整a和b的值，a,b为常数。;地 址;分析：该方法计算简单，一个关键字对应一个 存储地址，不会产生冲突，这种方法适用于关 键字分布连续的情况，但在实际应用中有一定 的局限性。;若干位作为哈希地址，它要求可能出现的关键 字事先知道的情况。 例如：以下一组关键字由7位十进制构成。 ; ① ② ③ ④ ⑤ ⑥ ⑦; 我们对关键字的每一位数字分析发现，第①② 位都是数字7和2；第③位的数字只取0和1；第⑤位的数字取0，1，2和3；第⑦位的数字取1和2，因此第①②③⑤⑦几位都不取，而第④⑥位的数字分布均匀。我们取④⑥ 两位数字为哈希地址。所有元素的哈希地址得出的结果如下： H（k1）=56 H（k2）=14 H（k3）=23 ;H（k4）=20 H（k5）=35 H（k6）=41 ;3、平方取中法 平方取中法是指取关键字平方后的中间几 位为哈希地址，一个数的平方数与该数的每一 位数都有关，所选取的位数与表长有关。例如 哈希表长1000，如下图所示：;分析：平方取中法适用于关键字中每一位的取值 都不够分散或分散的位数小于哈希地址所需要的 位数的情况。;4、折叠法 当关键字的位数很多，采用平方取中法计 算太复杂时，采用折叠法，即将关键字分成 位数相同的几段（最后一段位数可以少 些）。每一段的长度取决于哈希地址的位 数，然后取这几段的叠加和（舍去最高进 位）作为哈希地址。 ;;这两种叠加的过程如下图所示：;其中高位舍去后，对应的哈希地址为158和762。 折叠法适用于关键字位数多，而对应的哈希地 址的位数要求较少的情况。 ;5、除留取余法 指取关键字k除以最接近表长的素数m所 得的余数为哈希地址，对应的哈希函数为： H（k）=k%m 这是一种最简单、也最常用的构造哈希函 数的方法，它不仅可以对关键字直接取模 （MOD）也可在折叠、平方取中等运算之后 取模。; 一般地，m是哈希表的长度，它的取值在～之间。 注意：在使用此种方法时，对m的选择很重要。 若选择不好，容易产生同义词，从而产生冲突。 ;6、随机数法 选择一个随机函数，取关键字的随机函数 值为它的哈希地址，即 H(key)=random(key) 其中random为随机函数。通常，当关键字长 度不等的时采用此法构造哈希函数较恰当。 ; 以上介绍了建立哈希函数产生哈希地址的方 法，在实际应用中，应根据关键字的特点，确定 适当的方法，还可以根据具体情况构造出满足需 要的随机性能好的哈希函数。; 处理冲突的方法 在前面已经讲过，均匀的哈希函数可以 减少冲突，但不能够避免，因而解决冲突的 问题尤为重要。 假设哈希表的地址范围为0…..m-1,冲突是 指由关键字得到的哈希地址为j（0=j=m-1） 的位置上已有关键字记录，则“处理冲突”就 ;是为该关键字的记录找到另一个空的哈希地址。 在处理冲突的过程中可能得到一个地址序列Hi i=1,2,3,……,k(Hi属于[0，m-1]),即在处理哈希地 址的冲突时，若得到的另一个哈希地址H1仍然发 生冲突，则在求下一个地址H2，若仍然冲突，在 求H3。依次类推，直至不发生冲突为止。 解决冲突的方法有两大类：开放地址法和 链地址法。;一、开放地址法 开放地址法指当发生冲突时，使用某种方 法在冲突位置前后寻找可存放记录的空单元。 我们利用下列公式来求得用来存放该记录的下一个地址单元的地址： Hi=(H(k)+di)%m 其中，H(k)关键字为 k的记录所对应的哈希地 址（即发生冲突的地址）； di为增量序列；;m为哈希表的长度。根据di的取法，开放地址 法又可以分为线性探测法、二次探测法和随机 探测法。下面就这几种方法作一介绍。;1、线性探测法 是开放地址法处理冲突的一种最简单的探测 方法，此时di的取值为di =1，2，3…….m-1， 即它发生冲突的地址单元依次探测下一个地址 （当探测达到地址为m-1的表尾时，在从地址为 ; 0的表头单元依次探测），直到碰到一空闲地址 或探测完所有地址为止。 假设哈希表大小为T[m]，哈希函数为H （key）那么，公式如下： H1=H（key） Hi+1= (Hi+1)%m 其中i=1，2…..;例如：假设一组记录关键字为{4，17，29，38，48，53，60，76，82}，试对这组关键字构造哈希表。 取哈希表表长m=11 ，用除留余数法构造哈希函 数H(k)=k%11,用开放地址法处理冲突，处理过程如下： H(4)=4%11=4 H(17)=17%11=6 H(29)=29%11=7 H(38)=38%11=6 H(48)=48%11=4与H(4)=4发生冲突，由线性探测;法，探测下标为5的单元，仍然冲突，直到下标 为8的单元为空，此时将48防入该单元。 H(53)=53%11=9 H(60)=60%11=5与H(38) 发生冲突，由线性探测法依次推测，最后放在 地址为10 的单元中。H(76)=76%11=10，此时与H(60)发生冲突，将其最后放在地址为0的单元中。 H(82)=82%11=5，;此时与H(38)发生冲突，将其最后放入地址为1的单元中。构造结果如下图所示：;2、二次探测法 此法可以较好的避免堆积现象，能较好的解决冲 突。此时di的取值依次为di=12，-12，22，-22…。 二次探测解决冲突的公式如下： H1=H（key） H2i=(H1+i2)% m H2i+1 =(H1 -i2)%m;如上例子中，H（48）=48%11=4与关键字为4的元素发生冲突时，由二次探测法可得 H1（48）=（4+1）%11=5， 仍然冲突又得H2（48）=（4-1）%11=3，此时该单元空闲。 这与线性探测法相比，避免了冲突的再次发生，因为第二次d2=-1,将所占单元向前分散开。由此依次可得：H（53）=9 H（60）=5时，发生冲突，以二次探测法得： ;H1（60）=（5+1）%11=6 H2（60）=（5-1）%11=4 H3（60）=（5+22）%11=9 H3（60）=（5-22）%11=1此时解决冲突。 H（76）=10 H（82）=5时冲突发生，用二次探测法最后得出 H8（82）=0构造结果如下图所示：;二次探测法的缺点是不能探测到哈希表上所有的 单元，在实际应用中，若探测一半仍未找到空闲 单元，说明该哈希表太满，应重新建立。 3、随机探测法 是指选择一个随机函数产生随机序列，并建立和 查找时使用同一随机生成序列。 随机探测解决冲突的公式是： H1=H（key） Hi+1=(H1+R)% m;其中R=伪随机数序列R1，R2，… 二、链地址法 链地址法是指将所有的关键字为同义词的 记录链接成一个线性表，而其链表头存储在相 应的哈希地址对应的存储单元中。如图1 总之，哈希表的建表过程中与查找过程所经历 的冲突是一致的，只是在建表时把一个关键字 通过哈希函数和解决冲突安排在一个空挡上，;而查找时，是对一个给定的值的方法，使得 某个位置通过哈希函数和找到解决冲突的方法，使得某个位置上的关键字等于给定的值。;0;哈希表举例;关键字的哈希地址，若有冲突，按照用线性探 测、二次探测来解决，得到下图的 哈希表。;27;^;ASL链地址=1/12（1*7+2*4+3*1） ASL顺序查找=（12+1） ASL折半查找=log2 ;9.3.4 哈希表的查找及分析 哈希表的查找过程与建表过程基本一致，在 以开放法处理冲突的情况下，对于待查找关键 字k，按建表时设定的哈希函数求哈希地址，如 表中位置没有记录，则查找不成功；否则，如 与待查元素相等，则查找成功；如不等则根据 建表时的处理冲突的方法找下一个地址，直至 哈希表中的相应位置为空或所填记录关键字等 ;于待查找记录关键字为止。为空表的时候查找不 成功。利用链地址法处理冲突，则查找更简单， 只要在该元素对应的哈希地址对应链表中进行。 以哈希表存储数据时，插入查找速度很快，优先 于前面介绍的任一种方法。缺点如下： （1）根据哈希函数计算关键字的哈希地址的过