Java基础--ArrayList
ArrayList简介
ArrayList实现了List接口，继承了AbstractList，底层是数组实现的。它是非线程安全的，一般多用于单线程环境下(与Vector最大的区别就是，Vector是线程安全的，所以ArrayList 性能相对Vector 会好些)，它实现了Serializable接口，因此它支持序列化，能够通过序列化传输(实际上java类库中的大部分类都是实现了这个接口的)，实现了RandomAccess接口，支持快速随机访问(只是个标注接口，并没有实际的方法),这里主要表现为可以通过下标直接访问(底层是数组实现的，所以直接用数组下标来索引)，实现了Cloneable接口，能被克隆。
ArrayList的主要成员变量
private static final int DEFAULT_CAPACITY = 10;//默认初始容量；
private static final Object[] EMPTY_ELEMENTDATA = {};//定义一个空的数组实例以供其他需要用到空数组的地方调用
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//定义一个空数组，跟前面的区别就是这个空数组是用来判断ArrayList第一添加数据的时候要扩容多少。默认的构造器情况下返回这个空数组
transient Object[] elementData;//数据存的地方它的容量就是这个数组的长度，同时只要是使用默认构造器（DEFAULTCAPACITY_EMPTY_ELEMENTDATA ）第一次添加数据的时候容量扩容为DEFAULT_CAPACITY = 10
private int size;//当前数组的长度
ArrayList初始化
ArrayList提供了三种方式
public ArrayList();//
public ArrayList(int initialCapacity);//
public ArrayList(Collection<? extends E> c);//
下面将逐一分析以上三种初始化方式
首先分析无参构造方法的源码：
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
按注释描述无参构造方法将创建一个初始容量为10的空数组，但是从代码可以看出此时只是将elementData指向一个空数组而已。
再看看带初始容量参数的构造方法：
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
从源码可以看出：程序首先会对传进来的参数initialCapacit进行判断，如果初始容量小于0则抛出异常，如果初始容量等于0则将**elementData **指向一个空数组，如果初始容量大于0则创建一个大小为初始容量的数组。
最后分析带参数的构造方法：
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
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;
}
}
这个构造方法是直接将一个collection作为参数，不难看出程序直接将collection转化为数组赋值给elementData，如果elementData的size为0，则将elementData初始化为空数组，size为elementData的长度。这里size是ArrayList的一个int型私有变量，用于记录该list集合中当前元素的数量，注意不是容量。
ArrayList的Add方法
前面分析ArrayList的构造函数时，有一个小小的疑问，注释说创建的是一个默认大小为10的空数组，但是代码实现里面看到的只是将elementData赋值为一个空数组。其实这些都是在add方法里面实现的，下面我们分析add方法到底是如何实现的。
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
从源码里面可以看出，当调用add方法时首先会调用ensureCapacityInternal方法，从方法名可以看出，该方法是用于确保容量的。通过分析ensureCapacityInternal可看到如下逻辑：
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
通过这一步来判断，当前elementData是否为空数组(即初始化容量为0或者调用了无参构造函数后的结果)，如果是，则使用
Math.max(DEFAULT_CAPACITY, minCapacity)进行选择一个较大的，其中，DEFAULT_CAPACITY是ArrayList定义的静态常量10：可以看出，这里如果minCapacity小于10的话(如果elementData为空的话，size+1即minCapacity一般为1)，返回的是10，所以如果没有指定大小的话，默认是初始化一个容量为10的数组。然后在调用ensureExplicitCapacity方法：
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
在这个方法里进行判断，新增元素后的大小minCapacity是否超过当前集合的容量elementData.length，如果超过，则调用grow方法进行扩容。我们进入该方法进行查看:
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
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);
}
在这里可以很清楚的看到扩容容量的计算:int newCapacity = oldCapacity + (oldCapacity >> 1),其中oldCapacity是原来的容量大小，oldCapacity >> 1 为位运算的右移操作，右移一位相当于除以2，所以这句代码就等于int newCapacity = oldCapacity + oldCapacity / 2；即容量扩大为原来的1.5倍，获取newCapacity后再对newCapacity的大小进行判断，如果仍然小于minCapacity，则直接让newCapacity 等于minCapacity，而不再计算1.5倍的扩容。然后还要再进行一步判断，即判断当前新容量是否超过最大的容量 if (newCapacity - MAX_ARRAY_SIZE > 0)，如果超过，则调用hugeCapacity方法，传进去的是minCapacity，即新增元素后需要的最小容量：
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
如果minCapacity大于MAX_ARRAY_SIZE，则返回Integer的最大值。否则返回MAX_ARRAY_SIZE。然后回到grow方法，调用Arrays.copyof方法，即复制原数组内容到一个新容量的大数组里。这里Arrays.copyof方法实际是调用System.arraycopy方法。到这里，应该可以很清楚的知道ArrayList底层扩容的原理了。与Vector不同的是，Vector每次扩容容量是翻倍，即为原来的2倍，而ArrayList是1.5倍。
ArrayLIst的get方法
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
上面是对代码的分析得出的结论，下面将验证分析的结论是否正确
public class testArrayList {
public static void main(String[] args){
ArrayList list = new ArrayList<>();
System.out.print("size = "+list.size());
System.out.println(" Capacity = "+getCapacity(list));
for (int i = 0; i < 20; i++) {
list.add(i);
System.out.print("size = "+list.size());
System.out.println(" Capacity = "+getCapacity(list));
}
}
public static int getCapacity(ArrayList list){
int length = 0;
Class clazz = list.getClass();
Field field;
try{
field = clazz.getDeclaredField("elementData");
field.setAccessible(true);
Object[] objects = (Object[])field.get(list);
length = objects.length;
}catch (Exception e){
e.printStackTrace();
}finally {
return length;
}
}
}
测试代码中先创建一个ArrayList，然后输出刚创建时list的size和capacity，然后向list中添加元素，同时打印出list的size和capacity，结果如下：
size = 0 Capacity = 0
size = 1 Capacity = 10
size = 2 Capacity = 10
size = 3 Capacity = 10
size = 4 Capacity = 10
size = 5 Capacity = 10
size = 6 Capacity = 10
size = 7 Capacity = 10
size = 8 Capacity = 10
size = 9 Capacity = 10
size = 10 Capacity = 10
size = 11 Capacity = 15
size = 12 Capacity = 15
size = 13 Capacity = 15
size = 14 Capacity = 15
size = 15 Capacity = 15
size = 16 Capacity = 22
size = 17 Capacity = 22
size = 18 Capacity = 22
size = 19 Capacity = 22
size = 20 Capacity = 22
可以看出刚创建的时候list的capacity和size的大小都是为0，而添加第一个元素时，size = 0 capacity = 10，不难看出list是在调用add方法时才capacity 才为10；当添加到第11个元素时，因为size>capacity ，所以此时list会扩容，扩容后大小为15，即capacity的1.5倍。
总结
ArrayList默认容量是10，如果初始化时一开始指定了容量，或者通过集合作为元素，则容量为指定的大小或参数集合的大小。每次扩容为原来的1.5倍，如果新增后超过这个容量，则容量为新增后所需的最小容量。如果增加0.5倍后的新容量超过限制的容量，则用所需的最小容量与限制的容量进行判断，超过则指定为Integer的最大值，否则指定为限制容量大小。然后通过数组的复制将原数据复制到一个更大(新的容量大小)的数组。
