【抽丝剥茧】解析ArrayList源码

---

一、什么是ArrayList？

• 基于数组的实现，是一个“动态数组”
  我们知道数组的容量是固定的，不可改变，创建时指定容量大小。而ArrayList是会随着存入数据的增加而进行扩容。
• 由于实现了List接口，又可称为“数组列表”，实现了Collection接口，又可称为“数组集合”。

二、ArrayList与LinkedList的对比

 ArrayList是基于数组的实现，LinkedList是基于链表的实现，他们的区别基本上也取决于数组和链表的区别。

• 数组带下标，所以支持随机访问，且速度快，链表不支持。
• 数组遍历时指针在数组上移动即可，查询速度快；而链表遍历时需要一个个节点逐一查找，所以查询慢。
• 数组增删数据时，可能会移动其它数据，比如在头部插入一个新数据，下面的数据都需要往后移，所以增删速度慢；而链表在内存中是散列的，增删数据时，只需要改变其中一个节点对下一个节点的引用即可，所以增删快。

区别：
ArrayList 底层是数组，查询快、增删慢，有初始容量（默认10），容量满了，需要进行扩容
LinkedList 底层是链表，查询慢，增删快，无初始容量，默认为0，无扩容操作

三、4个默认值

1.默认初始容量

private static final int DEFAULT_CAPACITY = 10;

2.指定容量为0的时候，返回的空数组

private static final Object[] EMPTY_ELEMENTDATA = {};

new ArrayList(0);

3.未指定容量时，返回的空数组

private static final Object[] EMPTY_ELEMENTDATA = {};

new ArrayList();
此处区别与上面指定容量为0时的空数组，第一次调用add时如果未指定容量则会设置默认容量10，而如果是设置了初始容量为0，第一次add时，只会将容量变成1；

4.数组大小size的最大值

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

int最大值减8，超过这个数，可能会内存溢出，超过某些虚拟机的限制。

四、2个基本属性

1.元素数据

transient Object[] elementData;

elementData是实际存放数据的地方

2.数组大小（包含元素的数量）

private int size;

五、3个构造函数

1.无参构造函数

public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}

使用默认空数组

2.指定初始容量的构造函数

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);}}

阿里巴巴代码规范提示，需指定初始容量，一般用到几个就写几个或者稍大一点。

3.带Collection集合的构造函数

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;}}

先将传入集合c转化为数组元素，toArray，如果c为空，抛出空指针异常。
再将数组复制到elementData中，校验。
LinkedList转化为ArrayList时可使用此方法。

六、N个方法 公共API

1.⭐根据下标获取元素 get(index)

public E get(int index) {rangeCheck(index);return elementData(index);}

检查下标是否正确，当下标大于等于容量大小，抛出“下标越界异常”

private void rangeCheck(int index) {if (index >= size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}

当下标为负数时，上一步校验不到，数组根据下标获取元素时由数组抛出“下标越界异常”

2.在指定位置塞入元素 set(index, element)

public E set(int index, E element) {rangeCheck(index);E oldValue = elementData(index);elementData[index] = element;return oldValue;}

1.检查传入的下标是否正确；
2.获取下标对应的元素；
3.替换该下标的元素；
4.返回旧元素；

3.⭐添加元素 add(E e)

public boolean add(E e) {ensureCapacityInternal(size + 1);  // Increments modCount!!elementData[size++] = e;return true;}

private void ensureCapacityInternal(int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);}ensureExplicitCapacity(minCapacity);}

private void ensureExplicitCapacity(int minCapacity) {modCount++;// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);}

private void grow(int minCapacity) {// overflow-conscious codeint 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);}

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {@SuppressWarnings("unchecked")T[] copy = ((Object)newType == (Object)Object[].class)? (T[]) new Object[newLength]: (T[]) Array.newInstance(newType.getComponentType(), newLength);System.arraycopy(original, 0, copy, 0,Math.min(original.length, newLength));return copy;}

一、检查size+1后容量是否足够：1.如果此时数组是无参构造函数时返回的默认空数组，设置默认容量为10;2.校验元素个数是否大于数组容量，大于则触发扩容（1.5倍扩容）；3.扩容：旧数组的长度（容量）加上自身右移1位后的数，右移相当于除以2，所以扩容后的新容量是旧容量的1.5倍；4.当旧数组长度为0时，经过上面的操作还是0，则设置为传入的数；5.当新数组长度大于size最大值时，将数组长度设置为int的最大值（感觉前面减的8，就是为这里准备的）；6.扩容后将旧数组里的元素，复制到新数组Arrays.copyOf()7.Arrays.copyOf()，其实也是使用了 System.arraycopy()二、检查完容量后，在size++下标位置放入新元素
三、返回成功。

流程图：

4.在指定位置添加元素 add(int index, E element)

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++;}

1.校验传入下标：大于size或小于0，抛出“下标越界异常”；
2.检查容量是否足够，不够就扩容；
3.将指定位置及后面的元素都往后移，空出指定位置：将指定下标后面的元素复制到从这个下标+1开始的位置。下标位置的元素往后移，空出位置。
4.在指定位置放入新元素；
5.size++。

5.移除指定位置的元素 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 workreturn oldValue;}

1.校验转入的下标是否正确；
2.获取下标对应的元素；
3.移除指定位置的元素：截取该下标的前后位置，copy到数组中。将指定下标+1开始的元素复制到从这个下标开始的位置，下标位置的元素往前移，覆盖下标位置的元素。
4.数组最后一个位置元素设置为null；
5.返回被删除的元素。

移除元素时，并不会改变 ArrayList的容量，只会自动扩容，不会自动减少容量，如果要减少容量，需要手动调用 trimToSize()，将容量修剪为与当前size大小相等的容量。

6.移除数组中第一次出现的指定元素 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;}

1.判空，传入的元素为空，返回false
2.遍历数组元素，找到与传入元素相等的
3.匹配到了，执行快速删除，返回true  （类似于删除指定下标位置的元素）
4.匹配不到，数组不变，返回false

7.清除数据 clear()

public void clear() {modCount++;// clear to let GC do its workfor (int i = 0; i < size; i++)elementData[i] = null;size = 0;}

1.循环遍历，将所有位置的元素都设置为 null
2.size修改为0；
此时数组容量不变，只是都存了空

8.修剪容量 trimToSize()

public void trimToSize() {modCount++;if (size < elementData.length) {elementData = (size == 0)? EMPTY_ELEMENTDATA: Arrays.copyOf(elementData, size);}}

将容量修剪为与当前size大小相等的容量。
ArrayList只会自动扩容，不会自动缩容，需要手动调用修剪容量。

9.获取元素数量 size()

public int size() {return size;}

10.判断列表是否为空 isEmpty()

public boolean isEmpty() {return size == 0;}

11.判断列表中是否包含某元素 contains(Object o)

public boolean contains(Object o) {return indexOf(o) >= 0;}

12.查询指定元素在列表中出现的第一个索引 indexOf(Object o)

public int indexOf(Object o) {if (o == null) {for (int i = 0; i < size; i++)if (elementData[i]==null)return i;} else {for (int i = 0; i < size; i++)if (o.equals(elementData[i]))return i;}return -1;}

1.顺序循环遍历数组，对比指定元素；
2.找到相等的元素，返回该元素的下标；
3.找不到，返回 -1；

13.查询指定元素在列表中出现的最后一个索引 lastIndexOf(Object o)

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;}

1.倒序遍历数组，对比指定元素；
2.找到相等的元素，返回该元素的下标；
3.找不到，返回 -1；

14.复制列表 clone()

public Object clone() {try {ArrayList<?> v = (ArrayList<?>) super.clone();v.elementData = Arrays.copyOf(elementData, size);v.modCount = 0;return v;} catch (CloneNotSupportedException e) {// this shouldn't happen, since we are Cloneablethrow new InternalError(e);}}

浅拷贝，只复制数组元素对象的引用。

15.列表转化为数组 toArray()

public Object[] toArray() {return Arrays.copyOf(elementData, size);}

将 elementData 复制到一个新数组并返回。

16.列表复制到指定数组 toArray(T[] a)

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;}

17.将指定集合里的所有元素添加到列表的末尾 addAll(Collection<? extends E> c)

public boolean addAll(Collection<? extends E> c) {Object[] a = c.toArray();int numNew = a.length;ensureCapacityInternal(size + numNew);  // Increments modCountSystem.arraycopy(a, 0, elementData, size, numNew);size += numNew;return numNew != 0;}

1.将传入的集合转为数组
2.检查容量是否足够，不够则扩容
3.将上面转化的数组复制到原数组，从末尾开始
4.修改size
5.传入的集合没有元素，返回false，有元素，返回true

18.将指定集合里的所有元素添加到列表的指定位置 addAll(int index, Collection<? extends E> c)

public boolean addAll(int index, Collection<? extends E> c) {rangeCheckForAdd(index);Object[] a = c.toArray();int numNew = a.length;ensureCapacityInternal(size + numNew);  // Increments modCountint 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;}

19.从此列表中删除包含在指定集合中的所有元素 removeAll(Collection<?> c)

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 workfor (int i = w; i < size; i++)elementData[i] = null;modCount += size - w;size = w;modified = true;}}return modified;}

1.循环遍历数组，调用Collection集合的contains方法判断集合中是否包含该元素，不包含则放入该元素
2.将后面没有移动的元素设置为null

20.从此列表中删除不包含在指定集合中的所有元素 retainAll(Collection<?> c)

public boolean retainAll(Collection<?> c) {Objects.requireNonNull(c);return batchRemove(c, true);}

与 removeAll(Collection<?> c) 相反

21.⭐分割列表 subList(int fromIndex, int toIndex)

public List<E> subList(int fromIndex, int toIndex) {subListRangeCheck(fromIndex, toIndex, size);return new SubList(this, 0, fromIndex, toIndex);}static void subListRangeCheck(int fromIndex, int toIndex, int size) {if (fromIndex < 0)throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);if (toIndex > size)throw new IndexOutOfBoundsException("toIndex = " + toIndex);if (fromIndex > toIndex)throw new IllegalArgumentException("fromIndex(" + fromIndex +") > toIndex(" + toIndex + ")");}

截取下标从 fromIndex 到 toIndex 的元素，返回一个新的List