ArrayList源码解析
1.简介
- ArrayList 是 Java 集合框架中 List 接口的一个实现类。底层是数组，相当于动态数组。与 Java 中的数组相比，它的容量能动态增长。
- ArrayList是Vector的翻版，区别在于ArrayList是线程不安全的，而Vector则是线程安全的。
- 有序的（元素输出顺序与输入顺序一致）
- 元素可以为null
- 查询快，增删慢
- 占用空间更小，对比 LinkedList，不用占用额外空间维护链表结构
实现了三个标识型接口，这几个接口都没有任何方法，仅作为标识表示实现类具备某项功能： - RandomAccess表示实现类支持快速随机访问
- Cloneable表示实现类支持克隆，具体表现为重写了clone方法
- java.io.Serializable则表示支持序列化，如果需要对此过程自定义，可以重写writeObject与readObject方法
2.成员变量
// 序列号
private static final long serialVersionUID = 8683452581122892189L;
// 数组初始容量为 10
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;- 数组初始容量为10，数组元素个数初始为0
- 底层是一个Object数组
3.构造器
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}- 默认构造方法，初始为空数组
- 只有插入一条数据后才会扩展为10，而实际上默认是空的
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//创建initialCapacity大小的数组
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有可能不返回一个Object数组，如果不是需要转换为Object数组
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 替换为空数组
this.elementData = EMPTY_ELEMENTDATA;
}
}- 构造一个包含指定集合的元素的列表，按照它们由集合的迭代器返回的顺序
- Collection中toArray()将集合转为数组
- Arrays.copy()用于拷贝数组
4.内部类
private class Itr implements Iterator<E> private class ListItr extends Itr implements ListIterator<E> private class SubList extends AbstractList<E> implements RandomAccess static final class ArrayListSpliterator<E> implements Spliterator<E>
- Itr是实现了Iterator接口，同时重写了里面的hasNext()，next()，remove()等方法
- ListItr 继承 Itr，实现了ListIterator接口，同时重写了hasPrevious()，nextIndex()，previousIndex()，previous()，set(E e)，add(E e)等方法
- ListIterator在Iterator的基础上增加了添加对象，修改对象，逆向遍历等方法，这些是Iterator不能实现的
5.add()方法
public boolean add(E e) {
//先确保elementData数组的长度足够，size是数组中数据的个数，因为要添加一个元素，所以size+1，先判断size+1的这个个数数组能否放得下，在这个方法中去判断数组长度是否够用
ensureCapacityInternal(size + 1);
//在数据中正确的位置上放上元素e，并且size++
elementData[size++] = e;
return true;
}- //添加一个特定的元素到list的末尾
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;
}- 计算容量，判断初始化的elementData是不是空的数组，如果是空的话，返回默认容量10与minCapacity=size+1的较大值者
- 确保内部容量够用
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
//ArrayList能自动扩展大小的关键方法就在这里了
grow(minCapacity);
}- 确认实际的容量，这个方法就是真正的判断elementData是否够用
- minCapacity如果大于了实际elementData的长度，那么就说明elementData数组的长度不够用，不够用那么就要增加elementData的length。
- 那么minCapacity又是什么意思？
- 当 add 进第1个元素到 ArrayList 时，elementData.length 为0 （因为还是一个空的 list），因为执行了
ensureCapacityInternal()方法 ，所以 minCapacity 此时为10。此时，minCapacity - elementData.length > 0成立，所以会进入grow(minCapacity)方法。 - 当 add 第2个元素时，minCapacity 为2，此时elementData.length(容量)在添加第一个元素后扩容成 10 了。此时，
minCapacity - elementData.length > 0不成立，所以不会进入 （执行）grow(minCapacity)方法。 - 添加第3、4···到第10个元素时，依然不会执行grow方法，数组容量都为10。
- 直到添加第11个元素，minCapacity(为11)比elementData.length（为10）要大。进入grow方法进行扩容。
private void grow(int minCapacity) {
//将扩充前的elementData大小给oldCapacity
int oldCapacity = elementData.length;
//新容量newCapacity是1.5倍的旧容量oldCapacity
int newCapacity = oldCapacity + (oldCapacity >> 1);
//这句话就是适应于elementData就空数组的时候，length=0，那么oldCapacity=0，newCapacity=0，所以这个判断成立，在这里就是真正的初始化elementData的大小了，就是为10。
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果newCapacity超过了最大的容量限制，就调用hugeCapacity，也就是将能给的最大值给newCapacity
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//新的容量大小已经确定好了，就copy数组，改变容量大小。
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}- 扩容核心方法
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0)
throw new OutOfMemoryError();
//如果minCapacity都大于MAX_ARRAY_SIZE，那么就Integer.MAX_VALUE返回，反之将MAX_ARRAY_SIZE返回。因为maxCapacity是三倍的minCapacity，可能扩充的太大了，就用minCapacity来判断了。
//Integer.MAX_VALUE:2147483647 MAX_ARRAY_SIZE：2147483639 也就是说最大也就能给到第一个数值。还是超过了这个限制，就要溢出了。相当于arraylist给了两层防护。
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}- 赋最大值
public void add(int index, E element) {
rangeCheckForAdd(index);
//先确保elementData数组的长度足够
ensureCapacityInternal(size + 1);
//将数据整体向后移动一位，空出位置之后再插入，效率不太好
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}
// 校验插入位置是否合理
private void rangeCheckForAdd(int index) {
//插入的位置肯定不能大于size 和小于0
if (index > size || index < 0)
//如果是，就报越界异常
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}- 在指定位置插入元素
public boolean addAll(Collection<? extends E> c) {
//把该集合转为对象数组
Object[] a = c.toArray();
int numNew = a.length;
//增加容量
ensureCapacityInternal(size + numNew);
//挨个向后迁移
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
//新数组有元素，就返回 true
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);
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 是底层方法，但每次添加都后移一位效率还是不太好
- 涉及到扩容，就会调用到grow()方法，那么就会调用Arrays.copyOf()方法（底层调用的是System.arraycopy()方法）。说明扩容数组本质是新建一个新数组。
PS：总结，ArrayList的扩容机制：首先创建一个空数组elementData，第一次插入数据时直接扩充至10，然后如果elementData的长度不足，就扩充至1.5倍，如果扩充完还不够，就使用需要的长度作为elementData的长度(addAll()调用的时候会有这种情况)。
Point1：大数据插入问题
- 在遇到大量数据插入时，会出现频繁的拷贝数据的情况，这是很不友好的
- 使用ArrayList(int initialCapacity)这个有参构造，在创建时就声明一个较大的大小，这样解决了频繁拷贝问题，但是需要我们提前预知数据的数量级，也会一直占有较大的内存
- 可以在插入前先进行一次扩容。只要提前预知数据的数量级，就可以在需要时直接一次扩充到位，与ArrayList(int initialCapacity)相比的好处在于不必一直占有较大内存，同时数据拷贝的次数也大大减少了。这个方法就是ensureCapacity(int minCapacity)，其内部就是调用了ensureCapacityInternal(int minCapacity)
public void ensureCapacity(int minCapacity) { int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY; if (minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); } }
6.remove()方法
- 根据索引删除指定位置的元素，此时会把指定下标到数组末尾的元素挨个向前移动一个单位，并且会把数组最后一个元素设置为null，这样是为了方便之后将整个数组不被使用时，会被GC，可以作为小的技巧使用。
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; 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;
}- 从此列表中删除指定元素的第一个匹配项，如果存在，则删除
- 传入可以是null
public void clear() {
modCount++;
//并没有直接使数组指向 null,而是逐个把元素置为空
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}- 将elementData中每个元素都赋值为null，等待垃圾回收将这个给回收掉
private boolean batchRemove(Collection<?> c, boolean complement) {
//将原集合，记名为A
final Object[] elementData = this.elementData;
//r用来控制循环，w是记录有多少个交集
int r = 0, w = 0;
boolean modified = false;
try {
//遍历 ArrayList 集合
for (; r < size; r++)
//参数中的集合c一次检测集合A中的元素是否有
if (c.contains(elementData[r]) == complement)
//有的话，就给集合A
elementData[w++] = elementData[r];
} finally {
//发生了异常，直接把 r 后面的复制到 w 后面
if (r != size) {
//将剩下的元素都赋值给集合A
System.arraycopy(elementData, r,elementData, w, size - r);
w += size - r;
}
if (w != size) {
//这里有两个用途，在removeAll()时，w一直为0，就直接跟clear一样，全是为null。
//retainAll()：没有一个交集返回true，有交集但不全交也返回true，而两个集合相等的时候，返回false，所以不能根据返回值来确认两个集合是否有交集，而是通过原集合的大小是否发生改变来判断，如果原集合中还有元素，则代表有交集，而元集合没有元素了，说明两个集合没有交集。
// 清除多余的元素，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;
}- 删除或者保留指定集合中的元素
- 这个方法阅读起来还是有点绕的
- 该方法用于两个方法:
- removeAll()：清除指定集合中的元素，complement传入false
- retainAll()：保留指定集合中的元素，complement传入true
7.get()方法
public E get(int index) {
// 检验索引是否合法
rangeCheck(index);
return elementData(index);
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
E elementData(int index) {
return (E) elementData[index];
}- 检查索引是否合法只检查是否大于size，而没有检查是否小于0
- elementData()函数中的返回的值都经过了向下转型
8.set()方法
//设定指定下标索引的元素值
public E set(int index, E element) {
// 检验索引是否合法
rangeCheck(index);
// 旧值
E oldValue = elementData(index);
// 赋新值
elementData[index] = element;
// 返回旧值
return oldValue;
}9.indexOf()方法
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;
}- 从首开始查找数组里面是否存在指定元素
- 可以查找null元素，意味着ArrayList中可以存放null元素的
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;
}- 返回列表中指定元素最后一次出现的索引，倒着遍历
10.contains()方法
public boolean contains(Object o) {
return indexOf(o) >= 0;
}- 判断是否含有某个元素
11.toArray()方法
public Object[] toArray() {
//elementData：要复制的数组；size：要复制的长度
return Arrays.copyOf(elementData, size);
}
public <T> T[] toArray(T[] a) {
//如果只是要把一部分转换成数组
if (a.length < size)
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
//全部元素拷贝到数组a
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}- 将集合转换为数组
System.arraycopy()
public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length) // src：源对象 // srcPos：源对象对象的起始位置 // dest：目标对象 // destPost：目标对象的起始位置 // length：从源对象起始位置往后复制的长度
- 将指定源数组中的数组从指定位置开始复制到目标数组的指定位置
Arrays.copyOf()
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
//Arrays的copyOf()方法传回的数组是新的数组对象，改变传回数组中的元素值，不会影响原来的数组。
//newLength指定要建立的新数组长度，如果新数组的长度超过原数组的长度，则保留数组默认值
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;
}
// @Description 复制指定的数组, 如有必要用 null 截取或填充，以使副本具有指定的长度
// 对于所有在原数组和副本中都有效的索引，这两个数组相同索引处将包含相同的值
// 对于在副本中有效而在原数组无效的所有索引，副本将填充 null，当且仅当指定长度大于原数组的长度时，这些索引存在
// 返回的数组属于 newType 类
// @param original 要复制的数组
// @param newLength 副本的长度
// @param newType 副本的类
// @return T 原数组的副本，截取或用 null 填充以获得指定的长度
// @throws NegativeArraySizeException 如果 newLength 为负
// @throws NullPointerException 如果 original 为 null
// @throws ArrayStoreException 如果从 original 中复制的元素不属于存储在 newType 类数组中的运行时类型- 选择指定的数组，截断或填充空值（如果需要），使副本具有指定的长度。以达到扩容的目的。
- 两者联系与区别：
- 联系：看两者源代码可以发现copyOf()内部调用了System.arraycopy()方法
- 区别：arraycopy()需要目标数组，将原数组拷贝到你自己定义的数组里，而且可以选择拷贝的起点和长度以及放入新数组中的位置；copyOf()是系统自动在内部新建一个数组，并返回该数组。
你想占我便宜我就占你便宜，谁也拿我没办法，主打一个双向奔赴
