知乎：哈希树（HashTree）查找算法
CSDN : 哈希树（HashTree）查找算法
百度文库：哈希树（HashTree）查找算法
哈希树(HashTree)
依据哈希函数查找算法要求，将数据集合中的数据记录按照一定的规律组织起来，形成多叉树结构。该数据结构可以被称为哈希树（HashTree）。
在这里假定所有的数据记录均以\((key, value)\)的形式进行存储。其中\(key\)代表数据记录的关键字，\(value\)代表具体的数据。对于给定的数值\(k\)，查找的目的就是在数据集合中找到\(key = k\)的数据记录，或者返回数据集合中不存在这样的\(key\) 。为了绘图和讨论的简便性，后面仅讨论和数值关键字\(key\)部分。
为了后续算法说明的简便性，这里选择哈希函数的除数序列\(M=\{2,3,5\}\) 。（其中）\(M(n)\)表示除数序列数组的数值。例如：\(M(1)=2 ，M(2)=3 ，M(3)=5\)。具体程序设计时，可以按照本文之前推荐的方法选择除数序列。
组织结构
哈希树数据结构是一种典型的多叉树结构。
但是哈希树数据结构与常见的多叉树又有显著的不同。下图是一个典型的哈希树数据结构：
如图2所示，该哈希树数据结构是基于除数序列构建的。
- Root为哈希树的根（深蓝色节点）。
- R0和R1为第一层节点（灰色节点）共有2个，对应除数序列中的第一个数 \(M(1)=2\)。
- R00、R01、R02、R10、R11、R12为第二层节点（黄色节点）共6个。其中R00、R01和R02是属于R0的子节点，R10、R11和R12是属于R1的子节点。R0和R1下分别有3个子节点，对应除数序列中的第二个数\(M(2)=3\)。
- 后续的R00、R01、R02、R10、R11和R12节点下又分别有5个子节点（白色节点），对应除数序列中的第三个数\(M(3)=5\)。
读者由本例可以推知，每一层节点下的子节点个数与除数序列的关系。哈希树数据结构的实际情况，与指定的除数序列有着紧密的联系。
插入数据
（步骤1）假设当前哈希树数据结构中没有任何数据记录，现在新插入一条数据记录 (\(key=25\)) 。
- 查询除数序列可知，根节点下应该有\(M(1)=2\)个节点。根据前面所描述得算法，将关键字数值取余可得 \(1\,(25\, mod \,2)\)。由于根节点下目前没有任何子节点，因此先生成一个子节点R1，并将数据记录放置至R1节点中。
（步骤2）在此次操作完成之后，继续新插入一条数据记录 (\(key=12\)) 。
- 查询除数序列可知，根节点下应该有\(M(1)=2\)个节点。根据前面所描述得算法，将关键字数值取余可得\(0\,(12\, mod \, 2) \)。由于根节点下目前没有任何子节点，因此先生成一个子节点R0，并将数据记录放置至R0节点中。
（步骤3）在此次操作完成之后，继续新插入一条数据记录 (\(key=13\)) 。
- 查询除数序列可知，根节点下应该有\(M(1)=2\)个节点。根据前面所描述得算法，将关键字数值取余可得\(1\,(13\, mod \, 2)\) 。调取节点R1的状态，发现该节点已经存储了一条数据记录。因此需要继续查询R1下的子节点寻找空出的存储位置。
- 查询除数序列可知，R1节点下应该有\(M(2)=3\)个节点。将关键字数值取余可得 ）\(1\,(13\, mod \, 3)\) 。由于R1节点下的R11节点并未生成，可以先生成R11节点，并将数据记录放置其中。
按照上述的方法将关键字序列\(key=\{25,12,13,30,128,77,1,9,18,1024\}\)依次添加到哈希树数据结构中，最后可以得到哈希树数据结构如下图所示：
这种数据插入方法的一个好处就是，可以优先占据接近根节点的子节点，降低单次操作中访问的次数，同时使树结构均衡化。按照这种数据插入方法，此哈希树数据结构中，最多可以存储的数据记录数量应大于该哈希算法的总体分辨能力。
查找数据
在图9所示的哈希树状态下，进行数据查找。
- 查找的数据记录 (\(key=128\)) 。
- 查询除数序列可知，根节点下应该有个节点。根据前面所描述得算法，将关键字数值取余可得\(0\,(128\,mod\,2)\)。调取节点R0的状态，发现该节点已经存储了一条数据记录，而且关键字不等于128。因此需要继续查询R0下的子节点。
- 查询除数序列可知，R0节点下应该有个节点。将关键字数值取余可得\(2\,(128\,mod\,3)\)。由于R0节点下的R02节点节点已经存储了一条数据记录，且关键字等于128，因此该节点即为所查找的节点。
- 程序操作到此即可结束。
- 查找的数据记录 (\(key=31\)) 。
- 查询除数序列可知，根节点下应该有个节点。根据前面所描述得算法，将关键字数值取余可得\(1\,(31\,mod\,2)\) 。调取节点R1的状态，发现该节点已经存储了一条数据记录，而且关键字不等于31。因此需要继续查询R1下的子节点。
- 查询除数序列可知，R1节点下应该有个节点。将关键字数值取余可得\(1\,(31\,mod\,3)\)。由于R1节点下的R11节点节点已经存储了一条数据记录，且关键字不等于31。因此需要继续查询R11节点下的子节点。
- 查询除数序列可知，R11节点下应该有个节点。将关键字数值取余可得\(1\, (31\,mod\,5)\)。调取节点R111的状态，发现该节点已经存储了一条记录，且关键字不等于31。
- 由于节点R111是最底层节点，因此哈希树中不存在关键字所对应的数据记录。程序到此即可结束。
删除数据
在图9所示的哈希树状态下，进行数据删除。显然删除数据的前提是能找到数据记录。因此在查找算法上，两者具有一致性，这里就不再赘述。
- 删除 (\(key=13\)) 的数据记录。
- 找到所对应的数据节点R11，并将数据节点R11的状态设置为无数据状态。
- 程序到此即可返回。
- 删除 (\(key=18\)) 的数据记录。
- 找到所对应的数据节点R003，并将数据节点R11的状态设置为无数据状态。
- 程序到此即可返回。
经过两次删除操作后，哈希树的当前状态如下图所示：
在经过删除操作后，会出现末端空节点R003和中间空节点R11。考虑到充分利用存储空间的实际要求（避免哈希树的膨胀），可以对末端节点进行”释放”处理。对于中间空节点，可以考虑将最末端的节点挪动到该层上（形成末端空节点的，则需要释放）。当然也可以放置不管，后续的插入数据可以直接利用这些空节点。无论如何操作都是为了保证树结构的紧凑性，减少单次操作中的访问次数。
哈希树的特点
（1）结构简单
哈希树的结构非常简单，每层节点的子节点个数由除数序列指定，子节点可以随时动态创建。哈希树结构是动态的，不需要长时间的初始化过程，没有必要为不存在的关键字节点提前分配存储空间。
（2）易于实现
从上面所讲述的操作过程来说是相当简单的。程序上特别容易实现，比起\(B^−\)树更容易理解和实现。
（3）查找迅速
从前面的分析可以看出，时间复杂度是\(O(n)\)（其中\(n\)为除数数列的长度）。实际应用中，平均查找长度应该小于\(n\)
推荐适用数列：
\[M^*=\{256，255，253，251，247，241，\\ 239，233，229，227，223，217，211，199，197，193，\\ 191，181，179，173，167，163，157，151，149，139，\\137，131，127，113，109，107\}\]
共计32个数。这些数相互互素，它们的乘积约为\(2.372×10^{72}\)（\(2^{256}\)约为\(1.158×10^{77}\)）。而且单个元素的数值用一个无符号字节（8bit）可以表达。
以推荐的除数序列\(M^*\)为例。对于无符号4字节（即32bit）整数的，预估时间复杂度是\(O(5)\)（\(256×255×253×251×247>2^{32}\)），平均查找查找长度要小于5。
（4）易于调整
从前面的删除操作可以看出，对哈希树的平衡操作十分简单：主要在于调整空节点。将最末端节点向前挪动至当前空节点，并释放末端空节点。
（5）非排序性
哈希树不支持整体排序，没有整体顺序特性。
不过哈希树可以支持部分排序，只需要在插入数据时将较大（或者较小）数据逐节点交换至末端节点即可。不过这种部分排序性，目前尚未找到实际用途，与其他支持排序的数据结构相比也没有什么优势。
拓展阅读
CSDN : 查找算法
CSDN : 哈希树 (HashTree)
CSDN : 查找——图文翔解HashTree（哈希树）
CNBlogs : 查找——图文翔解HashTree（哈希树）