常用算法及数据结构之HashTree

【导读：数据是二十一世纪的石油，蕴含巨大价值，这是·情报通·大数据技术系列第[142]篇文章，欢迎阅读收藏】

1 基本概念

在计算机科学中，哈希树（ HashTree ）是一种持久性数据结构，可用于实现集合和映射，旨在替换纯函数式编程中的哈希表。在其基本形式中，哈希树在 Trie 中存储其键的哈希值（被视为位串），其中实际键和（可选）值存储在 Trie 的 “ 最终 ” 节点中。

2 术语解释

在将一个数进行哈希的时 , 对于这个数，当一个质数不够用的时候，可以加上第二个质数，用两个 mod 来确定该数据在库中的位置。那么这里需要简单的解释一下，对于一个质数 x ，它的 mod 有 [ 0 .. x - 1 ] x 种；所以对于两个质数 x 和 y ，能存储的无一重复的数据有 x*y 个，其实也就是开一个 x*y 的二维数组。但是当数据极其多时，用两个质数去 mod 显然也是有不够的时候，就还要再加一个。为了便于查找，选取最小的十个质数，也就是 2 ， 3 ， 5 ， 7 ， 11 ， 13 ， 17 ， 23 ， 29 ， 31 来 mod ，能包括的数就有 10555815270 个，已经远超出 longint 了。就是说，如果创建一个十维数组，那么取到一个数的效率就是 O( 1 ) ！但是那样显然太浪费空间了，就可以用到树。

同一节点中的子节点，从左到右代表不同的余数结果。例如：第二层节点下有三个子节点。那么从左到右分别代表：除 3 余 0 ，除 3 余 1 和除 3 余 2 。

对质数的余数决定了处理的路径。例如：某个数来到第二层子节点，那么它要做取余操作，然后再决定从哪个子节点向下搜寻。如果这个数是 12 那么它需要从第一个子节点向下搜索；如果这个数是 7 那么它需要从第二个子节点向下搜索；如果这个数是 32 那么它需要从第三个子节点向下搜索。这就是一个哈希树了。

3 详细说明

3.1 哈希树的建立

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

以随机的 10 个数的插入为例，来图解 HashTree 的插入过程。如下图：

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

3.2 查找

哈希树的节点查找过程和节点插入过程类似，就是对关键字用质数序列取余，根据余数确定下一节点的分叉路径，直到找到目标节点。

如上图，最小 ” 哈希树 (HashTree) 在从 4G 个对象中找出所匹配的对象，比较次数不超过 10 次。也就是说：最多属于 O(10) 。在实际应用中，调整了质数的范围，使得比较次数一般不超过 5 次。也就是说：最多属于 O(5) 。因此可以根据自身需要在时间和空间上寻求一个平衡点。

3.3 删除

哈希树的节点删除过程也很简单，哈希树在删除的时候，并不做任何结构调整。

只是先查到到要删除的节点，然后把此节点的 “ 占位标记 ” 置为 false 即可（即表示此节点为空节点，但并不进行物理删除）。

3.4 优点

1 、结构简单

从哈希树的结构来说，非常的简单。每层节点的子节点个数为连续的质数。子节点可以随时创建。因此哈希树的结构是动态的，也不像某些哈希算法那样需要长时间的初始化过程。哈希树也没有必要为不存在的关键字提前分配空间。

需要注意的是哈希树是一个单向增加的结构，即随着所需要存储的数据量增加而增大。即使数据量减少到原来的数量，但是哈希树的总节点数不会减少。这样做的目的是为了避免结构的调整带来的额外消耗。

2 、查找迅速

从算法过程我们可以看出，对于整数，哈希树层级最多能增加到 10 。因此最多只需要十次取余和比较操作，就可以知道这个对象是否存在。这个在算法逻辑上决定了哈希树的优越性。

一般的树状结构，往往随着层次和层次中节点数的增加而导致更多的比较操作。操作次数可以说无法准确确定上限。而哈希树的查找次数和元素个数没有关系。如果元素的连续关键字总个数在计算机的整数（ 32bit ）所能表达的最大范围内，那么比较次数就最多不会超过 10 次，通常低于这个数值。

3 、结构不变

从删除算法中可以看出，哈希树在删除的时候，并不做任何结构调整。这个也是它的一个非常好的优点。常规树结构在增加元素和删除元素的时候都要做一定的结构调整，否则他们将可能退化为链表结构，而导致查找效率的降低。哈希树采取的是一种 “ 见缝插针 ” 的算法，从来不用担心退化的问题，也不必为优化结构而采取额外的操作，因此大大节约了操作时间。

3.5 缺点

哈希树不支持排序，没有顺序特性。如果在此基础上不做任何改进的话并试图通过遍历来实现排序，那么操作效率将远远低于其他类型的数据结构。