00:00
好,各位同学,接下来我们介绍一下我们的跳表相关的知识,以及涉及到的面试题。一提起这个SK list跳表啊,那么好像刚才有同学之前呢,还跟我聊过,说好像只在red里面听过这个东东,确实他呢red的考题里面频繁的出现过,但是注意我们Java里面大家有没有见过这个东东。那么各位同学可以思考一下,首先啊,如果你跟杨哥混了这么长时间,应该是知道我讲过我们之前哈,在白天的时候,当时给大家介绍过大长面试题第四集提出来。一部分题目,以及我们在GUUC里面介绍过,它并不在集合类里面,它在我们的什么地方,是不在我们GUUC里面,大家呢,一定现在呢。在去年甚至2021年,大家都清楚啊,这个什么是不是经常被问到啊,OK啊,其实很无聊的,就是现在这些公司呢,考这样的源码筛不出什么人,比如说啊,我作为上硅谷的主要面试官,很多大厂阿里P7的或者美团的来我们公司应聘做讲师啊,像杨哥是从来不会去问人家,出于对陈学的尊重,我从来不会问人家什么哈希map坎哈希map底层源码是什么,这个当然你放心啊,我肯定懂,但我不会去问一个有三年工作经验以上,去问人家这个底层源码是什么。
01:26
啊,这样,如果有一天各位同学你们也成为面试官了,如果这位求职者。识英雄,重英雄,切记这是对求职者的尊重,你不要去问人家这种无聊的八股文的面试题,答出来答不出来,不能作为他水平高低的参考啊,这是我个人观点,闲聊一举回到我们的题目,现在外面呢。OK,这个之前我们是不是介绍过,所以是这个动作,回忆一下在我们之前讲过的知识,杨哥给大家介绍过这些面试题,深度讲解过它不算新知识了。好,那么回到我们这儿,那么对于我们的这个right里面的跳表,这种结构,首先它撑死,它是一个数据结构,听懂了吧,不是什么神奇的知识,所有数据结构归中到底也就是那些什么堆栈,数组,链表,一些排列组合,甚至加了点新东西,比如说之前我们介绍过呢,这个list底子是不是就是我们的quick list好类,那么接下来来了。
02:30
这个东西是什么?能干什么?为什么会出现这种结构?给我们解决了哪些痛点和问题?兄弟们走起。首先为什么会出现跳表?我们先从一个单链表来开始大家讲解,那么对于一个单链表,每个节点都有指向后一个节点的指针next。那么单链表。增删改查这些基本操作,它的时间复杂度我就不再啰嗦了,默认你懂,最简单一句话,它是不是增删比较快,只要把next指针不要指向下一个节点,指向下一个节点的下一个不就OK了吗?
03:09
但是它变历是不是比较慢,所以弟兄们请看,对于一个单链表来讲,哪怕它存储的数据是有序的降序或升序啊,一般我们为了查的快,都会来进行先排序了以后从低到高,从高到低,然后再做进一步的细化和数据结构的选取。那么如果我们想要在链表当中查找某个数据,也只能从头到尾遍历这个链表,我们大家都清楚它不是数组,下面有索引,有个坑位,九号index出来,17号index出来,所以这样查找效率就会比较低,时间复杂度就是on。那么下面我就想能不能加快链表的查询呢?那这个时候我们来眼。假设我们在链表遍历的时候,我们的痛点时间复杂度最差,就会出现on,我们优化一下。
04:04
能不能给这个列表上面加个索引,俗称索引升级,两两取舍好,这什么意思呢?同学们请看啊,我现在要查找,由于链表的查找只能是从头撸到尾,那么假设我们要找18这个节点上面的元素,且已经是排好序的一个链表,12345678,走几步八步,我们要需要比较八次,那这个时候我就想问,我们能不能在链表的基础上?降低这个时间复杂度。好,我们在学MYCQ的时候讲过,MYCQL的索引是比加数,在所有数据结构里面,日常工作当中,你起码你要记得三个一个啊,弟兄们都清楚叫什么呢?是不是叫O1,一般我们的哈希查一次就能查到另外一个叫什么?是不是o log几二为底2N,那么另外一个是不是叫on?一般这三个是不是弟兄们一定要清楚明确的常考的动作。那假设我们的。
05:19
MYSQL数据库里面对于我们B加数,那么它呢,其中最重要的一个是不是就是。竖的左边的。是小,比中间节点小,右边是比这个节点要大的,那么这样的话,它是不是从便利的on进一步往上哪怕走一步,是不是可以变成裸个2N?那比如说裸个二八,如果八条记录,你全表扫描要走八步,如果裸格二八,答案是多少?是不是等于三?意思就是说如果八条记录,理论上而言,你要查找三遍三次便利就够了,那么这样算法的时间复杂度上面某个2N是不是要优于on呢?那么基于此,我们也就来设计我现在告诉你了。
06:07
我现在呢,只能是练表,我现在想在练表的便利上花点心思,做点功夫,我想便利练表不要是OA优化一下,尝试空间换时间。哎,注意啊,从。我们来这儿尽量的让内存紧凑。节约内存。前面所讲过的大多数情况都是以牺牲时间去换空间,这次是反过来尝试空间换时间。给链表加个索引,俗称索引升级,两两取舍即可,至于说什么叫两两取舍,三三取舍,我们后面聊,那么接下来我们解决方法就俗称升维,也叫空间换时间,好阳哥。痛点明白了,咋解决,我们来做一下优化来。
07:04
我们呢,这么干,假设啊,我们第一层12345678,我要比八步。那么这个时候我们就会发现,由于我这个链表假设是从小到大排序排好的啊。那这个时候我们就想一个问题,怎么减少这些查询的步骤,好索引升级,两两取舍。我们都晓得当前这个。一定是什么小于后面这个,那么两两取少一,三我取一,五八我取五。十,12我取十,15 18我取15,好,那么这个意思就说咱都清楚了,是从小到大的排列,那这个时候我不用12345678走八步。我能不能这样用更少的索引减缓这个走的步数,那么大家请看这有这么多。
08:04
这个呢,我呢,每次第一层是二的一次方等于二,OK,每次我这项是什么?二分查找就是折半查找一样,我加索引每次都是这些节点的一半,那么大家请看这次我再来找,那么现在要找18 18大不大于一,大于往后走,有点像我们二叉数一样,这18大不大于这个节点大于往右走一回事,18大不大于五,大于往前走,18大不大于十,大于往前走,哎,那么18是否大于20,不是了。到15接近了,往下往下,大家请看123456,这个时候是不是就少了两步,好,那么再来两两取手,一五得10 15得十,然后再来,这我们相当于说再在这个的基础上再砍一半。
09:04
二分之N再除以二,那么是不是就是四分之N,那这个时候是不是第二层就是二的二次方等于四,那么来吧,不用多说,18肯定要大于12,一步两步,这个时候回答我,我们直接过了这了以后是不是这比较的次数是不是就越来越少?OK,那么最终我们达到头节点和尾节点啊,假设我们这是两两取的话,取不到了,那么我们的所以就建到这儿。那么由此可见,我们可以发发从这个案例上可以发现加了一层索引之后查找的节点需要并列的节点。就会减少,这也就是说我们查找效率提高了,能不能理解我们前面所说的原始单链表,在上面给它加索引,每次砍一半,两两取少,那么这样他走的步数是不是就越来越少?好,那么弟兄们搁到这儿了,以后我们会清楚结合这我们再进一步优化,我们来看一下,你可能会说杨哥,我这个案例我感觉没有多少步嘛,好像也省不了多少事,限于我们的数据,最多也就八步,哎,你两两的话,节约一两步你看不出,不妨我们来个狠的,我们画了一个包含64个节点的节点,64个节点的链表,按照前面讲这种思路,建立了一个五级索引,兄弟们请看。
10:31
假设一六十二,63 64好,那么这个时候大家请看,每次砍一半。如果我们在这种数字量特别大的情况下,有没有发现?基本上就是一二三四五六七八九十十一。差不多到这儿,OK,所以说我们62如果以前变列要走到62步才能找到,现在我们直接就是什么11次就能找到,这个是不是有点像我们买色跳所学过的,你要么全表变列找到62,要么加索引一个二叉树,比我小的靠左,比我大的靠右,62步和11步哪一个效果更好,不用我多啰嗦了,所以这个就是为什么会引出跳表这种数据结构。那么杨哥请小总结何为跳表面试怎么说一句话,跳表是可以实现二分查找的有序列表,它是一种空间换时间,为什么索引占不占空间?这个在满赛克高级篇杨哥给大家说过,索引是不是也是一种数据结构,它建的是也要占空间的,我们强调过索引就像一本。
11:51
新华字典数据就是新华字典的正文,正文越来越多,节点越来越多,信息越来越多,那么目录也就这个索引是不是也越来越好?那么这个索引是不是也是新华字典的一部分?目录也是新华字典的一部分,听懂了吗?所以呢,我们都会明白,由于链表啊,单独而言是无法进行二分查找的,所以借鉴数据库索引的思想,我们提出在链表的关键节点上面给它加索引,先在关键节点上面查找,再进入下层列表查找,提取多层关键节点,就形成了跳跃表SK list,简称跳表。那么它好处就是可以以空间换时间的方式,在大量表上面加多极索引,实现减少节点的便利,快速的查找。缺点就是有点费空间,因为索引也占了一点点空间,所以你在链表上面添加的索引越多,空间占用的越。
12:51
最多OK,好,那么基于此,我们总结成公式,所谓的跳表就等于量表加多极。所以。
13:02
接下来给大家介绍跳表的时间、空间、复杂度分别是什么?你死记硬背不行的,他会问你怎么出来的求过程,你别忘了,我们这还有个小尾巴。跳表的时间复杂度是O个2N,首先要回答正确,第二个怎么出来的,你怎么推算出来的?第三个,那它的空间复杂度是多少呢?好,所以请同学们记着,红色面试题很重要,务必把这一小节拿下来,我们这儿先来看一下啊,前面这画了张图。第一层第二层第三层请告诉我是不是永远是起始数据的,看一半节点过来,那么这是不是二的一次方等于二?第二层是不是二的二次方就等于四?第三层是不是二的三次方就等于八,这么说能跟上?这什么意思呢?就是说你这个多少节点每次砍一半,假设两两取首啊,那么这个时候是不是这就是二的K次方?听懂了吗?哎,所以说搁到这儿,我们先来看一下啊,我们跳表的时间复杂度怎么推算出来的?先记结论。
14:25
跳表的时间复杂度O挪个2N好,怎么来的?请大家看,我们查询的时候,假设这个列表里面有N个节点啊,会有多少级索引呢?那么首先按照我们前面所讲,刚才看那个图两两取舍,每两个节点抽出来一个节点作为上一级节点的,所以那们以此估算第一个是不是总数的一半?对吧,第一层,那么第二层不是又是这层的一半,相当于二分之N再除个二,那么第三层是不是第二层的一半,又是四分之N再除个二,所以说叫八分之N,以此类推,也就是说DK级所引的节点个数是DK减一级所引节点个数的1/2,比如说我们的第三级K级啊,表示第三级索引节点个数是不是就是三减一,其是第二级索引个数的一半,因为我们都是两两取首,每两个节点抽出一个作为上一层嘛,所以DK级,所以你就能个数就是二的K次方分之N,第一波弟兄们没问题吧?好,那么假设索引有H几,那么最高级的索引有两个节点,哎,你可能说那杨哥为什么是两个呢?你可以把它这么近似的理解啊,就是头到尾,相当于是到头节点和尾节点,一般两两取首到两个就没了,OK。
15:51
哎,所以说在这我们就会发现最高的。两个拿不出来,你一个没意思嘛,对吧,所以说通过上面的公式我们会发现二的H次方。
16:06
分之N刚好等于二,就代表终结了,所以得到DH级就等于落个2N减一,如果包含原始链表这一层,那么整个跳表的高度干嘛就是落个2N,听懂了吗?所以说如果是两个节点,两两取首啊,两个里面出一个,那么它呢?基本上的结论就是这么一点点推过来的,那么这一点什么指数函数,对数函数,这个我就不再废话了,OK,都能听得懂吧?好,那接下来想问一下大家这么一个问题,大家觉得。我能不能三三取舍呢?但是这个问题我们继续就是杨哥,你这是两两取舍,我能不能135取一,80 12取85 18 20取15,这不就更少了吗?
17:05
好,那么带着问题我们呢,了解了时间复杂度它的推出来的公式,那么接下来我们来唠唠我们的空间复杂度啊,请看。比起单纯的单链表,跳表需要存储多极,所以肯定需要消耗更多的存储空间。那么到底需要消耗多少呢?我们来分析一下跳表的空间复杂度。第一步,原先链表链表的长度假设就是N,那么假设我们按照两两取少,这个已经说过了,巴拉巴拉巴拉对吧?每上升一级就砍一半,直到剩下两个节点,以此类推。如果我们把每层索引的节点数写出来,就是一个等比速率,请看原始列表大小为N。两两取少二抽一,每层的索引节节点个数就这么点,这么点,这么点。这几集索引节点就是全部相加刚好等于N减二,所以跳表的时间复杂度是on。
18:07
明白吗?数字越多,它呢,占用的空间也就越多,也就是说,如果将包含N个节点的单链表构成跳表,我们需要额外再用接近N个节点的存储空间好几两两取舍,那两个三个呢?那请问一下,思考一下,那也是原始列表,大小为N,每三个节点抽一个,每层所有的节点数我告诉你二了,那么弟兄们,你们能不能推一下三应该怎么写呢?好,同学们请看一下。三三取舍,那么每层节点的是不是也就是三分之N,三分之N再除三,九分之N,九分之N再除三,是不是就是27分之N1直到一,以此类推,第一级索引需要大约三分之N个节点,那么第二节所以大家需要九分之N个节点对吧?每晚上一级索引节点个数除个三,为了方便计算,我们假设最高一级索引节点个数就是一,已经是分无可分了,我们把每一级所引的节点个数都写下来,也是一个等比数列。
19:19
OK,所以最终我们会发现此时它的总的作用节点这么一家。按照这么一个。等比数列求和的公式二分之N,所以时间复杂度还是on,但是比上面的每两个节点构建的这种,所以呢来看,我们又要减少一半的索引节点的存储空间,所以它的时间复杂度on,那你说杨哥我懂了,我我干更狠妈,我试试。取一差不多了,二十三一积一,哦,一般足够你用了啊,个人建议好,那么所以说我们得到的结论,对于跳表它的空间复杂度就是on,哎,好,那么这两个请同学们面试的时候稍微准备一下它的推导过程以及最终的结论,那么好,最后跳表的优缺点总结如下,优点,最典型的空间换时间,一句话索引越来越多,对吧,多级索引嘛,自然而然占的空间越多,但是你查询的时间就少,空间换时间的解决方案。
20:29
再来这么做,只有在数据量较大的情况下才能体现出来优势,而且应该是读多写少的情况下才使用,所以它适用的范围还是有限。那缺点是什么?维护成本高,只就像数据库一样,你有数据了还要有索引,索引是占空间的,那么在单链表当中啊,我们都清楚,一旦定好要插入的位置。我们对于。新增和删除节点的时间复杂度就是O1指针一段是不是就没了,但是回到我们的跳表的话,由于你新增或删除的时候什么概念,就比如说在这儿啊,兄弟们,我们大家都清楚啊,就就这个吧。
21:16
假设我这啊需要在五,我这写个六行不行,那么我在五和六之间,我是不是先便便例先找到六是不是比五要大,比五要大,要先排在六的,要排在五的后面,那么首先我是不是要先找一次啊,然后再做插入,好非但如此,你最下面这个数据变了,上面的索引是不是也要更新,比如说两两取首。五料。八,那么就变成以前是五八取五,现在是不是变成五六取五了,那么可能索引要被逼迫着更新一下,所以它的缺点也就导致新增或删除时需要把所有的索引都要再更新一遍,为了保证原始列表中数据有序性,我们需要先找到要动作的这个位置,就是要删除点或插入点的这个写操作的位置啊,这个查找操作就会比较耗时,最后在新增和删除过程当中再去更新我们的,所以所以这个时间复杂度也是我们跳表的时间复杂度O罗个2N,因为主要是浪费在找。
22:22
对吧,插入和那些写操作就是OE嘛,列表就是next指向另外一个就完了,就一步,所以OE那个不复杂,啰嗦的还是这个。跳表的查找,那么还是我们跳表的时间复杂度O个2NOK,好,那么同学们,这个就是我们对跳表相关的总结,那么基于此,我们WRITE5大经典常用数据类型的原码分析就给大家介绍到这儿,这章还是重点参考,请同学们务必该记的记,该背的背。
我来说两句