00:00
好,同学们,那么接下来我们看看第二种写法啊,为什么呢?啊,因为肯肯定通过上一讲大家都知道参考link哈,Map写出来的话呢。啊,非常巧妙,或者是叫投机取巧了,对吧,当然这也是你基于对这些数据结构的一种熟悉和了解。那么。运气好,这关就过了,运气不好,可能面试官会跟你说,不允许用link map请你手写。好,那么接下来从理论到编码,咱们认认真真的走一次。第一个。这点东西呢,我相信肯定都懂了是吧,无非就是说谁先进来,该走的坑位不够的话就走一个谁走,那么就是最近最少使用保障缓存。第二个问题是。哈希加链表时间复杂度都是O1,那么下面呢,我们要来试试你如何自己手写,那么原理最后看一遍。
01:01
增删有点类似于查找要快,删除要快等等哈,所以说我们用哈希加链表,那么上面是一个哈希map,下面是一个叫什么double link list,一个双向链表,那么每这个链表里面的每一个节点的数据是什么?是不是就是一个node?有点参考与我们的aqs的。OK,它有个头指针,有个尾指针,指针里面的一个个的节点,每一个节点是不是就叫漏,前面我们已经阅读过我们的。Aqs的源代码,那么这个时候我们不妨呢,来再来看一下啊,我们的AQS好同学们。这儿呢,它有一个AQS的队列同步器,我们大家都清楚啊。这个哥哥弄过来了以后的话呢,他这个类里面是有一个静态的内部类叫no。没问题吧,OK,所以说这个note里面它要装着一个一个的什么。
02:01
前指针后那个下一个前面指针后面指针装着一个个的什么等等一个线程,但是至少可以得到AQA4啊,是不是也是类似于我们的双向队列来进行,所以说我们这儿参考这个思想,第一个。哈希来决定它的查找,第二个通过双向链表模拟着参考着我们的aqs啊,来完成我们的。出兑和入兑什么意思呢?首先啊,最近最少使用这个用包含两种,一种叫写,一种叫读,再次强调大家请看这个是你。不管是首次写还是重复写,不管是首次读还是重复读,只要你点了它了。读和写粘一个就说明现在又用了一次,那么用了一次以后,它说白了,是不是要把它添到对头OK队列的头部,如果没有用的,那么呢,我们把它删除,如果说找不到,我们返回负一,那么这一切都是我们之前讲过的。
03:02
那么再来。回到我们刚才所说。我们这儿是不是有一个尿?哈map,那么这个new哈map的话,同学们请看我们都清楚啊。这个六哈是map的话。我们的底层我们都清楚哈希map它是不是有一个东西叫put方法,OK吧,那么大家看put value,哈希map里面有一个什么东东,我们原来强调过,相当于说这个里面。不管是aqs啊,还是我们哈map,它都采用了一种通用的数据结构,这种思想叫node,这个node叫什么?是不是一个叫map安好,相当于说我们的哈希map表面上丢进去put k,实际上而言,这个K又包了一层。是叫node,我们都知道哈,它这个node是不是一个,你看next单向链表啊,OK,那么结合我们的。
04:00
这个题目我们原来上一讲已经说过了,什么链表,双向链表,所以说结合这一圈思路。我们走起。我们就是什么哈希加链表,上面是哈希map,下面是表头,大家请看有没有点像我们以前讲过的aqs啊?没什么问题吧,我们是不是一再的这个。强调过aqs,我们干过这个都见过吧,所以说呢,参考着这个头尾指针和节点,我们呢,尝试着来写手写一下我们的。哎,还有算法,好,最后看看我们的算法打了以后,那么可不可以得到这个结果,或者是这个结果两个中的任意一个,对吧,你可以按照是访问顺序或者插入顺序都可以,好那么下面先看思路。走起,那么哈西迈,人家要干活,底层里面是不是有这么一个动作,我们这儿就得到的?一个结论,那么就是我们的map。
05:02
负责。查找。那么。要构建一个什么?类似于一个什么虚拟的。双向链表。他。里面。安装的就是一个个no的节点。作为数据。载体类似于我们的AQS和哈奇map强调过了,你看AQS也是。人家装的是什么,一个一个的。Node OK哈,Map里面也是什么node好,那么现在所以说我们呢,第一步啊,我们把这个总体思想写在这儿。那么接下来我们是不是应该有一个内部类,你看它是不是叫static class no OK,当然你这我们这也就定义一个静态的class node,这一波同学们能跟上吧,那么一样啊。
06:05
参考这些源码,读源码最终不是为了读懂。而是为了读懂以后能够照着写,那么大家请看它是不是要翻译到什么key呀,这些懂不懂我也一样这么难好。OK。OK,那么我们的node,那么是不是就是我们的TV建制队,我们讲过这种数据结构,哈希要装TV建制,对,但是TV建队拿一个no的封装。我们这是哈map,待会儿我们是不是自己还要再定义一个类,比方说啊,我们这提前去透,我们这是要根据我们的设计double。Link的list。这样的一个内压,相当于这个就是个载体double,我看双向链表。Linked list,它这个里面叫装,我们刚才的设计大家也看了,这个就像是类似于我们的AQX队列同步器这样的,这样的一个链表,装的就是一个个node,那么所以说第一步我们先要有这个数据载体node。
07:10
参考源码的思想,所以说我们这pro OK noe k,所以说我们这是个什么,Next这一波O吧,然后呢,Public node,我们的构造方法,那么this点它的前指针。等于它的后指针,那么现在都是,那那么这一步呢,其实就是等价于这两行。OK,现在就是有一个前指针后指针,告诉你它是个单向链表还是一个双向链表,如果只有next是单向,如果是两个都表示双向,OK,好。的构造方法,那么接下来我们都要有一个无参的构造方法,对吧,那么。跑过来这儿那么气。然后喂。原谅。OK。完了以后的话呢,那么大家请看this.t那么。
08:02
等于T。This value等于。Value,然后接下来还是前面的类似。有点类似于把它做一个数据的初始化。好那么。同学们。上面这个是。总体思路,下面就是我们第一步干嘛呢?构造一个no的节点作为数据。哪一题说穿了就是哈希map,说白了有点类似于这张图,哈希map这个K就是得到里面的一个noe,明白吗?哈希map也就是只关心气查一次就到,那么这个就是我们的第一步构建了我们的什么?No,那么KV。前指针下一个指针漏的构图方法,空仓的代餐的构图方法,这个时候我们第一步完成。那么第二步。
09:02
哎呀,是吧。构造。一个。双向。队列,那么里面。安放的就是我们的。Noe类似于我们的AA,现在noe是不是有了?Noe装哪装到一个个的双向队列里面,队列里面装的就是noe好。接下来。同学们,我们来看看我们的no应该怎么写。首先,漏。TV。OK。头节点。然后呢,一样。你晓得的。这个是不是尾节点。然后呢,Public。Double link的这么一个好。也是个构造方法,那么它这个构造方法就相当于说注意什么,构建一个虚拟的双向链表,这个是我们的。
10:02
第二步。这一波同学们能不能跟上?拿上来,一步步来啊,相当于说火车里面装的是一个个乘客,每个乘客就是个noe,带着我们的TV电车队好。安放啊。来,那么下面呢,我们这个没方法啊,后面是测试的这个写下去,省得刚才张飞了那么过来。空的,那么现在呢?相当于是一个构建这个虚拟节点,那么had就等于什么?Noe。这一波OK,头节点你要每一个双向队列里面,你就就像这样,这个头节点,原来我们说过的是不是头节点尾节点都要指向一些漏,那么所以说这儿类似于一个什么。
11:01
数据的初始化等于六。Note。然后呢,接下呢,相当于说我们先构建这个,构建这个的意思是我们拿图来说啊,现在是有个头节点和尾节点,强调过啊,头尾头尾随便你啊,放哪一边都成,有点类似于啊,我们现在要构建一个空的,那么有点是不是就让他们首尾相连,那么就导致呢是头节点。指向我们的。为节点,那么为节点。指向我们的头节点,OK,有点类似于先虚着这么来一个队列。好吧,那么这。待会儿呢,我们的指针会变好。完了以后呢,什么叫虚着来呢?有点类似于就是头节点的,因为双向。链表吧。那么你的自己是头,你的下一个等于什么?就等于我的尾。OK,那么你的。
12:02
尾的。前一个就等于我们的什么头,那么这样一个构造方法,你用了以后,相当于是不是就搭了一个轮廓,一个架子,头节点的下一个等于尾节点,尾节点的前一个等于头节点,那么这样是不是雏形有了,相当于有个车厢了,可以装。一个一个的no,待会就这么挨个进来,OK。这个呢,是我们的构造方法。这儿呢?2.1。构造方法。那么接下来。有了这个以后,是不是我们的2.2就是。添加到头就是最先进来的那个对头对吧,第一个元素转进来嘛,那么好。定义变量。构造方法添加到头,这个是重点,也比较难写。你其实也不难写,搞懂就行,I had,那我要干一件什么事呢?No he。V,然后node。
13:03
好了,那么我们这相当于说第一个节点现在是不是要进来了。好吗?那么好,进来了以后啊,反正它现在就是第一个节点,那么是不是头节点的什么。下一个。节点这些东西的话,是不是要这是不是要有个指针指向它,然后它有个指针指向它,这一波能不能跟上好,那么同学们请看,有点类似于就是我们这样的前后指针啊,还是aqs那套的思想,那么我们应该干一件什么事呢?那么当前船站这个节节点的下一个节点是不是应该指向。尾节点,那么是不是就是头节点的下一个?然后当前这个进来的这个节点的前一个是不是应该等于我们的头节点,那么头节点的。下一个节点原来是尾节点,尾节点的前一个是不是应该等于当前这个团在这个节点,那么头节点的下一个就应该等于我们的。
14:05
漏的节点,OK,好,不要慌,那么在这同学们可能会有点懵逼,我们这儿呢,直接把它呢?写过来一张,同学们一看就会了。那么现在通过上面的构造方法,我们已经知道了一个什么?虚拟的一个队列了。那么这个队列。搁到这,他说这个节点的下一个节点,这个节点下一个节点是不是应该是这个尾节点,然后是什么,那么现在尾节点怎么表示,是不是头节点的下一个节点,那么就是它,所以说这哥们。过去。OK。那么这个就是我们的next。然后你说这个节点的前一个,那你懂的是不是就是我们的这个节点头节点这一波同学们能跟上。当然第三个,那么现在就是头节点的下一个节点,OK的前节点,那么是不是现在就是第三行等号,左边这个数不就是尾节点导致尾节点的那么。
15:10
头顶的下一个的前一个就指向是尾节点,尾节点的前一个,那么是不是就是。指向它,那么这个是不是就是我们的。可以不,最后一个,同学们请看头节点的下一个,那就等于我们当前入队的这个节点一。那么弟兄们。这一波能跟上,通过这样是不是相当于它就入队,那么导致了我们的这个队列啊,当然这两个可以把它用虚线表示,你要不好看,因为重要的它们两个只是头尾,就是这个意思。那么同学们,这个就是我们的。2.2添加到头,那么。一样。2.3呢干嘛?如果说坑位涨了,是不是我们要。
16:00
删除。这个节点同意吧,那么所以说是public VO。Remove node,那么过来吧,No TV,然后node来。各位亲,过了删除节点,下面说这个节点要干嘛出对,那么怎么删呢?这个时候,那请同学们注意。那是不是这个节点的下一个节点的。前一个节点等于no的点。哈,我们先写完这个节点的。前一个节点的下一个节点等于no.next相当于绕过它,然后no点。CRA前接点等于烂了,那么no.next节点也就等于我们的。烂了能不能理解,比方说这个要出对了啊,还是这样啊,我把它考过了,那么请同学们呢。思考,那么进来入队这就不管了。
17:02
我现在。假设要删除啊。请看啊,要删掉,那么是不是这个节点的下一个节节点。前节点等于以前这个节点的前节点,那么相当于说它就要出去了,把这个呢,就要指向我的前一个。那么这个节点的前一个的下一个节点,就等于我原来这个节点的下一个,给它指向后面一个。OK,就这两句话,然后我自己的前后都变成捺,那么我是不是有点像我们以前这样,这个哨兵节点就出对了?OK,那么请同学们呢,这样一定要跟上,那么完了以后我们呢,删除节点完成。接下来。2.4这个叫什么?获得最后一个。这个时候呢,就是。Public。Not get。因为最后一个节点要出对嘛。他应该怎么办呢?那么就是return,那么尾节点的前一个节点,那么到最后可能呢,最后一个节点呢,就需要你滚蛋,要是坑位满了的话就要出局。
18:11
OK,那么这个就是我们手写算法,我们的两个数字结构,一个是构造。一个漏的节点,第二个虚拟的一个双向列表,那么它里面呢?各种方法。加头。删除获得最后一个节点,好,那么继续。这些数据描述清楚以后,现在终于到这相当于我们的构造方法。一口气将它写完硬套。那么比方说。Cash。上一次吧,这一波这次换一个OK,那么来了我们接下来呢,就是我们的。Map,那么这个map啊,我们就数字,那么这个map里面就像我们这儿弄的。音体讲第二。数字吧,就好出一点,相当于这个map,就告诉你哥们。
19:05
我要干的活就是这个map,装的是一个个漏好。那么这个漏就是我们map,那么。上面呢,就是double link的list,那么我一步步完成。它呢,也就是一个个no的节点。这个节点里面,那么里面就是我们的什么呢?一个一个的数字。OK,这一波没问题吧,那么link list好。搁到这儿,完了以后,终于轮到了我们的什么。构造方法,Public。这个呢,慢慢的就写回来。和。前面的就越来越接近,也越来越一样了。好,写到这一步,我们先暂停一下。
我来说两句