写在前面
Java的集合框架完备而又牛叉，其实现值得我这样的小白去一探究竟。当然了，在这我暂时不会很深入的去阅读整个集合框架，而是通过一两个实现去摸一下他的套路，希望最终我能摸到点集合框架的门路。在本文中，我将会带你阅读：
- ArrayList内部的基本实现
- add()方法
- get()方法
是的，你没看错，就看这三个……当然了，ArrayList远不止如此，但现在我只会去探究一下其基本实现。
基本实现
首先回忆一下平时我们是如何初始化一个ArrayList的：
List<String> list = new ArrayList<>();
得益于Java的多态使得我们可以写出如上的代码，那么无参的ArrayList的构造函数是啥样的呢？
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
接下来看看他是怎么初始化的，左边那个值是个什么东西，右边那个值又是个什么东西。
首先是左边：
/**
* 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
如果用transient声明一个实例变量，当对象存储时，它的值不需要位置。换句话说就是，用transient关键字标记的成员变量不参与序列化的过程。
回过头来再看看，这是个Object的数组，这就是ArrayList元素被存储的地方。ArrayList的容量就是这个数组的长度。再来看看上面那个构造函数的右边具体是个什么东西：
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
从上面的代码可以看出来就是个空的Object数组，果然很符合空的ArrayList（笑）。接下来解析代码将会在我们调用了无参的构造函数的基础上去分析，那么让我们通过几个常用的方法去看看ArrayList内部究竟是如何使用这个Object数组的。
add()
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
向list的末尾追加一个指定的元素，第一行代码看样子和ArrayList的尺寸有点关系，第二句代码很明显就是追加元素的操作了。那么回过头来，看看第一句代码究竟干了啥：
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
首先从名字上分析分析……确定内部的容量，果然是和尺寸有关系的。看下具体的代码，如果elementData等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA，那么会从minCapacity和DEFAULT_CAPACITY中比较大的值中挑一个出来赋给minCapacity，接着调用ensureExplicitCapacity方法
首先DEFAULTCAPACITY_EMPTY_ELEMENTDATA这个在前面的空构造函数中已经看到过了，如果你调用的是空的构造函数，那么在这里elementData的值明显是和这个值相等的。那么看看DEFAULT_CAPACITY是个啥东西：
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
很明显就是个常数值，很明显，当你调用空的构造函数创建一个ArrayList时，其内部Object数组是一个空值，当你调用add()方法时(add(E e,int index)方法稍有不同)，他会先判断你的ArrayList是否是一个空值，如果是的话，它会给minCapacity赋上10的值然后调用ensureExplicitCapacity()方法，那么来看看那个方法：
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
第一行代码可以先抛开。if里判断minCapacity的值是否大于elementData的长度，那么看一下grow这个方法的代码：
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
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);
}
代码不多，一行一行看过来。第一行拿到内部对象数组的长度，第二行计算出新的容量。计算方式是：旧容量+旧容量/2，也就是每次扩充当前内部对象数组长度的一半。当然了，如果刚开始你的内部对象数组的长度是0的话，那你得出的值也还是0。那么newCapacity-minCapacity的值将会小于0，那么nweCapacity的值将会是10。之后便是调用Arrays.copyOf方法，这个方法最终会调用一个native方法实现将指定的数组拷贝到一个拥有新的尺寸的数组中，那么整个ensureCapacityInternal方法咱就过了一遍了。
在调用无参构造函数的情况下，内部的object数组尺寸是0，在调用了一系列方法之后构造了一个值为10的数组出来，最终将值插入相应的位置。
get()
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
老规矩，一行一行来看首先第一行：
private void rangeCheck(int index) {
if (index < 0 || index >= this.size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
边界检查，小于0或者大于内部数组的长度就报个越界的错误。
之后就是从数组取出这个下标的值。。没啥好说的。。数组取个值。。。
remove()
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their
* indices).
*
* @param index the index of the element to be removed
* @return the element that was removed from the list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
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;
}
第一行仍旧是边界检查。modCount++还是忽视……之后取出对应下标的元素，拿到需要移动的元数量，如果数量大于0，调用arraycopy将内部数组elementData中index之后的元素统统向前移动一个位置。之后将内部数组的最后一个位置置空，方便gc去回收这块内存。在Java中强引用的内存无法被回收，所以需要我们手动的将在逻辑上已删除的元素置空。
