ArrayList详解
1、概述
ArrayList 实现了 List 接口，是顺序容器，即元素存放的数据与放进去的顺序相同，允许放入null元素，底层通过数组实现。
每个ArrayList实例都有一个容量（capacity），该容量是指用来存储列表元素的数组的大小。默认初始容量为10。 随着ArrayList中元素的增加，它的容量也会不断的自动增长。
在每次添加新的元素时，ArrayList都会检查是否需要进行扩容操作，扩容操作带来数据向新数组的重新拷贝，所以如果我们知道具体业务数据量，在构造ArrayList时可以给ArrayList指定一个初始容量，这样就会减少扩容时数据的拷贝问题。
当然在添加大量元素前，应用程序也可以使用ensureCapacity操作来增加ArrayList实例的容量，这可以减少递增式再分配的数量。
2、ArrayList的继承关系
ArrayList 实现了List接口（规定了List的操作规范）、RandomAccess（可随机访问）、Cloneable（可拷贝）、Serializable（可序列化）。
3、ArrayList底层数据结构
底层数据结构
ArrayList的底层是一个object数组，并且由trasient修饰。因此，ArrayList底层数组不会参与序列化，而是使用另外的序列化方式！
/**
* 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;
构造函数
/**
* 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);
}
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 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;
}
}
4、说一说ArrayList 的扩容机制？
一句话： ArrayList扩容的本质就是计算出新的扩容数组的size后实例化，并将原有数组内容复制到新数组中去。默认情况下，新的容量会是原容量的1.5倍！
下面看看扩容源码！
以JDK1.8为例：
// 每次在add()一个元素时，arraylist都需要对这个list的容量进行一个判断
// 通过ensureCapacityInternal()方法确保当前ArrayList维护的数组具有存储新元素的能力
// 经过处理之后将元素存储在数组elementData的尾部
public boolean add(E e) {
//判断是否可以容纳e，若能，则直接添加在末尾；若不能，则进行扩容，然后再把e添加在末尾
ensureCapacityInternal(size + 1); // Increments modCount!!
//将e添加到数组末尾
elementData[size++] = e;
return true;
}
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//如果传入的是个空数组则最小容量取默认容量与minCapacity之间的最大值
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 若ArrayList已有的存储能力满足最低存储要求，则返回add直接添加元素；
// 如果最低要求的存储能力>ArrayList已有的存储能力，这就表示ArrayList的存储能力不足，因此需要调用 grow();方法进行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// 获取elementData数组的内存空间长度
int oldCapacity = elementData.length;
// 扩容至原来的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
//校验容量是否够
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//若预设值大于默认的最大值，检查是否溢出
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 调用Arrays.copyOf方法将elementData数组指向新的内存空间
//并将elementData的数据复制到新的内存空间
elementData = Arrays.copyOf(elementData, newCapacity);
}
每当向数组中添加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求。
数组扩容通过一个公开的方法 ensureCapacity(int minCapacity) 来实现。在实际添加大量元素前，我们也可以使用ensureCapacity来手动增加ArrayList实例的容量，以减少递增式再分配的数量。
数组进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长大约是其原容量的1.5倍。
这种操作的代价是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张。
当我们可预知要保存的元素的多少时，要在构造ArrayList实例时，就指定其容量，以避免数组扩容的发生。或者根据实际需求，通过调用ensureCapacity方法来手动增加ArrayList实例的容量。
5、增删改查
ArrayList.size()、ArrayList.isEmpty()、ArrayList.get()、ArrayList.set()方法均能在常数时间内完成，时间复杂度为 O(1)；
而ArrayList.remove()涉及到元素移动，时间复杂度为 O(n)；
ArrayList.add() 方法的时间开销跟插入位置有关，并且也有可能产生扩容，时间复杂度为 O(n)。
其余方法大都是线性时间。
增：add()
添加元素时，首先判断索引是否合法，然后检测是否需要扩容，最后使用System.arraycopy方法来完成数组的复制。
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++;
}
这个方法无非就是使用System.arraycopy()方法将C集合(先准换为数组)里面的数据复制到elementData数组中。这里就稍微介绍下System.arraycopy()，因为下面还将大量用到该方法。该方法的原型为：
public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
它的作用就是进行数组元素的复制，即从指定源数组中复制一个数组，复制从指定的位置开始，到目标数组的指定位置结束。
删：remove()
删除元素时，同样判断索引是否和法，删除的方式是把被删除元素右边的元素左移，方法同样是使用System.arraycopy进行拷贝：
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;
}
ArrayList还提供一个清空数组的办法，方法是将所有元素置为null，这样就可以让GC自动回收掉没有被引用的元素了：
/**
* Removes all of the elements from this list. The list will
* be empty after this call returns.
*/
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
改：set()
修改元素时，只需要检查下标即可进行修改操作：
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
查：get()
get()方法同样很简单，唯一要注意的是由于底层数组是Object[]，得到元素后需要进行类型转换：
public E get(int index) {
rangeCheck(index);
return (E) elementData[index];//注意类型转换
}
说明：上述方法都使用了rangeCheck方法，其实就是简单地检查下标而已：
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
6、线程安全
ArrayList 没有实现同步 (synchronized)，即ArrayList是线程不安全的。在其迭代器iteator中，如果有多线程操作导致modCount改变，会执行fast-fail（快速失败），抛出异常：
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
如果需要多个线程并发访问，用户可以添加手动同步锁，亦可使用Collections 工具类！
Collections 提供了多个synchronizedXxx()方法·，该方法可以将指定集合包装成线程安全的集合，从而解决多线程并发访问集合时的线程安全问题。
方法如下：
synchronizedCollection(Collection<T> c) //返回指定 collection 支持的同步（线程安全的）collection
synchronizedList(List<T> list)//返回指定列表支持的同步（线程安全的）List
synchronizedSet(Set<T> s) //返回指定 set 支持的同步（线程安全的）set
但是，最好不要使用这些方法，效率非常低，需要线程安全的集合类型时请考虑使用 JUC 包下的并发集合！