00:00
来,同学们,我们尝试着来手写一下我们的IRU,那么这个方法呢,有很多很多种写法啊,具体的同学想挑战自己的,你可以在这去写,但是实际工作中他可能要求你。最好最快短平快的来写,那么这我们先介绍一种其中的一种方法,那么。最好的最快的一种方法啊,算是有点这个投机取巧,哎,那么我们先来体会一下第一种,那么Java。做到这儿了以后。非常的成熟,很多API你都可以继承了以后直接使用,那么我们第一种方法干嘛呢?参考我们的link的哈希map诶。杨哥,这个是个什么东东?六。Link的。哈迈。OK,那么同学们这就是什么?是不是有点刚才我们所说的哈希加链表啊,能跟上,说实话他就是天生最适合做I算法的。
01:08
何以见得,请同学们打开。我们的源代码注意啊,哈希迈普大家肯定用过link的,哈希迈普是可以按照顺序能够对我们,因为哈希本来是散列嘛,那么我们想有有序的哈希map呢?Link哈希map可以是一种实现和参考,那么我们来看看他的说明和源代码。那一点开了以后,构造一个空的。这样的一个按照顺序插入的link的哈希迈普,它的实际上而言呢,大小是16,复杂因子0.75,得到一个什么结论,兄弟们,这货是不是有点跟我们的哈西map差不多啊?哈斯迈也是构建出这么动的。那么我们不妨看看它的。结构。我们得到一个问题是。Link哈希迈普继承哈希迈得。
02:01
你看人家是不是也可以继承一个,对吧?好,Link的哈希迈普继承以哈西麦,它是这么做的,有这个一一生二,二生三,三生无穷。那么我为什么会提起这个呢,同学们?请看一下。大场考的这个过程当中,就看你写的算法,可以看你的思路,来看看你对JDK的熟练程度了,那么同学们。不妨我们往上翻。找到了以后,我们可以看到看到这样的一段说明文字,第64行,他说,This kind of map。这个这个这样的link达哈是map,这个map啊。非常适合于构建Li cash的。说明什么概念?它是不是天生就是一个I算法的最佳实现者呀?那么?为什么呢?来同学们,因为它也是类似,实不相瞒,就是I算法的体现。它这有个方法叫。
03:06
Remove old entry意思是什么?你看oldest什么意思啊?是最近最常使用的entry插入到这个map里面。那么干嘛也一样,将会如果你是最老的了,会干什么的,把你remove不掉,所以说参考它,我们来用最快的方法来实现这个link克的哈希迈普,我们就可以投机取巧的干一件什么事啊兄弟们,如果link克的哈希迈普是继承以哈希迈普,那么能不能写一个我我们要为了完成这个算法,能不能实现一个事情是我们自己的类来继承这个link克哈希迈普,借用他的API是不是可以完成这个工作。最好最快。好,那么同学们,我们简单的就来写一下。走起。那么。搁到这儿了,以后我们应该怎么写呢?会让你大惊失色,大吃一惊,简单到让你觉得不可思议。首先。
04:06
我们呢,放行,OK。那么我就继承以。Link的哈,Map那么KO了吧,好了。那么接下来。接下来,同学们请看我们这么干。第一个。参考我们的题目要求,你看人家是不是写这么一个类,我也写了,人家这有一个什么构造方法,我也这么干,为什么这个值啊,就是我们缓存的容量,说白了就是这个坑位,OK,那么来吧,那么。Private capacity,那么这个就是。什么东东?缓存坑位没问题吧,比方说待会我们设置成个三啊那么一样。我们看呢。要带个构造方法,你看这个构造方法的话。
05:01
默认出现是不是要写?哪一个是不是还是写负类一样的,那么一样负类以后我们干嘛再把这个元素加进来,OK,我们在这儿了以后干一件什么事。印堂。我们这儿呢,不用这个啊,直接简单一点,尽量跟它保持一致啊,就传这么一个就完了,好,那么这个负类它是什么意思呢?我们呢,这个副类有很多种,这个副类是哪个,就是我们的link哈,Map,还有这个,还有float,还有这个,我们用哪一个呢?如果我不为了讲课,我们用哪一个都可以,但是这呢,我们为了给大家演示一些效果,我呢用第三个,这是一个构造方法重载,听懂了吧,负类的它呢是int float和布尔型。好,那么同学们点开它,它自己说的这个看那不用说了,那么就是你传过来那个值啊,对吧,那么。假设我们现在这个坑位就是三个,那么0.75就是哈西迈默认的负载因子,关键是第三个叫access order反问顺序,那么这呢,我们就给大家呢。
06:09
看看这个怎么弄啊。待会我们会说,这个反问顺序倒是值得我们来花点时间来看一下这个效果和对比好。Access。Order代表是反问顺序,那么如果是true的话,你看它是按照反问顺序来。如果是force的话,它是按照什么。插入顺序来那。字面意思是不是暂时有点懵逼,搞不懂啊,不重要,我们先完成我们的工作好,根据刚才所说的,我们现在呢,是不是就干三个参数的这个那么好。现在。坑位就是它那么负杂因子啊,我也就写死了啊,我就不去定义什么产量了,这偷个懒啊,那么下面我们这儿就写个处,反正它这是一个什么布尔行吗?布尔行不是true就是false,我这用处第一步完成完全跟这个是么一样。
07:10
第二个。我们是不是要写读写呀,那么就是put对不对,哈希的,可问题你懂的,我这个link哈map已经又继承了哈MAP100%它已经天生自带什么。Put get不写,但是我们为了完成我们的功能,我们需要有一个,如果说这个坑位不好意思啊,只有三个,那么第四个来了,你需要告诉我怎么腾出去一个坑位删除的方法,所以说我们要remove干嘛?Old en将这个构造要将这个删除方法进行方法的over right重写一下,那么它的写法很简单,如果负类的size就是这个,它带的已经。大于了我们的这个坑位了,听到那么好假设哈,Map里面的这个size就真实存进去的数字已经大于,待会我们做测试,假设我们的坑位就是三个大于这个三个了,我们要把最近最少使用的remove了。
08:15
就这么简单,OK,好,那么同学们,我们下面呢?直接来做一下这个测试,那么这个类呢,过来吧。然后呢,IRU看DEMO等于六。搁到这儿,我们呢。几个三个很简单,那么LDEMO这一个葡特,那么一这个就是A,这一步没问题吧,那么来现在呢,我们就是二,然后呢,这个就是三,这个是B,这个是C,我们重,因为重要是这个k value无所谓,所以说这呢,我们先来看看我们写的对不对。点,如果这样打印也可以,但是它会连这个key和value一块打印过来,我们只关心T,所以说我们这key set OK,那么同学们来吧。
09:07
一跑我们呢,将会看到我们的结果,如果不出意外,我们的123是不是就存进去了?OK,那么到这儿我们的I算法就写完了。简不简单?当然,还有好多细节给同学们展开。坑位是三个,你现在存三个,那么最先进来的,你看是不是就像入队一样,123 OK,那接下来我要给同学们。惹事了。干嘛?我这是不是铺他。第四个是不是出来了。这一波没问题吧,那么第四个出来了以后,我们再来看看。那么你告诉我,兄弟们现在谁走呢?谁会被挤掉?那么按照时间而言,最先用的是123,最近最少使用的是不是一是最少的?那么不妨我们再来看一次。
10:06
大家请看。这次啊是123入队,然后完了以后四啊。从这个顶进来,它是就像我们有点类似于是什么概念,123抖音,微博微信,OK,第四个假设我们要点开一个美团。过来把一抖音给挤出去了。OK吧,那么好,我们一步一步的来。继续给大家验证。假设现在啊,我们来随便找一个。就说三。3C3C无所谓啊。我们呢?继续。三又来了一次,现在也就是说上一步的结果即是叫234,没错吧,我这个三又来了。四是新数据以前从来没出现过,那么我们主要现在呢,要给大家看一下。
11:01
也就是说目前我们在处的这个情况下,什么叫反问顺序?OK,那么来,同学们,这是3C。好。这是3C,我再来一次好。这是3COK,然后我这儿来。五。X。那么我们来看看。他。又会出现什么样的效果?那么大家告诉我啊,现在如果四倒是好理解对不对?四挤进来把以前。不常用的一给挤掉了,但是现在呢,新加入三个333,就是我又点三又点了三次,假设第一个三进来,现在打印什么,第二个三进呢打印什么,第三个三打印什么好,请同学们可以思考一下。同学们,我们呢,直接跑一步走起来。大家请看。现在是。四进来的时候,我们的结果就是234,但是三进来以后请看。
12:04
三一定是往前搞,看到没有三三。三听懂了吧,他每次啊都会在这个最新的按照访问的顺序填到这儿,那么234,那么现在三就不是最近最少使用,三是不是最近最经常使用嘛,对吧,点了三次嘛,那么这这这好,然后的话什么直到五进来,那么上一步的结果是这个五进来继续往前搞把二。给挤出去,OK,好,那么在这个测试条件下面,我们主线我们现在的值是多少是错啊。我们呢?来看一下我们的运行数据,是这个处,主要是要给大家说清楚什么,这个处跟false是不一样的啊,处是反问顺序,False是什么?插入数据,那么这两个有什么区别呢?那么来,同学们,我现在把它改成false。
13:01
这个order就变成false了啊,那么来,同学们又来看看。这两个有什么区别和不一样的地方?好,那么同学们。不妨啊,我也给大家看的清楚一点,我先把它注掉,我们跟刚才一样啊,那么也就是说注掉了以后,就是前两次如果是处的话是123234,那么如果现在是false呢。那么大家log有没有什么区别啊,那么大家请看是不是也是123234啊好关键啊,那么在这是现在是first后面的效果,那么要给大家演示,那么来。我们从第二排234开始看。第二盘是234,听懂,你看它后面都是234 234234,然后又是345,那么请大家。对比一下。To跟fourth,你们觉得?能看到什么东西?前两个都一样,123234,坑位充足嘛,好说。
14:03
然后呢?四加进来了以后又来333啊同学们请看它的顺序是24324323,也就是说有点类似于什么三进来三进来三进来,但是有没有发现啊。到最后三个三的时候,处的时候是243,但是我们的负的时候是234 234 234怎么着是不是有点类似于是纹丝不动啊,它没有往这扎,它是按照什么可以就像是没有移动,可以省略一些步骤一样的,有点类似于这样,那么到第五个进来了以后,不好意思啊。按照我们的处这种情况,第五个进来,不好意思啊,二给我滚出去。急着补进来,但是呢,我们这儿234大家请看。它的顺序上面这个处是435,下面这个处是345,听懂了吗?那么这个东西。234最近最少使用的是二五,也就。
15:00
把它挤走了,OK,但是中间这步顺序他们是不一样的,一个是243,一个是234 OK,也就是上一步的结果集会,因为这的出false,它的访问顺序不同,我们呢会得到两种顺序,那么你在使用的时候,请同学们务必注意这个小细节。好,这个就是我们用的什么投机取巧,最简单的用link哈,Map完成了我们的I算法,那么面试当中对吧,如果说能够用这个算法能够过关,那么恭喜你,这个面试官可能是。蛮喜欢你的,不会难为你了。
我来说两句