哈希表在电信公用电话经营分析中的应用_计算机工程与应用.doc

本文收录于2003年12期哈希表在电信公用电话客户流失分析中的应用 马根峰，常文卓 (广东电信公用电话管理中心 广州 510635) 摘要 哈希表是数据结构中的重要概念之一。由于它在记录查找时一次存取便能得到所查记录，所以在经常要进行的大容量数据库表的查询时，显示出相当高的效率。本文首先介绍了哈希表的有关知识，然后介绍了电信公用电话客户流失分析中为了实现合并表所采用的哈希表、冲突解决方法，接着介绍了合并表的处理流程，最后简介了应用中的关键算法。 关键词 哈希表；哈希函数；冲突处理方法 ；关键算法The application of Hash Table in statistics of client lose analyzing in telecommunacation public payphone MA Gen-feng Chang Wen-zhuo (Guangdong Telecommunacation public payphone management center , Guangzhou 510635)ABSTRACT: Hash Table is a important conception of data structure in computer field. Because it can get the record in one times read & write, its very efficient in the query of big table. Firstly the article introduces the interrelated knowledge to Hash Table, then introduces the Hash Table used and method of resolving conflict in the process of building the Hash Table in statistics of client lose analyzing in telecommunacation public payphone, then introduces the flow of uniting two data table in a application. Finally the key algorithm is introduced.KEY WORDS: Hash Table ; Hash function ; method to resolving the conflict; key Algorithm1 引言在电信公用电话的经营分析中，客户流失分析的一个方面是确定不同时期使用电信公话业务（如广东电信的200业务）客户的变化。为了统计各种数据的方便，通常要将两个不同时期发生电信业务（如200业务）时的关系模式R和S进行合并成关系模式T，其中R、S和T分别为R（电话号码,），S（电话号码, ）T（电话号码,存在表,）但是由于关系模式R和S中通常都有上百万个元组，采用常规的方法实现起来算法复杂度都非常大，耗用的时间都太长，所以必须采用特殊的方法来解决上边的问题。在数据结构中有一个重要的概念，那就是哈希表，在解决这类问题上显示出卓越的效率。2 哈希表在折半查找、二叉树查找和B_树查找时，查找的效率依赖于查找过程中所进行的比较次数。而我们期望的情况是希望不经过任何比较，一次存取便能得到所查记录，那就必须在记录的存储位置和它的关键字之间建立一个确定的关系f，使每个关键字和结构中一个唯一的存储位置相对应。因而在查找时，只要根据这个对应关系f找到给定值K的像f（K）。若结构中存在关键字和K相等的记录，则必定在f（K）的存储位置上，由此，不需要进行比较便可直接取得所查记录。这个对应关系f就是哈希函数，按这个思想建立的表为哈希表。3 使用哈希表来进行数据表的合并 3.1 哈希函数的选定哈希表的构造方法很多，常用的方法包括直接定址法、数字分析法、平方取中法、折叠法、除数余数法和随机数法。其中除数余数法是种最简单，也最常用的构造哈希函数的方法。在这里我选用了除数余数法来构造哈希函数，将Rphonenum转换成int64型。P值的选择： 在使用除数余数法时，对P值的选择很重要。若选的不好，容易产生哈希冲突。根据众人的经验，可以选P为质数或不包含小于20的质因数的合数。在本应用中所采用的是寻找一个大质数P，并且P稍大于关系模式R的元组数。这可以在哈希表类中增加一个函数来构造这个大质数P。哈希表长度的确定：由于P稍大于R的元组数，所以可以利用P作为哈希表的长度。 3.2 处理冲突的方法的选定通常用的处理冲突的方法有下面几种，开放定址法、再哈希法、链地址法和建立一个公共溢出区法。在本应用中我采用的是链地址法。因为采用链地址法时，查找成功时的平均查找长度Snc 和不成功时的长度Unc都比较小， 其中=表中填入的记录数/哈希表的长度，在这里3.3 利用哈希表进行合并表的处理流程利用哈希表，我们很容易想到两个不同时期的数据表进行合并的解决方案。具体的处理流程如下图所示：4 关键算法简介4.1 哈希表类type pointer=nodeType; nodeType=record data：int64； next：pointer； end； linkSttp=pointer；THash = class intLenHash：integer； /哈希表的长度 intDataInHash：integer； /哈希表中填入的记录数 HashTbl ：array of linksttp；/采用链地址解决哈希冲突的哈希表 function isExistsInHash(int_var：int64)：boolean；/判断某一电话号码是否存在 constructor Create(ary_data：array of int64)；/创建哈希表 destructor Destroy()； procedure GenerateLenHashtbl(p_RecordCount：integer)；/产生大质数P end；4.2 建立哈希表constructor THash.create(ary_data：array of int64)；var i：integer； intMod：integer； p_hash,p_temp,p_next,：linksttp；begin intDataInHash：=high(ary_data)+1； /设置哈希表中数据的个数 GenerateLenHashtbl(high(ary_data)； / 生成一个比记录个数稍大的素数,也/就是哈希表的长度intLenHash setlength(HashTbl,intLenHash)； for i：=0 to high(ary_data) do begin intMod：=ary_datai mod intLenHash；/用除数余数法构造哈希函数f p_hash：=HashTblintmod； if p_hash=nil then begin new(p_temp)； p_temp.data：=ary_datai； p_temp.next：=nil； HashTblintmod：=p_temp； end else begin p_hash：=p_hash.next； while p_hash nil do begin p_hash：=p_hash.next； end； new(p_temp)； p_temp.data：=ary_datai； p_temp.next：=nil； p_hash.next：=p_temp； end； end；end；4.3 利用哈希表判断Sphonenum是否存在function THash.isExistsInHash(int_var：int64)：boolean；/存在的话返回true，不存在的话返回falsevar intMod：integer； p_hash：linksttp；begin intMod：=int_var mod intLenHash； p_hash：=HashTblintMod； if p_hash=nil then result：=false else begin if p_hash.data=int_var then result：=true else begin p_hash：=p_hash.next； while p_hashnil do begin if p_hash.data =int_var then result：=true； p_hash：=p_hash.next ； end； result：=false； end； end；end；5 结束语 在电信业务领域内，对大容量数据表的处理是经常要进行的。而利用哈希表来进行记录的查找时，一次存取便能得到所查记录，显示出卓越的性能。关于这方面的问题，还需要和大家共同探讨。参考文献： 1 严蔚敏，吴伟民 数据结构 北京：清华大学出版社,1992.62 （美）Steve Teixerira Xavier Pacheco 任旭钧，王永生，冯泽波等译 DELPHI 5 Developers Guide 北京：机械工业出版社20