区间表的快速查找算法

本文发表于中文核心刊物《计算机工程与设计》2005年第4期。

<wbr></wbr>

<wbr></wbr>

<wbr></wbr>

区间表的快速查找算法

马根峰<wbr><wbr></wbr></wbr>

<wbr><wbr><wbr><wbr> (广东电信公用电话管理中心<wbr> 广州 510635)</wbr></wbr></wbr></wbr></wbr>

摘要<wbr><wbr><wbr><wbr> 区间表（表中每一元素表示的是一个范围的数据）的查找是一个常见的问题，在表的长度较小或要查找元素的数量不多的情况下，折半查找是一种不错并且容易实现的算法。但在某些特殊的行业（如电信业）由于要对长度较大的表进行数量巨大的元素的查找，我们就不得不考虑它的执行效率了。笔者在广东电信公用电话管理中心从事的”签约分销商售卡话务”统计中，巧用哈希表来实现大量数据在众多签约分销商售卡记录中的数据查找，将整个查找的总长度较折半查找降低了一个数量级，大大提高了数据查找的效率。</wbr></wbr></wbr></wbr>

关键词<wbr><wbr><wbr> 折半查找；哈希表；查找长度；算法<wbr><wbr></wbr></wbr></wbr></wbr></wbr>

<wbr></wbr>

<wbr> Fast Lookup algorithm for table with element between extent</wbr>

<wbr>MA Gen-feng<wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr>

^<wbr></wbr>(Public Payphone Center, Guangdong Telecom Corporation, Guangzhou 510635)

ABSTRACT:<wbr></wbr> It’s a usual question to search in the table with records in which every element is in some extent. In the case of few records in the table or few element to be searched, Binary Search is proper algorithm and also is easily programmed. But in the special trade for example in the telecom, as it’s required to process plenty of element’s searching in tables with many records, so we have to consider the efficiency of Binary Search algorithm. In the process of statistic of the charge for phone of the phone card sold by the merchants who have contract with Public Payphone Center, Guangdong Telecom Corporation, I use Hash skillfully to realize the search of plenty of phone card read from the files in the tables with many records according to the phone card sold by those merchants. The total length of search is reduced about decuple compared with Binary Search and the efficiency is greatly improved.

KEY WORDS: Binary Search; Hash; Search Length; Algorithm

<wbr></wbr>

<wbr></wbr>

1<wbr><wbr> 引言</wbr></wbr>

<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>数据的查找或检索是一个常见的问题，并且在数据结构中都有比较常规的查找算法。但对于查找表中的元素表示的是一区间内的数据，并且要对它进行大量的查找（如几亿次）时，如何对它进行快速的查找，这就是一个比较复杂的问题。如笔者在广东电信公用电话管理中心从事的”签约分销商售卡所发生话务的统计”中，经过对”卡管理系统”中6个数据表整合后产生的关系模式R（分销商名,售卡种类,售卡数量,起始卡号,结束卡号,本地话费,漫游话费,充值次数,充值金额,地区名,地区,出库日期）、全省200业务的话单文件格式S（卡号, 发话地,被叫号码,┅,话费合计）。通常的解决方案是采用折半查找，对话单中的每条记录取其卡号，通过折半查找来判断该卡是否在签约分销商所销售的卡区间。但是签约分销商的售卡记录有3000多条，一个月全省200业务的话单就有近3亿条之多，在这种情况下折半查找的总长度就在30亿左右，折半查找的效率就成了问题。笔者在实际中采取将售卡区间转变成多个售卡卡号，然后利用哈希表来进行查找，大大降低了查找的总长度，体现出了相当高的效率。

<wbr></wbr>

<wbr></wbr>

2<wbr><wbr><wbr> 折半查找</wbr></wbr></wbr>

<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>对于签约分销商售卡互不重合的记录表

<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>TYPE Rec_Card=RECORD

<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>Id:integer;<wbr> //从0开始、增量为1的整数序列</wbr>

<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>Saler:string;

<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>CardType:string;

<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>CardNum:integer;

<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>CardStart:integer;

<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>CardEnd:integer;

<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>┅

<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>END;

<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>Card_List：ARRAY OF Rec_Card;

<wbr></wbr>

<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>注：

<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>Rec_Card的Id通过从数据库中取得关系模式R的所有记录时获得；增加Id属性的目的是与动态数组的下标对应。

在将其按照CardStart与CardEnd进行排序后，进行折半查找的平均查找长度为：

<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>对于查找表中每个元素（或记录）的查找概率相等（ ）的情况下，其平均查找长度为：

<wbr></wbr>

<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>对任意的n，当n较大（n>50）时，可有下列近似结果

<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><img src="http://hi.csdn.net/attachment/201203/16/0_1331910029TU7H.gif" alt=""><wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>

<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>而对于签约分销商售卡记录来，n为3000多条，平均查找长度约为10；另一方面，全省每个月200业务的话单有3亿条左右。因此，处理一个月签约分销商销售的卡所发生的话务情况，大致需要进行30亿次的查找。而用哈希表进行查找，则可以大大降低查找的总长度。

<wbr></wbr>

<wbr></wbr>

3<wbr><wbr><wbr> 哈希查找</wbr></wbr></wbr>

<wbr></wbr>

3.1<wbr><wbr> 哈希函数的选定</wbr></wbr>

<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>哈希表的构造方法很多，常用的方法包括直接定址法、数字分析法、平方取中法、折叠法、除数余数法和随机数法。其中除数余数法是种最简单，也最常用的构造哈希函数的方法。在这里我选用了除数余数法来构造哈希函数，将关系模式R中的11位的200卡起始卡号、结束卡号转换成int64型，这个int64型整数除以一个大质数P所得的余数即为卡号所对应的哈希值。

<wbr></wbr>

3.2<wbr><wbr> P值的选择</wbr></wbr>

<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>在使用除数余数法时，对P值的选择很重要。若选的不好，容易产生哈希冲突。根据众人的经验，可以选P为质数或不包含小于20的质因数的合数。由于签约分销商售卡数量为近1500万，考虑到系统的扩充性，在实际中选择了稍大于3000万的一个大质数作为P值。

<wbr></wbr>

3.3<wbr><wbr><wbr>哈希表长度的确定</wbr></wbr></wbr>

<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>考虑到应尽量避免哈希冲突，所以用P作为哈希表的长度。

<wbr></wbr>

3.4<wbr><wbr> 处理冲突的方法的选定</wbr></wbr>

<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>通常用的处理冲突的方法有下面几种，开放定址法、再哈希法、链地址法和建立一个公共溢出区法。在本应用中我采用的是链地址法。在链地址法中，将所有哈希值相同的记录存储在同一线性链表中，见下图1用链地址法处理冲突的哈希表示意。

<wbr></wbr>

<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>而且采用链地址法时，查找成功时的平均查找长度S_nc 和不成功时的长度U_nc都比较小，

<wbr><wbr></wbr></wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><img src="http://hi.csdn.net/attachment/201203/16/0_1331910085iqm6.gif" alt=""><img src="http://hi.csdn.net/attachment/201203/16/0_13319101001b4X.gif" alt=""></wbr></wbr></wbr></wbr></wbr></wbr></wbr>

<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>其中 a=表中填入的记录数/哈希表的长度，由于哈希表中填入的记录数据签约分销产售卡的数量，所以在这里

<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><img src="http://hi.csdn.net/attachment/201203/16/0_1331910120hZmi.gif" alt=""></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>

3.5<wbr><wbr> 哈希表的数据结构与构造算法</wbr></wbr>

<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>Type<wbr> Pointer_Hash=^Hash_Node;</wbr>

<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr> Hash_Node=RECORD

<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr> Card:int64;

<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr> Id:integer;

<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr> Next:Pointer_Hash;

<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr> END;

<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>Hash_List：ARRAY [1..P] OF Pointer_Hash;

注：

<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>Hash_Node中的Id为关系模式R中的ID值

<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>哈希表的构造过程如下算法及流程图2所示：

⑴<wbr> 从数据库中打开关系模式R的记录集；</wbr>

⑵<wbr> 记录集为空，则跳转到⑿；</wbr>

⑶<wbr> 根据记录集的长度来设置动态数组Card_List，根据记录集的值来设置动态数组Card_List的值；</wbr>

⑷<wbr> Low(Card_list) →i；</wbr>

⑸<wbr> Card_List[I].CardStart→iCardStart，Card_List[I].CardEnd→iCardEnd；</wbr>

⑹<wbr> iCardStart→j；</wbr>

⑺<wbr> 判断哈希表Hash_List中是否存在结点j，不存在则建立该结点；</wbr>

⑻<wbr> j+1→j；</wbr>

⑼<wbr> 如果j&lt;= iCardEnd，则跳转到⑺；</wbr>

⑽<wbr> i+1→i</wbr>

⑾<wbr> i&lt;=High(Card_list)，则跳转到⑸；</wbr>

⑿<wbr> 退出；</wbr>

<wbr></wbr>

<wbr></wbr>

3.6<wbr><wbr> 签约分销商售卡话务统计的总流程及查找的总长度</wbr></wbr>

<wbr></wbr>

3.6.1<wbr><wbr> 用哈希表进行售卡话务统计的总流程如图3所示：</wbr></wbr>

<wbr></wbr>

3.6.2<wbr><wbr><wbr> 查找的总长度</wbr></wbr></wbr>

<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>采用哈希技术来统计签约分销商售卡话务时的查找总长度包括三部分：一是对动态数组Card_List中各元素建立哈希表Hash_List时查找成功或不成功的长度；二是对话单处理时，在哈希表Hash_List中对每条话单中的200卡号在哈希表中进行查找时成功查找的长度或不成功查找的长度；三是在二查找成功时在签约分销商售卡表Card_List中查找该卡属的售卡记录的次数。具体总长度计算如下：

A、建立哈希表Hash_List时：

<wbr><wbr><wbr><wbr><wbr><wbr> 由于各分销商所销售的卡不存在重合，所以不存在查找成功的长度，查找不成功的总长度为：</wbr></wbr></wbr></wbr></wbr></wbr>

<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr> 售卡数量*a=1500万*a=750万</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>

B、处理话单时：

<wbr><wbr><wbr><wbr><wbr> 由于一个月中200话单大致在3亿条，所以</wbr></wbr></wbr></wbr></wbr>

<wbr><wbr><wbr><wbr><wbr>查找的总长度最大值为全部成功查找时的长度，3亿*（1+a/2）=3.11亿</wbr></wbr></wbr></wbr></wbr>

<wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr>查找的总长度最小值为全部不成功查找时的长度，3亿*a=1.5亿

<wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr>查找的总长度平均值为2.31亿

C、在B查找成功时在签约分销商售卡表Card_List中查找该卡属的售卡记录：

<wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr>在B查找成功时，得到结点的Id值，而这个Id在构造时由于采用的是Card_list数组的下标，所以这一步的查找长度为1，所以总的查找长度为B中查找成功的总长度。显然其最大值为3.11亿，最小值为0，平均值为1.55亿。

<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>

总之，整个处理过程的最大总查找长度约为750万+3.11亿+3.11亿=6.276亿；最小总查找长度约为750万+1.5亿=1.575亿；平均总查找长度约为750万+2.31亿+1.55亿=3.935亿；

<wbr></wbr>

<wbr></wbr>

<wbr></wbr>

4<wbr><wbr> 结束语</wbr></wbr>

<wbr><wbr><wbr><wbr> 折半查找是对有序表（包括有序区间表）进行数据查找或检索中的一种见算法，在表的长度较小或要查找元素的数量不多的情况下，由于对所有要查找的元素进行查找时的总长度的数量级较小，加上它的易实现特点，所以在实际中得到了广泛地应用。但在表的长度较大或要查找的元素较多时，尤其是对长度较大的表进行数量巨大的元素的查找时，我们就不得不考虑它的执行效率了。笔者提出的将区间表中的元素变成许多单个元素、然后用哈希表来进行数据查找的方法，将整个查找的总长度较折半查找降低了一个数量级，大大提高了数据查找的效率。</wbr></wbr></wbr></wbr>

<wbr></wbr>

<wbr></wbr>

[参考文献]<wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr>

<wbr> [1]<wbr><wbr> 严蔚敏，吴伟民<wbr> · 数据结构<wbr> · 北京：清华大学出版社，1992</wbr></wbr></wbr></wbr></wbr>

<wbr> [2]<wbr> （美）Steve Teixerira Xavier Pacheco 任旭钧，王永生，冯泽波等译<strong>.</strong>DELPHI 5 Developer’s Guide<strong>.</strong>北京：机械工业出版,2000.7,16-72</wbr></wbr>