前言：所有数据结构以及源码相关内容基于jdk1.8版本。对常见的数据结构进行解释以及对常见方法进行源码解读。
ArrayList
ArrayList底层数据结构较为简单
// 底层为数组结构 所有数据均存储在elementData数组中
transient Object[] elementData;
底层为数组结构决定了该集合的优缺点：
优点：
有序，有索引。
可以根据索引直接获取对应的元素，同时数组结构根据索引定位元素性能高，因此查询快。
缺点：
数组长度是固定的，导致每次add元素都需判断长度是否满足，如果不满足需要扩容数组，扩容的过程其实效率比较低(后面会通过源码分析扩容过程)。
随机插入或者删除元素会导致数据内容大范围移动，效率低。
这就是常说的ArrayList查询快 增删慢
源码剖析
构造函数剖析
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
首先，通过源码注释可以了解到，当使用无参构造的时候会初始化一个长度为10的空数据，但是实际源码发现刚初始化出来的数组其实长度是0。而真正初始化该数据的位置其实是在add方法中。后面讲到add方法的时候再做详细说明。
有参构造
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 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);
}
}
通过以上源码我们可以发现，当传入一个容量长度的时候，会初始化一个对应长度的数组，如果传入的长度为0则相当于使用了无参构造。如果传入的为负数则会抛出非法参数异常。
add(E e)源码剖析
/**
* 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) {
// 长度动态判断以及扩容的方法，是ArrayList的核心方法
ensureCapacityInternal(size + 1); // Increments modCount!!
// 长度满足之后会直接将传递进来的数据 赋值给size对对应的索引位置。
// 同时让当前集合的size+1 注意集合的长度是size，并不是集合中数组的长度，这里要特别注意
elementData[size++] = e;
return true;
}
以上代码不难看出，ArrayList对数据的存储就是把元素放到数组中。
接下来主要看这个核心扩容的方法代码。
这段代码方法较多，为了方便阅读，直接通过注释来解析。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 最大数组长度
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// 数组默认容量长度
private static final int DEFAULT_CAPACITY = 10;
protected transient int modCount = 0;
// 核心确保数组容量的方法，主要功能有计算当前所需的容量值，以及如果容量不够完成扩容操作。
private void ensureCapacityInternal(int minCapacity) {
// calculateCapacity方法用于计算当前所需容量
// ensureExplicitCapacity方法用于扩容
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 首先结合之前看到的无参构造的例子来讲
// 无参构造初始化的数组其实就是一个{}空数组其实就是DEFAULTCAPACITY_EMPTY_ELEMENTDATA
// 因此这里判断成立。而此时minCapacity = size + 1 默认数组长度为0，因此minCapacity值为1。
// 到此 可以看到 如果使用无参构造，计算容量的方法返回的值为DEFAULT_CAPACITY = 10。
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 此时再看另外一种情况，假设使用有参构造初始化的一个长度为20的数组，
// 上面的判断条件就不满足，就会直接返回传递过来的minCapacity = size + 1 ,
return minCapacity;
}
// 当计算出来当前数组所需的长度之后执行该方法完成数组的扩容操作
private void ensureExplicitCapacity(int minCapacity) {
// modCount该值没有实际的业务含义，只要的作用就是为了防止在使用迭代器遍历的时候对数组做增删操作，会根据该值的变化抛出并发修改异常
modCount++;
// 当计算出来当前数组应有的容量比当前数组现有长度要大的时候来完成数组的扩容操作，否则不进行任何操作。
// 当使用无参构造初始化数组的时候，默认数组长度为0，而计算出来的数组长度为默认的长度10，所以这里就会直接调用grow方法来完成数据的扩容操作
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// 数组的扩容方法
private void grow(int minCapacity) {
// 记录扩容之前数组的长度
int oldCapacity = elementData.length;
// 根据之前数组的长度，计算扩容之后的数组长度。这里用到了位运算，如果对位运算有了解的应该不难看出，这个扩容系数大致就是0.5。
// 假定当前老数组长度为10 10的二进制为 1010 右移一位之后变成0101 换算回来就是5 ， 10+5 = 15.
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 判断当前传递过来数组的最小应有长度和扩容之后的长度，取较大值。
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果当前算出来的扩容长度大于最大数组长度 Integer.MAX_VALUE - 8(一般不会有这么长的数组)，则会使用hugeCapacity方法来限定一个大小。
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 最终调用Arrays工具类的复制方法来完成数组的扩容。这个方法会先初始化一个newCapacity长度的数组，
// 再把elementData中的数据拷贝过去，这里就是比较耗时，耗内存的地方。
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;
}
add(int indec,E e)源码剖析
public void add(int index, E element) {
// 校验传入的index合法性方法，如果传入的索引小于0或者大于当前数组的size则会抛出索引越界异常
rangeCheckForAdd(index);
// 和上面add方法扩容一样。
ensureCapacityInternal(size + 1); // Increments modCount!!
// 调用系统的native方法完成数组的拷贝操作。
// 从elementData数组索引为index的位置开始拷贝，讲数据拷贝到index+1的位置，拷贝的长度为size-index
// 例如当前数组内容为["a","b","c","d","e","","","","",""]，此时调用add(1,"f")方法。
// 则拷贝之后的内容为["a","b","b","c","d","e","","","",""]
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 拷贝完成之后在给对应index位置元素值做一次覆盖，覆盖之后数组的值为 ["a","f","b","c","d","e","","","",""]
// 由此可以看出这种对应索引位置的插入会导致整个数组发生拷贝，大部分数据位置发生移动。
elementData[index] = element;
size++;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
set(int index,E e)源码剖析
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
以上代码就比较简单，就是直接的值覆盖对应索引位置的值，并返回旧值。
remove(int index)源码剖析
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;
}
和上面的代码基本类似，同样使用System.arraycopy来拷贝元素，相当于把要删除的索引位置的元素用后面index+1开始的索引元素整体前移了一位。
remove(E e)源码剖析
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
private void fastRemove(int index) {
modCount++;
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
}
这里的移除和之前的一样都是使用复制的方式来覆盖内容。只不过移除的时候需要整体遍历元素找到需要移除的值对应的索引。
get方法源码
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
get方法的源码非常简单。直接就是去数组对应索引的元素。
到这里ArrayList相关常用的api源码差不多就分析完了。看完源码后应该更能体会ArrayList查询快，增删慢的原因了。
接下来继续来看LinkedList以及Map相关的一些api。
