ArrayList数组主要方法纯源码分析：
- 1.add(E e)方法和newCapacity()方法:
-
- 1.1.add(E e)方法：
- 1.2.扩容方法newCapacity(int minCapacity) ：
- 1.2.1.首先是扩容时机：
- 1.2.2.扩容函数：
- 1.2.3.扩容函数的执行顺序：
- 1.2.4.void add(int index, E element)方法:
- 2.构造方法：
-
- 2.1.有参构造方法1：
- 2.2.无参构造方法：
- 2.3.有参构造方法2：
- 3.Get()方法：
- 4.remove()方法：
-
- 4.1.remove(int index)方法：
- 4.2.remove(Object o)方法：
- 4.3.removeRange(int fromIndex, int toIndex)方法：
- 4.4.removeAll(Collection<?> c)方法：
- 5.set(int index, E element)方法：
- 6.Clear()方法：
ArrayList数组主要方法纯源码分析：
)
1.add(E e)方法和newCapacity()方法:
1.1.add(E e)方法：
一.由于第一次添加时扩容的特殊性，所以先以第一次添加元素观察第一种add()方法（
add(E e)
）和扩容函数以及复制函数，可谓一箭三雕。需要注意的是：size代表现在数组中元素个数,minCapacity代表当插入数据后数组元素个数。
断点Debug强制进入函数进入，
进入add()方法，s就是size，
创建对象时未传参，默认长度大小为0，进入grow()方法，返回值为新数组，
minCapacity变为1（代表当插入数据后数组元素个数），再进入另一个grow()方法，返回值为新数组,
进入Arrays.copyof()方法，该方法返回值为新数组,
进入newCapacity()方法，返回新数组长度（扩容后）
新数组长度=旧数组长度+扩容长度（算法）
判断扩容后的数组长度是否大于添加元素后总元素个数，但值得注意的是：第一次扩容经过扩容算法后新数组长度依旧为0，这是个特例，故第一次扩容后新数组长度为10,
执行完newCapacity()方法后递归回Arrays.copyof()方法，该方法的操作：旧数组长度计算新数组长度（newCapacity()方法）和复制旧数组数据到新数组，所以要传旧数组。返回值为新数组（包含原来数据）。
下图为进入Arrays.copyof()的第一个copyof()方法，第一个copyof()方法有newLenght，说明先执行了newCapacity()方法，由第一个进入第二个copyof()方法，该方法利用原数组和newCapacity()得到的新数组长度得到新数组（包含原来数据，不包含新数据）。
第一次扩容新数组长度为10的来源：
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private static final int DEFAULT_CAPACITY = 10;
下面都是递归返回了，
这里特别注意：grow()方法后得到一个新数组（包含原数组数据），然后再添加新数据到新数组中，新数组现有总元素个数加1，
1.2.扩容方法newCapacity(int minCapacity) ：
二.大家其实不难发现，此次add值数组进行了扩容，那么大家就会纠结到底什么时候数组会进行扩容，如何扩容？这就关系到一下几行代码：
1.2.1.首先是扩容时机：
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}
每次进入add()方法里面都会有一个当前数组元素个数和当前数组长度的比较（也就是说在即将添加元素之前看看数组是不是已经满了），如果为真，就进入grow()方法进行扩容，这就是扩容时机：
if (s == elementData.length)
elementData = grow();
1.2.2.扩容函数：
/**
* Returns a capacity at least as large as the given minimum capacity.
* Returns the current capacity increased by 50% if that suffices.
* Will not return a capacity greater than MAX_ARRAY_SIZE unless
* the given minimum capacity is greater than MAX_ARRAY_SIZE.
*
* @param minCapacity the desired minimum capacity
* @throws OutOfMemoryError if minCapacity is less than zero
*/
private int newCapacity(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity <= 0) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
return Math.max(DEFAULT_CAPACITY, minCapacity);
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return minCapacity;
}
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? newCapacity
: hugeCapacity(minCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE)
? Integer.MAX_VALUE
: MAX_ARRAY_SIZE;
}
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
很明显扩容后新数组总长度=旧数组长度+扩容量
对于oldCapacity >> 1 可能会有小白不明白：
首先，<<为左移，>>为右移（简单记法：箭头向左为左移，箭头向右为右移），对于右移，例如01110010，可以把01110010看成计算机网络里发送窗口里的的字节，每位代表一个字节，只是这里有些特别：只能显示窗口中的数字，并且窗口左右两边的都是0。当右移1位时，相当于把这串二进制往右挪1位，最右边的0在窗口外了，同时窗口左边的外部的0进入到窗口，即01110010>>1结果为00111001，同理01110010>>2的结果为00011100,01110010>>3的结果为00001110…….就是这样的规律，左移规律一样，读者可以自行尝试。
同时：右移1位整体数值就变为原来的1/2（也就是原数值除以2^1）。
也就是说右移N为，整体数值就除以2^N。
1.2.3.扩容函数的执行顺序：
- 先按照扩容算法扩容。
- 判断扩容后新数组长度是否满足添加元素后数组长度要求。根据扩容时机
if (s == elementData.length) elementData = grow();
if (newCapacity - minCapacity <= 0)
if (newCapacity - minCapacity <= 0)
- 判断即将添加数据后数组总长度是否大于
MAX_ARRAY_SIZE
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
@Native public static final int MAX_VALUE = 0x7fffffff;
-
举个扩容例子：
通过扩容函数不难看出，第一次扩容为10（当然，这是相对于当初创建ArrayList对象时执行无参构造方法的默认数组长度），即执行
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
后newCapacity为0，
然后执行到
if (newCapacity - minCapacity <= 0)
符合条件进入，
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
return Math.max(DEFAULT_CAPACITY, minCapacity);
返回10。
第二次扩容：执行
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
后，
即
int newCapacity = oldCapacity + (oldCapacity >> 1);
翻译为 15=10+10/2，
第三次扩容：22.5=15+7.5，
第四次扩容：33.75=22.5+111.25……
不难发现从第二次扩容开始，每次扩容都是上一次的1.5倍（包括第二次扩容）。
1.2.4.void add(int index, E element)方法:
将元素插入到数组相应index位置。这个跟第一个add()方法有几点不同：
1.增加了index合法检查的函数。进入
rangeCheckForAdd(index);
/**
* A version of rangeCheck used by add and addAll.
*/
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
2.当需要扩容时有一次建立新数组，一次对新数组index后的元素移动操作：
先扩容：
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();
跟第一个add()一样，就是根据扩容算法算出新数组长度，根据新数组长度建立新数组，将原来数组中的数据复制上去，返回新数组（不需要扩容时直接跳过这一步到下面的移动数组）。
再移位，不用猜也肯定知道，既然要指定数组index插入数据，必然要将index后的元素向后移动，但这里注意的是，它这次的操作的源数组和目标数组都是同一个数组，都是扩容后的新数组。
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);
解析一下：将新数组的index位置开始的元素复制到的index+1的位置上，s-index，就是index开始后面的所有元素，也就是说将index后的元素整体向后挪一个位置。
最后留下指定index的空位，插入指定元素。
2.构造方法：
2.1.有参构造方法1：
/**
* 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);
}
}
对于函数里面几个关键的数组定义需要理解一下：
NO.1
/**
* 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 = {};
NO.2
/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
NO.3
/**
* 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
所以说当
initialCapacity == 0
时（也就是指定容量为0时），使用
private static final Object[] EMPTY_ELEMENTDATA = {};
将空数组
EMPTY_ELEMENTDATA
赋给存储数据的数组。
2.2.无参构造方法：
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
由有参构造方法中的N0.1可知，使用
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
将空数组
DEFAULTCAPACITY_EMPTY_ELEMENTDATA
赋给存储数据的数组
elementData
。
2.3.有参构造方法2：
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// defend against c.toArray (incorrectly) not returning Object[]
// (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
1.
ArrayList(Collection<? extends E> c)：
构造一个包含指定 collection 的元素的列表，这些元素是按照该 collection 的迭代器返回它们的顺序排列的。该有参构造方法构造时赋的值是它的父类对象Collection（可以理解为父类引用指向子类对象）。
2.将collection对象转换成数组，然后将数组的地址的赋给elementData。
3.如果数组的实际大小等于0（c中没有元素），根据上面的NO.2将空数组
EMPTY_ELEMENTDATA
赋值给
elementData
（因为它毕竟也是有参构造函数，不是默认的）
4.如果size的值大于0（说明collection中有值），则执行
Arrays.copy()
方法，把collection对象的内容（可以理解为深拷贝）copy到elementData中。
3.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) {
Objects.checkIndex(index, size);
return elementData(index);
}
分析：
Objects.checkIndex(index, size);
检查index的合法性，具体检查规则：
if (index < 0 || index >= length)
throw outOfBoundsCheckIndex(oobef, index, length);
4.remove()方法：
4.1.remove(int index)方法：
/**
* 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) {
Objects.checkIndex(index, size);
final Object[] es = elementData;
@SuppressWarnings("unchecked") E oldValue = (E) es[index];
fastRemove(es, index);
return oldValue;
}
/**
* Private remove method that skips bounds checking and does not
* return the value removed.
*/
private void fastRemove(Object[] es, int i) {
modCount++;
final int newSize;
if ((newSize = size - 1) > i)
System.arraycopy(es, i + 1, es, i, newSize - i);
es[size = newSize] = null;
}
分析：跟get()方法一样，都有检查index的合法性。关键是
fastRemove(es, index);
方法。该方法里的
if ((newSize = size - 1) > i)
System.arraycopy(es, i + 1, es, i, newSize - i);
es[size = newSize] = null;
的理解：首先明白要么是扩容（复制原数组内容到新数组）要么是对同一个数组进行元素移动，两者区别在于
System.arraycopy(es, i + 1, es, i, newSize - i);
的源数组和目标数组是否相同。显而易见，这明显是对同一个数组进行元素移动（根据数组删除非末尾元素后该元素后面的元素都要向前移动也能判断）。既然说是删除非末尾元素元素才进行移动，那么删除末尾元素就不用移动了，也就是说
if ((newSize = size - 1) > i)
判断待删除元素的index是否是末尾元素，如果是就不用执行
System.arraycopy(es, i + 1, es, i, newSize - i);
，直接执行
es[size = newSize] = null;
将待删除index中元素的值赋为null；
4.2.remove(Object o)方法：
/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If the list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
* {@code i} such that
* {@code Objects.equals(o, get(i))}
* (if such an element exists). Returns {@code true} if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
* @return {@code true} if this list contained the specified element
*/
public boolean remove(Object o) {
final Object[] es = elementData;
final int size = this.size;
int i = 0;
found: {
if (o == null) { //对象的指向为空
for (; i < size; i++)
if (es[i] == null)//遍历找出这样的对象
break found;//找到跳出循环执行fastRemove(es, i);删除
} else {//对象的指向不为空
for (; i < size; i++)
if (o.equals(es[i]))//遍历找出对象内容跟传入对象内容一样的
break found; //找到跳出循环执行fastRemove(es, i); ;删除
}
return false;
}
fastRemove(es, i);
return true;
}
/**
* Removes from this list all of the elements whose index is between
* {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
* Shifts any succeeding elements to the left (reduces their index).
* This call shortens the list by {@code (toIndex - fromIndex)} elements.
* (If {@code toIndex==fromIndex}, this operation has no effect.)
*
* @throws IndexOutOfBoundsException if {@code fromIndex} or
* {@code toIndex} is out of range
* ({@code fromIndex < 0 ||
* toIndex > size() ||
* toIndex < fromIndex})
*/
4.3.removeRange(int fromIndex, int toIndex)方法：
protected void removeRange(int fromIndex, int toIndex) {
if (fromIndex > toIndex) {
throw new IndexOutOfBoundsException(
outOfBoundsMsg(fromIndex, toIndex));
}
modCount++;
shiftTailOverGap(elementData, fromIndex, toIndex);
}
/** Erases the gap from lo to hi, by sliding down following elements. */
private void shiftTailOverGap(Object[] es, int lo, int hi) {
System.arraycopy(es, hi, es, lo, size - hi);
for (int to = size, i = (size -= hi - lo); i < to; i++)
es[i] = null;
}
分析：此方法删除lo到hi之间的全部元素，
System.arraycopy(es, hi, es, lo, size - hi);
将源数组的hi后面的元素移动到目标数组以lo开始的index。根据
for (int to = size, i = (size -= hi - lo); i < to; i++)
es[i] = null;
}
可知复制后原来存在的且没有被覆盖的数据数据并没有消失，要置为null。
4.4.removeAll(Collection<?> c)方法：
/**
* Removes from this list all of its elements that are contained in the
* specified collection.
*
* @param c collection containing elements to be removed from this list
* @return {@code true} if this list changed as a result of the call
* @throws ClassCastException if the class of an element of this list
* is incompatible with the specified collection
* (<a href="Collection.html#optional-restrictions" target="_blank" rel="external nofollow" target="_blank" rel="external nofollow" >optional</a>)
* @throws NullPointerException if this list contains a null element and the
* specified collection does not permit null elements
* (<a href="Collection.html#optional-restrictions" target="_blank" rel="external nofollow" target="_blank" rel="external nofollow" >optional</a>),
* or if the specified collection is null
* @see Collection#contains(Object)
*/
public boolean removeAll(Collection<?> c) {
return batchRemove(c, false, 0, size);
}
boolean batchRemove(Collection<?> c, boolean complement,
final int from, final int end) {
Objects.requireNonNull(c);
final Object[] es = elementData;
int r;
// Optimize for initial run of survivors
for (r = from;; r++) {
if (r == end)
return false;
if (c.contains(es[r]) != complement)
break;
}
int w = r++;
try {
for (Object e; r < end; r++)
if (c.contains(e = es[r]) == complement)
es[w++] = e;
} catch (Throwable ex) {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
System.arraycopy(es, r, es, w, end - r);
w += end - r;
throw ex;
} finally {
modCount += end - w;
shiftTailOverGap(es, w, end);
}
return true;
}
上面这个版本比较难看，下面的比较容易看：
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.
//官方的注释是为了保持和AbstractCollection的兼容性
//我的理解是上面c.contains抛出了异常，导致for循环终止，那么必然会导致r != size
//所以0-w之间是需要保留的数据，同时从w索引开始将剩下没有循环的数据(也就是从r开始的)拷贝回来，也保留
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
//for循环完毕，检测了所有的元素
//0-w之间保存了需要留下的数据，w开始以及后面的数据全部清空
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;
}
核心思想都在下面这个代码里：
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
简单说一下这部分代码的思想：
初始值：w和r都是0，complement==false
规律：
1.r值不断自增，w并不是每轮都增加。
2.每次覆盖的时候elementData[w]必定集合c包含的值。
3.由于跳出循环后w=w+1，此刻最后一次elementData[w]不是集合c包含的值。
4.跳出循环后w所指index后的所有原数组的元素都已经有序前移了。因此有了后面这段代码。
核心思想：每轮都找不属于集合c的elementData[r] 去覆盖 elementData[w]，原因：w迟早h会走到集合c包含的元素的位置，并且w每走一个位置都会停下，直到找到一个不属于集合c的elementData[r]去覆盖 elementData[w]（也就是说w所经过的位置的值都会用一个不属于集合c的elementData[r]去覆盖）。
for (int i = w; i < size; i++)
elementData[i] = null;
将w后面的所有元素的值赋为null。
思想参考：核心思想领悟自
5.set(int index, E element)方法：
/**
* Replaces the element at the specified position in this list with
* the specified element.
*
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
Objects.checkIndex(index, size);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
分析：这是更新相应index位置的元素。
6.Clear()方法：
/**
* Removes all of the elements from this list. The list will
* be empty after this call returns.
*/
public void clear() {
modCount++;
final Object[] es = elementData;
for (int to = size, i = size = 0; i < to; i++)
es[i] = null;
}
分析：清空数组。