ArrayList集合源码分析
最常用的集合就是ArrayList集合，现在通过源码去分析一下它的内部到底是怎么一回事。
ArrayList
看源码的过程中需要解决这几个问题：
- ArrayList是如何实现动态添加或者减少的？
- 它的线程安全性？
- 它的最大容量是多少？
ArrayList源码分析
ArraryList定义
public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable
可以看到ArrayList继承了AbstractList，同时实现了List,RandomAccess,Cloneable,java.io.Serializable接口。
- 继承AbstractList,实现List:意味着ArrayList是一个数组对列，提供了增，删，改查，遍历等功能
- 实现RandomAcccess接口：意味着ArrayList提供了随机访问的功能。RandomAccess接口在java中使用来被List实现的，提供了快速访问功能。在ArrayList中可以通过元素的序号快速获取元素对象。
- 实现Cloneable接口：意味着ArrayList实现了clone函数，可以被克隆。
- 实现了java.io.Serialable接口：意味着ArrayList能够通过序列化传输
ArrayList关键属性
//默认初始容量
private static final int DEFAULT_CAPACITY = 10;
//实例化一个空的数组 当用户指定的ArrayList为0时返回这个
private static final Object[] EMPTY_ELEMENTDATA = {};
//存储ArrayList元素的数组，ArrayList的容量是此数组的长度。当空的ArrayList添加第一个元素时，将扩展为DEFAULT_CAPACITY
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
//List中元素的数量，存放List元素的数组长度可能相等也可能不相等
private int size;
ArrayList三种构造方法
//ArrayList有固定的长度
public ArrayList(int initialCapacity) {
//长度大于0 创建固定长度的Object数组
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
//长度为0，将EMPTY_ELEMENTDATA作为当前Object数组
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
//ArrayList默认构造函数，默认为空
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//参数为集合元素
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
//如果不是Object类型的数组，然后给elementData数组
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
this.elementData = EMPTY_ELEMENTDATA;
}
}
从这三个构造方法里可以看到Object[] elementData数组是非常重要的，它就是ArrayList内部维护的对象数组，而且它还被transient修饰。transient在序列化的时候就会被经常用到，当变量被transient修饰的时候就可以不被序列化，当反序列化时被transient修饰的变量如果是Object类型其值为null，如果是int类型其值为0。
那么为什么elementData数组要用transient修饰呢？
可以在ArrayList源码中看到数据在序列化和反序列化用到的方法是readObject和writeObject。不序列化数组元素为null的值，这些值是没必要序列化的。
存放元素和改变容量的方法
//将集合的长度变成集合中所拥有的数据的实际个数。size和elementData.length不相等
public void trimToSize() {
//继承在AbstactLsit中的字段，表示数组修改的次数，数组没修改一个，modCount就加一次
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
//增加ArrayList的容量 minCapacity代表所需的最小容量
public void ensureCapacity(int minCapacity) {
//最小容量大于当前elementData数组的长度且不满足（elementData是DEFAULTCAPACITY_EMPTY_ELEMENTDATA且最小容量小于10）
if (minCapacity > elementData.length
&& !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
&& minCapacity <= DEFAULT_CAPACITY)) {
modCount++;
grow(minCapacity);
}
}
//调用Arrays.copyOf创建新的elementData数组
private Object[] grow(int minCapacity) {
return elementData = Arrays.copyOf(elementData,newCapacity(minCapacity));
}
//调用上面的grow方法
private Object[] grow() {
return grow(size + 1);
}
private int newCapacity(int minCapacity) {
//旧容量
int oldCapacity = elementData.length;
//新容量 是之前的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果新容量-旧容量 <= 0
if (newCapacity - minCapacity <= 0) {
//判断当前elementData数组是不是无参构造函数创建而来的
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
return Math.max(DEFAULT_CAPACITY, minCapacity);
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return minCapacity;
}
//MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;在AbstractList中定义
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? newCapacity
: hugeCapacity(minCapacity);
}
//最大容量不能超过int的最大值
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE)
? Integer.MAX_VALUE
: MAX_ARRAY_SIZE;
}
从上面的代码可以看到ArrayList扩容的方法，每次都扩增到原来的1.5倍，如果新旧容量都为0的话会根据当前数组是否是无参构造中的默认数组进行10和传入minCapacity取最大值。如果不符合，就会判断当前minCapacity是否小于Integer.valueof-8,是数组长度为计算出的newCapacity,否则就用hugeCapacity()方法计算。
加入当前数组的长度为10，当加入第十一个数据的时候会将数组容量增加到15，也就是10-->15-->22-->33...
增加
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}
//当使用list.add()方法其实调用的是这个方法
private void add(E e, Object[] elementData, int s) {
//会先进行扩容检查
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}
//这种add的方式之前没使用过，可以对指定位置添加元素
public void add(int index, E element) {
//判断index是否越界，错误产生IndexOutOfBoundsException
rangeCheckForAdd(index);
modCount++;
final int s;
Object[] elementData;
//判断当前size是否和elementData数组长度相等，是否需要扩容
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();
//对数组进行复制，将index后的所有元素都向后移一位
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);
elementData[index] = element;
size = s + 1;
}
查找
//返回指定元素第一次出现的索引，列表不包含此元素返回-1
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
//返回指定元素最后一次出现的索引
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
这两个方法的思路还是很容易看的
删除
//删除元素的方法是fastRemove
public E remove(int index) {
Objects.checkIndex(index, size);
final Object[] es = elementData;
@SuppressWarnings("unchecked") E oldValue = (E) es[index];
fastRemove(es, index);
return oldValue;
}
//从此列表中删除第一次出现的指定元素
public boolean remove(Object o) {
final Object[] es = elementData;
final int size = this.size;
int i = 0;
found: {
if (o == null) {
for (; i < size; i++)
if (es[i] == null)
break found;
} else {
for (; i < size; i++)
if (o.equals(es[i]))
break found;
}
return false;
}
fastRemove(es, i);
return true;
}
//快速删除，向前移动一位
private void fastRemove(Object[] es, int i) {
modCount++;
final int newSize;
if ((newSize = size - 1) > i)
System.arraycopy(es, i + 1, es, i, newSize - i);
es[size = newSize] = null;
}
ArrayList线程不安全的原因
之前就只是知道ArrayList是线程不安全的，但是没有想过它为什么不安全，现在总结一下原因。
在调用add方法向集合中加数据时，会先判断是否需要扩容，如果需要就去进行扩容。add方法主要做了两大步骤：
- 判断elementData数组容量是否满足需求
- 在elementData对应位置上设置值
这样会出现第一个导致线程不安全的隐患，在多个线程进行add操作时可能会导致elementData数组越界。具体逻辑如下：
- 列表大小为9，即size=9；
- 线程A开始进入add方法，这时它获取到size的值为9，若需要扩容则调用grow方法进行扩容；
- 线程B此时进入add方法，它获取到size的值也为9，也开始调用grow方法；
- 线程A发现需求大小为10，而elementData的大小也为10，可以容纳。于是不再扩容，返回；
- 线程B也发现需求大小为10，也可以容纳返回；
- 线程A开始进行设值操作，elementData[size++]=e操作。此时size变为10。
- 线程B也开始进行设值操作，它尝试设值elementData[10]=e,而elementData没有进行扩容，它的下标最大为9。此时会报出一个数组越界的异常ArrayIndexOutOfBoundsException。
还有另一个地方，就是在给elementData赋值的时候：
- elementData[index] = element;
- size = s + 1;
在单线程执行这两条代码的时候没有任何问题，但是在多线程的情况下就可能会发生一个线程的值覆盖另一个线程添加的值，具体逻辑如下：
- 列表大小为0，即size=0;
- 线程A开始添加一个元素，值为A，此时它执行第一条操作，将A放在了elementData下标为0的位置；
- 接着线程B刚好也要开始添加一个值为B的元素，且走到了第一步操作。此时线程B获取到size的值依然为0，于是它将B也放在了elementData下标为0的位置；
- 线程A开始将size的值增加为1；
- 线程B将size的值增加为2。
我们希望size的值为2，下标为0的值为A，下标为1的值为B。而实际情况变成了size为2，下标为0的值为B，下标为1的位置上什么都没有。
总结来说ArrayList线程不安全有两方面：一是数组刚好到不扩容的边界值，下一个进程判断不用扩容放入数据后数组越界；二是线程对size加一的问题，没有对共有数据进行保护。
ArrayList面试中的问题总结
- 简单介绍一下ArrayList
ArrayList是以数组实现的，可以自动扩容的动态数据，数组默认长度是10，当超出限制的时候会增加50%的容量。在加入新的数据时可以直接传入值，也可以传入值和值想要放入的位置，通过System.arraycopy()方法去复制数组，将当前要插入位置之后的值都向后移一位。ArrayList的性能很高效，不论是查询还是取值都很迅速，但是插入和删除的性能较差，该集合线程不安全。
- ArrayList的自动扩容是如何实现的
每次在调用add方法时，会先通过size是否等于elemetData数组来判断是否执行扩容数组的方法grow,若满足会先获取数组当前的长度，然后对当前数组扩容容量大小为之前的1.5倍，如果新容量不满足需求量，直接把新容量改为需求量；否则会判断新容量和Integer.MAX_VALUE-8的差值，若小于则扩容量为新值否则就根据需求值去判断。将当前新增的数据放在对应的位置上。
