上篇我们提到了顺序表在平常开发中的应用，现在我们只重点分析ArrayList及Vector的实现。
ArrayList想必大家都已经很熟悉了，但是我们只是在外面调用接口，有的人并不知道其内部的实现原理。我以前也是遇到集合都用ArrayList,但是用了那么多次也没有对其有深入的了解，现在我们就一起来分析。
ArrayList是基于数组实现的，所以里面有很多操作都是通过数组来操作的，它是一个动态数组，其容量能自动增长，类似于C语言中的动态申请内存，动态增长内存。ArrayList不是线程安全的，只能在单线程环境下，多线程环境下可以考虑用Collections.synchronizedList(List l)函数返回一个线程安全的ArrayList类，也可以使用concurrent并发包下的CopyOnWriteArrayList类。
（一）ArrayList的继承关系与实现的接口
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
--------------------------------------------------------------------------------------------------
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E>
--------------------------------------------------------------------------------------------------
public abstract class AbstractCollection<E> implements Collection<E>
从ArrayList<E>可以看出它是支持泛型的，ArrayList继承的是AbstractList，而AbstractList又继承了AbstractCollection，AbstractCollection是Collection接口的实现类，里面封装了一些集合的通用接口；而AbstractList可以说是实现List接口的一个顶层实现类，里面也定义了一些有关List接口在对Collection的接口基础上的拓展接口。我们通常使用的ArrayList就是AbstractList其中的一个子类。
ArrayList实现了List接口，所以ArrayList必须实现List接口里面封装的方法。
ArrayList实现了RandomAccess接口，支持快速随机访问。
ArrayList实现了Cloneable接口，使得ArrayList能被克隆，
通过实现 java.io.Serializable 接口以启用其序列化功能。未实现此接口的类将无法使其任何状态序列化或反序列化。序列化接口没有方法或字段，仅用于标识可序列化的语义。
（二）ArrayList的属性字段
private static final int DEFAULT_CAPACITY = 10; //ArrayList默认的初始容量
private static final Object[] EMPTY_ELEMENTDATA = {}; //用于空实例的共享空数组实例
ArrayList定义了两个属性，咋一看这不是我们的顺序表的结构吗？
其中transient关键字表示的字段的生命周期仅存于调用者的内存中而不会写到磁盘持久化。
transient Object[] elementData; //存放ArrayList的元素数组
private int size;
（三）ArrayList的构造函数
（1）带有初始容量的构造函数
public ArrayList(int initialCapacity) {
super(); //调用分类AbstractList的空构造
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
this.elementData = new Object[initialCapacity]; //根据传进来的初始容量建表
}
（2）无参构造函数
public ArrayList(){ //可能有些Api的写法不一样，但思想都是构造了一个初始容量为10的数组
super();
this.elementData = EMPTY_ELEMENTDATA;
}
（3）无参构造函数
//将集合c中的元素全部复制到表中
public ArrayList(Collection<? extends E> c){
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
//这个是谷歌工程师写的，他说c的toArray方法有可能不返回一个数组，这里是一个bug
if(elementData.getClass() != Object[].class){
//数组的copy操作在这里就不分析了，可以查看Arrays的源码
elementData = Arrays.copyOf(elementData,size,Object[].class);
}
}
（四）ArrayList的增删改查
（1）添加操作
//在数组尾部添加元素e
public boolean add(E e) {
ensureCapacityInternal(size + 1); //先确保数组容量是否够用
elementData[size++] = e;
return true;
}
//在指定的位置index添加元素e
public void add(int index,E e){
rangeCheckForAdd(index); //查看要添加的index是否越界
ensureCapacity(size+1);
//将index位置（包含）之后的数组全部往右移动一位
System.arraycopy(elementData,index,elementData,index+1,size-index); //性能慢就是体现在这里
elementData[index] = e;
size++;
}
//将集合c添加到ArrayList中的指定位置
public boolean addAll(int index,Collection<? extends E> c){
rangeCheckForAdd(index);
Object[] o = c.toArray();
int numNew = o.length;
int numMoved = size - index; //数组要移动的位数
if(numMoved>0){
//将index位置（包含）之后的数组全部往右移动numNew位
System.arraycopy(elementData,index,elementData,index+numNew,numMoved);
}
System.arraycopy(o,0,elementData,index,numNew);
size += numNew;
return numMoved != 0;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) { //如果空表
//取默认容量和数组要达到的最小容量的最大值
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity); //确保容量
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++; //这个是List的改变次数，在ArrayList的父类上定义的，可以不必太过理会
// overflow-conscious code
if (minCapacity - elementData.length > 0) //如果传进来的容量大于数组长度，就说明数组的容量不够用了
grow(minCapacity); //增长容量
}
//ArrayList的扩容机制
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length; //原来的容量
int newCapacity = oldCapacity + (oldCapacity >> 1); //定义新的容量为原来的3/2倍
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); //把原来的数组复制到新的数组中，还是用elementData 表示,并指定新的容量
}
//MAX_ARRAY_SIZE=Integer.MAX_VALUE - 8;
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError()；
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
private void rangeCheckForAdd(int index){
if(index<0 || index>size){
throw new IndexOutOfBoundsException("Index:"+index+",Size:"+size);
}
}
(2)删除操作
//删除数组中指定位置的元素
public E remove(int index){
rangeCheck(index); //为要删除和查找的Index查看是否越界
E oldValue = (E)elementData[index];
//需要复制元素的个数，也就是index后面的元素个数
int numMoved = size - index -1;
if(numMoved>0){
//将index后面的元素全部往前移动1个位置
System.arraycopy(elementData,index+1,elementData,index,numMoved);
}
//经过arraycopy的移位，数组容器的最个位置被腾空，但是仍然持有某个对象的引用，需要把这个多余的引用置为null.
elementData[--size] = null;
return oldValue;
}
//删除数组中的对象
public boolean remove(Object o){
if(o == null){ //对象为Null的删除方法
for(int index=0;index<size;index++){
fastRemove(index);
return true;
}
}else{
for(int index=0;index<size;index++){
if(elementData[index].equals(o)){
fastRemove(index);
return true;
}
}
}
return false;
}
//快速删除 这是个内部方法，数组越界已经在上个方法中判断，这里就不再进行判断了
private void fastRemove(int index){
int numMoved = size - index -1;
if(numMoved > 0){
System.arraycopy(elementData,index+1,elementData,index,numMoved);
}
elementData[--size] = null;
}
private void rangeCheck(int index){
if(index<0 || index>=size){
throw new IndexOutOfBoundsException("Index:"+index+",Size:"+size);
}
}
(3)修改操作
public E set(int index,E e){
rangeCheck(index); //检查下标越界问题
E oldValue = (E)elementData[index];
elementData[index] = e; //直接将当前位置的元素进行替换
return oldValue;
}
(4)查询操作
public E get(int index){
rangeCheck(index);
E oldValue = (E)elementData[index];
return oldValue;
}
(五)ArrayList定义的一些集合方法和数组的下表查询方法
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
//清空数组
public void clear() {
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
//将当前容量值设置为实际元素个数
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size);
}
}
//判断数组中是否包含这个对象
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
//返回对象在数组中的下标(第一次出现的)
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;
}
这些就是ArrayList的大概了，还有遍历和迭代器没分析，但是我觉得那不是最重要的，重要的是了解ArrayList的数据结构和增删改查操作还有扩容机制。这些也是面试中可能遇到的问题，只有了解了其中的实现原理，我们才能在面试官面前对答如流，还有提升自己。有些方法可能在个版本的不一样，我这里是在用Android SDK里面的源码进行分析的，除非有版本变了数据结构，否则实现原理都是一样的。对于Vector我们不必太过深究，因为现在基本看不到使用了。
(六)ArrayList和Vector
还有Vector没分析，但其实Vector的实现原理和ArrayList基本上是一模一样的，只是Vector在实现增删改查等等操作时添加了synchronized关键字，在多线程情况下是安全的。
List接口下一共实现了三个类：ArrayList，Vector，LinkedList。LinkedList就不多说了，它一般主要用在保持数据的插入顺序的时候。ArrayList和Vector都是用数组实现的，主要有这么三个区别：
1、Vector是多线程安全的，而ArrayList不是，这个可以从源码中看出，Vector类中的方法很多有synchronized进行修饰，这样就导致了Vector在效率上无法与ArrayList相比；
2、两个都是采用的线性连续空间存储元素，但是当空间不足的时候，两个类的增加方式是不同的，很多网友说Vector增加原来空间的一倍，ArrayList增加原来的1.5倍。
//ArrayList的扩容
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);
}
// Vector扩容，这个扩容需要做个判断：如果容量增量初始化的不是0，即使用的public Vector(int initialCapacity,int capacityIncrement)构造方法进行的初始化，那么扩容的容量是(oldCapacity+capacityIncrement)，就是原来的容量加上容量增量的值；
//如果没有设置容量增量，那么扩容后的容量就是(oldCapacity+oldCapacity)，就是原来容量的二倍。
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);
}
3、Vector可以设置增长因子，而ArrayList不可以，最开始看这个的时候，我没理解什么是增量因子，不过通过对比一下两个源码理解了这个，先看看两个类的构造方法：
ArrayList有三个构造方法：
public ArrayList(int initialCapacity)//构造一个具有指定初始容量的空列表。
public ArrayList()//构造一个初始容量为10的空列表。
public ArrayList(Collection<? extends E> c)//构造一个包含指定 collection 的元素的列表
Vector有四个构造方法：
public Vector()//使用指定的初始容量和等于零的容量增量构造一个空向量。
public Vector(int initialCapacity)//构造一个空向量，使其内部数据数组的大小，其标准容量增量为零。
public Vector(Collection<? extends E> c)//构造一个包含指定 collection 中的元素的向量
public Vector(int initialCapacity,int capacityIncrement)//使用指定的初始容量和容量增量构造一个空的向量
（七）ArrayList总结
（1）ArrayList是线性表中的顺序存储结构的顺序表，因为内部维护的是一个数组，数组是一个拥有连续存储地址的存储块。
（2）ArrayList因为内部维护的是一个数组，查询和修改的效率很高，尾部插入效率也高，但是插入添加和删除的效率比较低，性能变慢具体体现在数组的copy上，特别是数据量大的情况下必较明显。
（3）ArrayList在添加元素的时候是允许加入null元素的。但我们在添加数据的时候最好对数据进行非空判断，否则取出来的数据在使用的时候空指针分分钟教你做人。
（4）ArrayList的是线程不安全的，尽量不要在多线程环境下使用ArrayList。
请老司机指出不足之处，谢谢！
网友评论