Java源码学习--ArrayList
好久没有看Java了，最近在学习上出现了一些迷茫，之前是打算在课余时间学习一下代码，但是懈怠了很长一段时间，作为一个考研狗，也没有太多的时间去学习代码。就在闲暇之余看看源代码、记记笔记什么的，即让自己心安（没有打游戏），又可以有所收获，重要的是随时随性没有复习时的那种负担。
Java的ArrayList从初学开始到现在，使我们代码中的常客了，而其源代码也是相当简单，有一定的Java基础就可以无障碍阅读。之前看过，但是没有去系统的记录和整理，今日温故希望可以知新。
一、重要属性
ArrayList的属性不多，但好像都很重要的(可能是复习的紧张感，让我感觉就像考试一样，都会考到)：
类成员
- serialVersionUID：该属性是final和private修饰的long，该属性和序列化有关，用来在反序列化的时候标志是否为同一个版本，相关内容在序列化中，在这里不是很重要
- DEFAULT_CAPACITY：该属性是final和private修饰的int，且默认值是10，代表默认情况下的ArrayList的size的值
- EMPTY_ELEMENTDATA：该属性是final和private修饰的Object[]，且默认是{},当在调用ArrayList的构造器的时候如果设置的容量为0的话，会使用（elementData成员初始化为EMPTY_ELEMENTDATA）这个空数组(capcity为零的情况有两种：1. 构造器的initialCapacity手动设置为零 2. 构造器的Collection参数的size为零*)
- DEFAULTCAPACITY_EMPTY_ELEMENTDATA：该属性是final和private修饰的Object[]，且默认是{}。和EMPTY_ELEMENTDATA的区别是，该属性在调用无参构造器的时候使用（elementData成员初始化为EMPTY_ELEMENTDATA），也就是没有指定初始容量的时候使用
- MAX_ARRAY_SIZE：该属性是final和private修饰的int，且默认值是Integer.MAX_VALUE - 8。代表ArrayList最大能够容纳的元素的个数
普通成员
- elementData：该属性是使用transient修饰的Object[]。是用来存放ArrayList中数据的具体数组，其根据构造函数传递参数的情况来进行初始化
- size：该属性是使用private修饰的int。用来表示ArrayList中元素的个数，也就是size()方法返回的值
- modCount：该属性是使用protected和transient修饰的int。该属性来自于父类：AbstractList用来表示ArrayList对象的结构被修改的次数
二、重要方法调用详情
1. add(E e)
该方法算是最常用的方法了，都知道往里面添加元素的时候如果满了的话，ArrayList会进行扩容操作：
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
第二行代码将维护size和添加元素一步到位，扩容就发生在ensureCapacityInternal方法，值得注意的是这里传递的参数是size+1,也即当前元素的个数加一。
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
可见，当我们通过无参构造器实例化一个ArrayList对象的时候，此时elementData是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，这个时候调用add方法内部进行扩容时，用的是DEFAULT_CAPACITY(10)；其他情况扩容使用的minCapacity为ArrayList的size+1;真正进行扩容的地方是grow(int minCapacity)。
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);
}
扩容的实现是Arrays.copyof方法；newCapacity值的确认是首先进行max(1.5倍的elementData数组的长度, minCapacity)，结果通常为1.5倍的数组长度[当无参构造器实例化ArrayList首次add时结果为DEFAULT_CAPACITY(10)]；之后便判断此时的1.5倍的数组长度有没有超过MAX_ARRAY_SIZE；如果超过了就会根据minCapacity(一般为size+1)的大小进行判断：
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE；
至此，ArrayList的add方法就这样介绍完了。
小结：需要注意的一点是，扩容发生的时机是当size()的值等于elementData的length的时候就会发生扩容，之后，elementData的length会变为原来的1.5倍
add(int index, E element)
该方法用来在特定的位置添加元素：
public void add(int index, E element) {
rangeCheckForAdd(index); // 该方法只是用来检查index是否满足大于等于0且小于等于size
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
可见该方法和add(E element)方法相比，只是多了两部：1. 检查index是否合法 2. 将index后面的元素向后平移一个元素的位置(System.arraycopy)
addAll(Collection c)
该方法用来批量添加元素：
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;
}
批量添加的代码是System.arraycopy。
addAll(int index, Collection c)
该方法是往特定的位置插入批量的数据：
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;
}
add系列方法小结：1. add单个添加在一般情况下都是elementData数组元素的添加，几乎不耗时；而单个指定位置添加时多了index之后元素的移动操作System.arraycopy，这时候如果移动的数据量大的话，会有一定的耗时； 2. 批量添加与单个添加相比，耗时在于比前者多执行了个System.arraycopy，而且这种情况下一不小心就会到达elementData的length，从而导致grow的时候又执行了Arrays.copy从而更加耗时；而带指定位置的批量添加元素有与普通的批量添加元素多了一个移动后面元素的操作System.arraycopy。
2. remove(int index)
看过上面的方法之后ArrayList后面的方法就很简单了，先看看remove(index)方法的实现：
public E remove(int index) {
rangeCheck(index); // 该方法只是用来检查index是否满足小于等于size
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;
}
可以看到remove的方法实现非常简单：将index后面的元素向前移动一个位置，最后将最后一个元素设为null
问题：这里的rangeCheck(index)为啥不去判断index小于0的情况，只保证了index小于等于size？
remove(Object o)
该方法通过对象来移除元素：
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
}
可见该方法的实现是通过for循环遍历ArrayList中是所有元素，直到找到目标元素，之后的动作就和根据索引删除是一样的了；如果想要通过这种方法移除一个元素该类必须重写equals方法；可见该方法与根据索引移除的另一个大的区别就是该方法有一个for循环操作，所以稍微要耗时一些。
removeAll(Collection<?> c)
该方法用来对ArrayList进行批量的移除操作，平时用的比较少：
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
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;
}
重点在batchRemove方法，值得注意的是在removeAll中调用的时候第二个参数为false，所以这里的for循环的作用是将ArrayList中不在参数一c中的元素保留到elementData中；之后就将w至size区间的元素都赋值为null即可，如果在过虑元素的过程中发生了异常，finally中的第一个if语句会保证从发生异常位置之前的删除是有效的。
值得注意的是：该方法会很耗时，因为for循环对每一个参数一中的元素都会执行contain判断是否含有，而这个方法在ArrayList中也是通过for遍历所有元素实现的，所以在这里会被执行size次，是非常耗时的，慎用。
retainAll(Collection c)
该方法和remove是正好相反的，其是保留ArrayList中存在于c中的元素：
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
和removeAll相比，只是在调用batchRemove时第二个参数传为了true。
3. set和get
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
看过add和remove的方法之后，你会觉得这两个方法索然无味...这里也不过多赘述了...
4. 其他方法
ArrayList中还有很多不常用的方法，其的代码实现都很简单：
public boolean isEmpty() {
return size == 0;
}
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
// 该方法就是一个for循环遍历集合中的所有元素
// 以后想找某一个对象的位置，直接用这个就行
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
// 从后往前遍历集合中的元素
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
其contains方法还是通过遍历所有元素来查找的，所以时间复杂度还有有一定的。
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int expectedModCount = modCount;
@SuppressWarnings("unchecked")
final E[] elementData = (E[]) this.elementData;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
action.accept(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
ArrayList继承自父类的方法，其本质还是for循环每一个元素都传递个action执行一次。
二、迭代器实现
在使用ArrayList的时候经常会使用到for、forEach、迭代器等来进行遍历，一直不是很习惯使用迭代器来进行遍历，正好来看看迭代器的实现原理。
在ArrayList中又两种迭代器的实现：Itr和ListItr(继承了Itr)
1. Itr
Itr的属性有三个：
- cursor：是一个int值，代表当前所在的位置，其范围是[0, size - 1]
- lastRet：是一个int值，默认为-1，代表最后一次调用next方法返回的数据的位置
- expectedModCount：为一个int值，初始化时赋值为了ArrayList的modCount
重要方法：
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
// 可见lastRest即为上一次调用next方法返回的位置
return (E) elementData[lastRet = i];
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
// 迭代器的remove方法之后，lastRet会重置，因此，不可以连续执行remove方法，期间至少要执行一次next()方法
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
迭代器的常用方法就只涉及这三个方法：需要我们重点关注的是next和remove都调用了checkForComodification()这个方法：
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
所以，在使用ArrayList的iterator方法活动的Itr对象进行遍历操作的时候需要注意1. 不能使用ArrayList对象来进行add、remove等操作(如果你细心观察了的话，会发现他们两个都会执行到modCount++从而导致Itr在执行checkForComodification方法抛出异常) 2. 可以使用Itr的remove删除最后一个next返回的数据，因为其维护了expectedModCount 3. 通常情况下cursor比lastRet大1，在执行过remove方法后，cursor的值变为了lastRet，lastRet变为了-1(这并不影响什么，因为lastRet只在remove中用到了，而且在next方法中cursor又会比lastRet大1) 4. 同时不能够连续执行remove()方法，期间至少执行一次next()方法
注意：使用Itr的时候调用ArrayList的get和set方法没有问题，因为这两个方法并不会使得modCount发生改变
通过ArrayList的iterator()方法得到的Itr对象有很大的限制：只提供了remove方法其限定了删除的数据，为此，ArrayList中的ListIterator方法返回的ListItr就为我们解放了很多。
2. ListItr
该类继承了Itr，并为我们提供了set、add、previous三个方法。
public E previous() {
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[lastRet = i];
}
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void add(E e) {
checkForComodification();
try {
int i = cursor;
ArrayList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
可见set、add方法都自行维护了expectedModCount的值，从而避免了Itr的缺点。
3. ArrayList各种遍历方式对比
for (int i = 0; i < list.size(); i ++) {
System.out.println(list.get(i));
}
for (String cont : list) {
System.out.println(cont);
}
Iterator ite = list.iterator();
while(ite.hasNext()) {
System.out.println(ite.next());
}
list.forEach((i) -> {
System.out.println(i);
});
从本质上来讲，这四种方法都是由一个for循环实现的，但是我认为第一种手动for循环反而是最简单的，因为它很单纯(因为list的get方法很简单没有各种检查)，而其他的方法需要各种检查校验工作。
三、SubList
不看不知道，原来subList方法返回的是一个SubList，并不是ArrayList：
private class SubList extends AbstractList<E> implements RandomAccess {
private final AbstractList<E> parent;
private final int parentOffset;
private final int offset;
int size;
SubList(AbstractList<E> parent,
int offset, int fromIndex, int toIndex) {
this.parent = parent;
this.parentOffset = fromIndex;
this.offset = offset + fromIndex;
this.size = toIndex - fromIndex;
this.modCount = ArrayList.this.modCount;
}
public E set(int index, E e) {
rangeCheck(index);
checkForComodification();
E oldValue = ArrayList.this.elementData(offset + index);
ArrayList.this.elementData[offset + index] = e;
return oldValue;
}
public E get(int index) {
rangeCheck(index);
checkForComodification();
return ArrayList.this.elementData(offset + index);
}
public int size() {
checkForComodification();
return this.size;
}
public void add(int index, E e) {
rangeCheckForAdd(index);
checkForComodification();
parent.add(parentOffset + index, e);
this.modCount = parent.modCount;
this.size++;
}
public E remove(int index) {
rangeCheck(index);
checkForComodification();
E result = parent.remove(parentOffset + index);
this.modCount = parent.modCount;
this.size--;
return result;
}
protected void removeRange(int fromIndex, int toIndex) {
checkForComodification();
parent.removeRange(parentOffset + fromIndex,
parentOffset + toIndex);
this.modCount = parent.modCount;
this.size -= toIndex - fromIndex;
}
public boolean addAll(Collection<? extends E> c) {
return addAll(this.size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
int cSize = c.size();
if (cSize==0)
return false;
checkForComodification();
parent.addAll(parentOffset + index, c);
this.modCount = parent.modCount;
this.size += cSize;
return true;
}
。。。。
}
需要注意的只是一点：SubList可以看做是ArrayList中区间上元素的映射(类似于数据库中的View)对其任何操作都会反映到ArrayList本身上来
五、总结
ArrayList的源码分析到此就已经结束了，我们可以得到如下认识：
- ArrayList是线程不安全的，其没有对于多线程进行任何处理
- forEach、iterator()方式、listIterator()方式、forEach(Comsour)方式进行遍历本质都是一个for循环，所以对ArrayList进行遍历时不如直接手动for循环，反而更加纯粹
- 通过迭代器进行遍历期间不能对操控ArrayList对象执行add、remove操作
- 其subList方法生成的集合是ArrayList区间的映射，所有操作都会相互影响
看完ArrayList的源代码，确实很简单，我想如果让任何一个人来写，都会是这个样子吧，因为ArrayList本就是很简单的一个工具类；但是其代码的严谨性还是值得学习的，可以看到在参数中执行了index的时候，你都会在方法体中看到各种rangeCheck方法的调用，的确首先要保证index的合法性才能够进行后续的操作，但就是这么一个小地方，我们在面试或者自己写代码的时候还是很容易忽略的--细节决定成败！！
