哈希表在电信公用电话经营分析中的应用

《哈希表在电信公用电话经营分析中的应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、哈希表在电信公用电话客户流失分析中的应用马根峰，常文卓(广东电信公用电话管理中心广州510635)摘要哈希表是数据结构中的重要概念之一。由于它在记录查找时一次存取便能得到所查记录，所以在经常要进行的大容量数据库表的查询时，显示出相当高的效率。本文首先介绍了哈希表的有关知识，然后介绍了电信公用电话客户流失分析中为了实现合并表所采用的哈希表、冲突解决方法，接着介绍了合并表的处理流程，最后简介了应用中的关键算法。关键词哈希表；哈希函数；冲突处理方法；关键算法TheapplicationofHashTableinstatisticsofclientloseanalyzi

2、ngintelecommunacationpublicpayphoneMAGen-fengChangWen-zhuo(GuangdongTelecommunacationpublicpayphonemanagementcenter,Guangzhou510635)ABSTRACT:HashTableisaimportantconceptionofdatastructureincomputerfield.Becauseitcangettherecordinonetime’sread&write,it’sveryefficientinthequeryofbigtab

3、le.FirstlythearticleintroducestheinterrelatedknowledgetoHashTable,thenintroducestheHashTableusedandmethodofresolvingconflictintheprocessofbuildingtheHashTableinstatisticsofclientloseanalyzingintelecommunacationpublicpayphone,thenintroducestheflowofunitingtwodatatableinaapplication.Fi

4、nallythekeyalgorithmisintroduced.KEYWORDS:HashTable;Hashfunction;methodtoresolvingtheconflict;keyAlgorithm1引言在电信公用电话的经营分析中，客户流失分析的一个方面是确定不同时期使用电信公话业务（如广东电信的200业务）客户的变化。为了统计各种数据的方便，通常要将两个不同时期发生电信业务（如200业务）时的关系模式R和S进行合并成关系模式T，其中R、S和T分别为R（电话号码,），S（电话号码,）T（电话号码,存在表,）但是由于关系模式R和S中通常都有上百万个元

5、组，采用常规的方法实现起来算法复杂度都非常大，耗用的时间都太长，所以必须采用特殊的方法来解决上边的问题。在数据结构中有一个重要的概念，那就是哈希表，在解决这类问题上显示出卓越的效率。2哈希表在折半查找、二叉树查找和B_树查找时，查找的效率依赖于查找过程中所进行的比较次数。而我们期望的情况是希望不经过任何比较，一次存取便能得到所查记录，那就必须在记录的存储位置和它的关键字之间建立一个确定的关系f，使每个关键字和结构中一个唯一的存储位置相对应。因而在查找时，只要根据这个对应关系f找到给定值K的像f（K）。若结构中存在关键字和K相等的记录，则必定在f（K）的存储位置上

6、，由此，不需要进行比较便可直接取得所查记录。这个对应关系f就是哈希函数，按这个思想建立的表为哈希表。3使用哈希表来进行数据表的合并3.1哈希函数的选定哈希表的构造方法很多，常用的方法包括直接定址法、数字分析法、平方取中法、折叠法、除数余数法和随机数法。其中除数余数法是种最简单，也最常用的构造哈希函数的方法。在这里我选用了除数余数法来构造哈希函数，将R[phonenum]转换成int64型。P值的选择：在使用除数余数法时，对P值的选择很重要。若选的不好，容易产生哈希冲突。根据众人的经验，可以选P为质数或不包含小于20的质因数的合数。在本应用中所采用的是寻找一个大质

7、数P，并且P稍大于关系模式R的元组数。这可以在哈希表类中增加一个函数来构造这个大质数P。哈希表长度的确定：由于P稍大于R的元组数，所以可以利用P作为哈希表的长度。3.2处理冲突的方法的选定通常用的处理冲突的方法有下面几种，开放定址法、再哈希法、链地址法和建立一个公共溢出区法。在本应用中我采用的是链地址法。因为采用链地址法时，查找成功时的平均查找长度Snc和不成功时的长度Unc都比较小，其中=表中填入的记录数/哈希表的长度，在这里3.3利用哈希表进行合并表的处理流程利用哈希表，我们很容易想到两个不同时期的数据表进行合并的解决方案。具体的处理流程如下图所示：4关键算

8、法简介4.1哈希表类ty