第1页共22页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第1页共22页哈希树（HashTree）罗堃吴朝宏从2000年开始，作者开始研究基于TCP/IP的短信息传输技术。这种技术目前在国际上的标准被成为SMPP（ShortMessagePeertoPeerProtocol）。SMPP协议是一种支持异步传输模式（AsynchronizedTransmissionMode）的信息传输方式。这种异步方式主要体现在两个地方：传递信息和等待确认。在为电信运营商编写软件的过程当中，解决大容量（百万用户以上）要求下的快速查找与匹配成为实现这个系统的核心任务。作者在反复设计整个过程中曾经尝试过很多种方式和算法，但都未能取得满意的效果。最终不得不自己开始设计针对这种系统的特殊存储模式。并在这个过程中，找到了一种比较理想的数据存储结构——哈希树（HashTree）。一、查找算法在各种数据结构（线性表、树等）中，记录在结构中的相对位置是随机的，和记录的关键字之间不存在确定的关系。因此在机构中查找记录的时需要进行一系列和关键字的比较。这一类的查找方法建立在“比较”的基础上。在顺序查找时，比较的结果为“=”与“¿”两种可能。在折半查找、二叉排序树查找和B−树查找时，比较的结果为“¿”、“=”与“¿”三种可能。查找的效率依赖于查找过程中所进行的比较次数。为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值成为查找算法在查找成功时的平均查找长度（AverageSearchLength）。下面我们简单讨论一下在含有n个数据记录的结构中，各种查找算法的平均查找长度。第2页共22页第1页共22页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第2页共22页在等概率的情况下，顺序查找的平均查找长度为：ASLss=n+12对于折半查找（表要求是顺序表），在n比较大（n>50）的时候，可有以下近似结果：ASLbs=log2(n+1)−1在随机情况下（二叉树查找可能退化为顺序查找），对于二叉树，其平均查找长度为：ASLb=1+4logn在平衡二叉树上进行查找，其平均查找长度为：ASLbb=logϕ(√5(n+1))−2，其中ϕ=1+√52对于一颗m阶的B−树，从根节点到关键字所在节点的路径上涉及的节点数可以说是平均查找长度的上限：ASLB−≤logm/2(n+12)+1总的来说，这些查找算法的效率都将随着数据记录数的增长而下降。仅仅是有的比较快（时间复杂度为O(n)），有的比较慢（时间复杂度是O(logn)）而已。这些查找算法的平均查找长度是在一种比较理想的情况下获得的。在实际应用当中，对数据结构中数据的频繁增加和删除将不断地改变着数据的结构。这些操作将可能导致某些数据结构退化为链表结构，那么其性能必然将下降。为了避免出现这种情况而采取的调整措施，又不可避免的增加了程序的复杂程度以及操作的额外时间。二、哈希表理想的情况是希望不经过任何比较，一次存取便能得到所查的记录，那就第3页共22页第2页共22页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第3页共22页必须在记的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。因而在查找时，只要根据这个对应关系f找到给定值K的像f(K)。若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上，由此，不需要进行比较便可直接取得所查记录。在此，我们称这个对应关系为哈希（Hash）函数，按这个思想建立的表为哈希表。在哈希表中对于不同的关键字可能得到同一哈希地址，即K1≠K2，而f(K1)=f(K2)。这种现象称做冲突（Collision）。在一般情况下，冲突只能尽可能地减少，而不能完全避免。因为哈希函数是从关键字集合到地址集合的映像。通常关键字的集合比较大，它的元素包括所有可能的关键字，而地址集合的元素仅为哈希表中的地址值。假设标识符可定义为以字符为首的8位字符，则关键字（标识符）的集合大小为C261×C367×7!≃1.09338×1012，而在一个源程序中出现的数据对象是有限的，设有10000个元素。地址集合中的元素为0到9999。因此在一般情况下，哈希函数是一个压缩映像函数，这就不可避免的要产生冲突。二、哈希树的理论基础2.1质数分辨定理定理1：选取任意n个互不相同的质数...
