高效查找的数据结构-HashTree（哈希树）

彭晨涛 • 2020年2月17日 02:14 • 算法 • 阅读 312

本文参考资源：

痴人说Hash - 哈希树 (HashTree)_Java_PinusLee阳光灿烂的生活-CSDN博客

查找——图文翔解HashTree（哈希树）Java菜鸟的自留地-mooyang-CSDN博客

概述

二叉排序树，平衡二叉树，红黑树等二叉排序树在数据量大的时候树高很深，我们不断向下找寻值时会比较很多次。二叉排序树自身是有顺序结构的，每个结点除最小结点和最大结点外都有前驱和后继，不论是排序还是搜索它的综合性能比较好，但是单独在搜索这一方面二叉排序树的性能就没有这次要讲的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/

高效查找的数据结构-HashTree（哈希树）

概述

理论基础

哈希树的实现

插入

查找

删除

相关推荐

发表回复