ArrayList超详细源码解析
2018-05-15 本文已影响28人
阴天吃鱼
首先要清楚ArrayList基本特点
- 查询某节点数据、更改某节点数据，快
- 增加、删除可能会慢，存在扩容和移动元素。
- 底层实现是Object数组
- 默认大小为10
ArrayList类的继承关系：
image.png
比对着源码看一下
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
-
可以看到继承了AbstractList。而AbstractList 是继承AbstractCollection 抽象类，实现了 List 接口，是 ArrayList 和 AbstractSequentiaList 的父类。AbstractList 主要是搭建List, 关系看图1.
图（1）.png
图（1）.png
-
实现了List接口，就意味着ArrayList元素有序的，可以重复的，并且可以有null的元素。
-
实现了RandomAccess接口标识着其支持随机快速访问。
-
实现了Cloneable接口,标识着可以它可以被复制。调用ArrayList里面的clone()方法，需要注意的是clone是浅层拷贝。浅层拷贝对于ArrayList变量的意思就是说：ArrayList变量指向的是不同的内存地址，但是变量中的元素指向的是同一个元素。深层拷贝是指，不仅仅变量指向的内存地址不一样，而且变量中的各个元素所指地址也是不一样的。
-
实现了Serializable 可被序列化。
ArrayList 的构造方法
在说构造方法之前我们要先看下与构造参数有关的几个全局变量：
//默认的数组容量
private static final int DEFAULT_CAPACITY = 10;
//用于空实例的共享空数组实例。
private static final Object[] EMPTY_ELEMENTDATA = {};
//另一个共享空数组实例,与EnvyTyEeltDATA区分开来.
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//底层容器
transient Object[] elementData;
//当前存放了多少个元素
private int size;
底层容器数组的前面有一个transient关键字，transient标识之后是不被序列化的。
但其实是ArrayList在序列化的时候会调用writeObject()，直接将size和element写入ObjectOutputStream；反序列化时调用readObject()，从ObjectInputStream获取size和element，再恢复到elementData。
transient标识主要原因在于elementData是一个缓存数组，它通常会预留一些容量，等容量不足时再扩充容量，那么有些空间可能就没有实际存储元素，采用上诉的方式来实现序列化时，就可以保证只序列化实际存储的那些元素，而不是整个数组，从而节省空间和时间。
无参构造方法
/** * 构造一个初始容量为10的空列表*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
命名里面讲elementData指向了一个空数组，但是注释说的是默认为10.
指定初始容量的构造方法
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) { //容量>0 构建数组
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) { //容量>0 指向了一个空的数据
this.elementData = EMPTY_ELEMENTDATA;
} else {报错 负数
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
如果我们预先知道一个集合元素的容纳的个数的时候推荐使用这个构造方法，避免使用ArrayList默认的扩容机制而带来额外的开销.
使用另一个集合 Collection 的构造方法
构建指定元素，顺序由迭代器返回顺序为准。排序啥用过
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();构建数据
if ((size = elementData.length) != 0) {有数据赋值
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.没有给空
this.elementData = EMPTY_ELEMENTDATA;
}
}
ArrayList的函数分析
增加元素+扩容机制
添加单个元素
public boolean add(E e) {//添加元素到最后
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
//如果arraylist是无参构造，数组是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA。然后DEFAULT_CAPACITY=10 ，
//所以一开始上面构造的时候写的默认10.
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
//被修改次数，保证线程安全，迭代时候如果修改会报错。ConcurrentModificationException
modCount++;
// overflow-conscious code可能溢出代码
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//扩容
private void grow(int minCapacity) {
// 原来的数组长度
int oldCapacity = elementData.length;
//新数组的大小=老数组大小+老数组大小的一半
int newCapacity = oldCapacity + (oldCapacity >> 1);
//判断上面的扩容之后的大小newCapacity是否够装minCapacity个元素
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//判断比最大值Integer.MAX_VALUE - 8 还大的话给hugeCapacity处理
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
//终于溢出了
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
小章总结:
- 首先判断如果新添加一个元素是否会导致数组溢出
- 判断是否溢出:如果原数组是空的,那么第一次添加元素时会给数组一个默认大小10.接着是判断是否溢出,如果溢出则去扩容,扩容规则: 新数组大小是原来数组大小的1.5倍,最后通过Arrays.copyOf()去浅复制.
- 添加元素到最后
-
添加元素到指定位置
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
ensureCapacityInternal(size + 1); //要不要扩容
//相当于Index开始以及后面的数据，都往后移动了一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//之前移动的坑 填上
elementData[index] = element;
//记录元素个数
size++;
}
其实就是在数组的某一个位置插入元素,那么我们将该索引处往后移动一位,腾出一个坑,最后将该元素放到此索引处(填坑)就行啦.
- 添加集合到末尾
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
//是否要扩容
ensureCapacityInternal(size + numNew); // Increments modCount
//a数组全部复制到size后面
System.arraycopy(a, 0, elementData, size, numNew);
//记录现有的元素个数
size += numNew;
return numNew != 0;
}
将需要插入的集合转成数组a,判断了一下是否需要扩容，再将a数组插入到当前elementData的末尾。
- 添加集合到指定位置
public boolean addAll(int index, Collection<? extends E> c) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
Object[] a = c.toArray();
int numNew = a.length;
//跟上面一个意思
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;//需要后移的元素个数
if (numMoved > 0)
//将原有数据从Index以及之后开始的numMoved的元素，移动到index+numNew后面去。因为要插入a数组。
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
//把a数组复制到elementData数组中
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
判断一下添加了集合之后是否需要扩容,因为需要将集合插入到index处,所以需要将index后面的元素往后挪动,需要挪动的元素个数为:size - index,挪动的间隔是index + numNew。
- 移除指定位置元素
public E remove(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
modCount++;
E oldValue = (E) elementData[index];//记录删除的元素
int numMoved = size - index - 1;//获取移动的位置
if (numMoved > 0)//删除元素后面有数据往前移动
//将Index后面的数据往前移动一个，不包含Index
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//删除 ， 就是赋值null,让gc回收
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
- 保存删除元素旧值
- 然后将数组的index后面的元素往前挪动一位
- 将数组的末尾元素赋值为null,方便GC回收。
-
移除指定元素
-
移除第一个集合中与指定元素相同(通过equals()判断)的元素.移除成功了则返回true,未移除任何元素则返回false
-
如果传入的是null,则移除第一个null元素
-
如果传入的是非null元素,,通过equals()移除第一个相同的元素
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
//获取第一个为Null的
if (elementData[index] == null) {
fastRemove(index);//移除
return true;
}
} else {
//获取第一个相同的
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);//移除
return true;
}
}
return false;
}
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;//获取删除元素后面要移动元素的个数
if (numMoved > 0)
//移动index后面的数据往前移动1.
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
判断需要移除的元素是否为null
如果为null,则循环遍历数组,移除第一个为null的元素
如果非null,则循环遍历数组,移除第一个与指定元素相同(equals() 返回true)的元素
- 删除原有集合里面所有包含的数据
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);//判断空指针
return batchRemove(c, false);
}
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
//遍历数组
for (; r < size; r++)
//complement = false取补集，C包含不记录，不包含记录
//complement = true 取交集，C包含记录 ，不包含不记录
if (c.contains(elementData[r]) == complement)
//r是正在遍历的位置 w是用于记录有效元素的 在w之前的全是有效元素,w之后的会被"删除"
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
// clear to let GC do its work
// 将w之后的元素全部置空 因为这些已经没用了,置空方便GC回收
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
- 首先我们进行c集合检查,判断是否为null
- 然后我们调用batchRemove()方法去移除 c集合与当前列表的交集
- 循环遍历当前数组,记录c集合中没有的元素,放在前面(记录下标为w),w前面的是留下来的元素,w后面的是需要删除的数据
- 第3步可能会出错,出错的情况下,则将出错位置的后面的全部保留下来,不删除
- 然后就是将w之后的元素全部置空(方便GC回收),然后将size(标记当前数组有效元素)的值赋值为w,即完成了删除工作
再笼统一点说吧,其实就是将当前数组(elementData)中未包含在c中的元素,全部放在elementData数组的最前面,假设为w个,最后再统一置空后面的元素,并且记录当前数组有效元素个数为w.即完成了删除工作.
-
清空列表
将数组所有元素都置为null,然后GC把它回收了
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
改动元素
- 替换指定下标的元素内容
就是将index处的元素替换成element
public E set(int index, E element) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
E oldValue = (E) elementData[index];//记录旧值
elementData[index] = element;//替换
return oldValue;
}
查询元素
- 返回指定位置处元素
将index索引处的数组的值返回
public E get(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
return (E) elementData[index];
}
总结
下面我们来总结一下ArrayList的关键点
- 底层是Object数组存储数据
- 扩容机制:默认大小是10,扩容是扩容到之前的1.5倍的大小,每次扩容都是将原数组的数据复制进新数组中.。
- 如果是添加到数组的指定位置,那么可能会挪动大量的数组元素,并且可能会触发扩容机制;如果是添加到末尾的话,那么只可能触发扩容机制.
- 如果是删除数组指定位置的元素,那么可能会挪动大量的数组元素;如果是删除末尾元素的话,那么代价是最小的. ArrayList里面的删除元素,其实是将该元素置为null.
- 查询和更改某个位置的元素是非常快的。
有兴趣的小伙伴可以帮忙关注一下csdn，谢谢
https://blog.csdn.net/binbinxiaoz
