近日突发奇想，觉得自己是不是可以仔细撸一遍常用的java的基础代码，虽然以前都差不多看过点，但是从来没有认认真真一句一句推敲过其中的含义，从这次开始在工作之余开始尝试多读读一些常用的代码，不定期更新。理想频率是一周一篇，但是至于可以做到哪一步就拭目以待吧。
ArrayList简单介绍
首先应该大致看一下集合的家族谱。(图片是网上找的。。)
这个图片应该很清楚了，我们看一下ArrayList的继承路线。ArrayList ->AbstractList->List->Collection。具体的Collection和List接口的内容都很简单，就是定义一下简单的方法(相当于容器已经做好，就等着具体往里面填入真实的内容)。因为本篇重点关注ArrayList的实现，所以只有在涉及AbstractList的时候我才会去进行一部分解读。
ArrayList具体实现
<strong >类定义</strong>
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
从基本的类定义上我们看到它又实现了另外的RandomAcess,Cloneble和java.io.Serializable接口。
RandomAccess：接口没事实际方法定义，只是为了表明ArrayList支持快速随机访问。此接口的主要目的是允许一般的算法更改其行为，从而在将其应用到随机或连续访问列表时能提供良好的性能。
Cloneable：表示ArrayList是支持克隆(clone)的，但是这些克隆都是浅克隆。如果需要深克隆的话需要自己进一步实现。
Serializable：表明ArrayList是支持序列化的，序列化就是讲对象本身存储为二进制数据保存起来以便于以后再将其形式逆转为Java对象。
<strong>属性值</strong>
/**
* 序列化ID
*/
private static final long serialVersionUID = 8683452581122892189L;
/**
* ArrayList本身使用数组实现的，所以这个属性就是实际数据存放的地方，所有对于ArrayList的操作本质上就是在操作数组，只不过做了一层封装而已。
*/
private transient Object[] elementData;
/**
*内部数组实际大小
*/
private int size;
/**
* 数组长度的最大限制值，如果超出了这个值可能会撑爆堆内存
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
<strong>基本构造函数</strong>
/**
* 初始化一个指定数组长度大小的ArrayList
* 如果初始化长度小于0的话就抛出异常了(数组长度是负数的话不出事才怪）
*/
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
/**
* 默认的初始化长度为10
*/
public ArrayList() {
this(10);
}
/**
* 讲一个Collection的数据放到ArrayList里面进行初始化，泛型参数<? extends E>说明这个Collection原先的元素要是E或者E的子类。
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
//因为c.toArray()可能返回的不是Object[]类型，所以需要进一步判断然后将类型转为Object[]
//这是一个向下转型的官方BUG,在此不会过多介绍
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
<strong>基本方法</strong>
这里我们从常用的方法开始切入，然后一层一层跟踪。
/**
* 核心就是在数组的尾部添加一个元素，然后自动返回true。
* ensureCapacityInternal(size + 1); 保证有这个元素的添加空间，而不会覆盖其他元素。
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
//其中modCount只要用来记载结构的变化次数，这个变量的核心作用就是在使用for循环遍历的时候如果进行数据结构的变化
//的时候就抛出异常。所以我们说在使用for循环遍历的时候结构不能变，实现就在这里。因为增加元素会改变结构，所以需要modCount++
modCount++;
// 如果期待的数组长度最小值已经大于数据数组的长度的话。
// 这里完全可以写成 if(size + 1 > elementData.length)
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* 扩容操作
*/
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
//新数组的长度接近等于原数组长度值*1.5
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//我们知道oldCapacity没有超过MAX_ARRAY_SIZE，但是心newCapaticy完全有可能超过
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) {
//超过int值最大范围的话就会引发内存异常
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
//原则上最大长度为MAX_ARRAY_SIZE，但是强行扩容的话还是可以扩展到Integer.MAX_VALUE（毕竟只差了8）
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
/**
* 在特定位置进行插入操作
*/
public void add(int index, E element) {
//插入位置必须在0-size之间
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1);
//在指定位置插入后将后面的数据整体后移一个位置
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
/**
* 将集合中的全部元素插入到ArrayList中
* addAll(int index, Collection<? extends E> c)的实现主要是判断插入位置是不是在数组末尾然后进行不同的移动元素操作，不在贴码
*/
public boolean addAll(Collection<? extends E> c) {
//注意这里没有进行参数的判空，可能引发NPE
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
public E get(int index) {
//index必须小于数组元素数目(这里我觉得也可以加入小于0的判断)
rangeCheck(index);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
//public E set(int index, E element)没内容可讲
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
//主要是移除的数据是不是位于末尾的数据，但是数组长度不会缩小呦。
if (numMoved > 0)
//index位置后面的数据整体左移一位
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//手动将最后一个元素至为空，减少引用数量，促进垃圾清理
elementData[--size] = null;
return oldValue;
}
/**
* 因为可以在ArrayList中插入null，所以移除的时候当然也可以移除null，但是这里只会移除第一个发现的元素
* fastRemove(int)跟remove(int)差不多，只是少了参数判断而已。
*/
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++)
//这里不会报NPE，因为上面已经排除了参数为null的情况
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
public boolean removeAll(Collection<?> c) {
return batchRemove(c, false);
}
/**
* complement为true：只保留存在于c里面的元素
* complement为false：只保留不存在于c里面的元素
*/
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
//将包含(不包含)在List中的数据存到新数组elementData
elementData[w++] = elementData[r];
} finally {
//这一步应该是匪夷所思的操作了，这是为了防止c.contains()抛出异常而导致数据丢失。
//假如我在i=5的时候抛出异常，但是我i=5之后的数据不会丢失，elementData是整个List的核心构建，所以他的数据能保存尽量保存
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
// 促进GC
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;//这里是批量操作，所以modCount次数变化多点
size = w;
modified = true;
}
}
return modified;
}
关于ArrayList基本的方法我们已经看完了，其实因为内部没有很多关于同步的内容存在，也仅仅只有一个数组作为核心的容器，所以整个实现过程还是非常简单的，下面我们关于一下源码中一些平时不太引人注目的地方。
/**
* 将现有数组的长度缩短到数据的长度，换句话说就是把数组中没有数据的项都去除。
* 这个操作一般使用在ArrayList已经不会变化，而且内存也比较紧张
*/
public void trimToSize() {
modCount++; //因为涉及到结构变化所以这里modCount加一
if (size < elementData.length) {
elementData = Arrays.copyOf(elementData, size);
}
}
/**
* 从这里可以看出这个克隆就是一个浅克隆，所以我们克隆得到的新List其实就是想当于克隆出来一个引用而已，List里面存的数据还是原来的那一份
*/
public Object clone() {
try {
@SuppressWarnings("unchecked")
ArrayList<E> v = (ArrayList<E>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0; //注意初始化modCount
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError();
}
}
/**
* 其实还是把内部数组的引用Clone了一份丢出去而已。注意的是toArray()方法返回的是Object[]类型
*/
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
/**
* 这种有类型的toArray方法平时使用会多一点，整个toArray方法其实就是变相的System.arraycopy而已
*/
public <T> T[] toArray(T[] a) {
if (a.length < size)
// 如果a能装下list中的数据就复制到a里面
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null; //这一步的作用还是促进GC
return a;
}
后序还有Iterator的内容没有写出来，之后找时间补上来。
