数据结构之Hash树

﹏ヽ暗。殇╰゛Y 2022-05-25 05:16 185阅读 0赞

### 1.0 简介 ###

也叫散列树

散列树 选择从2开始的连续质数来建立一个十层的哈希树。

第一层结点为根结点，根结点下有2个结点；

第二层的每个结点下有3个结点；

依此类推，即每层结点的子节点数目为连续的质数。

### 2.0 关于散列表的一些个人理解吧 ###

先说什么是散列函数？  
我们知道HashMap< K,V> 这是java Map接口的的一个实现 我们可以通过K 来获取V  
k 就是key 也就是关键码 v 就是value 也就是指

假设有一个函数 add = key%10 add是内存中的地址 这个地址的值是 value的值

这样就通过k找到了 v

其中 key/10 叫做散列函数 或者哈希函数（Hash）

并且这个add的区间假设是在数组a\[10\] 范围内的

就称这段连续的存储空间 或者说数组 是散列表

add 称为散列地址

1.  存储的时候 通过散列函数算出散列地址，然后把value的值存入
2.  查找的时候 通过散列函数算出散列地址 ，然后读出数据

关于冲突 就是不同的键值得到相同的散列地址 就像散列表的大小10

我们存key = 10的时候，地址是0 key = 100的时候还是0 这就是冲突

如果冲突了 就找另一个空闲位置的 处理方法叫做 闭散链表 常见的处理方式是 开放定址法

如果是冲突了 则采用链接的方式继续存在这个地方 类似树的孩子链表表示法 这叫开散链表 常见的处理方式是拉链法

**哈希树的理论基础**

【质数分辨定理】  
简单地说就是：n个不同的质数可以“分辨”的连续整数的个数和他们的乘积相等。“分辨”就是指这些连续的整数不可能有完全相同的余数序列。  
（这个定理的证明详见：[http://wenku.baidu.com/view/16b2c7abd1f34693daef3e58.html][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次取余的整数除法操作几乎不算什么难事。在实际应用中，整体的操作速度往往取决于节点将关键字装载内存的次数和时间。一般来说，装载的时间是由关键字的大小和硬件来决定的；在相同类型关键字和相同硬件条件下，实际的整体操作时间就主要取决于装载的次数。他们之间是一个成正比的关系。

### 3.0 哈希树的建立 ###

哈希表的建立就是遵从上面的指数序列 一般都是从2开始，即

第一层的结点有2个子节点，第二层结点每个节点都有3个子节点，

第三层每个节点有5个子节点，第四层结点每个节点都有7个子节点

第五层每个节点有11个子节点，第六层结点每个节点都有13个子节点

第七层每个节点有17子节点

。。。。。。

就按质数序列来的

一般来说10层就够了

哈希树的数据结构如下

struct Node  
    {  
        keyType      key ;  
        //用occupied来表示节点是否被占据。如果节点的关键字（key）有效，
        //那么occupied应该设置位true，否则设置为false。 
        bool         occupied ;    
          //我们用subNodes[i]来表示节点的第i个子节点的地址。 
        struct Node* subNodes[1] ; 
    } ;

在实际使用当中，只需要初始化根节点就可以开始工作。子节点的建立是在有更多的数据进入到哈希树中的时候建立的。因此可以说哈希树和其他树一样是一个动态结构。

下面演示插入过程 [ 图的来源][Link 1]

![这里写图片描述][Center]

查找

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

删除

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

### 4.0 优点和缺点 ###

优点：结构简单 注意hash树是单向增加的，即使删除也不会减少hash树的结构  
查找迅速 对于int的数据 最多查找10次  
结构不变 即使删除属于也不会改变结构，

缺点：非排序性 就是数据时没有顺序的

[http_wenku.baidu.com_view_16b2c7abd1f34693daef3e58.html]: http://wenku.baidu.com/view/16b2c7abd1f34693daef3e58.html
[Link 1]: https://blog.csdn.net/yang_yulei/article/details/46337405
[Center]: /images/20220525/19c4cfb941284ec6820717a09eff93d1.png