关注点 | 结论
---|---
ArrayList是否允许空 | 允许
ArrayList是否允许重复数据 | 允许
ArrayList是否有序 | 有序
ArrayList是否线程安全 | 非线程安全
#### 1. 继承的父类和实现的接口
```java
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
```
> ArrayList 继承了 AbstractList 类，此类提供了 List 接口的骨干实现，继承此类的子类适合用于“随机访问”数据存储（如数组），Vector 也是此类的子类。
> 与 AbstractList 类对应的类是 AbstractSequentialList 类，继承该类的子类适合用于“连续访问”数据存储（如链接列表），代表的子类如 LinkedList 。
> ArrayList 实现了 List 接口，List 接口通常表示一个列表（数组、队列、链表、栈等），其中的元素可以重复，代表的实现类有 ArrayList、LinkedList、Stack、Vector。
> ArrayList 实现了 RandomAccess 接口，该接口为标记接口，用来表明其支持快速随机访问。
> ArrayList 实现了 Cloneable 接口，以指示 Object.clone() 方法可以合法地对该类实例进行按字段复制。
> ArrayList 实现了 Serializable 接口，因此它支持序列化，能够通过序列化传输。
#### 2. 属性
```java
/**
* 序列版本号
*/
private static final long serialVersionUID = 8683452581122892189L;
/**
* 默认容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 无参的空数组常量
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 有参的空数组
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 存放元素的数组，从这可以发现ArrayList的底层实现就是一个Object数组
*/
transient Object[] elementData;
/**
* 当前的实际元素个数
*/
private int size;
```
#### 3. 构造函数
```java
//用初始容量作为参数的构造方法
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//初始容量大于0，实例化数组
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//初始容量等于0，赋予空数组
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
//无参的构造方法
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
```
> 从构造方法中我们可以看见，默认情况下，elementData是一个大小为0的空数组，当我们指定了初始大小的时候，elementData的初始大小就变成了我们所指定的初始大小了。
#### 4. get，set方法
```java
//返回指定索引的值
public E get(int index) {
//检查索引值是否越界
rangeCheck(index);
return elementData(index);
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
//将制定索引上的值替换为新值，并返回旧值
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
```
> 因为ArrayList是采用数组结构来存储的，所以它的get方法非常简单，先是判断一下有没有越界，之后就可以直接通过数组下标来获取元素了，所以get的时间复杂度是O(1)。
> set方法的作用是把下标为index的元素替换成element，跟get非常类似，所以就不在赘述了，时间复杂度度为O(1)。
#### 5. add
```java
//将指定的元素添加到列表的尾部
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);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//默认是扩大为原来的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
//1.5倍还是不够的话，直接用传进来的minCapacity作为容量值
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//自己传进来的值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;
}
//将元素添加到指定位置
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
//arraycopy(被复制的数组，从第几个元素开始复制，要复制到的数组，从第几个元素开始粘贴，一共需要复制的元素个数)
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
```
> ArrayList的add方法也很好理解，在插入元素之前，它会先检查是否需要扩容，然后再把元素添加到数组中最后一个元素的后面。在ensureCapacityInternal方法中，我们可以看见，如果当elementData为空数组时，它会使用默认的大小去扩容。所以说，通过无参构造方法来创建ArrayList时，它的大小其实是为0的，只有在使用到的时候，才会通过grow方法去创建一个大小为10的数组。
> 第一个add方法的复杂度为O(1)，虽然有时候会涉及到扩容的操作，但是扩容的次数是非常少的，所以这一部分的时间可以忽略不计。如果使用的是带指定下标的add方法，则复杂度为O(n)，因为涉及到对数组中元素的移动，这一操作是非常耗时的
> grow方法是在数组进行扩容的时候用到的，从中我们可以看见，ArrayList每次扩容都是扩1.5倍，然后调用Arrays类的copyOf方法，把元素重新拷贝到一个新的数组中去。
#### 6. remove
```java
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
//arraycopy(被复制的数组，从第几个元素开始复制，要复制到的数组，从第几个元素开始粘贴，一共需要复制的元素个数)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
```
> remove方法与add带指定下标的方法非常类似，也是调用系统的arraycopy方法来移动元素，时间复杂度为O(n)。
#### 7. size(),isEmpty()
```java
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
```
> size方法非常简单，它是直接返回size的值，也就是返回数组中元素的个数，时间复杂度为O(1)。这里要注意一下，返回的并不是数组的实际大小。
#### 8.indexOf()和lastIndexOf()
```java
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;
}
```
> indexOf方法的作用是返回第一个等于给定元素的值的下标。它是通过遍历比较数组中每个元素的值来查找的，所以它的时间复杂度是O(n)。
> lastIndexOf的原理跟indexOf一样，而它仅仅是从后往前找起罢了。
#### 9. removeRange()
```java
//删除fromIndex到toIndex之间的全部元素
protected void removeRange(int fromIndex, int toIndex)
{
modCount++;
//numMoved为删除索引后面的元素个数
int numMoved = size - toIndex;
//将删除索引后面的元素复制到以fromIndex为起始位置的存储空间中去
System.arraycopy(elementData, toIndex, elementData, fromIndex,numMoved);
int newSize = size - (toIndex-fromIndex);
//将ArrayList后面(toIndex-fromIndex)个元素置为null
for (int i = newSize; i < size; i++)
{
elementData[i] = null;
}
size = newSize;
}
```
#### 10. Vector
> vector因为很多方法都跟ArrayList一样，只是多加了个synchronized来保证线程安全罢了。如果照着ArrayList的方式再将一次就显得没意思了，所以只把Vector与ArrayList的不同点提一下就可以了。
Vector比ArrayList多了一个属性：
> protected int capacityIncrement;
这个属性是在扩容的时候用到的，它表示每次扩容只扩capacityIncrement个空间就足够了。该属性可以通过构造方法给它赋值。先来看一下构造方法：
```java
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
public Vector() {
this(10);
}
```
从构造方法中，我们可以看出Vector的默认大小也是10，而且它在初始化的时候就已经创建了数组了，这点跟ArrayList不一样。再来看一下grow方法：
```java
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
```
从grow方法中我们可以发现，newCapacity默认情况下是两倍的oldCapacity，而当指定了capacityIncrement的值之后，newCapacity变成了oldCapacity+capacityIncrement。
#### 10. 总结
> 注意扩充容量的方法ensureCapacity。ArrayList在每次增加元素（可能是1个，也可能是一组）时，都要调用该方法来确保足够的容量。当容量不足以容纳当前的元素个数时，就设置新的容量为旧的容量的1.5倍，如果设置后的新容量还不够，则直接新容量设置为传入的参数（也就是所需的容量），而后用Arrays.copyof()方法将元素拷贝到新的数组（详见下面的第3点）。从中可以看出，当容量不够时，每次增加元素，都要将原来的元素拷贝到一个新的数组中，非常之耗时，也因此建议在事先能确定元素数量的情况下，才使用ArrayList，否则建议使用LinkedList。
> 1、ArrayList创建时的大小为0；当加入第一个元素时，进行第一次扩容时，默认容量大小为10。
> 2、ArrayList每次扩容都以当前数组大小的1.5倍去扩容。
> 3、Vector创建时的默认大小为10。
> 4、Vector每次扩容都以当前数组大小的2倍去扩容。当指定了capacityIncrement之后，每次扩容仅在原先基础上增加capacityIncrement个单位空间。
> 5、ArrayList和Vector的add、get、size方法的复杂度都为O(1)，remove方法的复杂度为O(n)。
> 6、ArrayList是非线程安全的，Vector是线程安全的。
> 7. ArrayList不是线程同步的，在多线程下可以考虑使用 Collections.synchronizedList 方法将该列表“包装”起来。这最好在创建时完成，以防止意外对列表进行不同步的访问：代码如下：
```java
List list = Collections.synchronizedList(new ArrayList(...));
```