集合容器：ArrayList 源码阅读
一、概述
ArrayList是一个可以支持动态扩容的数组，底层采用数组实现。ArrayList是AbstractList的子类，并且实现了List接口及相关方法，允许所有元素(包括null)的插入操作。ArrayList和Vector除了线程不同步之外，其它大致相同。
二、属性
// 默认初始容量
private static final int DEFAULT_CAPACITY = 10;
// 空数组常量
private static final Object[] EMPTY_ELEMENTDATA = {};
// 默认空数组常量
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 存放元素的buffer
transient Object[] elementData;
// 包含元素的个数
private int size;
// 数组最大上线
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// 继承自父类的，结构修改次数
protected transient int modCount = 0;
成员变量只有elementData和size两个，可以看出ArrayList底层采用的是数组存储。
所以具备数组具有的优势，插入、查找快，时间复杂度O(1)。
删除的时候会进行元素的移动，时间复杂度O(n)。
三、构造方法
1. 无参空容量构造
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
利用DEFAULTCAPACITY_EMPTY_ELEMENTDATA构造了一个空的数组。数组长度为0，在初次使用的时候会扩容到10。
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. 根据指定集合构建ArrayList
public ArrayList(Collection<? extends E> c) {
// 将给定集合元素赋值给容器，如果给定的是null会抛出NPE
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;
}
}
根据给定集合构造容器。
四、添加元素
1. 数组尾端添加
在添加的时候，首先需要确保容器能放下要添加的元素，在判断的过程中进行了modCount++，然后将元素放在数组的尾端。
扩容的次数很少，时间复杂度为O(1)。
public boolean add(E e) {
// modCount自增，确保容器能放下最新元素
ensureCapacityInternal(size + 1); // Increments modCount!!
// 将插入的元素放入数组尾部
elementData[size++] = e;
return true;
}
2. 将元素添加到指定index处
在指定index处添加元素的时候，需要调用native方法将index后的元素向后移动。时间复杂度O(n)，涉及到数组的移动非常耗时。
public void add(int index, E element) {
// 索引合理化校验
rangeCheckForAdd(index);
// modCount自增，确保容器能放下最新元素
ensureCapacityInternal(size + 1); // Increments modCount!!
// 调用native方法，将index后的所有元素向后移动
System.arraycopy(elementData, index, elementData, index + 1, size - index);
// 将element放在指定的index处
elementData[index] = element;
size++;
}
3. 替换指定索引处的元素
首先要判断给定索引是否合理，需要处在[0,size)内。替换后返回被替换掉的元素。时间复杂度O(1)
public E set(int index, E element) {
// 指定索引检查，是否是合理范围，这里有一个bug，未校验负数。
rangeCheck(index);
E oldValue = elementData(index);
// 替换指定索引处的元素为新元素
elementData[index] = element;
return oldValue;
}
4. 将给定集合的元素添加到容器
首先要对容器的容量进行处理，确保容器能放下新老元素。不能放下则进行扩容，然后将新元素放到容器的尾端。
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
// modCount自增并确保容器能放下新老元素
ensureCapacityInternal(size + numNew); // Increments modCount
// 调用native方法，将新元素复制到容器内
System.arraycopy(a, 0, elementData, size, numNew);
// 现有元素为新老元素的和
size += numNew;
return numNew != 0;
}
5. 将给定集合添加到index处
将给定的集合添加到index索引处，index后的元素需要向后移动。index后的元素需要向后挪动，时间复杂度O(n)
public boolean addAll(int index, Collection<? extends E> c) {
// 索引合理化校验，index区间(0,size)，不合理则抛出异常
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
// 确保容器能放下所有的新老元素，放不下则进行扩容
ensureCapacityInternal(size + numNew); // Increments modCount
// index后元素挪动的索引数
int numMoved = size - index;
if (numMoved > 0)
// 调用native方法，将index后的元素向后挪动numMoved个索引
System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
// 调用native方法，将新元素copy到指定的index处
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
五、容量伸缩
1. 根据实际元素数量缩容
将容器的容量缩小为当前元素的实际个数，减少实例的存储。
public void trimToSize() {
// 修改次数自增
modCount++;
// 实际元素数量小于容器容量的时候，进行缩容
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
// 创建了一个以size为大小的数组，并把元素放到新数组。
: Arrays.copyOf(elementData, size);
}
}
2. 确保可以容纳minCapacity个元素
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// 如果不是默认的空数组，将允许给定的数值
? 0
// 默认空数组的时候为默认容量 10
: DEFAULT_CAPACITY;
// 如果给定数值大于
if (minCapacity > minExpand) {
// 确保给定的容量
ensureExplicitCapacity(minCapacity);
}
}
根据给定的容量与实际容量比较，确定合适的容量大小。
六、元素获取相关
1. get指定索引处的元素
时间复杂度O(1)，但是需要注意此处参数校验的时候未判断负数，只判断了是否小于size。
public E get(int index) {
// index索引合理化校验，此处未校验负数。需要注意
rangeCheck(index);
return elementData(index);
}
2. 判断容器内是否包含给定元素
此处调用的是indexOf方法，如果indexOf返回的当前元素的索引大于0则证明这个元素存在，时间复杂度O(n)，和indexOf一致。
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
3. 获取给定元素第一次出现的索引
利用循环遍历判断给定的元素在数组中出现的索引，如果未匹配到则返回-1。时间复杂度O(n)
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;
}
4. 获取给定元素最后一次出现的位置
采用倒序遍历，判断元素出现的索引，如果未匹配到返回-1.时间复杂度O(n)。
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. 移除指定索引处的元素
将指定位置的元素删除，并将后续元素向前移动补位。最后将删除掉的元素失去引用，明确GC回收。
public E remove(int index) {
// index索引合理化校验，此处未校验负数。需要注意
rangeCheck(index);
// 修改次数自增
modCount++;
// 要删除索引处的元素
E oldValue = elementData(index);
// 将待删除后的元素向前移动
int numMoved = size - index - 1;
if (numMoved > 0)
// 调用native方法将，待删除后的元素向前移动
System.arraycopy(elementData, index+1, elementData, index, numMoved);
// 根据GC可达性分析，明确GC要回收掉删除后失去引用的对象
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
2. 移除给定元素
采用for循环遍历，对元素一一匹配，找到要删除的元素将其删除，如果未找到则返回false。这里要注意，只删除了元素首次出现，并不是将集合内的全部这个元素都删除。时间复杂度O(n)。
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])) {
// modCount自增，并且将找到的index索引后的元素向前移动，最后将删除掉的元素失去引用。
fastRemove(index);
return true;
}
}
return false;
}
3. 清空当前集合容器
循环遍历将数组内所有的元素都失去引用，并将数组的每个索引都指向null。时间复杂度O(n)。
public void clear() {
// 修改次数自增
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
// 现有元素归零
size = 0;
}
4. 删除给定索引范围内的元素
删除掉的是包含fromIndex处，但不包含toIndex处的元素。时间复杂度O(2n)
protected void removeRange(int fromIndex, int toIndex) {
// 修改次数自增
modCount++;
// 计算出要删除掉的元素个数，将toIndex处的元素向前移动。
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved);
// clear to let GC do its work
// 最新元素个数为原size减去删除掉的元素个数
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
// GC可达性算法明确GC回收删除掉的代码
elementData[i] = null;
}
size = newSize;
}
5. 删除给定集合的所有元素
public boolean removeAll(Collection<?> c) {
// 判空，抛出NPE
Objects.requireNonNull(c);
return batchRemove(c, false);
}
6. 批量删除/保留指定集合元素
根据参数complement的值，如果为true则取容器内和给定集合的交集，如果为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.
// r不等于size，说明遍历过程中容器内元素有增删操作。
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;
}
7. 快速删除指定index处的元素(内部方法)
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
}
网友评论