Hash|Hash Tree HashTree

??Hash Tree 是一种高效数据查询树形结构。其结构固定，不会存在其他树形结构出现退化的情况。听到Hash我们可能第一个想到的是冲突，那么Hash Tree 是否存在冲突呢? 答案是肯定的，不过只要树高足够冲突完全可以避免。

数学基础

文章图片
【Hash|Hash Tree】由上可得一个一般结论对于任意小于M 的数对Pi 取余是可以唯一标识一个数。那么这个M有多大呢？我们取前十个质素M10 = 23571317......*29 = 6469693230 这个已经超出一个 32位计算机可以表达的最大范围。

文章图片

每层节点个数与素数保持一致。由于第10个质素为29.所以针对M10 节点最大数组为29就足够了。当然我们也可以固定层高将所有节点都存储在叶子节点上。。
实现和Tire树差不错就不多说了。
详细解说请参考这里

Hash|Hash Tree