java 中ArrayList底层实现
最近听一个同事公司面试，问及java中ArrayList底层实现问题。对于一个搞java变成的人来说，这个问题真的应该算陌生。因为这是基础中的基础，不应该不知道，今天我就拿出点时间来叙述一下java中ArrayList的底层具体实现，讲解一下主要方法的实现细节。希望对那些还不了解的人有所帮助，也欢迎大家对我提问。

ArrayList是接口List的一个实现类，List的实现还有其他的类，底层的实现都不尽相同，我们常有的还有LinkedList类，该类的底层是采用双向链表实现的，今天就不详细介绍。今天主要讨论是ArrayList类。在开始介绍底层实现之前，我先交给大家一个学习的方法，java源代码都是开源的，学习这些工具类，最简单的方式就直接阅读sun公司发布的jdk源码。

public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
这是ArrayList继承关系，不需要多介绍，如果大家看过List接口底层实现话，其实非常简单，无非定义了一些操作List的基本方法。ArrayList 底层维护着一个数组，这个数字定义如下：
private transient Object[] elementData;，这是一个可以存放任意类型的数组，那么到底这个数组长度是多大呢。我们都知道数组的长度是固定，问题的关键来了，ArrayList底层到底如何使该数组变成增长的呢。这就需要我们看看他的构造方法。

ArrayList总共有三个构造方法，分别如下，这些都可以在jdk的源码里面找到：
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}

public ArrayList() {
this(10);
}
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
很明显可以发现，我们一般都使用的是不带参数的构造方法，来生成一个ArrayList对象，这个构造方法实际上调用第一个带参数构造方法来实现，仔细观察第一个构造方法，我们可以发现，使用默认的构造方法生成对象，底层会生成一个大小为10 的数组，当然也可以指定初始大小。那是如何将数据添加到ArrayList中的呢？我们还是先来看看源码？
public E set(int index, E element) {
RangeCheck(index);

E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}


public boolean add(E e) {
ensureCapacity(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}


public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(
"Index: "+index+", Size: "+size);

ensureCapacity(size+1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}

sun公司提供很多种方式来添加数据，但是这些方法本质没有任何区别都是往数组里面添加对象，大家疑惑点可能就是ensureCapacity(size + 1); 这里，这个方法是干什么用的，这就是解决大家疑惑调用的方法，如果数组满了怎么办呢？其实只要你看过源码是就一目了然的。我还是看看ensureCapacity(size + 1); 这个方法实现吧。
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
这个方法实现也是非常简单。无非就是判断当前数组长度是否还能放进去，如果放不进去，那就重新生成一个数组，这个数组大小是原来数组的（oldCapacity * 3)/2 + 1;就是1.5+1大小，以此类推。然后将老数组数据拷贝到新的数组里面。就是这么简单，没有任何复杂点。


所以可以肯定的说ArrayList底层是采用数组实现，这种数据结构实现，对插入和删除数据的代价是非常大，但是对查找数据是非常高速的。所以在使用的时候也要注意。