原创文章，转载请注明出处
Java程序的核心就是那些在启动时和运行中所创建的对象，如何管理这些对象是一项非常重要的工作。既要方便存储，又要方便读取，有时候还需要对对象进行排序，根据不同的场合，需要将同一类的对象存放在一起，就形成了容器的概念。
Java 集合框架.gif
Java类库为我们提供了一套相当完整的容器来解决程序运行中对象的存储问题，其中最常用的有 List、Set、Queue以及 Map。上面是一张完整的 Java 框架类库图，其中有许多接口和抽象类，他们定义了不同种类基础容器的行为，这个系列的文章将从源码的角度解释图中常用的集合类的实现以及使用。
线性的存储
ArrayList 其实是一个典型的线性表，从名字也不难看出它与数组有莫大的关联，其实 ArrayList 内部本身就是维护了一个数组，所有的插入、删除等操作都是基于这个数组实现的。
首先看一下 ArrayList 中的变量定义:
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
transient Object[] elementData;
private int size;
}
除了一些预定义的常量，ArrayList 中一共就两个变量：用于存放对象引用的数组elementData和标识个数的size。值得区分一下的概念是 size 和 capacity，size 表示的是当前 ArrayList 中所存放有效对象的个数，而 capacity 表示的是当前 elementData 数组的容量（即数组大小）。众所周知数组的长度一旦被指定就无法更改，既然 ArrayList 底层使用数组来实现，那它又是如何做到在被调用add()方法时看上去没有容量限制的呢？答案就是不断的比较 size 和 capacity，然后创建新的数组，再将原数组的内容复制过去，这在ArrayList内部称为扩容操作。
对象的存放
ArrayList共有三个构造器，他们的作用都是初始化elementData数组：
// NO.1
public ArrayList() {
this(10);
}
// NO.2
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
this.elementData = new Object[initialCapacity];
}
// NO.3
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
前两个构造器通过指定的capacity来初始化一个空的数组：this.elementData = new Object[initialCapacity]，如果没有initialCapacity参数则默认为10。
tips: 在新建一个ArrayList时可以预估需要的大小，以
new ArrayList(20)这种形式调用，可以避免在使用ArrayList时多次扩容。
第三个构造器接收一个Collection参数，如果你有仔细看过文章开头的集合框架图不难发现ArrayList是Collection的一种实现，这个构造器表示可以接收Collection接口的所有实现类型，并将其转换为自身类型（ArrayList）进行存储。
扩容与移位
要想将对象放入 ArrayList 中需要调用add(E)或者add(int, E)方法，前者将对象按顺序放到末尾，后者可以指定放置的位置。
//...
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
//...
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
在调用两种 add 方法时都需要先调用ensureCapacityInternal，这个方法的做用是将数组进行扩容。由于在真正扩容之前 JDK 会进行一些逻辑检查和判断，最终调用到grow()函数，出于篇幅考虑将一些函数的调用关系省略掉，有兴趣的朋友可以自行查阅源码。先看看grow()函数中关键的部分：
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);
}
可以看到参数 minCapacity 只是一个“建议”值，ArrayList 默认每次扩容为当前容量的1.5倍：
int newCapacity = oldCapacity + (oldCapacity >> 1);
在扩充到1.5倍之后如果还没有达到 minCapacity 时，便会采用 minCapacity 的值，最后调用 Arrays.copyOf(elementData, newCapacity);将整个数组进行拷贝。
回到add(int, E)方法，数组扩容完后，需要在指定的位置插入元素，接着便调用了System.arraycopy，根据参数可以看出这一步将 elementData 数组第index之后的元素全部向后移了一位，再在 index 位置插入新元素。
至此，对象的存放完成，通过对扩容和移位的分析，可以看出基于数组实现的 ArrayList 在对象的插入操作上效率并不高，但是数组的优点是快速的随机访问，在接下来的对象获取方法中将可以看到 ArrayList 很好的继承了数组的这一特性。
对象的获取
ArrayList 最常用的get(int index)方法一共只有两行：
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
//...
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
在检查完参数 index 的范围之后，直接就返回 index 位置上的元素，非常快速。
另一个获取对象有关的常用函数是indexOf(Object o)，到这里读者应该可以想到基于数组的 ArrayList 是怎样查找元素在数组中的下标了，遍历：
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;
}
通过源码可以观察到比较有趣的一点，indexOf的参数允许为 null，并且如果数组中有值为 null的元素（在 size 范围以内）时将返回下标。
调用remove(int index)函数同样会使数组中多个元素位置变动：
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;
}
同样是调用 arraycopy方法，只不过拷贝的位置与 add 时相反。同时注意到elementData[--size] = null;是非常关键的，正如注释所说，进行remove操作以后，数组最后一个位置上引用的对象逻辑上已经被“移除”，但是实际数组还保持着对象的引用，这会导致 GC 无法将其回收，造成内存泄露。
功能性函数
介绍完了主要操作函数，ArrayList 封装的一些功能函数也非常有意思。
- trimToSize：
这个函数的作用是将数组容量（capacity）修整到 size 的大小。譬如ArrayList在大量读入对象之后又进行了许多移除操作，并且预计在今后很长一段时间容量都将保持在较小范围内，这时可以手动都用trimToSize()来节约内存空间。
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
- addAll:
addAll 方法接收一个实现了 Collection 接口的类型，并将其添加到当前 ArrayList 末尾：
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
其实质最终还是调用了 arraycopy 方法，ArrayList.addAll()方法很容易让人联想到定义在 Collections 中的 addAll 方法，在没有特殊要求的时候两者可以互换，个别情况下由于其实现逻辑不同两者的性能会有一些差异，这里不做过多讨论，开发者可以根据编程风格和规范自行选择，Collections.addAll()的定义如下：
public static <T> boolean addAll(Collection<? super T> c, T... elements) {
boolean result = false;
for (T element : elements)
result |= c.add(element);
return result;
}
小结
ArrayList 正如其名字，是实现了 List接口规范，底层采用数组的一个集合类。ArrayList 继承了数组的所有优缺点，并且在使用上针对 List 接口进行了封装，例如在指定位置插入、删除元素等。开发人员在使用时可以完全按照 List 接口定义的规范进行调用，但是知道其底层实现细节对程序调优、不同集合类之间的选择有很大的帮助。
网友评论