image.png
ArrayList源码分析主要由五部分组成，一是继承和实现类，二是基本属性，三是构造方法，四是主要方法，五是分析与总结。
一、 ArrayList概述：
ArrayList特点：是基于数组实现的动态数组，其容量能自动增长，元素有顺序、可重复 、查询快、增删慢、线程不安全，内部的元素可以直接通过get与set方法进行访问。
ArrayList继承了AbstractList，实现了RandomAccess、Cloneable和Serializable接口！
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
（1）继承AbstractList,把模板类定义成抽象类，抽象类本身不能实例化，继承接口的实现类必须要实现接口的所有方法，而模板类仅仅是为了实现一些通用方法不需要实现所有接口方法，不会产生没有实现的接口滥用。实现了代码的最大化复用和代码的最大化精简。
AbstractList又继承了AbstractCollection实现了List接口，List提供了相关的添加、删除、修改、遍历等功能！
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
protected AbstractList() {
}
（2）实现了List接口，表明ArrayList是一个有序、可重复的数组，提供了相关的添加、删除、修改、遍历等功能！
（3）实现RandomAccess接口，提供了随机访问功能，是一个标记接口，实际上就是通过下标序号进行快速访问，主要目的是使算法能够在随机和顺序访问的list中表现的更加高效。
Collections下的binarySearch方法的源码：
public static <T>int binarySearch(List<? extends Comparable<? super T>> list, T key) {
if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
return Collections.indexedBinarySearch(list, key);
else
return Collections.iteratorBinarySearch(list, key);
}
indexedBinarySearch是直接通过get访问数据
iteratorBinarySearch是通过ListIterator查找响应的元素
实现RandomAccess接口的的List可以通过简单的for循环来访问数据比使用iterator访问来的高效快速。
（4）实现了Cloneable接口，表明ArrayList支持克隆，即可以重写Object.clone方法，否则在重写clone方法时，报CloneNotSupportedException
（5）实现了Serializable接口可以被序列化与反序列化。
二、ArrayList的继承关系
java.lang.Object
java.util.AbstractCollection<E>
java.util.AbstractList<E>
java.util.ArrayList<E>
All Implemented Interfaces:
Serializable, Cloneable, Iterable<E>, Collection<E>, List<E>, RandomAccess
Direct Known Subclasses:
AttributeList, RoleList, RoleUnresolvedList
类中属性
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
// 版本号
private static final long serialVersionUID = 8683452581122892189L;
// 缺省容量
private static final int DEFAULT_CAPACITY = 10;
// 空对象数组
private static final Object[] EMPTY_ELEMENTDATA = {};
// 缺省空对象数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 元素数组
transient Object[] elementData;
// 实际元素大小，默认为0
private int size;
// 最大数组容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
}
三、ArrayList方法（API）
// Collection中定义的API
boolean add(E object)
boolean addAll(Collection<? extends E> collection)
void clear()
boolean contains(Object object)
boolean containsAll(Collection<?> collection)
boolean equals(Object object)
int hashCode()
boolean isEmpty()
Iterator<E> iterator()
boolean remove(Object object)
boolean removeAll(Collection<?> collection)
boolean retainAll(Collection<?> collection)
int size()
<T> T[] toArray(T[] array)
Object[] toArray()
// AbstractCollection中定义的API
void add(int location, E object)
boolean addAll(int location, Collection<? extends E> collection)
E get(int location)
int indexOf(Object object)
int lastIndexOf(Object object)
ListIterator<E> listIterator(int location)
ListIterator<E> listIterator()
E remove(int location)
E set(int location, E object)
List<E> subList(int start, int end)
// ArrayList新增的API
Object clone()
void ensureCapacity(int minimumCapacity)
void trimToSize()
void removeRange(int fromIndex, int toIndex)
四、构造方法（有3个）
（1）无参构造，初始化长度为0的数组
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
（2）传入int类型的值，初始化长度为自定义的数组
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）对传入的集合元素进行复制，构造一个包含指定元素的列表
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;
}
}
五、 主要方法解析
1. add(E e)，在元素列表的末尾插入指定的元素，返回true或者抛出异常，无其他返回值
每次添加元素之前都会判断添加后的容量是否需要扩容
//添加单个元素
public boolean add(E e) {
//判断添加后的长度是否需要扩容
ensureCapacityInternal(size + 1);
//在数组末尾添加上当前元素，并且修改size大小
elementData[size++] = e;
return true;
}
看到它首先调用了ensureCapacityInternal()方法.注意参数是size+1,这是个面试考点
//集合的初始容量为10
private static final int DEFAULT_CAPACITY = 10;
//判断是否是第一次初始化数组
private void ensureCapacityInternal(int minCapacity) {
/**
EMPTY_ELEMENTDATA是elementData 的初始化{}一个空数组，elementData是数组缓冲器，
ArrayList的元素都放在这个数组缓冲器中。
DEFAULT_CAPACITY是数组列表初始容量大小为10，ArrayList会在第一次添加元素的时候设置数组缓冲
器的初始大小为10.
**/
//判断当前数组是否 == EMPTY_ELEMENTDATA，因为默认构造函数创建时是将空数组EMPTY_ELEMENTDATA赋值给elementData
if (elementData == EMPTY_ELEMENTDATA) {
//判断默认容量10和当前数据长度的大小，取其中大的值作为判断本次是否需要扩容的依据，由于第一次数组是空的，所以默认要使数组扩容到10的长度
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//判断是否需要扩容
ensureExplicitCapacity(minCapacity);
}
这个方法里又嵌套调用了两个方法:计算容量+确保容量
计算容量：如果elementData是空，则返回默认容量10和size+1的最大值，否则返回size+1
计算完容量后，进行确保容量可用：(modCount不用理它，它用来计算修改次数)
如果size+1 > elementData.length证明数组已经放满，则增加容量，调用grow()。
//判断扩容的方法
private void ensureExplicitCapacity(int minCapacity) {
//如果需要扩容modCount++，此参数是指当前列表结构被修改的次数
modCount++;
// 判断当前数据量是否大于数组的长度
if (minCapacity - elementData.length > 0)
//如果大于则进行扩容操作
grow(minCapacity);
}
增加容量：默认1.5倍扩容。
获取当前数组长度=>oldCapacity
oldCapacity>>1 表示将oldCapacity右移一位(位运算)，相当于除2。再加上1，相当于新容量扩容1.5倍。
如果newCapacity>1=1,1<2所以如果不处理该情况，扩容将不能正确完成。
如果新容量比最大值还要大，则将新容量赋值为VM要求最大值。
将elementData拷贝到一个新的容量中。
// 内部数组的容量可以扩展到的最大值
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//扩容方法
private void grow(int minCapacity) {
// 记录扩容前数组的长度
int oldCapacity = elementData.length;
//将原数组的长度扩大0.5倍作为扩容后新数组的长度（如果扩容前数组长度为10，那么经过扩容后的数组长度应该为15）
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果扩容后的长度小于当前数据量，那么就将当前数据量的长度作为本次扩容的长度
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//判断新数组长度是否大于可分配数组的最大大小
if (newCapacity - MAX_ARRAY_SIZE > 0)
//将扩容长度设置为最大可用长度
newCapacity = hugeCapacity(minCapacity);
// 拷贝，扩容，构建一个新的数组
elementData = Arrays.copyOf(elementData, newCapacity);
}
//判断如果新数组长度超过当前数组定义的最大长度时，就将扩容长度设置为Interger.MAX_VALUE,也就是int的最大长度
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
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的问题
好了，那到这里可以说一下为什么要size+1。
size+1代表的含义是：
如果集合添加元素成功后，集合中的实际元素个数。
为了确保扩容不会出现错误。
假如不加一处理，如果默认size是0，则0+0>>1还是0。
如果size是1，则1+1>>1还是1。有人问:不是默认容量大小是10吗?事实上，jdk1.8版本以后，ArrayList的扩容放在add()方法中。之前放在构造方法中。我用的是1.8版本，所以默认ArrayList arrayList = new ArrayList();后，size应该是0.所以,size+1对扩容来讲很必要.
2. 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++;
}
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
代码解释:
Object src : 原数组
int srcPos : 从元数据的起始位置开始
Object dest : 目标数组
int destPos : 目标数组的开始起始位置
int length : 要copy的数组的长度
示例：size为6，我们调用add(2,element)方法，则会从index=2+1=3的位置开始，将数组元素替换为从index起始位置为index=2，长度为6-2=4的数据。
image.png
3. addAll(Collection<? extends E> c)，将指定集合追加到列表的末尾，返回值为true或者false，还可能抛出异常
// 在列表的结尾追加一个集合
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;
}
4. addAll(int index, Collection<? extends E> c)，在指定位置追加指定元素列表，返回值为true或者false，还可能抛出异常
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;
}
5. remove(int index)，移除指定下标对应的列表元素，返回值为指定下标对应的列表元素
/**
*按下标移除元素
*/
public E remove(int index) {
//先判断index是否大于等于size，如果大于等于将报异常
rangeCheck(index);
modCount++;
//防止数组index下标位置所指向的内存在移动元素的时候被占用
E oldValue = elementData(index);
//需要在elementData数组中移动元素的长度
int numMoved = size - index - 1;
if (numMoved > 0)
//将elementData从下标index+1开始的元素到，长度为numMoved，移除到elementData的下标为index开始的地方
//这样就能将elementData中下标为index的元素覆盖掉
System.arraycopy(elementData, index+1, elementData, index,numMoved);
elementData[--size] = null; // Let gc do its work
return oldValue;
}
6. remove(Object o)，移除列表中的指定元素，返回值为true或者false，也可抛出异常
public boolean remove(Object o) {
if (o == null) {
// 如果移除的指定元素为null，先找到列表中值为null的元素的下标，然后移除元素
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
// 如果移除的元素不为null，先找到下标，然后移除元素
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;
}
7. removeAll(Collection<?> c)，移除指定的集合元素
public boolean removeAll(Collection<?> c) {
// 采用Objects工具类，如果指定集合为null，则抛出空指针异常
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;
}
8. removeIf(Predicate<? super E> filter)，根据指定的筛选条件删除指定的列表元素，这是Jdk1.8新增的方法
@Override
public boolean removeIf(Predicate<? super E> filter) {
// Objects工具类判定null操作
Objects.requireNonNull(filter);
int removeCount = 0;
// 装载int类型的小型数组，可以理解为装载int的列表
final BitSet removeSet = new BitSet(size);
// 因为后面的遍历列表元素，可能有多线程同时访问的情况，固做此标记
final int expectedModCount = modCount;
final int size = this.size;
// 遍历列表元素找到符合筛选条件的下标，然后存储到BitSet中
for (int i = 0; modCount == expectedModCount && i < size; i++) {
@SuppressWarnings("unchecked") final E element = (E) elementData[i];
if (filter.test(element)) {
removeSet.set(i);
removeCount++;
}
}
// 上面如果有多线程同时访问，则此处可能会报异常
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
// shift surviving elements left over the spaces left by removed elements
final boolean anyToRemove = removeCount > 0;
// 如果符合筛选提交的元素个数不为0，则进行删除操作
if (anyToRemove) {
// 移除符合筛选条件的元素后，列表的长度
final int newSize = size - removeCount;
for (int i = 0, j = 0; (i < size) && (j < newSize); i++, j++) {
// 可以参加下面的testBitSet测试分析，它表示返回的是正序排列BitSet中没有的int类型值
i = removeSet.nextClearBit(i);
elementData[j] = elementData[i];
}
for (int k = newSize; k < size; k++) {
elementData[k] = null; // Let gc do its work
}
this.size = newSize;
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
return anyToRemove;
}
测试BitSet类型的存储，主要测试nextClearBit方法
微信图片_20190821185923.jpg
public void testBitSet() {
// 长度为6，对应存储元素为{0,1,2,3,4,5}
BitSet removeSet = new BitSet(6);
// 如下为装载的数据，浅绿色标记
removeSet.set(1);
removeSet.set(0);
removeSet.set(3);
removeSet.set(5);
// 可采用如下方式，找到为装载的数据，即为{2,4}
for (int i = 0; i < 6; i++) {
System.out.println("清除前i=" + i);
i = removeSet.nextClearBit(i);
System.out.println("清除后i=" + i);
System.out.println("-----------------");
}
}
清除前i=0
清除后i=2
-----------------
清除前i=3
清除后i=4
-----------------
清除前i=5
清除后i=6
-----------------
测试removeIf(Predicate<? super E> filter)方法
public void testRemoveIf() {
ArrayList<String> mArrayList = new ArrayList<>();
mArrayList.add("a");
mArrayList.add("b");
mArrayList.add("ab");
mArrayList.add("c");
mArrayList.add("aa");
mArrayList.add("d");
System.out.println("初始时：" + mArrayList.toString());
mArrayList.removeIf(s -> s.contains("a"));
System.out.println("过滤完：" + mArrayList.toString());
// 初始时：[a, b, ab, c, aa, d]
// 过滤完：[b, c, d]
}
9. 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 Cloneable
throw new InternalError(e);
}
}
10. set(int index, E element)，用指定元素替换指定下标的值并返回
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
11.get(int index)方法：返回指定下标处的元素的值。
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
rangeCheck(index)会检测index值是否合法，如果合法则返回索引对应的值。
5、总结
1：ArrayList 本质实现方法是用数组！是非同步的！
2:初始化容量 = 10 ，最大容量不会超过 MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8！
3：indexOf和lastIndexOf 查找元素，若元素不存在，则返回-1！
4：当ArrayList容量不足以容纳全部元素时，ArrayList会重新设置容量：新的容量=“(原始容量x3)/2 + 1”。
5：ArrayList的克隆函数，即是将全部元素克隆到一个数组中。
6：ArrayList实现java.io.Serializable的方式。当写入到输出流时，先写入“容量”，再依次写入“每一个元素”；当读出输入流时，先读取“容量”，再依次读取“每一个元素”。
7：造成ArrayList添加（add）慢的原因是什么？
当容量不够时，每次增加元素，使用System.arraycopy()方法将原来的元素拷贝到一个新的数组中，造成了资源的浪费，也因此建议在事先能确定元素数量的情况下，在使用ArrayList。
8：ArrayList的实现中大量地调用了Arrays.copyof()和System.arraycopy()方法。
9：造成ArrayList移除（remove）慢的原因是什么？
ArrayList基于数组实现，可以通过下标索引直接查找到指定位置的元素，因此查找效率高，但每次根据下标插入或删除元素时，就需要调用System.arraycopy（）方法将下标前数据和下标后的数据进行拼接并复制到新的数组里，因此插入、删除元素的效率低。
10：在查找给定元素索引值等的方法中，源码都将该元素的值分为null和不为null两种情况处理，ArrayList中允许元素为null。
11：ArrayList为什么能自动扩展大小，不需要手动设置大小？
ArrayList内部采用的是Array对象存储，本身该对象是需要定义长度的，所以每次添加数据的时候，都是判断是否先扩展容量，且容量有最大值限制，容量的大小是在原来基础上扩大1.5倍：公式（oldCapacity + oldCapacity >> 1）。
12：ArrayLIst查询效率高：ArrayLIst是连续存放元素的，找到第一个元素的首地址，再加上每个元素的占据的字节大小就能定位到对应的元素。
13：LinkedList插入删除效率高。因为执行插入删除操作时，只需要操作引用即可，元素不需要移动元素，他们分布在内存的不同地方，通过引用来互相关联起来。而ArrayLIst需要移动元素，故效率低。
