您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

数据结构不迷茫

时间:2020-11-06 10:04:37  来源:  作者:

前言

HashMap是怎么实现地?为什么JDK8之后要换成红黑树?MySQL的索引为什么要用B+树?

这些问题在面试中是经常被问到的。今天抽空把这些数据结构进行总结。其实每种数据结构都是为了满足某种场景的需求,都是有着某种内在的联系的,今天我们将尝试进行梳理和总结。此外,在我们对这些数据结构进行研究的时候,主要关注于其评价指标,包括查找,删除,插入的时间复杂度。

这里解释下,我只是对其进行了梳理和总结,里面的配图是在网上找的,会在后面注明来源。

数组和链表

数组和链表是我们最先接触到的数据结构,我们先来分析下

数组 链表 查找 O(1) O(n) 插入 O(n) O(1) 删除 O(n) O(1)

注:我们一般设置一个哨兵节点,这样在处理头结点的删除和插入的时候不至于进行特殊处理。

上面的链表说的是单链表,除此之外,我们还需要了解双向链表和循环链表

栈和队列

这里需要注意,栈和队列本质上是用数组/链表来实现的,不过二者是操作受限的线性表,其在特定的场景下可以发挥特有的作用。

跳表

跳表是什么?我们为什么需要跳表呢?

我们知道,二分查找的时间复杂度为lgn,性能是很好的,但是其只能局限在数组中,链表是不能使用二分查找的。那么有没有办法在链表中实现二分查找的特性呢?

如果数据是有序的,还是需要O(n)的时间复杂度。

数据结构不迷茫

 

那怎么提高查找效率呢?每两个结点提取一个结点到上一级。

数据结构不迷茫

 

类推:

数据结构不迷茫

 

所以,当链表的长度 n 比较大时,在构建索引之后,查找效率的提升就会非常明显。直观上,我们可以看到查找的效率提高了提高,下面让我们来具体分析提高的效率。

假设链表的长度为n,那么第一级索引的节点个数为n/2,第二级为n/4,那么第k级索引的节点个数为n/(2^k)。我们知道,最高的索引有2个节点,则k=lgn-1。在我们查询数据的时候,如果每一层需要查找m个节点,则在跳表中查询一个数据的时间复杂度就是 O(m*logn)。

且m=3,则时间复杂度为O(lgn)。

原因如下:假设我们要查找的数据是 x,在第 k 级索引中,我们遍历到 y 结点之后,发现 x 大于 y,小 于后面的结点 z,所以我们通过 y 的 down 指针,从第 k 级索引下降到第 k-1 级索引。在 第 k-1 级索引中,y 和 z 之间只有 3 个结点(包含 y 和 z),所以,我们在 K-1 级索引中 最多只需要遍历 3 个结点,依次类推,每一级索引都最多只需要遍历 3 个结点。

数据结构不迷茫

 

我们可以看到,通过建立索引,我们实现了快速查找,代价了浪费了空间,空间复杂度为O(n)。其实在实际的软件开发中,链表中存储的是比较大的对象,但是索引中存储的是id,所以相比较之下是可以忽略的。

下面我们来分析插入和删除的时间复杂度,先给结论,也是O(lgn)。

数据结构不迷茫

 

我们还需要注意的是要及时更新索引,红黑树是通过左右旋来保持稳定的,而跳表是通过随机函数来保存平衡性的。

数据结构不迷茫

 

hashmap

我们知道,数组可以在O(1)的时间复杂度内完成查询,但是需要O(n)的时间复杂度完成插入和删除,而链表正好相反,那么我们是否可以综合利用数组和链表的优势,这就是hashmap。

数据结构不迷茫

 

二叉查找树

前面我们看到,hashmap是十分高效的,但是其问题也是比较明显的。

  1. Hashmap中的数据是无序存储的,若要输出有序数据,则需要先进行排序,而二叉查找树直接中序遍历即可;
  2. Hashmap扩容耗时多;
  3. Hashmap在hash冲突的时候耗时多;
  4. Hashmap的构造复杂,需要考虑散列函数的设计、冲突解决办法、扩容、缩容等问题,而二叉查找树只需要考虑平衡性问题;

所以综合以上的考量,在某些场景下,我们需要二叉查找树,其查找的时间复杂度为O(logn)。

平衡二叉树和红黑树

前面我们学到二叉查找树在某些情况下可能会失衡,即退化为链表,时间复杂度降低为O(n),所以我们需要对二叉查找树进行平衡。

最先被使用的是AVL平衡二叉查找树,其首先符合二叉查找树的概念,然后左右子树的高度差不超过1。这样就可以很好的保证查找的时间复杂度了。但是其缺点也是很明显的,需要不断的对整棵树进行调整。

数据结构不迷茫

 

这个时候我们就引入了红黑树:左右子树的高度差不超过1倍。红黑树的高度,是2logn。其查找,插入,删除的时间复杂度都是O(logn)。

数据结构不迷茫

 

我们再来看另外一种特殊的二叉树:堆。

我们知道堆是一种完全二叉树,往往采用数据里存储。堆在很多地方都有应用,比如

  • 优先级队列:用在赫夫曼编码、图的最短路径、最小生成树算法
  • TOPK问题
  • 求动态数据中的中位数

此外,堆在排序算法中的表现也是很好的,时间复杂度是O(logn),空间复杂度为O(1),从这个角度来讲,是要比快排和归并排序都要优秀的,但是工程中更常见的排序算法依然是快排的,那这是为什么呢?主要从2个角度来考虑:

  1. 堆排序数据访问的方式没有快速排序友好。CPU的空间局部性原理。快排中,数据是顺序访问的,而堆中是跳着访问的。
  2. 同样的数据,堆排序的交换次数多余快排。

B树和B+树

这里要从mysql讲起,使用mysql来查询数据,我们比较关注的两个点是等值查询和范围查询,如:

select * from user where id=1234;
select * from user where id > 1234 and id < 2345

我们前面学到的数据结构中:

  • 散列表:等值查询时间复杂度为O(1),但可能存在hash冲突的问题,且范围查询不支持;
  • 二分查找树:可能失衡
  • 平衡二叉树(AVL,红黑树):范围查询仍然不方便,且树的高度为logn;
  • 跳表:插入、查找、删除数据的时间复杂度都为logn,同时支持区间查询,但是logn的时间复杂度仍然过高。且B+树提出于1972年,跳表提出于1989年,所以B+树才是爸爸。

综上,我们必须要降低树的高度,所以肯定是多叉树。

  • B树:
数据结构不迷茫

 

  • B+树
数据结构不迷茫

 

我们来对比下B树和B+树:

B B+ 存储结构 每个节点存数据 叶子节点存数据,非叶子节点存储索引。所以可以存放更多的数据 查找性能 不稳定 稳定,必须查找到叶子节点 范围查询 不支持 支持

所以,mysql的索引选择了B+树。那么B+树是怎么演化来的呢?

如果我们对二分查找树进行改造,树中的节点并不存储数据本身,而是只是作为索引。除此之外,我们把每个叶子节点串在一条链表上,链表中的数据是从小到大有序的。

数据结构不迷茫

 

如果我们要为上亿的数据建立索引,比如,我们给一亿个数据构建二叉查找树索引,那索引中会包含大约 1 亿个节点,每个节 点假设占用 16 个字节,那就需要大约 1GB 的内存空间。给一张表建立索引,我们需要 1GB 的内存空间。如果我们要给 10 张表建立索引,那对内存的需求是无法满足的。如何解决这个索引占用太多内存的问题呢?

答案是把索引存放到硬盘中,但是如此一来,需要从硬盘中读取数据,速度是无法忍受的,因为树高是需要IO的次数,所以要降低树高。答案是多叉树。

数据结构不迷茫

 

那多叉树的m到底是多少比较好呢?不管是内存中的数据,还是磁盘中的数据,操作系统都是按页(一页大小通常是 4KB,这 个值可以通过 getconfig PAGE_SIZE 命令查看)来读取的,一次会读一页的数据。如果要 读取的数据量超过一页的大小,就会触发多次 IO 操作。所以,我们在选择 m 大小的时 后,要尽量让每个节点的大小等于一个页的大小。读取一个节点,只需要一次磁盘 IO 操作。

数据结构不迷茫

 

总结

我们可以看到,任何一种技术都是为了解决在某些场景下,其他的方案存在的某些问题,我们要理清这种内部的关系,这样我们才可以了然于胸。

这篇文章的字数不多,但是希望可以帮助你梳理下常见的数据结构,在学习的时候不至于迷茫。

参考

数据结构与算法之美:https://time.geekbang.org/column/intro/126



Tags:数据结构   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
1 概述数据结构和内部编码 无传统关系型数据库的 Table 模型schema 所对应的db仅以编号区分。同一 db 内,key 作为顶层模型,它的值是扁平化的。即 db 就是key的命名空间。 key...【详细内容】
2021-11-01  Tags: 数据结构  点击:(28)  评论:(0)  加入收藏
Redis常用的数据结构有 string list set zset hashstringstring 是 Redis 的基本的数据类型,一个 key 对应一个 value。string 类型是二进制安全的,Redis的string可以包含任...【详细内容】
2021-10-12  Tags: 数据结构  点击:(36)  评论:(0)  加入收藏
遵从所有教材以及各类数据结构相关的书书籍,我们先从线性表开始入门。今天这篇文章更偏概念,是关于有线性表的一个知识点的汇总。上文说过,物理结构是用于确定数据以何种方式存...【详细内容】
2021-07-19  Tags: 数据结构  点击:(94)  评论:(0)  加入收藏
1. 线性表线性表是一类最简单、最常用的数据结构。简单来说,一个线性表是n个元素的有限序列,其中n&ge;0,通常表示为(a1,a2,...,an)。其特点是,在非空的数据元素集合中:(1)存在唯一的一个...【详细内容】
2021-06-09  Tags: 数据结构  点击:(139)  评论:(0)  加入收藏
Mysql索引数据结构下面列举了常见的数据结构 二叉树 红黑树 Hash表 B-Tree(B树)Select * from t where t.col=5我们在执行一条查询的Sql语句时候,在数据量比较大又不加索引的情...【详细内容】
2021-06-07  Tags: 数据结构  点击:(90)  评论:(0)  加入收藏
Redis五种数据结构如下: 1.String 字符串类型是redis中最基本的数据类型,一个key对应一个value。String类型是二进制安全的,意思是 redis 的 string 可以包含任何数据。如数字,...【详细内容】
2021-04-14  Tags: 数据结构  点击:(208)  评论:(0)  加入收藏
一、栈栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈...【详细内容】
2021-04-06  Tags: 数据结构  点击:(266)  评论:(0)  加入收藏
序列是python中最基本的数据结构。所谓的序列,指的是可以连续存放多个值的内存空间,序列中的每个元素都会有一个数字,即它的位置或索引。通过这个索引就能找到序列中的元素 。...【详细内容】
2021-02-24  Tags: 数据结构  点击:(197)  评论:(0)  加入收藏
不要虚度每一天,你的经验就是这样积累出来,然后用在了你的事情上面。 一:摘要概述很多 redis 的使用者都可以清晰明白的道出Redis中常用的对象如string、list、hash、set、zset...【详细内容】
2021-01-18  Tags: 数据结构  点击:(167)  评论:(0)  加入收藏
速介绍8种常用数据结构数据结构是一种特殊的组织和存储数据的方式,可以使我们可以更高效地对存储的数据执行操作。数据结构在计算机科学和软件工程领域具有广泛而多样的用途...【详细内容】
2020-12-18  Tags: 数据结构  点击:(93)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(9)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(19)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(13)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯&middot;奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(37)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条