00:00
来,同学们前面的题目和我们的最朴素的意思听懂了以后,那么接下来我们呢,从案例就要延伸到它的设计思想。那么下面啊,我们呢,走起。我们来看一下啊。按照他这个要求,我们先不看我们的笔记,同学们先思考一下。O1是什么意思啊?是不是叫一次命中斜?要写成高读要读成读成高,一次就要拿到,先想一个什么样的数据结构能保证你O1的时间复杂度。我们。不管是在介绍MYSQL,不管是在介绍Java,不管是在介绍高并发多线程的时候多次提及过这种数据结构,那么同学们,在Java的世界里面,什么样的情况下能够保证你一次就找到?请大家思考一下,我先暂停,同学们,我们继续。那么接下来走起。
01:00
所谓的这个缓存啊。那么。读写两个操作你逃不了吧,看到没有一个是。呃,一个是读取get,一个是写入put进去,好两大操作。按照命中率的思路思考这两个O1。它的特性要求必须要有顺序之分,以便于区分最近使用的和很久没有使用的数据结构。那么。这是最近使用的。这个是很久很久没有使用的了,那么告诉我兄弟们这个叫什么?是不是就是一个队列,那么这样的话呢,是不是就要有点像我们学过的消息中间键一样,哪些消息是积压消息了,你积压着我新的消息进不来,那么是不是也会有一种淘汰的算法,其实IRU不见得用在这种思想。不和某一个具体技术绑定,思想是通用的。比如说我们学英语。
02:00
有一种东西叫语法。比方说这些什么介词啊,各种虚拟语气啊,各种时态,初中英语要用,大学英语也用这种语法,这种思想是通用的,不存在于它的阶段,那么一样,兄弟们,我们这儿是不是得到一个结论,就是需要排队,我要知道谁是1234啊,每一个带了多久,我们在你排队排了多久了,对吧?那么谁好久没用,谁出局,谁利用率最低,谁出局,所以说。我们这儿既然需要排序,那么就要入队,第二读写一次搞定。第三,如果容量与坑位满了,要删除最不常用的数据,每次新访问的还要把新的数据插入到对头,那么前面说过了,按照业务你自己设定左右哪一边是对头,就像我们的red是不是叫l push和什么r push,相当于说如果我们的l push就是red,是不是有list?这个数据有两个命令,一个叫l push,那么这边是腾。R铺也可以往这边灵活啊,两边都可以,如果你告诉我两边都可以是单向链表还是双向链表这个队列。
03:07
对吧,所以说呢,慢慢的引导大家那么继续。查的要快,缓存慢一次就要出来,对不对。有就是出来没有就告诉我一个负一或者烂,第二个插入的要快,第三一个删除的要快,插入是新的要进来,删除是好久不用的要滚蛋。且还要排序。那么什么样的数据结构可以满足这样的一个问题?你是否可以在OE的时间复杂度完成?最后,如果一次就可以找到,你觉得什么数据结构最合适啊?那么下我再请同学们思考。我们学过Java集合类,哪些是增删快?对吧,哪些是查找快。有没有一种数据结构能够满足?那么请思考。第一个。如果一种数据结构能满足,这种数据结构应该是什么?
04:02
第二个,如果一这种数据结构不能满足。你觉得应该怎么写,是不是可以打组合啊?思考一下,同学们一次就可以找到,我们都清楚是不是一定是我们的哈西,那么另外一个,这个需要各种的进出。算着谁是多少次,那么这种是不是需要头跟尾,而且还可以左右互相交换对吧?左边也可以是设置为头,右边也可以成为头,左边也可以是尾,右边也可以尾,那么这种东西是不是只能是我们的链表?OK,那弟兄们,我们马上就可以得到我们的结论来。Liu的算法核心,注意叫哈希加上链表。因为如果我现在问你哈希map底层数据结构是什么,你一定会说这还不简单,JAVA8为列是不是数组加链表加红黑数对吧。那么这。
05:02
哈希式速度加链表类似,为什么呢?它的本质就是用哈希map加双向链表来完成我们一个结合体,这个就是我们的Li算法的核心,何以见得?找我在这个里面去找。一次啊。我要在缓存里面,首先它是一个缓存,这个缓存就是哈希加链表,理由如下,哈希找一次就能找到满足我们的查找块第二个链表。首尾相过,我们用双向的,是不是保证我们的增删比较快,查用哈希增删用链表,这样就比较方便,因为你。假设这个已经抖音这个项目很久没用了,给我出去,OK,只需要断,我们学过aqs啊。抽象了队列同步器,双向链表一断开,这些列表是不是马上就出局了?那么我们可以来看一下,走起动画片来给大家说。
06:03
这个就是l ruu算法的核心,哈西加双向链表,假设这是头,这是尾,对吧?某一个本来按照是123呢,我一找你看T1是这,T2是在这儿,T3是在这儿,好比红色的就是我们的。手机的使用者,我点哪个后台的浮动窗口,我现在要用它了,以前是123,现在二号是谁微博,我又想看看新浪微博,那么他是不是最近频繁使用的,将会被我拉到头,再次强调,这个头看你的业务和表现,可以是左可以是右啊,双向的,那么这样的话请大家看。我的入队和出对,只要把这个指针一换K1的。下一个以前是K2,那么现在是不是马上可以变成K1的下一个是变成K3 K3的上一个以前是二,现在马上变成K1的上一个。是以前,是以前的T1,那么这样的话是不是迅速完成,从查找到增删都是一次性搞定,出队入队都非常快呀,那么所以说我们的哈希链表是我们IRU算法的核心,这个请务必把握住他们两个组合才有这种可能。
07:20
查找也快,插入也快,删除也快,而且还能排序。好,那么接下来我们思想明白了,面试的时候就要说这句话,一听就知道了,一针见血。那么接下来我们就要编码尝试实现一个LRU算法,那么好在这儿我们呢给大家准备的案例。第一种啊。那么大家思考一下,我们应该怎么写?哈希加电表。
我来说两句