ArrayList源码解析
看了一周的SpringMVC请求的过程，突然对老伙计，ArrayList这些我们使用比较多的集合类产生了兴趣，下面开始解析ArrayList源码
ArrayList 继承了AbstractList类
实现的接口有：List, RandomAccess, Cloneable, java.io.Serializable
首先ArrayList有四个静态域
1、serialVersionUID：序列化和反序列需要用到的id
2、DEFAULT_CAPACITY：默认的容量大小
3、EMPTY_ELEMENTDATA：是一个静态的空数组
4、DEFAULTCAPACITY_EMPTY_ELEMENTDATA：作用同EMPTY_ELEMENTDATA 一样。区别是这里表明创建这个类的时候没有指定capacity而是使用默认的DEFAULT_CAPACITY 。
transient Object[] elementData;//临时存放元素的地方，不加入序列化
ArrayList有三种构造函数：
第一种无参构造函数：
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
第二种是设置容量大小的构造函数
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);
}
}
第三种是直接传入一个集合作为参数：
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
前面两种构造方法都比较简单，第三个构造方法有点不一样的地方，首先第一个if语句，将elementData.length赋值给了size,然后进行里层的if语句判断，为什么还要进行类型判断呢，注释中解释道
c.toArray might (incorrectly) not return Object[] (see 6260652)，查过这个代码后，发觉问题源自参数，
如果是ArrayList.toArray()方法，返回的数组就是Object[]类型，但是Arrays.asList(...).toArray,返回的数组呢
Arrays.asList(...)返回的是class java.util.Arrays$ArrayList类型，这种类型的toArray()方法返回的是实际数据的类型，String类型的，那么toArray()方法就会返回String类型，就是因为有这种情况，所以在里层加多了一个判断，将elementData类型转换成Object[]类型。
在看过数据的增加的时候，印象最深的当属对于容量的处理工作，当数组大小超过默认的容器大小后，那么需要执行扩容语句，扩容涉及的部分：
public void ensureCapacity(int minCapacity)
private static int calculateCapacity(Object[] elementData, int minCapacity)
private void ensureCapacityInternal(int minCapacity)
private void ensureExplicitCapacity(int minCapacity)
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
private void grow(int minCapacity)
private static int hugeCapacity
看到这些方法，最直观的是不是ensureCapacity是public，而其他的方法都是private,实际上，ensureCapacity方法在内部源码中是没有调用到的，这个方法是提供给用户进行设置容量大小的。他的代码如下：
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
如果调用该方法的集合是空集，那么就会默认给这个集合内的elementData初始化大小10的容量，否则容量为0，在下边的增加数据的代码块中，都出现了ensureCpacityInternal()方法的调用，最终完成扩容工作的是ensureExplicitCapacity()方法。
扩容数组：
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
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);
}
这个方法的思路就是，先将原来的容量增加原来容量的一般，然后跟传入的容量进行比较，如果小于传入的容量，那么就将传入的容量赋值给扩容的容量，然后进行第二次判断，判断扩容的容量是否会大于数组的最大容量，如果大于数组最大的容量，那么将会有两个选择，如果传入的容量大小大于数组最大容量，则将扩容的容量赋值为整型的最大值，如果传入的容量大小小于数组最大容量，则将扩容的容量赋值为数组最大的容量。
增删
1、增加
public boolean add(E e)
public void add(int index, E element)
public boolean addAll(Collection<? extends E> c)
public boolean addAll(int index, Collection<? extends E> c)
增加的方法四种，刚刚说过，四种都调用了扩容判定的方法
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
public boolean addAll(Collection<? extends E> c) {
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 boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
这里我要讲的是System.arraycopy()的调用，该方法的参数顺序为：拷贝数组，开始位置，拷入数组，开始位置，长度。这也是我遇到的第一个native方法，在底层源码中看不到native的实现，拷贝的时候要注意拷贝的长度计算，跟删除略有不同。
2、删除
public E remove(int index)
public boolean remove(Object o)
private void fastRemove(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;
}
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
}
删除中，可以看到在长度上，增加是length = size -index ,而删除是length = size -index -1
这个方面自己算个例子就很容易明白了，这边要注意的是，删除一个object的时候，要判断变量是否为空，为空直接使用==null的方式，不为空要使用equals()方法进行判断，还有一个点是，删除完数据后，要记得将位置置为null，让java的gc机制回收不用的内存空间
讲完ArrayList对于增删的处理后，下边讲下这两个方法
1、public boolean removeAll(Collection<?> c)
2、public boolean retainAll(Collection<?> c)
第一个方法的代码为：
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
第二个方法的代码为：
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
可以看到，首先这两个方法先判断传入的集合进行了非空检测，检测完后返回的是batchRemove()方法的返回值，不同的是第二个参数设置一个为true，一个为false。
为了更容易理解，我先在这边介绍一下这两个方法的功能
第一个方法是移除list集合中有关集合c的元素
第二个方法是移除list集合中除集合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)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
首先创建了一个数组用来接收临时数组，然后分别创建了两个整型，一个是r，一个是w，整型r的作用类似于for循环第一个参数new出来的变量，用于遍历整个数组，整型w的作用是计算经过操作后，筛选出来的元素的个数，还有个布尔类型modified，默认为false，判断方法执行是否成功的元素。
所以r一般是大于w的，我们看到在finally代码块里有两个if语句，第一个判断语句r!=size，遍历整个数组的情况下，r是等于size的，只有出现异常，无法再继续执行下去的时候r!=size,将r后边为处理的数据加到w的后边。第二个判断语句w!=size,如果w等于size，说明筛选出来的元素是整个数组，那么就没有需要剔除的元素，也就是没有修改集合，返回默认的false,如果w!=size,则将List数组的w之后包括w全部置为null，让GC回收。
代码接着往下走，我们发现到了序列化和反序列化的方法，ArrayList都已经实现了Serializable接口，为何还要自己写序列化和反序列化方法呢，看代码：
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// Read in size, and any hidden stuff
s.defaultReadObject();
// Read in capacity
s.readInt(); // ignored
if (size > 0) {
// be like clone(), allocate array based upon size not capacity
int capacity = calculateCapacity(elementData, size);
SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
ensureCapacityInternal(size);
Object[] a = elementData;
// Read in all elements in the proper order.
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}
发现了什么，序列化和反序列化中的循环变量是以size为准的，在ArrayList中，有两个变量容易弄混，一个是size,一个是elementData.length，第一个是数组中实际拥有元素的个数，第二个是数组的长度，数组长度是大于等于数组拥有元素个数的，所以如果自己写序列化和反序列化语句，那么可以节省这部分的内存开销。
再之后的代码就是关于迭代器方面的，这部分我还没研究，暂时不讲。纵观ArrayList源码，通篇有两个要特别注意的点，就是Arrays.copyOf()和System.arraycopy()
copyOf()的作用是拿来扩容用的
arraycopy()的作用是进行数组内元素移位用的
这是二者最大区别，并且这两个方法也不是一个类的方法
copyOf()是Arrays的方法，arraycopy()是System的方法
说到这里，就有必要说一下ArrayList的toArray()方法，看代码：
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
这个是不带参数的toArray(),内部是通过Arrays.copyOf来实现的，比较简单
public <T> T[] toArray(T[] a) {
if (a.length < size)
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
而这个带有数组类型参数的toArray()，就相对复杂点，但是对比两个方法，可以看出来无参的toArray()方法是使用Arrays.copyOf(),有参的toArray()方法是通过System.arraycopy()和Arrays.copyOf()进行实现的，我解释一下有参的方法实现。首先List.toArray(T)，，这个方法是将list的数据拷贝到T中，并且返回的也是T的类型，先判断T和List的长度，如果拷入数组T的长度小于拷贝数组List的长度，则调用Arrays.copyOf()方法，直接将拷贝数组进行类型转换，如果拷入数组T的长度大于拷贝数组List的长度，则调用System.arraycopy()将拷入数组T的0~List.length范围数据置为List,然后list.length的位置置为null,这样其实可以达到区分拷贝前后数据的作用，测试代码如下：
public void testGoods() {
ArrayList<String> list = new ArrayList<>(Arrays.asList("s","t","r"));
String[] str = {"q","w","r","c","z"};
str = list.toArray(str);
for (String s :str)
System.out.println(s);
}
效果图：
QQ图片20180910223854.png
如果我将str的数据删除到只剩下一个数据，效果图如下：
image.png
这两种情况通过代码就很直观的显示出来了。
总结
1、如果在声明ArrayList的时候不设初始值，那么ArrayList会默认设置一个容量为10的数组，但是ArrayList的大小还是为0的
2、ArrayList可以看成是一个动态的数组，相比较与数组来说，ArrayList可以用ensureCapacityInternal方法自动扩容，在向ArrayList添加元素的时候，ArrayList会先检测现在数组的容量是否足够，若不够，ArrayList会将数组的容量扩大为原来的1.5倍，如果还不够，就用传进来的参数作为数组的容量。如果我们在知道存储元素多少的时候，尽量给ArrayList设定一个初始容量，这样就可以减少ArrayList的自动扩容，减少数组元素的移动来提高程序的性能。
3、ArrayList在增加或删除元素的时候，都需要将数组里面的元素移动到另一个数组中，这是非常耗时间的，所以遇到需要对元素进行频繁的删除和添加的集合时，这时候选用LinkedList要比ArrayList好很多，如果遇到在集合中查找元素比较多的操作时，ArrayList又是一个不错的选择，因为ArrayList直接可以用下标就可以获取到元素。
4、在读ArrayList源码的时候要注意ensureCapacityInternal扩容方法和System.arraycopy(original, 0, copy, 0,length)方法。
问题解析：
来讲一下ArrayList中遇到的一个问题，就是关于addAll(int index,Collection<? extends E> e)方法
该方法第一行代码就是对index进行的判断
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
可以看到第一个方法对于index的判断，index大于size或者小于0则抛出异常，也就是说size>=index>=0
我当时的疑问出于size怎么可以等于index,因为index是数组的下标，肯定比个数少一，然后在大佬的指点下，发觉，如果我的index==size,那么就是在数组尾插入集合C，这样是符合标准的，但是index==size，那么原数组就不需要移动了，如果没有加上长度的判定，那么会出现BUG，怪自己粗心。
参考链接：
https://blog.csdn.net/wangbiao007/article/details/52474756
http://www.cnblogs.com/ITtangtang/p/3948555.html#toArray
https://blog.csdn.net/weixin_39148512/article/details/79234817
https://blog.csdn.net/u011518120/article/details/52026076
https://www.cnblogs.com/gxl1995/p/7534171344218b3784f1beb90d621337.html
