哈希技术在广东电信公话200话单处理中的应用_广东通信技术.docVIP

本文收录于广东通信技术 2003年7期 哈希技术在广东电信公话200话单处理中的应用 马根峰 (广东电信公用电话管理中心 广州 510635) 摘要 在电信领域，处理上亿条记录的大型话单文件是经常的。如何对大型文件按照一些指标（如电话号码，卡号）进行统计，这是一件相当复杂的工作。而哈希表是数据结构中的重要概念之一，由于它在记录查找时一次存取便能得到所查记录，所以在电信领域中对大型话单文件进行处理时，显示出相当高的效率。本文首先介绍了哈希表的有关知识，然后介绍了广东电信公用电话200话单处理中为了实现话单统计所采用的哈希表、冲突解决方法，接着介绍了话单处理的流程，最后简介了应用中的关键算法。 关键词 哈希表；哈希函数；冲突处理方法 ；关键算法 The application of Hash Table in statistics of client lose analyzing in Public Payphone Center, Guangdong Telecom Corporation MA Gen-feng (Public Payphone Center, Guangdong Telecom Corporation, Guangzhou 510635) ABSTRACT: Hash Table is a important conception of data structure in computer field. Because it can get the record in one time’s read write, it’s 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 Algorithm 1 引言 公用电话业务是广东电信业务的一个重要部分，而200卡类业务则是广东电信公话中的一个举足轻重的业务，对200话务的分析因而显得非常重要。话务分析的依据是话机发生200业务的各项指标（如按本地、国内和国际流向的通话次数、计费时长和通话费用）和200卡发生的话务（卡属地通话费、卡异地通话费）。每个月如何对二十几GB的几十个话单文件中2至3亿条话单进行统计，形成几百万台话机使用200业务的情况和近二千万张200卡发生的话务，这是一件艰巨的工作。将话单文件直接入数据库进行处理是不可行的。在数据结构中有一个重要的概念，那就是哈希表，在解决这类问题上显示出卓越的效率。笔者利用哈希技术，在PC机上使用DELPHI编写了两个程序。 其中的一个运行了50分钟就完成了对20多GB话单文件的处理，生成了全省三百多万部电话使用200业务的情况，然后用了十几分钟将话务信息入库；另一个运行了70分钟就完成了全省1900多万张200卡话务信息的统计，然后用了五十多分钟将统计结果入库。 2 哈希表 在折半查找、二叉树查找和B_树查找时，查找的效率依赖于查找过程中所进行的比较次数。而我们期望的情况是希望不经过任何比较，一次存取便能得到所查记录，那就必须在记录的存储位置和它的关键字之间建立一个确定的关系f，使每个关键字和结构中一个唯一的存储位置相对应。因而在查找时，只要根据这个对应关系f找到给定值K的像f（K）。若结构中存在关键字和K相等的记录，则必定在f（K）的存储位置上，由此，不需要进行比较便可直接取得所查记录。这个对应关系f就是哈希函数，按这个思想建立的表为哈希表。 3 使用哈希表来进行数据表的合并 3.1 哈希函数的选定 哈希表的构造方法很多，常用的方法包括直接定址法、数字分析法、平方取中法、折叠法、除数余数法和随