Java中ArrayList源码解析
一、ArrayList介绍
ArrayList是Java和Android开发中使用最为频繁的一种集合。它的底层数据结构是动态数组,并且是线程不安全,允许元素为null. ArrayList类结构如下:
//实现了List、RandomAccess、Cloneable、Serializable接口
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
//...
}
其中, ArrayList
实现了RandomAccess
标记接口,用来表明其支持快速(通常是固定时间)随机访问。此接口的主要目的是允许一般的算法更改其行为,从而在将其应用到随机或连续访问列表时能提供良好的性能。ArrayList
实现了Cloneable
标记接口,用来指示Object.clone()
方法可以合法地对该类实例按字段复制。如果在没有实现 Cloneable
接口的实例上调用 Object
的 clone
方法,则会导致抛出 CloneNotSupportedException
异常。Serializable
接口: 类通过实现 java.io.Serializable
接口以启用其序列化功能。未实现此接口的类将无法使其任何状态序列化或反序列化
二、ArrayList基本使用
List<String> dataList = new ArrayList<>();//创建一个ArrayList集合
List<String> dataList = new ArrayList<>(3);//指定初始化集合的大小为3的ArrayList集合
List<String> dataList = new ArrayList<>(originalList);//指定已经存在集合
三、ArrayList特性
1、是否保证线程安全:
不是同步的,不能保证线程安全
2、底层数据结构:
ArrayList底层使用的是Object数组数据结构,动态数组
3、插入和删除是否受元素位置的影响:
ArrayList 采用数组存储,所以插入和删除元素的时间复杂度受元素位置的影响。 比如:执行add(E e)方法的时候, ArrayList 会默认在将指定的元素追加到此列表的末尾,这种情况时间复杂度就是O(1)。但是如果要在指定位置 i 插入和删除元素的话(add(int index, E element))时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。
4、是否支持快速随机访问:
ArrayList 实现了RandomAccess 接口,所以有随机访问功能。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
5、内存空间占用:
ArrayList的空间浪费主要体现在在list列表的结尾会预留一定的容量空间
四、ArrayList类的继承关系
五、ArrayList源码分析
1、构造器
通过分析ArrayList
的构造器,发现其实构造ArrayList
有三种方式,一种最为常见就是创建一个不带构造参数的ArrayList
的实例,默认是DEFAULTCAPACITY_EMPTY_ELEMENTDATA
空数组;然后第二种就是传入指定初始容量大小,默认会创建指定容器大小的Object数组;第三种就是传入已存在Collection集合,默认会直接把Collection集合转化成Object数组,并且如果转化失败就会利用Arrays.copyOf
方法会把集合中元素批量加入到Object数组以此来初始化elementData.
关于Arrays.copyOf(elementData, size, Object[].class)
方法,就是根据class的类型来决定是new 还是反射去构造一个泛型数组,同时利用native函数,批量赋值元素至新数组中。
2、ArrayList操作之增
add(E e)
- 执行
add(E e)
方法,往集合尾部添加元素,每执行一次add操作之前都会调用ensureCapacityInternal
来确认是否需要扩容
add(int index, E element)
- 执行
add(int index, E element)
方法, 先检查index是否合法,是否越界。然后确认是否需要扩容,然后将index开始之后的所有数据元素整体向后移动一位,然后再把指定index的元素进行新值覆盖,最后size自增1
addAll(Collection<? extends E> c)
addAll(int index, Collection<? extends E> c)
3、ArrayList扩容流程
- 1、扩容源码分析
- 2、扩容原理流程图
- 3、扩容原理的总结
对于ArrayList
扩容,首先需要明确一点ArrayList
的size
和elementData.length
数组长度不是相等的,size
表示当前数组的元素个数。如果ArrayList
是以默认无参构造的,那么当第1次执行add
操作后,会默认第一次扩容容量为DEFAULT_CAPACITY = 10
, 后面再执行第210次执行15次执行add
操作后,就不会进行扩容操作;当第11次执行add
操作后就会就触发扩容操作,此次扩容的容量为当前数组长度(注意是数组长度而不是size,size增加只有真正把值add到数组中后才增加)的一半也就是5;所以当第11add
操作后,又不会进行扩容操作。依次类推后续每次会扩容的容量为当前数组长度的一半,在扩容容量范围内就不会触发扩容操作。
验证上述理论,可以明显发现ArrayList
的add
操作执行的第1次,第11次,第16次会明显耗时更长。
4、ArrayList操作之删
remove(int index)
remove(Object o)
removeAll(Collection<?> c)
//在当前集合中批量删除传入集合c中的元素
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);//removeAll方法实际上是委托给batchRemove方法实现的,传入参数分别要删除,注意传入第二个参数,complement = false表示在当前集合删除传入的集合
}
//在当前集合中批量删除除了传入集合c中的元素(保留传入集合c中的元素,其他全删除)
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);//注意传入第二个参数,complement = true表示在当前集合保留传入的集合元素,其他全部删除
}
//批量移除集合中元素
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;//将当前集合中元素赋值给elementData
int r = 0, w = 0;//设置两个游标分别读游标r和写游标w
boolean modified = false;
try {
for (; r < size; r++)//遍历当前集合中的所有元素
//注意: 这里需要考虑两种情况:
//第一: 如果当前集合中元素在需要删除集合c中且complement为false则表示在当前集合中移除传入集合c中元素,
//会把当前集合中不在c集合中的元素,整体往前移动,w游标增加
//第二: 如果当前集合中元素在需要保留集合c中且complement为true则表示在当前集合中保留传入集合c中元素,
//会把当前集合中在c集合中的元素,整体往前移动,w游标增加
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// 出现异常会导致r != size,则将出现异常处后面的数据全部复制覆盖到数组里
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;//修改w游标
}
//最后w游标值就是产生新的数组的size
if (w != size) {
//从w之后到size的所有位置重置为null,以便GC回收
for (int i = w; i < size; i++)
elementData[i] = null;
//modCount增加表示修改到元素次数
modCount += size - w;
size = w;//最后的w也就是size集合大小
modified = true;
}
}
return modified;
}
5、ArrayList操作之改
//注意修改数组中对应元素的值是不需要修改modCount
public E set(int index, E element) {
rangeCheck(index);//越界检查
E oldValue = elementData(index);//通过elementData按到index元素
elementData[index] = element;//并用传入的新值覆盖旧值
return oldValue;//并返回旧值oldValue
}
6、ArrayList操作之查
//注意查找数组中对应元素的值是不需要修改modCount
public E get(int index) {
rangeCheck(index);//越界检查
return elementData(index);
}
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];//直接获取对应index的值
}
7、ArrayList操作之clear
public void clear() {
modCount++;//修改modCount
//elementData数组中的元素全部复制为null, 以便GC回收
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;//最后重置size为0
}
8、ArrayList操作之包含contains
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
public int indexOf(Object o) {
if (o == null) {//如果o为null, 遍历elementData数组找到第一个出现null的位置
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {//如果o不为null, 遍历elementData数组找到第一个出现与o值相等的位置
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;//否则找不到就返回-1
}
9、ArrayList操作之迭代器Iterator
private class Itr implements Iterator<E> {
int cursor; // 返回下一个元素的index
int lastRet = -1; // 返回上一个元素的index,没有上一个元素就默认返回-1
int expectedModCount = modCount;//整个过程中操作集合(包括add、remove操作)次数modCount
public boolean hasNext() {
return cursor != size;//当前游标cursor不等于size,说明集合并没有迭代完毕,还有下一个元素
}
@SuppressWarnings("unchecked")
//获取迭代器中当前的元素next
public E next() {
checkForComodification();//检查修改集合次数modCount
int i = cursor;
if (i >= size)//越界检查
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;//取出集合中数组elementData
if (i >= elementData.length)//越界检查
throw new ConcurrentModificationException();
cursor = i + 1;//cursor游标累加
return (E) elementData[lastRet = i];//取出当前i的元素中的值返回,并设置上一次返回的元素的下标
}
//迭代中移除当前迭代元素
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();//modCount检查
try {
ArrayList.this.remove(lastRet);//移除元素
cursor = lastRet;//删除的游标
lastRet = -1;//不能重复删除 所以修改删除的标志位
expectedModCount = modCount;//更新 判断集合是否修改的标志,
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
//主要是为了检查线程安全,ArrayList不是线程安全的,但是避免多线程操作ArrayList中在迭代器迭代过程中,
//对集合具有写操作的修改导致modCount次数和expectedModCount不一致就会抛出ConcurrentModificationException异常
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
7、ArrayList中的modCount了解一下
我们都知道ArrayList是非线程安全的,在使用迭代器遍历的时候,用来检查列表中的元素是否发生结构性变化(列表元素数量发生改变)了,主要在多线程环境下需要使用,防止一个线程正在迭代遍历,另一个线程修改了这个列表的结构,那么这个modCount
就是记录被修改的次数。使用迭代器遍历时,iterator.hasNext()
方法中的checkForComodification()
方法会检查modCount
和expectedModCount
是否相等,从而判断在多线程环境下,迭代器遍历的过程中列表中的元素是否发生结构性变化。
一起来看个有趣例子:
class ArrayListTest {
public static void main(String[] args) {
List<Integer> resultList = new ArrayList<>();
resultList.add(10);
Iterator iterator = resultList.iterator();
while (iterator.hasNext()) {
Integer value = (Integer) iterator.next();
if (value == 10){
resultList.remove(value);//注意这里是调用了ArrayList中的remove方法, 值删除后resultList为空,modCount++
}
}
}
}
得到的运行结果会抛出一个异常:
为什么会抛出这个异常呢?这个其实就是modCount导致的,不妨再次来看下ArrayList remove的源码。
public E remove(int index) {
rangeCheck(index);
modCount++;//会发现remove调用后modCount会自增
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
再接着来下ArrayList中的Iteator迭代源码,会发现resultList
为空,所以size
为0,但是cursor
不为0,hasNext()
返回true, 就会继续执行next()
方法
public boolean hasNext() {
return cursor != size;//会发现size为0,但是cursor不为0,hasNext()返回true
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();//检查modCount,还记得在ArrayList中的remove方法中modCount会自增后就造成expectedModCount和modCount不一致,抛出异常
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
//注意使用iteator自带的remove方法就不会抛出异常
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();//会先去检查modCount
try {
ArrayList.this.remove(lastRet);//虽然内部也是调用remove方法,modCount自增了
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;//但是这里需要特别注意它把修改后的最新的modCount重置给expectedModCount,所以需要在迭代过程中删除元素还是调用iteator自带的remove方法
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}