哈希树

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

介绍在将一个数进行哈希的时候，我曾经写过关于哈希的这么些东西：对于数，当一个质数不够用的时候，可以加上第二个质数，用两个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那么它需要从第三个子节点向下搜索。这就是一个哈希树了。

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

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

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

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

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

优点1、结构简单

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

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

2、查找迅速

从算法过程我们可以看出，对于整数，哈希树层级最多能增加到10。因此最多只需要十次取余和比较操作，就可以知道这个对象是否存在。这个在算法逻辑上决定了哈希树的优越性。
一般的树状结构，往往随着层次和层次中节点数的增加而导致更多的比较操作。操作次数可以说无法准确确定上限。而哈希树的查找次数和元素个数没有关系。如果元素的连续关键字总个数在计算机的整数（32bit）所能表达的最大范围内，那么比较次数就最多不会超过10次，通常低于这个数值。

3、结构不变

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

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

本词条内容贡献者为:

李岳阳 - 副教授 - 江南大学