00:00
好,那么这个数的这个内容呢,咱们就告一段落了啊,然后呢,咱们这一章的话呢,就算是讲清楚了第一个啊这个问题了啊,下边呢,就回归到咱们这个集合的源码这个层面,集合源码这块的话呢,我们主要呢,就讲两大类型,第一个呢,就是list这块的一个呢,就是我们的map。Set的话呢,因为set的底层就是map,所以我们讲完map的时候呢,最后再说一下这个set这个事儿啊就可以了。好,然后这块呢,我们首先来说一下这个list啊,List这块呢,我们讲过它的三个实现类啊,一个呢叫a list啊water,还有我们这个叫link list。诶,我们就按照这个顺序呢来讲解啊,首先的话呢,提到这个叫a release,哎,那首先我们先回顾一下它的一个主要特征啊。首先的话呢,这个呢,它呢实现了这个list接口。那例接口呢,它刻画的呢,就是来存储叫有序的。可以重复的这个数据是吧,所以这个呢,也是这样的特征。然后呢,这个呢,咱们说一下它的底层使用的是。
01:02
哎,数组了是吧,是object类型的一个数组存储的。啊,这呢是它的一个点,然后另外呢,这个瑞呢,它还是一个叫线程。不安全的是吧。它呢是线程不安全的啊,这个大家要注意一下。好这呢,就我们主要体现的它的一个特点了啊,那提到这儿呢,顺带着你像我们这个外ER的一个特征。这个不变,这个不变,它是线程安全的是吧,对那对于我们这个link的例子来讲呢。这个不变,这个不一样了是吧,它呢底层的使用的叫。链表啊,具体来说的话呢,是叫双向链表。啊,进行数据的一个存储。好,它呢也算是一个线程不安全的啊OK,行,这个呢,我们就说清楚它们三者的区别了,然后下边的话呢,我们就来看一看底层源码的一个问题。圆码这块的话呢,注意哈。大家你会发现呢,我这呢写了两个版本,一个呢是GP7,一个呢是GP8啊,因为七跟八的话呢,这两个版本呢,相对来讲底层源码变化稍微的大一些,然后呢,我们现在呢用的是GTK17了,17的话呢,相较于八的话呢,也会有变化,但是这个变化呢就比较小了。
02:13
他可能说原来这个定义一个方法,现在的话呢,他把这个方法呢,抽取出来,又里边这个代码抽取出来,又造成个方法了,然后在这个方法里边掉这个方法了,可能会这样啊,诶变动呢不太大,诶所以这块呢,我们以一个分界线来说的话呢,这块我就讲这两个版本。包括呢,现在呢,企业当中这个G8呢用的比较多,包括呢,在面试的时候呢,面试官一般呢,也都是主要问你这个八的这个版本这块呢,我们顺带的把它也说一下,这样会显得你整个这个表达面试呢会显得很厚实啊。好,那这个JDK7的话呢,咱们之前没有装,哎,当然呢,你可以装一下啊,这个我放在哪了呢?咱们这个资料里边,JDK里边,哎这呢是我们这个是17,这呢我还放了一个七,诶放单的目的呢,其实就为了我们现在讲这个源码,哎,大家看这个源码方便啊,然后装完之后的话呢,我们在这块咱们有一个project structure是吧,针对我们当年这个位置,哎,当然你这个操作之前呢,先来这儿啊。
03:11
这不有个IDKS吗?哎,你把他那先添加过来。这个还记得吧。哎,这要没有的话呢,你就先来个加号艾JDK,然后呢,看你装哪了,哎,我呢是装到了我的这个位置了。JDK1.7就它啊,然后点OK。啊,这就过来了,过来以后的话呢,我们建议你把这个名呢,稍微的给它精准化一点啊,CTRLC一下,哎这么着,然后apply。就可以了啊好,这个添加完以后的话呢,我们来这个modus这个位置,针对咱们当前这个module,然后在这块呢,我们就可以呢,指定呢,用这个比如说1.7的。这时候我们要用debug的话呢,自动的它就呈现的是1.7的这个源码了啊好这个位置呢,我们也可以呢,比如说选成七的,哎,这个JDK的API是吧,这个都可以啊。其实这块都还好,关键的就是这个IDK啊,你给大家设置好啊。
04:02
好,这个呢,我们就来确定了,确定好以后的话呢,这块我们首先来看一看啊,以这个七这个版本为例,诶,它的一个源码的一个情况啊,其实无外乎呢,就是我们涉及到呢,首先到对象。比如说我们这个啊叫a list,这个有泛型了,咱们就指定一下啊,假设呢,我就写的string了。哎,你一个。A release这么着写的,然后接下来我们拿着list点里边呢,添加了一个A。是吧,哎,比如我们再来一个啊艾,这个叫BB。哎,其实呢,我们就说一下这个过程呢,哎,它底层到底都是怎么做的啊,咱们呢先说清楚,然后呢,咱们再拿这个代码呢,再给大家去演示看一看它的源码情况啊,那对于这个JDK7这个版本来讲,我们一开始呢,去把这个诶对象呢就造好了,这个时候呢,它底层呢,就会直接呢对于我们这个。呃,集合里边呢,这个数组结构就会做一个初始化。啊,它底层的这个数据结构的话呢,我们提到了就是一个object类型的一个数组,它叫做element。
05:03
哎,Data啊,这个数组啊,然后这个数组的话呢,直接呢,就拗了一个object类型的一个数组,相当于我们这行代码一写完,这个数组呢,就造好了。这个数组呢,我们使用的是空三的构造器的情况下,这个数组的长度呢,就是十。哎,所以呢,就相当于我们默认的话呢,能够往里边放十个元素啊。好,你要再往里放的话呢,就盛不下了,盛不下就会扩容了啊好,当我们这块去调这个爱的方法的时候呢,它就相当于呢,把这个元素呢,就添加到我们这个呃,数组里边了。那就相当于我们这个角标零的位置。哎,他放的就是我们这里的这个A了。哎,就是这样的情况啊。好,那下边这个呢,自然而然的。诶,CTRLC一下。哎,粘过来这个呢,就放在这个叫BB。哎,这个是放到角标一的位置。呃,尤其呢,是这个位置,我们要明确说一下啊,只要呢,你造完这个对象以后,哎,我们说呢,就是底层。啊,会初始化。
06:03
哎,这个数组。啊哎,就是长这样了啊,通过这个呢,我们也能看到这个默认长度为十啊。这个我们把他那放到上边吧。说。诶,如下代码的这个执行啊。然后呢,它底层会初始化数组,然后呢。数组的。长度为十啊这样个情况啊。这个我们就看到了啊,然后呢,这个时候呢,我们就相当于呢,诶给它里边呢,去一个一个的添加了一个元素啊,然后就点点点。不断的添加,那就有可能是不是超出我们这个数组的范围了,是吧。哎,那这块呢,当我们添加了十个元素以后,当你要去添加第11个元素的时候。嗯,第11个啊元素的这个时候是吧,这个时候的话呢,注意它不会出一个角标越界了,它呢,就相当于呢,在添加之前呢,先判断一下这个长度够不够,如果长度够呢,就往里放,如果不够了就该扩容了是吧。
07:06
哎,当要添加第11个元素的时候呢,说底层的element。啊,这个data的这个诶数组长度哎,或者叫数组呢,已满是吧,则需要呢扩容。哎,那我们说默认呢,扩容为。原来长度的。啊,1.5倍。空为原来长度1.5倍,然后呢,并将是不是原有数组中的。啊,元素是不是,哎,复制到新的速度中啊。OK啊,这就是这样一个过程,然后呢,你复制完以后呢,接下来是不是就接着添加。第二天加的话呢,如果要不够了。不够的话就再扩容,再扩容还是默认扩容为原来的1.5倍。好,这个呢,就咱们说的1.7当中的这样的一个代码啊,那这块呢,既然说到这儿了,咱们CTRLC下。
08:00
来下边呢,我们来看一看啊,咱们先把这个事说清楚,然后咱们跑这个源码,看看是不是这样子的。关于我们这个list,它的一个测试啊。好,单元测试第一个啊,好把这个代码呢,我们就直接再拿过来了。这个alt加个回车。行可以了啊好,那么这块我们看这源码的话呢,呃,大家呢,可以通过这种点的方式来看,我直接按住CTRL键是吧,我一点这不就看它的构造器了啊,或者的话呢,我们是不是就可以debug了。哎,那咱们用一下debug吧。Debug的话呢,比如我们这儿呢,点一个断点啊,然后这块我们点一下这个叫debug。哎,稍等啊。诶然后呢,这块呢,就呈现出来我们相关的一些这个对象的一个情况了。啊,这个我原来呢,这块加过这种断点了啊,现在的这个断点呢,我就先都去掉了啊行,回过来重新呢,我们再去来一个啊第八个。
09:01
诶,这时候你看这个代码呢,停留在这儿啊,我们现在想看一下它这个构造器呢,是做了点什么,所以我们这块呢,是不是就点这个啊。啊,点一下。啊,这个位置呢,它相当于是涉及到一个加载的一个事儿哈,啊,这是我们讲反射的时候提一下这个类的加载器啊,所以暂且呢,我们就先跳出来,然后你再点一下。啊,这呢就进去了啊好,进去以后的话呢,我们会看到它呢,又调用了它重载的另外的一个构造器,这个位置呢,写的就是个十,那我们再去点一下这个,诶好相当于就看这个源码。这个位置呢,我们传进来的是一个十。这个星号呢,咱们就不用看了。然后接着往下走,这呢传的一个十吧,是不是这个十嘛,往下走一步说你这个小于零嘛,显然不是是吧,哎,再往下走,直接这不就到这了吗。相当于我们现在看这个构造器的时候呢,它就创建了一个长度为十的一个object类型数组,针对的这个叫element data塔,就是咱们诶。这个里边数据的这个类型的数组。
10:02
啊,这就看到了啊对它呢,进行一个初始化,然后你再点这个按钮啊。就回到这个断点位置了,好,然后这块呢,就没啥了,我们再点就回去了。哎,就回去了,相当于这个构造器的一个执行,咱们看到了底层数组啊,确实呢,就创建出来了,那针对于呢,这个位置这个S已经不是咱们这个这个里边这个S了啊成了它了,所以这块看不着了,刚才进去的时候能够看到这个数组呢,创建了。这意思啊,你看我再重新跑一下啊。这时候呢,我们点进去。啊,又到这儿了啊,咱们再出来,然后再进去,这不就进去了吗?然后呢,比如说我们,诶我走到这儿吧,刚才咱们看过了啊,然后这时候这个this呢。这时这个呢,其实就是我们当前这个创建的这个对象了啊,所以它里边这个element data这不就能看着吗。哎,这不,它就有这个长度为十的这样一个数组了吗。哎,大家说,诶我那块看都看不见,哎这块如果你看不见的话,你这样啊,这个呢叫customize views。
11:01
就是在你这个debug的时候呢,这个空白的位置点一下它,然后呢,把这个去掉,把这个去掉。看这两个都去掉是吧。这时候你再看的话呢,就能看得到了。这个在我讲这个idea使用的时候呢,最后debug那块呢,最后我有这样一个截图啊,你去找那一张呢,就能看到啊。好,这样我们就看到了啊,就像这块我就出来了,下边的话呢,我们看一看啊,往下走一步,哎,调这个爱的方法了,我们进到这个源码里边。啊,进到这儿了哈,哎,现在我要添加一个A了,首先呢,一上来就inure capacity eternal,这个呢,其实就是在判断一下我们当前这个容量够不够,不够的话呢,你就扩容,够的话呢,直接就走到下一步了,这个非常简单,就是添加进来的意思了。所以呢,我们首先呢,需要判断这个容量够不够,目前的话呢,这个size呢。实际上是零是吧。啊,就是零加个一,就这意思,咱们进到这个源码里边接着看啊。这个零加一呢,其实这时候呢,我们这个m capacity不就是一吗。
12:02
这个位置呢叫mode count加加,呃,这个变量呢,咱们就不多去说了,它呢是每次你做增删改操作的时候呢,这个变量都会做一个加加呢,就记录一下你增删改的这个行为。啊,它呢,实际上涉及到了一个快速失败机制了啊,这个不在咱们现在讲的一个范围内,咱就不管它了,好,然后你往下走。走到这儿了,诶当前呢,我们不是第一次添加,所以这个是零加一,这个是一一减去我们这个element得塔点lengths,就看一下你当前这个数的长度是不是正的。这个capacity你看咱们刚才怎么来的呢。是这个size加一来的。哎,就是现有已经存了这么多个了,你马上不是要加一个吗。要加一个的时候呢,看一下跟这个速度长度比一下,看够不。啊,你像刚开始加这个,显然这个数小,这其实呢,我们要判断的话呢,这是一这个呢,是不是十啊。所以这个就没进去吧。那就意味着我们不需要扩容。
13:00
你想对吧。不需要扩容啊,所以这块我们再去呢,点一下的时候呢,这不就直接略过这个衣了吗。哎,就出去了,什么时候能进来呢?对,你想这个呢,本身是十,你这个11的时候是不是就大于零了,那不就是size呢,是十了,然后你又加一个就相当于不够了呗。诶这时候才需要扩容是吧,所以现在你看我们第一次加的时候呢,这块呢就没进去啊,所以呢,接着执行,这不就出来了,然后呢,相当于你没扩容,直接呢,就把这个S是零嘛,哎放到零的位置了,把A呢就放进来了。啊,这个时候呢,我们再往下走一步,你要再看你这个Z里边这个速度里边,诶你看第零个位置,这不AA就进来了吗。啊,然后我们再执行,这不就出去了,然后再往下走一步,就该添加这个BB了。啊,添加BB呢,这个咱们看一眼啊,然后呢,我们再进到这个源码里边,首先呢,一上来也是先看一下这个是不是需要扩容的事,那第二元素呢,肯定也不需要扩容。咱们借着他呢,说一下需要扩容的时候啊。
14:00
需要扩容呢,其实就意味着我们当前这个数字里边其实已经都填满了哈,Size呢,再加个一显然就大于零了,这是我们就要割肉,这个呢,注意是把。比如说呢,你是S是十了加个一,这就是11哈,把这个11呢进来。哎,我就直接呢来看了哈,这呢叫格了。这个格位的时候呢,这个传进来,你注意是11。首先呢,把你当前这个数组的长度呢,先拿到这个,咱们知道是十是吧。好,然后呢,你看。新的这个容量。是旧的这个容量再这么着一下。诶,这个是不是就是扩容为1.5倍的一个事儿啊。你看这个是十,它加上这个向右移位,这不除以二吗。这不是五吗?哎,这呢,新的这个容量不就是15嘛,所以呢,就是我们所说的这个1.5倍嘛。然后最后呢,再把你呃现有的这个数组传进来,然后呢,再把你新的这个容量传进来,主要目的呢,不就是为了诶把你现有这个数中元素呢,都在这里边造个新的数组元素呢,一个一个放进去,诶造的新的这个数组呢,再付给咱们当前的这个属性呗。
15:06
哎,就是这样一个过程。所以这块就有一个扩容的一个行为是吧,哎,这个大家注意一下啊好,这个我们就诶回过来了,哎,我就直接呢就结束了。诶结束了啊好,那咱们刚才呢,相当于是把这个1.7这个源码呢,就看清楚了,1.7完了以后,下边呢,我们来诶看一下这个叫1.8的这个行为啊。我呢把这个事儿呢,还原封不动的CTRLC,我呢就粘过来,我说一下这个区别,这样一对比大家就知道了。然后当我们执行这一行代码的时候呢,诶说呢,底层注意这时候呢,并不会初始化数组。哎,这个事儿呢。这个事其实也做了哈,但是他做的话呢,他他是整了个这个东西哈。嗯,你说初始化吧,其实也算初始化了。啊,初始化的时候呢,它是。这么着一下。你看这个会报错吗?不会有同学说你这也没写长度,这也没写元素。
16:03
Uh huh。对这个呢,你可以理解成了就是这样也行是吧。哎,这样也行,或者说呢,我们这样一写的话呢,这其实你是想动态初始化了。讲静态初始化了啊,但是静态这里边儿你也没写东西,所以长度还是零。啊,所以这块呢,也可以这样说啊,说底层呢,会输入化数组。但是呢,初始化是长这样。那其实呢,就相当于我们没有看到它创建一个长度为十的这样一个数组了,是吧。然后呢,我们要去往里添加,那显然这块长度是零啊,这咋加呀。诶这样说哈,说首次。哎,添加元素时。啊,首次添加元素时呢,我们会啊,重新的这个初始化。哎,初始化这个。我们的这个呃,数组怎么着呢,就把这个element data呢,我们重新的给他再去扭一下。
17:00
这个时候呢,我们出现这个十了。这个是首次添加元素的时候啊,然后呢,这个出来以后呢,接着我们再把第一个元素的位置呢,哎,制成一个A了。诶,你第二次再添加直接呢,拿着你现成的这个呢,再去往里放就行,然后后续这块呢,没有什么区别。所以大家你会看到主要区别呢,就是一开始的时候有没有把这个数组造好的问题。啊OK了,行,这个完了以后来回过来啊,咱们接着看这啊,这个时候的话呢,我这么着。诶把这个位置呢,咱们调成1.8是吧。啊,这就意味着咱们现在呢,针对咱们当年这个module哈,我就想看一下1.8这个源码了,诶OK一下。来,我们再去做一个第八个。然后呢,我就进到了源码里边啊,又跑到class load了,你看这时候呢,看得很清楚,这不就1.8了吗。然后呢,我再退出来是吧,然后重新呢,我再去进去,然后就进来了,进来以后的话呢,大家明显看到不是掉重载的构造器了。
18:05
直接呢,这1.element,这是一个全局常量是吧,直接我们点一下。是不是我说的这个意思啊。诶,这时候我们造了一个数组,这个数组呢,没有任何元素。啊,就相当于呢,也不空。啊,就是回到我们刚才CTRL加个左是吧,回到我们刚回到我们刚才那个场景的话呢,就是这个元素呢,并不是no哈,实际上也造了一个,只不过呢长度为零。行,然后呢,我们接着呢,走下一步,下一步诶回来相当于你这里边儿呢,就是初始化为一个长度为零的一个数组了,接下来我们再往下走,这叫艾特了。啊,这时候你看我们要是看这个Z啊,这时候看这不行了。应该是看我们这个例子了是吧,那这个例子呢,你看目前长这样吧。里边没有任何的东西是吧,这个element data的话呢,里边呢,就就长这样。然后呢,我们现在要添加第一个元素了,我们进源码。好,一上来的话呢,它也是要先判断一下线的这个size呢,能不能乘得下啊,这时候我们就要进入到这个还是这个方法里边啊,进到源码。
19:08
这里边儿你看还挺复杂的。还有这么着类型是吧。这个的话呢,那咱就老老实实的先开这个方法吧。这个没太大,这呢是呃,Mean capacity,这个mean capacity呢是一。因为一开始S是零,加上你当前放的元素,哎,加一起这个就一呗。哎,这个我们点页码。啊,就看这个方法了啊。当前的你这个数组。啊,这不,我们就当前底层的个数组嘛,如果它是呢,叫default capacity element,实际上就是相当于你是不是这个。是其实是吧。如果,哎,这不是咱们现在呢,不就是长这样吗。你要是这样的话呢,我们就return一下它俩中的较大值。这个mean啊,不是mean了,这个default capacity呢,这就我们说的这个十。然后这个呢叫mean capacityity,这个我们是零加一,它是一是吧,是不是大这也能看到吗?取他俩中的较大值。
20:04
哎,那其实返回的这块呢,是不是就返回了一个十就出来了。好,我们这块再一点,诶,这个结果呢,相当于得到就是个十,然后呢,我们再来看这个方法啊,相当于他拿着这个十呢,不就进到这个方法里了吗。这个还能挺住吧。快挺不住了。这个。还都是小case呢。其实啊。我们还没有看map呢,是吧。好,这个就回到这儿来了啊,现在这个呢,这不就是十吗。哎,这个十过来之后呢,我们下边要干什么呢?哎,十呢,减去这个element贝塔点length这个呢,现在不是零嘛,显然就大于零,所以呢,就有呗。格瑞,那进去跑到这儿来了,诶拿着你现在这个长度是零零的话呢,先这样,右一这右一半还是零嘛。那个new这块没有任何作为是吧,零呢,加上一个零除以二还是零,那你这块呢,零去减去它这个。
21:01
这个不是传过来是一嘛,又小A了,所以干脆呢,就拿你这个。呃,拿这个capacity。哎哎,这个不是一,这个咱们刚才那块是十是吧。是不是在这儿嘛,十啊,哎,这个零减去这个十呢,小于零,那我干脆就把这个十付给你了。哎,那这样的话呢,咱们这个十呢,其实这不就出现了吗。这块就出现了,然后在这里边儿呢,他就把这个数组呢给造好了。啊。就这就出去了。就出去了,哎,就出去了,就出去了,就到这儿了,相当于呢,在这个方法里边,把这个长度为十的这个速度呢,就给造出来了,然后接着呢,就添加到你第一个元素的位置。哎,然后呢,接着往后走,那呃,目前在这儿的话呢,你看我们这个,嗯,数组已经造好了是吧,往下走是不是十个呢,就已经出来了啊。这个时候呢,你在执行这个操作呢,我往下走一步,是不是这个A就出来了吗。添加进去了是吧,然后呢,再往下走啊,下边这个BB啊,再走一下,是不是这个里边呢,BB就也放上去了嘛。
22:06
诶,这样的过程,然后再走,这就结束了啊。这个看懂了没?嗯,为啥我这块我先把这个代码,先把这个说明写出来呢,就是呢,大家你先理解这个事儿,然后再看源码的时候呢,就不迷了是吧。啊,如果先看源码的话呢,就还不知道是怎么回事,就有点懵了,所以呢,你实在不行,你就记一下这个结论哈,在八当中的时候呢,我们上来呢,先是这样的,当你首次添加的时候呢,我们给你把数组造好,把元素放进去,以此类推,后边这块我们其实刚才也看那个格的时候呢,也看到这样的逻辑了啊,它其实默认的就1.5倍。啊,这样的情况啊,那由刚才这样两个说明啊,刚才我也听到有的同学说了啊,这两个话呢,有点像我们,呃,之前呢,讲那个设计模式里边的两种写法是吧。对小结一下是吧,我们这个JDK7当中的哈。
23:00
注意,大家看我,为什么我非得强调一下这个小版本呢?就是其实这个JDK啊,你要是七看的时候呢,我们现在说的是七和八的区别,他这个七的话呢,诶我就是。你记得不是很清晰了哈,就是它后边的小本呢,其实他也好多是吧。呃,是还是说那个呀,它那个版本呢,特别接近于八的时候,就特别靠后的时候,那个版本的代码呢,其实跟八呢是类似一样。就相当于他在1.7的一个特别新的一个版本当中,其实他一开始的时候呢,也没有去造这个长的V10的数组啊。但是这块呢,我们前面这个版本其实都是先造好了,所以这块大家在说的时候,比如说啊,你在笔试面试当中,你讲到了,你说这个七当中一开始就造好了,八中没造好,对方如果说说我这个七的版本,我怎么就造好了呢?不是我七这版本怎么一开始也没造好呢。啊,你不要跟他去争。你就说呢,我看那个版本呢,就比较小,你看那个版本可能是比较靠后。知道这意思吧,就是1.7的比较靠后的版本,它可能跟八呢是一样的啊,OK,所以这块我呢明确说了,是咱们看的这个版本啊,那么在这个版本中啊。
24:09
哎,咱们这个呢。其实呢,有点类似于呢。他一上来就把这个数度造好了啊,类似于是不是单立里边这个叫恶汉式是吧。啊,而我们这个1.8这个版本。有点就像懒汉式了。这个注意啊,你就说类似啊。就是没有说他这是懒汉式,他也不是啥懒汉式是吧。啊,就是类似的,就是一开始就造好一个呢,是没造好,当你需要的时候呢,我再造,哎想法呢是一样的啊。好,那么关于a release呢,我就讲完了啊。
我来说两句