Java - 剖析ArrayList
一、基本用法
ArrayList 是一个泛型容器，在新建 ArrayList 的时候需要实例化泛型参数，如下：
ArrayList<Integer> intList = new ArrayList<Integer>();
ArrayList<String> strList = new ArrayList<String>();
在 ArrayList 中常用的方法如下：
public boolean add(E e) // 添加元素到末尾
public boolean isEmpty() //判断是否为空
public int size() //获取元素个数
public E get(int index) //访问指定位置的元素
public int indexOf(Object o) // 查找指定元素，如果找到返回索引位置，否则返回-1
public int lastIndexOf(Object o) // 从后往前找
public boolean contains(Object o) // 是否判断指定元素，判断依据是调用 equals 方法
public E remove(int index) // 删除指定位置的元素，返回值为删除的元素
//删除指定对象，只删除第一个相同的对象，返回值为被删对象
//如果o为null，则删除值为null的元素
public boolean remove(Object o)
public void clear() // 清空所有元素
// 在指定位置插入元素， index 为0表示插入到最前面，index为ArrayList的长度则表示插入到最后面
public void add(int index, E element)
public E set(int index, E element) // 修改指定位置的元素内容
二、基本原理
ArrayList内部有一个数组 elementData， 在一般情况下会有一些预留口那件，同时又一个整数 size 记录实际的元素个数。
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;
该类的方法内部操作的基本都是这个数组和这个整数， 其中 elementData 会跟着实际元素的个数增多而重新分配，而size使用记录实际的元素个数。
接下来查看 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;
}
首先调用ensureCapacityInternal方法来确保数组容量是足够的，其实现为：
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
首先调用calculateCapacity用于返回现在需要的最小容量，接下来进入ensureExplicitCapacity方法判断现有容量是否足够，如果不够则调用 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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
从oldCapacity >> 1可以看出是对原有数组容量除以2，因此每一次扩容都是原有容量的 1.5 倍。如果发现扩展1.5倍之后还是不够， 则直接扩容为minCapacity，与此同时还会对扩容的数量进行边界判断，在合法之后对数据元素进行拷贝，其中MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8。
接下来我们查看remove方法的实现
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their
* indices).
*
* @param index the index of the element to be removed
* @return the element that was removed from the list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
rangeCheck(index);
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;
}
首先对边界进行检查，获取元素。然后计算需要移动的元素的个数，从index之后的元素均需要移动，之后调用System.arraycopy方法进行元素的移动。 在元素移动完成之后，使用elementData[--size] = null，将 size - 1的同时将最后一个元素设置为 null，使得不再引用原有对象，这样就便于垃圾回收。
三、ArrayList实现的接口
ArrayList实现了三个主要的接口：
- Collection
- List
- RandomAccess
3.1 Collection
Collection表示一个数据集合，数据间没有位置或顺序的概念，接口定义为：
public interface Collection<E> extends Iterable<E> {
int size();
boolean isEmpty();
boolean contains(Object o);
Iterator<E> iterator();
Object[] toArray();
<T> T[] toArray(T[] a);
boolean add(E e);
boolean remove(Object o);
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c);
boolean removeAll(Collection<?> c);
boolean retainAll(Collection<?> c);
void clear();
boolean equals(Object o);
int hashCode();
}
Java 8对Collection接口添加了几个默认方法，包括removeIf、stream、spliterator等，具体可参见API文档。
3.2 List
List表示有顺序或位置的数据集合，它扩展了Collection，增加的主要方法有（Java 7）：
boolean addAll(int index, Collection<? extends E> c);
E get(int index);
E set(int index, E element);
void add(int index, E element);
E remove(int index);
int indexOf(Object o);
int lastIndexOf(Object o);
ListIterator<E> listIterator();
ListIterator<E> listIterator(int index);
List<E> subList(int fromIndex, int toIndex);
3.3 RandomAccess
RandomAccess的定义为：
public interface RandomAccess {
}
这种没有任何代码的接口在Java中被称为标记接口，用于声明类的一种属性。
实现了RandomAccess接口的类表示可以随机访问，可随机访问就是具备类似数组那样的特性，数据在内存是连续存放的，根据索引值就可以直接定位到具体的元素，访问效率很高。
比如，Collections类中有一个方法binarySearch，在List中进行二分查找，它的实现代码就根据list是否实现了RandomAccess而采用不同的实现机制，如下所示：
public static <T>
int binarySearch(List<? extends Comparable<? super T>> list, T key) {
if(list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
return Collections.indexedBinarySearch(list, key);
else
return Collections.iteratorBinarySearch(list, key);
}
四、总结
ArrayList，它的特点是内部采用动态数组实现，有以下的特点：
- 可以随机访问，按照索引位置进行访问效率很高，用算法描述中的术语，效率是O（1）
- 除非数组已排序，否则按照内容查找元素效率比较低，具体是O（N），N为数组内容长度，也就是说，性能与数组长度成正比。
- 加元素的效率还可以，重新分配和复制数组的开销被平摊了，具体来说，添加N个元素的效率为O（N）。
- 插入和删除元素的效率比较低，因为需要移动元素，具体为O（N）。
需要说明的是，ArrayList不是线程安全的。此外，需要了解的是，还有一个类Vector，它是Java最早实现的容器类之一，也实现了List接口，基本原理与ArrayList类似，内部使用synchronized实现了线程安全，不需要线程安全的情况下，推荐使用ArrayList。
