Hash Tree

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

数学基础

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


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

©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容