高效查找的数据结构-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/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年2月16日
下一篇 2020年2月17日

相关推荐

  • 算法竞赛常用数据结构-字典树Trie

    本文参考资源: 详谈树结构(传统树、字典树、hash 树、Merkle Patricia Tree)_C/C++_smilejiasmile的博客-CSDN博客 概述 Tire树称…

    2020年2月17日
    0670
  • 跳表-披着链表外衣的伪搜索树

    本文参考资源: 【数据结构与算法】之跳表(Java实现)---第九篇Java震哥聊校招-CSDN博客 跳表的原理及实例 - Rogn - 博客园 跳表Java实现Java偏离的定弦…

    2020年3月28日
    0670
  • 海量数据去重-由BitMap引出的布隆过滤器

    本文参考资源: 那些惊艳的算法们(一)——布隆过滤器_C/C++_xinzhongtianxia的博客-CSDN博客 详解布隆过滤器的原理、使用场景和注意事项 - 简书 概述 昨天…

    2020年2月28日
    01.3K0
  • leetcode225--用队列实现栈

    原题 使用队列实现栈的下列操作: push(x) – 元素 x 入栈 pop() – 移除栈顶元素 top() – 获取栈顶元素 empty() – 返回栈是否为空 注意: 你只能…

    算法 2019年12月13日
    0120
  • 带有优先级的完全二叉树-堆

    堆的概念 堆是一种完全二叉树(除了最后一层每个节点的子节点都是满的,最后一层的节点也是集中在左边) 虽然堆是一棵二叉树,但也由于它是一棵完全二叉树的原因,可以使用一个数组来表示堆。…

    算法 2020年2月9日
    0180
  • 多叉平衡查找树-B树与B+树

    本文参考链接: 从B树、B+树、B*树谈到R 树_磁盘,数据结构,存储_结构之法 算法之道-CSDN博客 【数据结构】B树、B+树详解 - Assassinの - 博客园 BTre…

    2020年2月8日
    0160
  • Redis常用数据类型使用的数据结构

    本文参考资源: Redis数据结构——压缩列表 - 老於` - 博客园 极客时间《数据结构与算法之美》 总体来说,Redis的key-value数据存储是通过哈希表实现的,那么具体…

    2020年4月6日
    0150
  • leetcode622-设计循环队列

    设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 循环队列的一个好处是…

    算法 2019年11月24日
    0130
  • 弱平衡的二叉查找树-红黑树

    为什么会出现红黑树? 之前我们提过AVL树-自平衡的二叉搜索树,但是一旦树的节点发生变化,AVL树为了维持绝对平衡(虽然说AVL也容忍左右两个子树最多为1的高度差,但这里仍视为绝对…

    2020年2月9日
    01000
  • leetcode707-设计链表

    原题 设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性:val 和 next。val 是当前节点的值,next 是指向下一个节点的指针/引用。如果要使用…

    算法 2019年12月14日
    0290

发表回复

登录后才能评论