Video在线视频

这一节我们来介绍一下

集合框架与arraylist

我们首先看一下这张图

在这张图上列出了

我们常见的一些集合框架的类

最上面的话

是我们的collection接口

那它有两个子接口 list和set

那再往下我们还可以看到

这些list有一些类来去实现这个接口

比如说AbstractList

那AbstractList往下

还有Vector Stack

甚至还有ArrayList等等等等

但对于set这个接口的话

底下也实现了一些类

比如说最下面的HashSet

或者TreeSet等等

但是这张图的右半部分

是我们另外一个接口叫Map

那个这个Map大家可以看到

它也延伸有很多很多的这些类

比如说HashMap LinkedHashMap

还有Hashtable等等

那这些类的话

都是我们在集合框架当中

比较常见的类

那这儿也列出了一些

常用集合类的名字

比如说在list

我们就会有ArrayList和LinkedList

这两个类

那在Map这个接口

我们就会有HashMap Hashtable

还有TreeMap LinkedHashMap等

这样四个常用的类

那对于Set

集合这个接口

我们常用的类包括HashSet

TreeSet和LinkedHashSet等等这些

都是我们在进行Java编程时候

所经常使用到的Java的数据结构类

那我们首先来看一个

最常见的类ArrayList

那ArrayList它是List接口

所实现的可变的数组

那在这里面实现了

所有可选列表的操作

允许包括null在内的所有的元素

当然ArrayList这个类

它是属于非线程安全

什么意思

就是说ArrayList在我们进行

多性能操作的时候

你们编程序的时候

一定要去主动加上（02：46英文）

这样的控制

才能保证多个线程

同时对ArrayList进行访问的时候

数据的安全性

那在ArrayList它的实现的内部结构

使用的是数组

一会儿我们可能会具体介绍

它的实现过程

那ArrayList它的特点是

它比较适合于去查找

当我们需要对ArrayList

进行增加或者删除的时候

它的这个性能就会受到影响

我们来看一下ArrayList

它到底是怎么实现的

那我们看一下第三行

我们这个类public E set

int index E element

那实际上这是一个方法

那这个方法就是说

我们想把这个列表上的

某一个元素的值

进行变更或者叫进行设置

那我们看这个方法里面的第一行

Range Check index

那这个方法是要检查说

你的index是否合法

也就是说我们要对某一个下标的

这个ArrayList的元素进行修改的时候

首先你看这个下标

也就是index是否越界

再往下一行E oldValue等于

elementData index

那就直接取出在原有的这个下标index

所对应的元素的值

把它保存在oldValue这个对象当中

然后elementData index等于element

那这个就是把我们下标为index

这个元素把它的值

设置为要新的值

就是这个element

紧接着下一行return old Value

那就是把旧的这个元素值返回

那这个方法的话

就是一个在ArrayList中

实现替换元素的这么一个方法

那再往下的话是增加元素的方法

那增加元素它主要是把它添加到

我们整个列表的尾部

我们看一下这一段代码

public boolean add E e

这个方法中第一行

ensureCapacity size+1

确保说我还有一个额外的这个容量

因为你要增加元素

我们要往这个列表的末尾增加

那我们就要看这个

是不是已经到达了整个列表的

最后的这个位置

再下一行elementData size++ =e

那就是说把这个最后的这个位置的

这个元素值设置成为e

也就是我们想增加的这个值

最后return true也就是表示增加成功了

那这两个方法就是我们ArrayList

当中的分别设定某个元素值的方法

以及在尾部增加某个元素的方法

那我们再往下看

当我们想往ArrayList这个列表当中

去增加或者叫插入某一个元素的时候

那你肯定要指定说

我要在哪个位置插入什么样的一个元素

我们看一下这段代码

public void add

int index E element

那这个方法就是add

只不过说它不是add到

这个列表的尾部

它是增加到某一个这个下标下面

就是由index来去指出这个位置

在这里插入一个元素

那插入的元素值就是element

那我们看看这个下一行代码是什么

if index大于size 或者index小于0

也就是说我们这个add

这个index参数

如果你指定的这个下标的位置

是已经超出了整个列表的范围

或者是小于0

那就说明你整个就是

这个相当于数组下标越界了

所以我们可以看到再下一行代码

就throw newindexOutOfBoundsException

然后index+index再加上size

那实际上在这个时候

就是生成了一个数组下标越界的异常

并把它抛出去

那假设都没有这个下标越界的话

那说明我们是可以去

这个往里添加的元素

再下一行代码ensureCapacity size+1

也是要确保说

我要往里这个插入元素的时候

我的整个这个列表的空间

还是能够容纳的

拿再往下就是system.arraycopy

elementData index

elementData index+1

然后最后size-index

那其实这个arraycopy的方法

它的作用就是相当于

把我们列表当中的若干元素的值

进行拷贝

那为什么要拷贝呢

因为我们当前要实现的这个add方法

实际上是说在列表当中的

某个位置去插入这个元素

我要插入元素的时候

必定是把从当前要插入这个位置

之后的这些元素

全都集体往后挪一位

然后紧接着再把要新增的元素

放到这个下标这个位置上面

所以这个system.arraycopy

就是把这个位置后面的这个元素

整体移动的过程

那再下一行代码就是collectionData

index等于element

那就是说把我们这个当前下标

所指定的元素的值

设定为我要插入的值

最后一行代码是size++

就是增加我们的整个空间

增加一个值

那我们可以看到在我们左下角

已经标明了一个列表的初始状态

这个列表有五个元素的空间

然后分别从第一到第四个是abcd

然后现在我们想在c

也就是下标为2的这个地方

想去插入这个

一个新的这个元素

那它的整个过程是怎么样的呢

这个很显然

我们要先把这个

由这个index这个指针指向的这个位置

之后的就是这些元素都往后挪一格

大家可以看到我们把cd

整个往后挪了一个位置

也就是说整体拷贝挪了一个位置

紧接着最后我们要把我们想插入的元素

插进来

那假设现在我们想插入的是e

所以我们插进来的这个列表的

最后的结果就是abecd

那其实这个过程

打一个比方就像

相当于大家去食堂打饭的时候

可能会碰到有人上来插队

或者叫加塞的

那其实这个过程

就是和那个过程是类似的

如果有一个人插到队伍中间

那从他插的那个队伍开始

那个后面所有人

都要往后挪一格

那这个时候我们这个add方法

其实就是类似的道理

当然大家也可以看出来

这里面有一个特点就是说

往后挪一格的这个代价还是蛮大的

因为你要把这个从插队开始

后面位置的所有的这些元素

都要往后挪一位

那在我们这里面

就是要逐一进行拷贝

所以它在列表

在进行插入操作的时候

它的这个性能确实不是很好

那我们再看下一个方法

也就是删除方法

就是从列表当中去删除

指定位置上的元素

那这个方法叫public E remove

int index

也就是说我们要删除某个元素的时候

你只需要指定是删除哪个位置上

也就是哪个下标上的元素就可以了

然后先来说RangeCheck index

先来检查一下这个给定的index

是不是超出了我们这个列表的

这个长度

或者是它就根本小于0

那如果都符合要求

那我们再往下看

那这个modCount++

实际上是说这个修改的次数加一的意思

然后紧接着这个E oldValue

等于elementData index

那这一行代码什么意思呢

也就是说先把我们当前

要删除的这个元素

它的值给保留下来

保存到oldValue这个对象当中

好 紧接着int numMoved

等于size-index-1

那其实我们当我们往列表当中

去删除某一个元素的时候

这个时候从这个元素之后的其他元素

都要往前去补空

那到底要多少个元素

要往前去补空呢

就由这个numMoved来去计算出来

那numMoved等于size-index-1

然后这时候再往下

我们看那个代码if numMoved大于0

就是说它要移动的这个数量的话

原数量是大于0的

那就进行这个拷贝移动

那怎么拷贝移动

还是调用system这个类的arraycopy方法

然后从哪些原来的数据去拷贝呢

从elementData这个列表的

它从下标index+1开始

那到底想拷贝到哪儿呢

拷贝到elementData这个列表

然后从它的这个index这个下标开始

然后要总共拷贝多少个呢

拷贝numMoved个

其实说白了也就是把这个元素

整体往前挪了一位

然后最后一步

elementData--size等于null

也就是说我们最后的一个元素

它是往前拷贝

但是最后这个元素它所在的这个位置

它的值应该把它置成空

所以就把它设置成null

然后最后我们return oldValue

也就是把我们这个旧有的

被删除的值返回去

那下面我们用一个小的动画

来去展示这个删除的过程

那我们这里有一个列表

它有四个元素

分别是abcd

那现在我们想把第二个元素

也就是下标为1的这个元素进行删除

也就是要把b元素删除

那b元素删除第一步做什么事情呢

就是把后面的c和d整体往前拷贝

覆盖掉原来b的这个位置

那就变成了acdd

大家看到最后这个元素它还是d

因为我们这个是把原来的cd

往前挪了一位

那最后这个位置还是d的话

就显得有点不合理了

所以我们还增加了一步

把这个d修改成为空

也就是把它这个给空出来

所以这么一个删除过程

再给大家举这个例子

就是像刚才我们说去食堂

这个排队的时候有人插队了

但是这个时候大家有了意见

要求插队的人赶紧从队伍中离开

那一旦插队的人

从队伍离开的话

从后面开始的人

就可以一次往前递补

移动一个位置

当然这个递补移动的位置

在我们用列表来实现的时候

你是要整体拷贝了

所以说我们的列表对于删除这样的操作

它确实在性能上表现的还不够好

那再下面这个方法是

就是去扩充我们整个这个数组

也就是我们这个列表的容量的

那它public void ensureCapacity

然后int min Capacity

那这个参数就是说

我希望确认一下说

我这个列表的长度

它不小于我这个长度

好 我们再往下看一下

modCount++这是修改次数加1

int old Capacity

等于elementData.length

也就是说旧有的这个容量大小

就是我们整个列表的它的长度

再往下if minCapacity

大于oldCapacity

也就是说我们要想指定的最小的

这个容量minCapacity

比现有的容量还要大的话

这就说明说这个列表

不能满足我的使用需求

这个时候就需要对列表的长度

进行扩充

怎么扩充呢

基本原则就是扩到1.5倍

我们看一下int newCapacity

等于oldCapacity乘以3除以2再加1

实际上它是乘以1.5倍再加1

然后这时候接着再往下判断

if newCapacity小于minCapacity

也就是说我们经过1.5倍

扩充以后的这个列表的长度

还比那个

在这个方法的参数里面指定的

minCapacity还小的话

那这时候我们只好把这个newCapacity

把它设置为minCapacity

也就是说把我们新变化后的

这个列表的容量它的值

就设定为这个参数里面

定义这个minCapacity的值

那设好这些这个列表的容量

或者叫长度以后

那它原来我们的列表当中

是不是也保存了一些数据

当然极有可能有

那这个时候怎么办

大家再看一下最后这一行

elementData等于arrays.copy of

elementData newCapacity

其实就是把这个原有的这些元素

再重新进行一遍这个拷贝

所以我们这个ensureCapacity

这个方法它是按照1.5倍的方式

进行扩充

来扩充我们的这个数组列表

那由于在这个扩充过程中

涉及到这个数组元素的拷贝

那这个速度的话

肯定是会相应的会减慢的

那这一节的内容我们就介绍到这里