试谈哈希树数据结构分析

《试谈哈希树数据结构分析》由会员分享，可在线阅读，更多相关《试谈哈希树数据结构分析（35页珍藏版）》请在金锄头文库上搜索。

1、哈希树( HashTree )罗堃 吴朝宏从 2000年开始，作者开始研究基于 TCP/IP 的短信息传输技术。这种技术目前在国际上的标准被成为 SMPP (Short Message Peer to Peer ProtocOl SMPP协 议是一种支持异步传输模式(Asynchronized Transmission Mode)的信息传输方 式。 这种异步方式主要体现在两个地方： 传递信息和等待确认。 在为电信运营商编写软件的过程当中， 解决大容量 (百万用户以上) 要求下的快速查找与匹配成为实现这个系统的核心任务。作者在反复设计整个过程中曾经尝试过很多种方式和算法， 但都未能取得满意的效果

2、。 最终不得不自己开始设计针对这种系统的特殊存储模式。 并在这个过程中，找到了一种比较理想的数据存储结构哈希树(HashTree) 。一、查找算法在各种数据结构(线性表、树等)中，记录在结构中的相对位置是随机的，和记录的关键字之间不存在确定的关系。 因此在机构中查找记录的时需要进行一系列和关键字的比较。这一类的查找方法建立在“比较”的基础上。在顺序查找时，比较的结果为“”与“”两种可能。在折半查找、二叉排序树查找和树查找时，比较的结果为“”、 “”与“”三种可能。查找的效率依赖于查找过程中所进行的比较次数。为确定记录在查找表中的位置， 需和给定值进行比较的关键字个数的期望值成为查找算法在查找成

3、功时的平均查找长度( Average Search Length) 。 下面我们简单讨论一下在含有个数据记录的结构中，各种查找算法的平均查找长度。在等概率的情况下，顺序查找的平均查找长度为：对于折半查找(表要求是顺序表) ，在比较大()的时候，可有以下近似结 果：在随机情况下(二叉树查找可能退化为顺序查找)，对于二叉树，其平均查 找长度为：ASLb 1 4logn在平衡二叉树上进行查找，具平均查找长度为：15 5ASLbb log 5(n 1) 2,其中1-对于一颗m阶的B树，从根节点到关键字所在节点的路径上涉及的节点数 可以说是平均查找长度的上限：.,n 1、,ASLB logm/2( 2)

4、 1总的来说，这些查找算法的效率都将随着数据记录数的增长而下降。仅仅是 有的比较快(时间复杂度为O(n),有的比较慢(时间复杂度是O(logn)而已。 这些查找算法的平均查找长度是在一种比较理想的情况下获得的。在实际应用当中，对数据结构中数据的频繁增加和删除将不断地改变着数据的结构。这些操作将可能导致某些数据结构退化为链表结构，那么其性能必然将下降。为了避免出 现这种情况而采取的调整措施，又不可避免的增加了程序的复杂程度以及操作的 额外时间。二、哈希表理想的情况是希望不经过任何比较，一次存取便能得到所查的记录，那就必须在记的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中

5、一个唯一的存储位置相对应。因而在查找时，只要根据这个对应关系f 找到给定值K的像f(K)。若结构中存在关键字和K相等的记录，则必定在f(K) 的存储位置上，由此，不需要进行比较便可直接取得所查记录。在此，我们称这 个对应关系为哈希(Hash)函数，按这个思想建立的表为哈希表。在哈希表中对于不同的关键字可能得到同一哈希地址，即K1 K2 ,而f(KJ “K2)。这种现象称做冲突(Collision )0在一般情况下，冲突只能尽可能地减少，而不能完全避免。因为哈希函数是从关键字集合到地址集合的映像。通常关键字的集合比较大， 它的元素包括所有可能的关键字， 而地址集合的元素仅为哈希表中的地址值。假设

6、标识符可定义为以字符为首的 8 位字符，则关键字(标识符)的集合大小为C216 C376 7! 1.09338 1012 ，而在一个源程序中出现的数据对象是有限的，设有 10000 个元素。地址集合中的元素为 0 到 9999。因此在一般情况下，哈希函数是一个压缩映像函数，这就不可避免的要产生冲突。二、哈希树的理论基础2.1 质数分辨定理定理 1 ： 选 取 任 意 n 个 互 不 相 同 的 质 数 ： P1 P2P3Pn-1Pn( n N ) ，定义：nMPiP1 P2 P3Pni1设 mk1k2 m M (m, k1,k2N ),那么对于任意的 i 1,n,(k1modp)=(k2 mo

7、d Pi)不可能总成立。证明：假设定理1结结论不正确，那么对于任意的i 1, n , ( k1 mod Pi)=( k2 mod Pi )将总是成立。这个可以表达为：ki团Pih,k2S2iPin,其中SiiSiJiN设：Kk2k1S2iS1iPi0显然， K 是一个合数，而且包含质因素Pi 。根据质数的定义和质因素分解定理， K 可以表达为：KP1 P2 P3Pn 1Pn S M ，其中 S N而另外一方面，根据mk1k2 m M ，可以得出：0 k2 k1 M很明显，这两个结论是相互矛盾的。因此原定理1 正确。这个定理可以简单的表述为： n 个不同的质数可以“分辨”的连续整数的个数和他们的

8、乘积相等。 “分辨”就是指这些连续的整数不可能有完全相同的余数序列。这个为哈希树的分辨方式奠定了理论基础。显然，这个定理的一个特殊情况就是 Pn(n N)为从2起的连续质数。我们可以记Mn为前n个连续质数的乘积。连续10个质数就可以分辨大约M 106469693230个数，已经超过计算机中常用整数(32bit )的表达范围。连续100个质数就可以分辨大约 M 100 4.7119307999061875 10219 。而按照目前的CPU水平，100次取余的整数除法操作几乎不算什么难事。在实际应用中，整体的操作速度往往取决于节点将关键字装载内存的次数和时间。一般来说， 装载的时间是由关键字的大小

9、和硬件来决定的； 在相同类型关键字和相同硬件条件下， 实际的整体操作时间就主要次决于装载的次数。 他们之间是一 个成正比的关系。2.2 余数分辨定理在这里，我们对更为普遍的余数分辨方式做一个讨论。定理 2： 选次任意n 个互不相同的自然数： I1 I2 I3In-1 In( n N ) ， 定义 LCM( Lease Common Multiple) 为 I 1 ， I2， I3， I n-1， In 的最小公倍数。设 m k1k2m LCM ( m, k1,k2N ) ， 那 么 对 于 任 意 的 i 1,n ，(k1modIi) = ( k2modIi)不可能总成立。证明：假设定理2结结

10、论不正确，那么对于任意的i 1, n , (k1modIi)=( k2 modIi )将总是成立。这个可以表达为：k15 Iii,k2S2iIii,其中 Gi,S2iJN设：Kk2k1s2is1iI i 0显然， K 是一个合数，而且包含因素I i 。根据最小公倍数的定义， K 可以表达为：Kk2k1 S LCM LCM ，其中 S N而另外一方面，根据m k1k2m LCM ，可以得出：0k2k1LCM很明显，这两个结论是相互矛盾的。因此原定理2 正确。这个定理 2 可以简单的表述为： n 个不同的数可以“分辨”的连续整数的个数不超过他们的最小公倍数。超过这个范围就意味着冲突的概率会增加。定

11、理1是定理 2 的一个特例。2.3 分辨算法评价标准1 . 状态和特征分辨也即分辨不同的状态。分辨一般是先定义一组不同的状态，然后将这些状态记录下来形成特征。 由这些特征所形成的空间是特征空间。 特征空间的纬数是特征数列的长度。2 . 分辨能力分辨能力 D， 也称分辨范围， 就是指分辨算法可以分辨的最大连续空间大小。在这个范围内， 分辨算法可以唯一确定被分辨数。 即任何两个在分辨范围内的数，不可能具有完全相同的特征数。 这些特征数会以某种形式被记录下来， 或者以数据结构的形式体现出来。对于两个具有相同分辨能力的分辨算法，我们认为他们是等价算法。当 D 的时候， 分辨算法的分辨能力最强。 但是同

12、时分辨算法所使用的特征空间也将是无穷大，我们不可能有足够的空间来存放这些相关特征记录。3 . 冲突概率当被分辨数之间的距离超出分辨范围的时候，就有可能发生冲突，这种冲突 的概率被定义为冲突概率D当被分辨的数是随机分布在整个数轴的时候，两个数之间的距离可能会超过 分辨范围。这个时候分辨算法不一定会完全失效。冲突概率就体现为衡量某种 分辨算法在处理散列时候的特性。冲突概率越小，那么处理散列的能力就越强， 对非连续空间的特征分辨能力就越高； 反之，那么处理散列的能力就越弱，对非 连续空间的特征分辨能力就越低。对于两个具有相同冲突概率的分辨算法，我们也认为他们是等价算法。4 .分辨效率0%分辨能力所有

13、用于分辨的特征个数的乘积根据分辨算法的特点，我们可以定义分辨效率LCM 100%= 100% 100%M在由定理1和定理2可以得知：当用于余数分辨的整数数列是某一个确定整 数，或者互不相等的质数数列的时候， 或者是互相没有公约数的整数数列， 分辨 效率 100% ;其他情况下，分辨效率都小于 100%。5 .简化度在分辨算法中，我们定义数列的简化度为:所有用于分辨的特征个数的和所有用于分辨的特征个数的和，代表了分辨所需要的特征总数。特征总数越 少，那么简化度就越高。分辨算法的简化度越高，说明所用状态数越少，分辨过 程将能更简单。这个评价标准有利于我们去除冗余特征的部分。定理3：在相同分辨范围条

14、件下的余数分辨算法中，所有分辨效率100%的分辨数列的简化度都小于分辨效率=100%的分辨数列的简化度。证明：分辨效率100%意味着用于分辨的整数数列中，肯定存在某两个整数有约数(否则他们的乘积就是他们的最小公倍数，那么分辨效率 =100%)。这个约数我们称它为这两个数之间的最大公约数GCD ( Greatest CommonDivisor)。不妨设这两个整数为：I1Q1GCD, I2Q2GCD,其中Q11,Q21,GCD 1显然如果用Q1代替I1 ,将不会影响这些整数之间的最小公倍数 LCM。一方面，这些整数的积得到了减少，分辨效率将有所提高；另外一方面，这些整数的 和得到了减少，简化度也因

15、此而提到。通过反复简化操作这个数列的分辨效率总可以达到100%1:分辨效率100%的分辨数列总可以简化，而且可以简化成分辨效率 =100%的分辨数列。6 .综合评价指标我们定义分辨算法综合评价指标_ D二特征空间纬数这个标准意味着：分辨范围越大，简化度越高，那么这个算法的综合性能就越好。例如：在余数分辨法中，如果我们选择数列100,200,300作为分辨数列,那么采取这个数列的余数分辨算法各项指标如下:D LCM 6001 0.001667 600LCM 0.00001 100 200 3000.001667100 200 300D 0.3333331如果我们选择数列2,3,5,711作为分辨数列，那么采取这个数列的余数分辨算法各项指标如下:D LCM123102310100%14.32 10 42 3 5 7 11D0.0357116.5显然后者在综合评价方面要优于前者。2.4 线性分辨算法线性分辨算法是利用线性函数f(x) ax b作为分辨算法的分辨算法，或者 称为余数