高效查找的数据结构-HashTree(哈希树)

本文参考资源:

痴人说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类型的范围。

而这个要分辩的整数,可以是数据库中的主键,可以是唯一标识某一对象的哈希码(不用哈希函数,保证不同对象的哈希码不冲突)。

哈希树的实现

哈希树的结构:每一层节点的最大子节点数都不一样,对应这一层代表的质数值:

高效查找的数据结构-HashTree(哈希树)

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(哈希树)

查找

查找和插入的逻辑一样,按除余的方法一直找到某个位置

删除

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/