HashTree(哈希树) ——和trie类似,只是将字符换成了质数,sphinx用到了???-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

HashTree(哈希树) ——和trie类似,只是将字符换成了质数,sphinx用到了???

简介:

摘自:http://blog.csdn.net/yang_yulei/article/details/46337405

哈希树的理论基础

质数分辨定理
简单地说就是:n个不同的质数可以“分辨”的连续整数的个数和他们的乘积相等。“分辨”就是指这些连续的整数不可能有完全相同的余数序列。
(这个定理的证明详见:http://wenku.baidu.com/view/16b2c7abd1f34693daef3e58.html

例如:
从2起的连续质数,连续10个质数就可以分辨大约M(10) =2*3*5*7*11*13*17*19*23*29= 6464693230 个数,已经超过计算机中常用整数(32bit)的表达范围。连续100个质数就可以分辨大约M(100) = 4.711930 乘以10的219次方。
而按照目前的CPU水平,100次取余的整数除法操作几乎不算什么难事。在实际应用中,整体的操作速度往往取决于节点将关键字装载内存的次数和时间。一般 来说,装载的时间是由关键字的大小和硬件来决定的;在相同类型关键字和相同硬件条件下,实际的整体操作时间就主要取决于装载的次数。他们之间是一个成正比 的关系。

 

插入

我们选择质数分辨算法来建立一棵哈希树。
选择从2开始的连续质数来建立一个十层的哈希树。第一层结点为根结点,根结点下有2个结点;第二层的每个结点下有3个结点;依此类推,即每层结点的子节点数目为连续的质数。到第十层,每个结点下有29个结点。
同一结点中的子结点,从左到右代表不同的余数结果。
例如:第二层结点下有三个子节点。那么从左到右分别代表:除3余0,除3余1,除3余2.
对质数进行取余操作得到的余数决定了处理的路径。

结点结构:结点的关键字(在整个树中是唯一的),结点的数据对象,结点是否被占据的标志位(标志位为真时,关键字才被认为是有效的),和结点的子结点数组。
哈希树的节点结构

[cpp] view plain copy
  1. struct Node  
  2. {  
  3.     keyType      key ;  
  4.     ValueType    value ;  
  5.     bool         occupied ;    //用occupied来表示节点是否被占据。如果节点的关键字(key)有效,那么occupied应该设置位true,否则设置为false。  
  6.     struct Node* subNodes[1] ; //我们用subNodes[i]来表示节点的第i个子节点的地址。(此技术在跳跃表中有介绍,可翻看前面博客)  
  7. } ;  

(如果在建立当初就建立所有的节点,那么所消耗的计算时间和磁盘空间是巨大的。在实际使用当中,只需要初始化根节点就可以开始工作。子节点的建立是在有更多的数据进入到哈希树中的时候建立的。因此可以说哈希树和其他树一样是一个动态结构。)

 

下面我们以随机的10个数的插入为例,来图解HashTree的插入过程,这个史上最清晰的图解,你一定能看的明白^_^

有读者可能有疑问,如果一直冲突下去怎么办?首先,若关键字是整型,我们的10层哈希树完全可以分辨出来它们,这是质数分辨算法决定的。

(我们其实也可以把所有的键-值节点放在哈希树的第10层叶节点处,这第10层的满节点数就包含了所有的整数个数,但是如果这样处理的话,所有的非叶子节点作为键-值节点的索引,这样使树结构庞大,浪费空间)

【这里没有说的太清楚,此图是以2开始的连续质数创建的,即:从上到下的层级中的每个节点中的子树个数为2、3、5、7、11、13、17、19、23、29。第一层中的每个节点的子树个数为2,第二层中的每个节点子树个数为5.。。。。

上图中的子树上的数字,是其父节点的子树指针数组的索引值】


查找 

哈希树的节点查找过程和节点插入过程类似,就是对关键字用质数序列取余,根据余数确定下一节点的分叉路径,直到找到目标节点。
如上图,最小”哈希树(HashTree)在从4G个对象中找出所匹配的对象,比较次数不超过10次。也就是说:最多属于O(10)。在实际应用中,调整 了质数的范围,使得比较次数一般不超过5次。也就是说:最多属于O(5)。因此可以根据自身需要在时间和空间上寻求一个平衡点。

 

删除 

哈希树的节点删除过程也很简单,哈希树在删除的时候,并不做任何结构调整。
只是先查到到要删除的节点,然后把此节点的“占位标记”置为false即可(即表示此节点为空节点,但并不进行物理删除)。

 

优点

1、结构简单

2、查找迅速

3、结构不变

从删除算法中可以看出,哈希树在删除的时候,并不做任何结构调整。 

缺点

非排序性














本文转自张昺华-sky博客园博客,原文链接:http://www.cnblogs.com/bonelee/p/6249605.html,如需转载请自行联系原作者


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章