本文参考资源:
痴人说Hash - 哈希树 (HashTree)_Java_PinusLee阳光灿烂的生活-CSDN博客
查找——图文翔解HashTree(哈希树)Java菜鸟的自留地-mooyang-CSDN博客
该数据结构的设计者编写的文档:哈希树HashTree - 百度文库
概述
二叉排序树,平衡二叉树,红黑树等二叉排序树在数据量大的时候树高很深,我们不断向下找寻值时会比较很多次。二叉排序树自身是有顺序结构的,每个结点除最小结点和最大结点外都有前驱和后继,不论是排序还是搜索它的综合性能比较好,但是单独在搜索这一方面二叉排序树的性能就没有这次要讲的Hash树快了。
理论基础
Hash树的理论基础为质数分辨定理:
n个不同的质数可以“分辨”的连续整数的个数和他们的乘积相等。“分辨”就是指这些连续的整数不可能有完全相同的余数序列。
基于这个理论,假设我们取前十个素数,能分辨的整数有2*3*5*7*9*...*29 = 6 469 693 230
个数,也就是说如果有21亿个数字的话,我们查找的哪怕是最底层的也仅仅需要计算10次就能找到对应的数字,而这已经超出int类型的范围。
而这个要分辩的整数,可以是数据库中的主键,可以是唯一标识某一对象的哈希码(不用哈希函数,保证不同对象的哈希码不冲突)。
哈希树的实现
哈希树的结构:每一层节点的最大子节点数都不一样,对应这一层代表的质数值:

java代码:
private class Node{ //定义了一个内部类,每一个结点会有一个next数组
public Node[] next = null; //用来装子节点的下标表示余数
public Integer data = 0; //数值
public boolean isDel = false; //是否被删除的标记,作删除用
public Node(Integer data,Integer level){ //构造函数
next = new Node[level];
this.data = data;
}
public Node(Integer data){ //构造函数
this.data = data;
}
}
插入
求余看对应位置的结点,如果为空则在空处插入一个新节点,如果被逻辑删除了替换值再逻辑恢复,如果有值就继续往下找,继续求余判断。

查找
查找和插入的逻辑一样,按除余的方法一直找到某个位置
删除
HashTree的删除节点并不要求真正删除节点,只需要逻辑性地删除节点,先按查找的方法获取对应节点,把节点的isDel标记为true,这样如果新加入节点需要放在这个位置也能直接替换它。
原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e9%ab%98%e6%95%88%e6%9f%a5%e6%89%be%e7%9a%84%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84-hashtree%ef%bc%88%e5%93%88%e5%b8%8c%e6%a0%91%ef%bc%89/