区间表的快速查找算法马根峰(广东电信公用电话管理中心广州510635)摘要区间表（表中每一元素表示的是一个范围的数据）的查找是一个常见的问题，在表的长度较小或要查找元素的数量不多的情况下，折半查找是一种不错并且容易实现的算法。但在某些特殊的行业（如电信业）由于要对长度较大的表进行数量巨大的元素的查找，我们就不得不考虑它的执行效率了。笔者在广东电信公用电话管理中心从事的”签约分销商售卡话务”统计中，巧用哈希表来实现大量数据在众多签约分销商售卡记录中的数据查找，将整个查找的总长度较折半查找降低了一个数量级，大大提高了数据查找的效率。关键词折半查找；哈希表；查找长度；算法FastLookupalgorithmfortablewithelementbetweenextentMAGen-feng(PublicPayphoneCenter,GuangdongTelecomCorporation,Guangzhou510635)ABSTRACT:It’sausualquestiontosearchinthetablewithrecordsinwhicheveryelementisinsomeextent.Inthecaseoffewrecordsinthetableorfewelementtobesearched,BinarySearchisproperalgorithmandalsoiseasilyprogrammed.Butinthespecialtradeforexampleinthetelecom,asit’srequiredtoprocessplentyofelement’ssearchingintableswithmanyrecords,sowehavetoconsidertheefficiencyofBinarySearchalgorithm.IntheprocessofstatisticofthechargeforphoneofthephonecardsoldbythemerchantswhohavecontractwithPublicPayphoneCenter,GuangdongTelecomCorporation,IuseHashskillfullytorealizethesearchofplentyofphonecardreadfromthefilesinthetableswithmanyrecordsaccordingtothephonecardsoldbythosemerchants.ThetotallengthofsearchisreducedaboutdecuplecomparedwithBinarySearchandtheefficiencyisgreatlyimproved.KEYWORDS:BinarySearch;Hash;SearchLength;Algorithm1引言数据的查找或检索是一个常见的问题，并且在数据结构中都有比较常规的查找算法。但对于查找表中的元素表示的是一区间内的数据，并且要对它进行大量的查找（如几亿次）时，如何对它进行快速的查找，这就是一个比较复杂的问题。如笔者在广东电信公用电话管理中心从事的”签约分销商售卡所发生话务的统计”中，经过对”卡管理系统”中6个数据表整合后产生的关系模式R（分销商名,售卡种类,售卡数量,起始卡号,结束卡号,本地话费,漫游话费,充值次数,充值金额,地区名,地区,出库日期）、全省200业务的话单文件格式S（卡号,发话地,被叫号码,┅,话费合计）。通常的解决方案是采用折半查找，对话单中的每条记录取其卡号，通过折半查找来判断该卡是否在签约分销商所销售的卡区间。但是签约分销商的售卡记录有3000多条，一个月全省200业务的话单就有近3亿条之多，在这种情况下折半查找的总长度就在30亿左右，折半查找的效率就成了问题。笔者在实际中采取将售卡区间转变成多个售卡卡号，然后利用哈希表来进行查找，大大降低了查找的总长度，体现出了相当高的效率。2折半查找对于签约分销商售卡互不重合的记录表TYPERec_Card=RECORDId:integer;//从0开始、增量为1的整数序列Saler:string;CardType:string;CardNum:integer;CardStart:integer;CardEnd:integer;┅END;Card_List：ARRAYOFRec_Card;注：Rec_Card的Id通过从数据库中取得关系模式R的所有记录时获得；增加Id属性的目的是与动态数组的下标对应。在将其按照CardStart与CardEnd进行排序后，进行折半查找的平均查找长度为：对于查找表中每个元素（或记录）的查找概率相等（）的情况下，其平均查找长度为：对任意的n，当n较大（n>50）时，可有下列近似结果而对于签约分销商售卡记录来，n为3000多条，平均查找长度约为10；另一方面，全省每个月200业务的话单有3亿条左右。因此，处理一个月签约分销商销售的卡所发生的话务情况，大致需要进行30亿次的查找。而用哈希表进行查找，则可以大大降低查找的总长度。3哈希查找3.1哈希函数的选定哈希表的构造方法很多，常用的方法包括直接定址法、数字分析法、平方取中法、折叠法、除数余数法和随机数法。其中除数余数法是种最简单，也最常用的构造哈希函数的方法。在这里我选用了除数余数...
