前言
本文开始分析具体集合的源码和实现原理,首先来看ArrayList
。ArrayList
可以理解为一个动态数组,与普通数组相比,它的容量能动态增长。其定义如下:
|
|
可以看到ArrayList
继承了AbstractList
类,实现了List
,RandomAccess
,Cloneable
和java.io.Serializable
四个接口。
上文提到,AbstractList
类提供了大部分List接口的实现,帮助我们减少了实现List接口的工作。
RandomAccess
接口是List实现所使用的标记接口,表明List支持快速随机访问功能(就是通过索引获取元素)。
实现Cloneable
接口表明覆盖了Clone()
函数,能被克隆,实现java.io.Serializable
接口表明ArrayList
支持序列化。
本文源码分析基于jdk 1.8.0_121
继承关系
ArrayList的继承关系
|
|
关系图
ArrayList的两个成员elementData
和size
比较重要:
elementData
是Object
类型的数组,保存了ArrayList
的数据,是ArrayList
的底层实现,它是个动态数组,在添加数据过程中不断扩展容量,最大容量为Integer.MAX_VALUE - 8
;容量的增长方式在源码中具体再分析size
是当前动态数组的实际大小构造函数
123public ArrayList() {} // 默认构造函数public ArrayList(int initialCapacity) {} // 构造一个具有特定初始容量的ArrayListpublic ArrayList(Collection<? extends E> c) {} // 创建一个包含Collection的ArrayList
以上三种构造函数在不同JDK版本之间也略有差异,但思想或者做的工作都基本一致。public ArrayList()
在JDK1.8.0_121
中令elementData
为一个空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA
,而此版本中还存在另一个空数组成员EMPTY_ELEMENTDATA
,
此两者的区别是用来区分ArrayList
添加第一个元素时容量要扩张多少。在之前的JDK版本中默认构造函数是直接初始化一个容量为10的数组。
(具体哪一版本开始出现这一区别暂不清楚)
public ArrayList(int initialCapacity)
构造一个指定初始容量的空列表,当initialCapacity
为0时,令elementData
为EMPTY_ELEMENTDATA
。
public ArrayList(Collection<? extends E> c)
构造一个包含Collection
的元素的列表,这些元素按照该Collection
的迭代器返回它们的顺序排列的,先将Collection
转为数组,再将数组拷贝给elementData
。
API
|
|
源码分析
成员对象
|
|
构造函数
|
|
改变容量值
|
|
确定容量
|
|
增加元素
|
|
toArray
|
|
调用toArray
方法有以下两种:
|
|
调用第一种方法会抛出“java.lang.ClassCastException
”异常,调用 toArray(T[] contents)
能正常返回 T[]
。
这是因为将Object[]
转换为的Integer[]
则会抛出“java.lang.ClassCastException
”异常,因为Java不支持向下转型。
设置元素
|
|
读取元素
|
|
删除元素
|
|
序列化
|
|
遍历方式
- 迭代器遍历,即通过Iterator遍历
|
|
- 随机访问,索引值
|
|
- foreach循环123for (Integer integ:list) {;}
通过比较以上三种遍历方式,我们发现通过随机访问方式效率最高,而另两种方式效率都不高。