HASH GAME - Online Skill Game GET 300

　　第33卷第5期 杭州电子科技大学学报 V01．33．No．5 Df 2013年lO月 JounudBayouⅨndUnivenIity 慨加13 dol：10．3969／j．妇．1001-9146．2013．05—013 改进的哈希表查找算法 朱芳芳，李训根 (杭州电子科技大学电子信息学院，浙江杭州310018) 摘要：哈希表查找作为一种快速的数据查询算法被广泛应用。为了更好地查找和解决哈希冲突， 在构建哈希表时常选用链地址法来解决冲突。由于在查找哈希表时需要遍历链表，大大降低了查 找效率。该文在结合链地址法和二分查找的基础上，提出了一种提高哈希表查找效率的改进方 法。实验结果表明，该方法降低了冲突时执行查询的查找长度，从而降低了查询所需的时间。 关键词：链地址法；哈希表；哈希查找；哈希冲突；--分查找 中图分类号：TP301．6 文献标识码：A 文章编号：1001—9146(2013)05—0046—04 0引言 查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算。查找 效率依赖于查找过程中所进行的比较次数。理想的情况是不经过任何比较，一次存取使能得到所需查 找的数据。哈希表作为一种根据关键字直接进行访问的数据结构被广泛应用于各种查找中n】。然而， 很难找到一个哈希函数能保证对任意不同的关键字都产生不同的哈希值。文献2中提出了完美哈希函 数，但该函数是针对特定的规则集而设定的，随机性很大，不能保证对任意规则集构造完美哈希函数。 因此，寻找高效解决冲突的方法从而降低冲突时执行查询的查找长度，缩短查询响应时间成了本文关注 的焦点。通常用的处理冲突的方法有：链地址法，开放定址法，再哈希法，以及建立一个公共溢出区。但 是，在建立哈希表处理冲突时，这些冲突解决方法往往未能有效地提高查找效率。比如，在利用链地址 法处理冲突构建的哈希表中，如果大批关键字具有相同的哈希值，查找这批关键字时，需要逐个遍历它 们的哈希值对应的链表，查找效率非常低。基于这种情况，本文提出了一种基于二分查找的哈希表查找 算法。 1改进方法 1．1二分查找 二分查找又称折半查找，它是一种效率较高的查找方法。其算法思想是：首先，将表中间位置记录 的关键字与查找关键字比较，如果两者相等则查找成功，否则利用中间位置记录将表分成前、后两个子 表；其次，如果中间位置记录的关键字大于查找关键字则迸一步查找前一子表，否则进一步查找后一子 表；之后，重复上述过程直到找到满足条件的记录使查找成功或直到子表不存在为止。 二分查找法的优点是比较次数少，查找速度快且平均性能好。假设数组长度为n，其算法复杂度为 结构，因此链表存储无法应用二分查找法。经实验发现，在查找时运用二分查找法需要将链地址存储法 收稿日期：2013—0r7—20 作者简介：朱芳芳(1986一)，女，河南信阳人，在读研究生，电路与系统． 第5期 朱芳芳等：改进的哈希表查找算法 47 中的所有同义k,3k2录存储到同一数glq：。利用这种机制将提高冲突情况下的查找效率，相应地提高了 哈希表的整体查找效率。 1．2链地址法处理冲突的哈希表查找方法 链地址存储法将所有关键字为同义词的记录存储在同一线性链表中。假设某哈希函数产生的哈希 地址在区间[O，1，2，…，m一1]上，则设立一个指针型向量T[m]；其每个分量的初始状态都是空指针。 凡哈希地址为i的记录都插入到头指针为T[i]的链表中。链地址法处理冲突时的哈希表如图1所示。 图1链地址法处理冲突时的哈希表 1．3方法改进 链地址法处理冲突对接收到的关键字进行哈希运算得到哈希值。 0 首先，根据哈希值查找哈希表，从哈希表得到指向存有冲突表项的链表 l 的地址；然后，使用该地址访问哈希链表；最后，通过遍历链表来查找需 2 要的信息。然而，在恶劣情况下，可能需要很多次存储器访问，查找速 3 度很慢。如果能在哈希查找的基础上引入二分查找，将会降低冲突执 4 行查询的查找长度，从而缩短查询响应时间。 5 鉴于二分查找的使用场合，可以使用数组来模拟链表。因此，改进 6 的哈希表建立过程首先对关键字进行排序，排序规则是按关键字的大 7 小从小到大排序。后续的构建过程如下：如果选定哈希长度为m，可将 8 哈希表定义为一个由m个头指针组成的指针数组T[m]，将散列地址9 0 为i的节点都插入到以T[i]为头指针的动态数组中。 1 该方法突破了原有的存储结构，构造了使用二分查找的前提条件， 2 使得二分查找方法在哈希表查找中得以运用。如关键字为(19，14，23， MOD 图2改进方法得到的哈希表 01，68，20，84，27，55，ll，10，79)，按哈希函数H(研)=key13和 改进的方法得到的哈希表如图2所示。 在关键字的存放问题上，具体实现时使用如下解决办法：在哈希表构建过程中，如果存在哈希地址 为i的记录，在指针数组的第i个元素上添加临时链表，构建过程类似原来的哈希表中链表的建立过程。 所有关键字处理完毕，根据指针数组中非空元素所指向的l临时链表的长度为该元素创建动态数组，并将 杭州电子科技大学学报 2013年 该链表中的数据逐个存人数组，同时销毁链表中的对应节点。 在哈希函数的选取上，根据不同的规则集选定不同的哈希函数。但考虑到本文的侧重点在于寻找 高效的解决冲突办法，所以可以假定所有的哈希函数都是“均匀的”(即不同的哈希函数对同一组随机 的关键字，产生冲突的可能性相同)。因此，该文采用了一种常用而有效的方法一除留取余法来构造 哈希函数。 1．4性能分析 查找算法中的基本操作是将记录的关键字和给定值进行比较，因此，通常将关键字和给定值进行过 比较的记录个数的平均值(也称为平均查找长度)作为衡量查找算法好坏的依据。 平均查找长度ASL定义如下： ASL=∑PiNi (1) ．式中，n是节点的个数；Pi是查找第i个节点的概率，一般情况下，认为每个节点的查找概率相等， 即Pi=1／n；N；是找到第i个结点所需的比较次数。 根据式1，可以推导出链地址法处理冲突的ASL： o k Nj (2) ASL=∑∑Pj 式中，s表示哈希链中不为空的首地址个数；k对应每个链表中的节点个数；P{对应查找该结点的概 率；Ni为查找该节点所需进行比较的次数。 在等概率情况下，通过顺序查找得到的平均查找长度ASL鹞： I ． ASL。=∑PjNj=半 (3) 。 】21 而通过二分查找得到的平均查找长度ASL鸲： l Nj=l092(n+1)一I (4) ASLb-=∑Pj 由式3、4可见，二分查找的效率比顺序查找的效率高，因此新方法得到的平均查找长度小于等于原 方法。在所有关键字都映射到同一地址的情况下，新方法的优势将更加明显。 2实例测试 ET500 测试环境：WindowsXP操作系统，CPU为Intel2．93G，内存为1．98GB的平台。 通过VC6．0对改进的哈希表进行测试，实验采用的数据源由VC6．0随机生成，并通过对这些数据 进行编程处理，保证输入的数据源中没有相同的两个数据。 000，5000，10000和15000个数据，排序后分别建立原 测试中分别选取数据源里的50，100，500，1 哈希表和改进的哈希表对这些数据进行查找。当装填因子(即表中填入的记录数除以哈希表的长度) 0l=1时的测试结果如表l所示。表格中的数值为两种不同查找方案下的平均查找长度。 表1两种查找方案对比 从表1可见，新方法得到的平均查找长度小于原来的方法，即减少了查找过程的总体消耗时间。 第5期 朱芳芳等：改进的哈希表查找算法49 另外，俚值对哈希表的查找长度有一定影响，本文选择不同的a对数据源中的1 000个数据进行测 试，测试结果如表2所示。 表2不同Ot下的平均查找长度 表2中，Ot为装填因子，ASL_seq表示查找由链地址法处理冲突构建的哈希表得到的平均查找长 度，ASLarr表示应用二分查找后的平均查找长度。从表2可见，d值对哈希表查找也有一定的影响，仪 值越大，平均查找长度越大。 3结束语 将二分查找的方法应用到哈希表查找，查找过程与查找原哈希表相比，在不增加消耗的同时降低了 冲突时执行查询的查找长度，从而使查询响应时间更短。本方法在记录数n较大且冲突相对集中的场 合更加适用。 参考文献 ． EfficientHashTable for Performance [1]KumarS，CrowleyP．Se弹nentedHash：An IIigh Implementation NetworkingSubsys- for te】m[C]．Pr／nceton：AssociationComputingMachinery，2005：91—103． M ofPerfect [2]Majewsk／Bs，WormaldC，HavasG，etal．AFamily HashingMethods[J]．TheJournal，1996，39 Computer (6)：547—554。 [3]王果，徐仁佐．结合哈希过滤的一种改进多连接查询优化算法[J]．计算机工程，2004，30(7)：57—59． [4]严蔚敏，吴伟民．数据结构(C语言版)[M]．北京：清华大学出版社，2009：217—221． 965—2966． [5]张朝霞，刘耀军．有效的哈希冲突解决办法[J]．计算机应用，2010，30(11)：2 [6]马如林，蒋华，张庆霞．一种哈希表快速查找的改进方法[J]．计算机工程与科学。2008，30(9)：66—68． MethodofHashTable ImprovedSearching ZHU Fang-fang，LIXun-gen (hodofElectronicInformation，H孵hou Dian五跏啪妙，蚴Ⅱ撕310018，‰) tablehasbeen usedasafast methodindata ordertosearchand Abstract：Hash widely searching query．In method resolvehash ofchain hasbeen toresolvehashcollisionwhen collision，the addressingusuallyadopted ahashtable．Thisme