试谈哈希树Hashree数据结构

哈希树（HashTree）罗堃吴朝宏从2000年开始，作者开始研究基于TCP/IP的短信息传输技术。这种技术目前在国际上的标准被成为SMPP（ShortMessagePeertoPeerProtocol）。SMPP协议是一种支持异步传输模式（AsynchronizedTransmissionMode）的信息传输方式。这种异步方式主要体现在两个地方：传递信息和等待确认。在为电信运营商编写软件的过程当中，解决大容量（百万用户以上）要求下的快速查找与匹配成为实现这个系统的核心任务。作者在反复设计整个过程中曾经尝试过很多种方式和算法，但都未能取得满意的效果。最终不得不自己开始设计针对这种系统的特殊存储模式。并在这个过程中，找到了一种比较理想的数据存储结构——哈希树（HashTree）。一、查找算法在各种数据结构（线性表、树等）中，记录在结构中的相对位置是随机的，和记录的关键字之间不存在确定的关系。因此在机构中查找记录的时需要进行一系列和关键字的比较。这一类的查找方法建立在“比较”的基础上。在顺序查找时，比较的结果为“”与“”两种可能。在折半查找、二叉排序树查找和树查找时，比较的结果为“”、“”与“”三种可能。查找的效率依赖于查找过程中所进行的比较次数。为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值成为查找算法在查找成功时的平均查找长度（AverageSearchLength）。下面我们简单讨论一下在含有个数据记录的结构中，各种查找算法的平均查找长度。在等概率的情况下，顺序查找的平均查找长度为：对于折半查找（表要求是顺序表），在比较大（）的时候，可有以下近似结果：在随机情况下（二叉树查找可能退化为顺序查找），对于二叉树，其平均查找长度为：在平衡二叉树上进行查找，其平均查找长度为：，其中对于一颗阶的树，从根节点到关键字所在节点的路径上涉及的节点数可以说是平均查找长度的上限：总的来说，这些查找算法的效率都将随着数据记录数的增长而下降。仅仅是有的比较快（时间复杂度为），有的比较慢（时间复杂度是）而已。这些查找算法的平均查找长度是在一种比较理想的情况下获得的。在实际应用当中，对数据结构中数据的频繁增加和删除将不断地改变着数据的结构。这些操作将可能导致某些数据结构退化为链表结构，那么其性能必然将下降。为了避免出现这种情况而采取的调整措施，又不可避免的增加了程序的复杂程度以及操作的额外时间。二、哈希表龟碧理想的情况径是希望不经启过任何比较似，一次存取桥便能得到所赚查的记录，挠那就必须在炒记的存储位搂置和它的关润键字之间建标立一个确定三的对应关系罪，使每个关较键字和结构短中一个唯一漠的存储位置糟相对应。因敌而在查找时衡，只要根据朋这个对应关涉系贝找到给定值酒的像训。若结构中淋存在关键字茫和纠相等的记录惕，则必定在婶的存储位置枯上，由此，第不需要进行轰比较便可直创接取得所查辱记录。在此洲，我们称这城个对应关系宋为哈希（H妻ash）函干数，按这个衫思想建立的尼表为哈希表逢。壶雷在哈希表中设对于不同的纲关键字可能畅得到同一哈掉希地址，即劝，而腹。这种现象伞称做冲突（患Colli蜜sion）狸。在一般情备况下，冲突畅只能尽可能胁地减少，而挎不能完全避船免。因为哈辨希函数是从询关键字集合悲到地址集合林的映像。通韵常关键字的停集合比较大狱，它的元素淹包括所有可厅能的关键字坏，而地址集塔合的元素仅举为哈希表中翼的地址值。绘糊假设标识符情可定义为以滨字符为首的锐8位字符，导则关键字（咳标识符）的做集合大小为居，而在一个贤源程序中出榆现的数据对扣象是有限的宁，设有10优000个元由素。地址集击合中的元素睡为0到99葛99。因此属在一般情况毒下，哈希函府数是一个压金缩映像函数耳，这就不可狂避免的要产筑生冲突。烧二、哈希树御的理论基础炸2.1质数眼分辨定理证疫定理1亲：抹选取任意摄个互不相同担的质数：绍（谈），定义：陡蓝设素（疫），那么对恭于任意的客，（才）＝（招）不可能总党成立。阀嘉证明博：假设定理陵1的结论不唱正确，那么破对于任意的瘦，（其）＝（收）将总是成喜立。这个可击以表达为：设：硬努显然，斑是一个合数脑，而且包含观质因素串。根据质数迈的定义和质确因素分解定捡理，惩可以表达为伏：兔脾而另外一方队面，根据厕，可以得出晓：讯闭很明显，这斧两个结论是严相互矛盾的涝。因此原定品理1正确。搏爷这个定理可状以简单的表园述为：丛个不同的质端数可以抹“若分辨炎”址的连续整数惨的个数和他葡们的乘积相匠等。耀“氧分辨诱”交就是指这些缺连续的整数遍不可能有完鹿全相同的余如数序列。这胆个为哈希树嗓的分辨方式祸奠定了理论个基础。父显然，这个赚定理的一个轰特殊情况就燥是步为从2起的亚连续质数。竹我们可以记雁为前轻个连续质数氏的乘积。连逢续10个质碧数就可以分御辨大约剩个数，已经欠超过计算机卧中常用整数炸（32bi觉t）的表达井范围。连续严100个质妈数就可以分永辨大约肝。午而按照目前纠的CPU水演平，100曲次取余的整编数除法操作弃几乎不算什煮么难事。在附实际应用中疑，整体的操遵作速度往往叫取决于节点浪将关键字装甲载内存的次巾数和时间。休一般来说，所装载的时间资是由关键字般的大小和硬膀件来决定的涂；在相同类蛇型关键字和界相同硬件条替件下，实际尸的整体操作邮时间就主要击取决于装载煌的次数。他男们之间是一返个成正比的疲关系。逃2.2余数交分辨定理竞搅在这里，我箭们对更为普络遍的余数分末辨方式做一态个讨论。略定理2业：愧选取任意菌个互不相同碧的自然数：杏（额），定义L揉CM（L因ease窗C刑ommon膨好M卖ultip从le中）为乎的最小公倍砌数。炸城设烤（东），那么对市于任意的抄，（债）＝（畏）不可能总稼成立。蜻匀证明骆：假设定理借2的结论不败正确，那么乳对于任意的衬，（且）＝（绘）将总是成株立。这个可吊以表达为：设：肝赔显然，吃是一个合数自，而且包含籍因素乞。根据最小华公倍数的定赏义，头可以表达为速：干搏而另外一方蹈面，根据食，可以得出筋：郊墨很明显，这蹦两个结论是吵相互矛盾的五。因此原定译理2正确。汁这个定理2弄可以简单的故表述为：排个不同的数摊可以寺“竹分辨厦”机的连续整数穷的个数不超雷过他们的最校小公倍数。畅超过这个范甘围就意味着这冲突的概率洽会增加。定尊理1是定理恳2的一个特滨例。准2.3分辨俗算法评价标嘉准状态和特征爹分辨也即分箭辨不同的状驻态。分辨一培般是先定义美一组不同的白状态，然后载将这些状态物记录下来形述成特征。由另这些特征所房形成的空间却是特征空间损。特征空间占的纬数是特英征数列的长但度。分辨能力慢分辨能力D裙，也称分辨晚范围，就是柏指分辨算法促可以分辨的泼最大连续空彻间大小。在煤这个范围内公，分辨算法微可以唯一确化定被分辨数捏。即任何两笔个在分辨范光围内的数，麻不可能具有焰完全相同的偶特征数。这培些特征数会邀以某种形式旗被记录下来骆，或者以数锈据结构的形膜式体现出来脸。脏对于两个具检有相同分辨绑能力的分辨锹算法，我们炮认为他们是俭等价算法。秒当兽的时候，分易辨算法的分拳辨能力最强冶。但是同时雪分辨算法所漆使用的特征汇空间也将是各无穷大，我思们不可能有装足够的空间您来存放这些屈相关特征记绍录。冲突概率砌当被分辨数井之间的距离该超出分辨范拿围的时候，斤就有可能发描生冲突，这幸种冲突的概越率被定义为省冲突概率删：寸当被分辨的涉数是随机分遣布在整个数监轴的时候，绵两个数之间历的距离可能被会超过分辨肯范围。这个艘时候分辨算包法不一定会摸完全失效。权冲突概率泰就体现为衡靠量某种分辨凳算法在处理移散列时候的骆特性。冲突混概率越小，意那么处理散偷列的能力就灵越强，对非戏连续空间的元特征分辨能亚力就越高；文反之，那么法处理散列的幻能力就越弱碰，对非连续叫空间的特征王分辨能力就企越低。丽对于两个具丘有相同冲突柳概率的分辨烫算法，我们秃也认为他们单是等价算法义。分辨效率茅根据分辨算庭法的特点，芦我们可以定评义分辨效率暗：部在由定理1少和定理2可好以得知：当康用于余数分计辨的整数数甘列是某一个乘确定整数，腿或者互不相搬等的质数数袍列的时候，包或者是互相熟没有公约数斑的整数数列开，分辨效率捡；其他情况院下，分辨效访率都小于1举00%。简化度灿在分辨算法阶中，我们定佳义数列的简员化度南为：松所有用于分除辨的特征个截数的和，代渣表了分辨所粒需要的特征荡总数。特征召总数越少，乒那么简化度弦就越高。分搭辨算法的简茅化度越高，滥说明所用状肝态数越少，叼分辨过程将啄能更简单。途这个评价标汁准有利于我生们去除冗余疼特征的部分抹。雨定理3僵：在相同分邻辨范围条件揉下的余数分酒辨算法中，窝所有分辨效内率尚的分辨数列单的简化度都速小于分辨效羞率狮的分辨数列伍的简化度。倚证明：分辨县效率展意味着用于犹分辨的整数雪数列中，肯俭定存在某两攀个整数有约锄数（否则他共们的乘积就蒸是他们的最储小公倍数，枪那么分辨效倦率滚）。这个约荷数我们称它四为这两个数挨之间的最大狸公约数GC际D（G状reate覆st校C恶ommon饰或D宵iviso瘦r歉）。不妨设两这两个整数缠为：扒显然如果用靠代替经，将不会影谱响这些整数驾之间的最小植公倍数LC骂M。一方面早，这些整数敲的积得到了年减少，分辨惧效率将有所伯提高；另外增一方面，这期些整数的和揪得到了减少灿，简化度也垂因此而提到庭。通过反复捉简化操作这祸个数列的分伐辨效率总可捏以达到10危0%1：分锄辨效率亭的分辨数列跟总可以简化困，而且可以电简化成分辨幅效率未的分辨数列扬。构综合评价指偏标俗我们定义分扰辨算法综合碑评价指标糊：碗懒这个标准意衔味着：分辨贷范围越大，膀简化度越高址，那么这个拿算法的综合没性能就越好娃。例如：在它余数分辨法悦中，如果我款们选择数列甚作为分辨数甩列，那么采玉取这个数列运的余数分辨苦算法各项指屋标如下：扰供如果我们选逝择数列挥作为分辨数牵列，那么采鸭取这个数列悄的余数分辨有算法各项指颠标如下：酒峰显然后者在房综合评价方挂面要优于前很者。棚2.4线性竹分辨算法载匹线性分辨算坟法是利用线青性函数此作为分辨算芳法的分辨算佩法，或者称峡为余数分辨行算法。这种晨算法简单易浮行。上面所收有的讨论都率是基于线性垫分辨算法的坑。果2.5非线魔性分辨算法缴凤非线性分辨蛇算法是指在始特征数的获尝取过程中采席用非线性函撤数的方法。职这也就是说抗，可以完全作使用非线性丽函数，或者盘非线性函数钢和线性函数绳混合使用。楼但是只要是鞋使用了非线窝性函数，那旦么就被称作廉非线性分辨包。医在这些算法把里面，可以负分成两类：摩非线性函数妥特征法和分拒段特征提取棚法。伸非线性函数努特征法课利用单值非奴线性函数（般例如：鼠）来提取特载征的方法就尸称为非线性迹特征法。很拍明显这些函辈数的单值对谢应性，并没很有改变分辨冷范围的大小控。这些函数皂仅仅是将特殿征空间做了轻一个变形处敲理。这种变唱形可能是平篮移、缩放等晋等。但是分免辨能力没有凳扩大，冲突东概率也并没蛋有得到减少须，简化度也书没有发生变项化，分辨算竭法的整体评闭价标准也没则有改变。爹分段特征提盒取法序分段特征提轧取法就是将口被分辨的数竖分成若干部玻分，每个部罚分有若干状夜态。假设某蛾个数可以被挺分成途段，每段所葵有可能的状拦态个数为斗（其中捎）。那么我苍们可以得出药以下结论：厌倚任何一个段秒的状态至少承是有两个状定态，否则这蒸种分段是毫呼无意义的。宗或者说这段喘是没有任何踏特征的，对恒分辨算法来静说是一种时允间和空间的喝浪费。瞒诱这种算法的饮分辨能力是僵：鸣哗其冲突概率音：愤以这种算法的哈分辨效率荷，简化度为治：挪拿总体评价：税海这种算法可谊以做到在所汗有分辨算法隆中的简化度勾最高，综合腔评价贿也可以很高科。但这种分千辨算法的综仓合评价辞并不总是最妨高的。奖愈例如：当我违们在分辨3织2位整数的淘时候，使用猾这种分段特存征分辨法，昌那么这种分静辨方法的各设项指标如下坛：篮为如果在余数糊分辨算法中多，我们选择动从2到29界的连续10降个质数作为虽分辨数列，服那么这个分愿辨方法的各殊项指标如下罚：菊音在分辨以2型进制为基础策的连续整数夸的时候，这漏种算法有着宣明显的优势贡。但是在分乒辨散列的时谣候，例如：虾以字符为基费础的字符串略的时候，其英特征纬数和捏者特征数将春会迅速增加培。过多的特滔征纬数和特闻征数意味者洒，对于特征蹲空间的浪费句、更多的初己始化时间以错及更多比较丸次数和比较箩时间。为了共仍然能够使展用这种分辨均方法，普遍屿采用对字符谈串压缩编码碌转换成整数闷后，再使用呢该分辨算法亭。但是即使撇是采取转换鸡手段，对于夕超长的字符籍串仍然不是宜十分容易处物理。村三、哈希树逆的组织结构痰使用不同的滋分辨算法都懒可以组织成蝶哈希树。一飘般来说：每证层哈希树的礼节点下的子陡节点数是和尿分辨数列一短致的。哈希企树的最大深插度和特征空蜘间的纬数是借一致的。防为了研究的腿方便，我们米选择质数分挺辨算法来建乓立一颗哈希比树。选择从绸2开始的连余续质数来建蔑立一个十层赞的哈希树（殿因为即已经超过了残计算机中常炕用整数的表秋达范围）。挺第一层节点阴为根节点，雅根节点下有江2个节点；臣第二层的每寸个节点下有蹦3个节点；然依此类推，周即每层节点毫的子节点数浩目为连续的灯质数。到了述第十层，每睛个节点下有拉29个节点犯。从图1哈希睁树的组织结极构颈同一节点中加的子节点，验从左到右代后表不同的余董数结果。例外如：第二层芹节点下有三俭个子节点。暗那么从左到盆右分别代表问：除3余0素，除3余1钥和除3余2手。础对质数的余数数决定了处纸理的路径。跪例如：某个患数来到第二宿层子节点，至那么它要做陕取余操作，揭然后再决定赏从哪个子节腐点向下搜寻约。如果这个怀数是12那段么它需要从年第一个子节捡点向下搜索峰；如果这个泻数是7那么吉它需要从第穗二个子节点浑向下搜索；哀如果这个数姥是32那么柏它需要从第瑞三个子节点静向下搜索。剂如果所有的酷节点都存在兄，并容纳数主据的话，那死么可以容纳蜂的数据项目验总数将比蛙要大一些：嘴如果在建立防当初就建立巾所有的节点颠，那么所消岗耗的计算时庙间和磁盘空擦间是巨大的自。在实际使夫用当中，只运需要初始化往根节点就可具以开始工作钳。子节点的稿建立是在有帅更多的数据榜进入到哈希尺树中的时候会建立的。因符此可以说哈羞希树和其他绍树一样是一茄个动态结构活。锻这些节点有涌以下基本元同素：纳节点的关键商字狼我们用ke游y来表示节由点的关键字体。在整个树方中这个数值吸是唯一的。俭当节点占据鉴标志位（o谜ccupi处ed）为真杨的时候，关怎键字才认为待是有效的，犹否则是无效时的。晨节点是否被蔑占据蹈我们用oc泛cupie忠d来表示节杯点是否被占鱼据。如果节趣点的关键字焰（key）眼有效，那么网occup梨ied应该浸设置位tr翅ue，否则扰设置为fa宫lse。艰节点的子节悲点数组动我们用no总des[i浩]来表示节吊点的第i个铜子节点的地对址。第10挡个质数为2丑9，余数不顽可能大于3创2。这个数微组的固定长攀度为可以设卖置为32，游即诸。当第回i胡个子节点不冷存在时，n寺odes[对i]栋=NULL销，否则为子陪节点的地址渗。悔节点的数据跌对象狠我们用va询lue来表略示节点的数沟据对象。价四、插入规扰则均心设需要插入惰的关键字和帖数据分别为规key和v勿alue。叙用leve夸l表示插入敲操作进行到肃第几层，l速evel从柱0开始。P然rime表份为连续质数枝表。插入过童程从根节点佣开始执行：捏如果当前节港点没有被占相据（occ悟upied培=fa曲lse），用则设置该节闲点的key且和valu鉴e，并设置属占据标记为迟true，提然后返回。梦如果当前节鼓点被占据（眠occup粒ied=川true姥），则计算后index申=ke娱ymod荒Prim疾e[lev日el]。涝如果nod卸es[in苏dex]循=NUL帮L，那么创帽建子节点，蚁将leve吃l加1，并丸重复第1步辜操作。蜓如果nod划es[in已dex]为步一个子节点扁那么，将l问evel加忧1，然后重垂复第1步操坛作。栗用伪码来表协示如下：冰void燥inser辆t(Ha太shNod扶eent俊ry,i屑ntle弃vel,站Keyk桌ey,V碎alue主value呼)晕{准抖if(t锯his.被occup撑ied=肠fals君e){念兄妹this.爸key=田key;跌晌镰this.奉value俯=va煌lue;伤锤这this.嘉occup该ied=穴true船;库脸吸retur丢n;}软灾inti岛ndex稠=key加mod迫Prime勉[leve徐l];袋亩if(n蹈odes[科index耻]=N秀ULL)余粱{陕抓宅nodes乌[inde受x]=私newH狠ashNo垮de();}棚袖level咐=le遣vel+可1;义龟距inser榨t(nod隆es[in赔dex],盟leve钢l,ke功y,va假lue);}丰五、查找操垄作阶予设需要查找恒的关键字为册key。用揪level誉表示插入进秆行到第几层窜，leve设l从0开始尖。Prim幼e表为连续严质数表。插投入过程从根奇节点开始执旅行：派如果当前节耕点没有被占爹据（occ慕upied小=fa仇lse），司则执行第5钳步操作。企如果当前节眼点已经被占秆据（occ霜upied铸=tr施ue），则镇读取该节点哑的关键字，加将它和ke口y进行比较独。震如果相等，牛则返回查找排成功和该节叮点的val捐ue。猴如果不等，舟则执行第5庸步操作。绕计算ind清ex=析keym兔odPr诉ime[l焦evel]宝。目如果nod饲es[in组dex]山=NUL芦L，那么则桌返回查找失驳败。遭如果nod艳es[in拣dex]为极一个子节点调那么，将l丈evel加护1，然后重累复第1步操鹅作。狗用伪码来表券示如下：惹Boole笋an址sear符ch(Ha因shNod喂eent梁ry,i肠ntle禾vel,右Keyk锹ey,V矛alue钢value乖){敢if(th麦is.oc坏cupie放d=t馆rue){秋if(th欺is.ke条y=k岸ey){增value筋=th融is.va龟lue;瑞retur食ntru遮e;正}}养肺inti括ndex告=key毅mod魔Prime意[leve滤l];乎裹if(n破odes[推index竟]=N至ULL)份明{写温熔retur芬nfal贼se复;}强警level逐=le幼vel+长1;胃毯值retur坦nsea牌rch(n诊odes[评index答],le级vel,迈key,兵value樱);}馋六、删除操影作种设需要删除闸的关键字为冬key。用权level售表示插入进远行到第几层虹，leve庆l从0开始骆。Prim并e表为连续辱质数表。插舱入过程从根笔节点开始执堆行：伶如果当前节侧点没有被占错据，则执行搬第5步操作旋。诊如果当前节雷点被占据，浊则读取该节干点的关键字返，将它和k绍ey进行比监较。蛾如果相等，要则设置该节衫点的占用标辫记为fal色se，并返冻回删除操作恋成功。祝如果不等，陷则执行第5冷步操作。月计算ind显ex=课keym细odPr泡ime[l首evel]怪。厚如果nod归es[in赌dex]廉=NUL笼L，那么则灭返回删除失诞败。偏如果nod斥es[in秘dex]为宜一个子节点备那么，将l易evel加贡1，然后重奏复第1步操竟作。鼻用伪码来表舅示如下：肾Boole城an军remo街ve(Ha扛shNod抗eent冤ry,i忌ntle坟vel,张Keyk滔ey){扮if(th黎is.oc膀cupie善d=t膝rue){炒if(th年is.ke相y=k晋ey){懒this.吼occup铜ied=阶fals粪e;私retur傻ntru姿e;呆}}童肌inti越ndex盾=key帝mod销Prime顶[leve豪l];催缴if(n搅odes[复index泄]=N矛ULL)瓦防{组姑肿retur览nfal乳se无;}堂册level哪=le栽vel+衰1;祝式何retur绝nrem材ove(n盛odes[弦index押],le潜vel,翅key);}拉七、哈希树挺的特点裂7.1仰结构简单蓬晋从哈希树的末结构来说，河非常的简单手。每层节点辰的子节点个接数为连续的漠质数。子节丑点可以随时柄创建。因此斥哈希树的结勤构是动态的贸，也不像某碗些哈希算法著那样需要长纵时间的初始疏化过程。哈脆希树也没有悟必要为不存匀在的关键字面提前分配空周间。滥备需要注意的呜是哈希树是搬一个单向增墙加的结构，桥即随着所需栽要存储的数毯据量增加而站增大。即使近数据量减少予到原来的数厅量，但是哈溉希树的总节誉点数不会减翁少。这样做建的目的是为宫了避免结构最的调整带来澡的额外消耗喊。锄7.2操作饥简单牙棚从上面所讲捷述的操作过孟程来说是相四当简单的。槐程序上特别世容易实现，被比起炸树都更容易进理解和实现处。作者是通酿过实际中的浅应用，将数纳据和代码量驶减到了最低咐。这种做法律不仅提高了欺速度，而且钳编写起来更素容易些。喇7.3查找贱迅速妥榜从算法过程堪我们可以看汤出，lev宝el最多能燥增加到10婚。因此最多描只需要十次剧取余和比较迁操作，就可闭以知道这个招对象是否存闪在。这个在若算法逻辑上串决定了哈希筒树的优越性痛。前一般的树状降结构，往往绸随着层次和壳层次中节点激数的增加而苦导致更多的尤比较操作。利操作次数可稼以说无法准葱确确定上限揭。而哈希树拖的查找次数古和元素个数孕没有关系。患如果元素的猴连续关键字提总个数在计乏算机的整数弯（32bi溜t）所能表冷达的最大范驼围内，那么行比较次数就尘最多不会超倦过10次，首通常低于这是个数值。难7.4结构揭不变献把从删除算法狭中可以看出障，哈希树在粘删除的时候往，并不做任净何结构调整扁。这个也是贞它的一个非歼常好的优点宴。常规树结黑构在增加元油素和删除元瓶素的时候都谈要做一定的勒结构调整，班否则他们将箱可能退化为苦链表结构，怕而导致查找应效率的降低样。哈希树采驾取的是一种潜“所见缝插针宴”浴的算法，从概来不用担心俊退化的问题奉。也不必为性优化结构而胜采取额外的拍操作，因为能大大节约了海操作时间。挖7.5非排侍序性纤柏哈希树不支哑持排序，没弊有顺序特性饭。就好比你残可以使用s蝴elect朵*wh各erei疏d=1哀2345的谷SQL选择千语句，但是口不可以使用叶selec稿t*w面here驻id>智12345堂的SQL语淋句。如果在晓此基础上不沃做任何改进获的话并试图丝通过遍历来圣实现排序，枯那么操作效素率将远远低喂于其他类型诉的数据结构拢。缝八、冲突处鸽理艰撕从定理1中饮我们可以知撕道，这个定配理只保证了遍个连续的整废数是可以被疲“侧分辨扭”怀的。如果在烂使用中，有批两个整数之圾间的距离超斑过扇，那么就可广能会出现冲摩突。胸解决冲突的老办法有两种省：一种是主鲜动解决这种汁冲突，另外塌一种是被动扮的。雕所谓主动解界决冲突，就赏是我们可以踏选择更大的阵质数序列来遗组织哈希树详，只到这些裕质数的乘积暑可以覆盖所习有可能的范夜围。或者选阔择更多的质写数，只到他阳们的乘积可寒以覆盖所有糠可能的范围铁。爬另外一个方县面如果这种袄冲突发生的矛概率很低，仔那么可以让勒哈希树被动志适应这种变弯化。冲突对页哈希树来说突并非不可以宪被接纳。无内非是增加了铸哈希树的层龄数，或者说霞增加了所需区要比较和取炼余的次数。瓶但是为了容取纳过多的冲跪突将会导致对哈希树的严搅重退化，最洽终将退化一盼个链表结构灾。畏这些能产生美冲突的数值淡之间的距离乏必须满足：狮召因此任何两选个重复的数摇之间的距离索必须为籍，而非简单脊成倍关系。地即货与承不会导致哈哄希树的退化渗。蛛九挨、字符串关孩键字的处理客盲字符串是由捧字符组成，重字符都具有给某种具体的姻编码方式。朝由这种编码众方式最终都铸可以转换成臣字节数组的去形式。因此京我们可以简宋单的将字符管串看作是2冲56进制的舅数。例如：硬“赶abc挠”双可以转换成秀字节数组0蜂x6162锁63，可以糠看作是十进吃制的638注2179。鼓互那么一个2接0个字符的抛字符串将是粉一个很大的慢数。我们不尺能简单地使杠用计算机的渴整数来做除混法，而是使恢用程序模拟举人工的除法交方式来做除永法并获得余专数。一个简库单的例子如瞎下：壁届inth威ash(S社tring术stri要ng,i励ntpr速ime){林油纲byte[浩]byt絮es=围strin景g.get斧Bytes悬();妻铃要intr房esidu椅al=局0;闻乎蔬for(i伏nti字=byt及es.le仰ngth;栋i>0妄;i--病){俭粗休哑resid共ual=晃resi堡dual悦*256哄+by漫tes[i赴障–啄1]遭resid纹ual=浊resi婆dual耻modp霞rime}凝retur变nres透idual滩;}排慈虽然多做了守几次基本的页加、减、乘茎、除运算。傅但是因为都膛是整数计算站，对于目前献的CPU水点平来说，几碌乎不算什么液难事。而且至还可以通过衔移位运算代晨替乘法运算驶，这样能更祝快些。而且赏除法的除数泽和被除数都君不会太大，慨计算起来也微不会有太多番的CPU消腹耗。管在这种情