JDK13源码学习笔记——ArrayList
2019-11-05 本文已影响0人
prik丶
JDK版本：13
1 类图
@[TOC]
1.1 实现接口
-
java.util.List：提供增删改查等基本操作 -
java.io.Serializable：标记接口，表示支持序列化 -
java.lang.Cloneable：标记接口，表示支持克隆 -
java.util.RandomAccess：这个接口可能很少注意到，其实也是一个标记接口，表示能够随机访问元素，简单来说就是底层是数组实现的集合。参考：RandomAccess 这个空架子有何用？
1.2 继承
-
java.util.AbstractList：抽象类，从注释中可以看到，它提供了List接口的基本实现，以最大程度地减少迭代遍历相关操作的实现。不过ArrayList基本都重写了AbstractList提供的实现。
2 属性
-
int elementData：储存元素的数组，ArrayList的真实大小 -
int size：elementData中实际存放元素的数量，我们经常调用的size()方法返回的也就是它
3 构造方法
3.1 ArrayList(int initialCapacity)
/**
* 空数组，当初始化容量为0时，将elementData指向它
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
public ArrayList(int initialCapacity) {
// 指定容量大于0 创建对应的Object数组
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
// 等于0 使用 EMPTY_ELEMENTDATA
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
// 小于0 抛出异常
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
尽量预估数组大小，使用该方法创建ArrayList，合理使用内存，避免数组扩容耗费性能。
3.2 ArrayList()
/**
* Default initial capacity.
* 默认初始化容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 使用默认容量时的空数组。当使用无参构造时，为了节省内存（考虑到创建了ArrayList对象但没使用的情况）
* 做了优化，在首次添加元素时，才将elementData初始化成长度为10的数组。
* 与EMPTY_ELEMENTDATA区分开，以便在初始化时知道是直接初始化成10。
* 而EMPTY_ELEMENTDATA从0开始按照1.5倍扩容。
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 使用默认容量10创建ArrayList
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
3.3 ArrayList(Collection<? extends E> c)
/**
* 传入一个集合来创建ArrayList
*/
public ArrayList(Collection<? extends E> c) {
// 将集合转为Object数组
elementData = c.toArray();
// 如果数组长度不等于0
if ((size = elementData.length) != 0) {
// defend against c.toArray (incorrectly) not returning Object[]
// (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
// 如果elementData不是Object数组类型，就创建个新的Object类型数组，
// 并将elementData中的元素赋值进去，最终再把新数组赋值给elementData
// 是为了修复JDK-626065的BUG，c.toArray不返回Ojbect[]类型数组
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
// 如果数组大小等于0，使用EMPTY_ELEMENTDATA
} else {
this.elementData = EMPTY_ELEMENTDATA;
}
// ？？为什么一会用this.elementData，一会又不加this.了
}
4 主要方法
4.1 添加一个元素
boolean add(E e) 添加到尾部
/**
* 将一个元素添加到末尾
*/
public boolean add(E e) {
// 定义于父类AbstractList中，用于记录数组被修改的次数，+1
modCount++;
add(e, elementData, size);
return true;
}
private void add(E e, Object[] elementData, int s) {
// 如果容量不足，进行扩容
if (s == elementData.length)
elementData = grow();
// 元素放到数组末尾
elementData[s] = e;
// size +1
size = s + 1;
}
void add(int index, E element) 添加到指定位置
/**
* 在指定位置插入一个元素
*/
public void add(int index, E element) {
// 检查index是否在数组范围内
rangeCheckForAdd(index);
// 修改次数 +1
modCount++;
final int s;
Object[] elementData;
// 如果容量不够，进行扩容
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();
// 将index位置及之后的元素向后挪一位
// 数组复制
System.arraycopy(elementData, // 原数组
index, // 从原数组的开始位置
elementData, // 目标数组
index + 1, // 在目标数组的开始位置
s - index); // 复制元素的个数
// 将插入元素放在index的位置
elementData[index] = element;
// size + 1
size = s + 1;
}
4.2 扩容
Object[] grow()
private Object[] grow() {
// 扩容后容量至少比以前大1
return grow(size + 1);
}
/**
* @param minCapacity 所需最小扩容后容量
*/
private Object[] grow(int minCapacity) {
// 记录老的容量
int oldCapacity = elementData.length;
// 如果容量 > 0 或 数组不是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，计算新的容量大小并扩容
if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, /* minimum growth 最小扩大量*/
oldCapacity >> 1 /* preferred growth 首选扩大量*/);
// 把元素拷贝到新数组中
return elementData = Arrays.copyOf(elementData, newCapacity);
/*
ArraysSupport.newLength 计算新数组大小，取 minimum growth 和
preferred growth 的更大值加上旧的容量。
还涉及到一些数组最大长度的校验和处理，这里不细说。
>> 是移位运算符，右移一位相当于除以二，也就是说这里是扩大到1.5倍
如果是从0扩容，0 >> 1 还是0，此时使用minCapacity，也就是1
*/
// 如果是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，创建新数组
} else {
// 容量取 默认容量 和 minCapacity 中的更大值
return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
}
}
4.3 添加多个元素
boolean addAll(Collection<? extends E> c) 向末尾添加
/**
* 向末尾添加多个元素
* 调用此方法相比一个一个添加元素，可以避免数组多次扩容
*/
public boolean addAll(Collection<? extends E> c) {
// 转换成数组
Object[] a = c.toArray();
// 修改次数+1
modCount++;
// 新加入元素个数
int numNew = a.length;
// 如果个数为0，返回false，ArrayList数组无变化，但修改次数是增加了的
if (numNew == 0)
return false;
Object[] elementData;
final int s;
// 如果新加入元素不够放了，则进行扩容，要求扩容后至少能放得下新加入的数据
if (numNew > (elementData = this.elementData).length - (s = size))
elementData = grow(s + numNew);
// 将新数组复制进elementData的末尾
System.arraycopy(a, 0, elementData, s, numNew);
// 计算size大小
size = s + numNew;
return true;
}
boolean addAll(int index, Collection<? extends E> c) 向指定位置添加
public boolean addAll(int index, Collection<? extends E> c) {
// 检查是否越界
rangeCheckForAdd(index);
Object[] a = c.toArray();
modCount++;
int numNew = a.length;
if (numNew == 0)
return false;
Object[] elementData;
final int s;
// 扩容，至少装得下新数组
if (numNew > (elementData = this.elementData).length - (s = size))
elementData = grow(s + numNew);
int numMoved = s - index;
// 如果index位置已有元素，则将它开始及之后的元素向后移出位置来
if (numMoved > 0)
System.arraycopy(elementData, index,
elementData, index + numNew,
numMoved);
// 将新数组加入elementData指定的位置
System.arraycopy(a, 0, elementData, index, numNew);
size = s + numNew;
return true;
}
4.4 移除单个元素
E remove(int index) 移除指定位置的元素，并返回该元素
public E remove(int index) {
// 校验 index不能 > size
Objects.checkIndex(index, size);
final Object[] es = elementData;
// 记录被删除的值
@SuppressWarnings("unchecked") E oldValue = (E) es[index];
fastRemove(es, index);
// 返回被删除的值
return oldValue;
}
/**
* 负责删除的核心逻辑，不关心返回被删除元素或越界校验等操作
*/
private void fastRemove(Object[] es, int i) {
// 修改次数+1
modCount++;
final int newSize;
// size是比下标大 1 的，size-1 和 i 比较，其实是在判断i是不是数组最后一位
// 如果不是最后一位，要把i后边的所有元素向前挪一位。
if ((newSize = size - 1) > i) // 注意这里藏着 size - 1 的操作
System.arraycopy(es, i + 1, es, i, newSize - i);
// 将最后一位置空，帮助 GC
es[size = newSize] = null;
}
boolean remove(Object o) 移除首个为o的元素，返回是否移除
public boolean remove(Object o) {
final Object[] es = elementData;
final int size = this.size;
// 用于标记找到的第一个 o 的位置
int i = 0;
found: { // 利用break终止代码块执行，使代码更简洁
// 如果 o 是 null
if (o == null) {
for (; i < size; i++)
if (es[i] == null)
break found;
// 如果 o 不是 null
} else {
for (; i < size; i++)
if (o.equals(es[i]))
break found;
}
return false;
}
// 移除
fastRemove(es, i);
return true;
}
4.5 移除多个元素
boolean removeAll(Collection<?> c) 如果元素在集合 c 中就移除
/**
* 删除多个元素
*/
public boolean removeAll(Collection<?> c) {
// 调用了批量删除方法
return batchRemove(c, false, 0, size);
}
boolean batchRemove(Collection<?> c, boolean complement, final int from, final int end) 批量移除或保留元素
这个方法有点绕。先来看参数 complement，它表示如果一个元素在集合c中，他是保留还是删除。结合另一个方法
public boolean retainAll(Collection<?> c) { return batchRemove(c, true, 0, size); }
就很容易理解了，当complement为false时，是移除的逻辑。而为true时，是求两个集合的交集。
这个方法的大致逻辑是：（以移除为例）先找到第一个要移除的元素索引，记为w，它的下一位记为r。然后从r的位置开始遍历，如果是要删除的元素就跳过，如果是要保留的元素，就将它写到w指向的位置，覆盖之前的元素，再把w挪向下一位，继续遍历判断。最后再把数组末尾无用的元素置为null。下文代码后我贴了一张手绘图，可以结合起来理解。或者debug调试几次。
/**
* 批量删除或保留多个元素
* @param c 要删除的元素集合
* @param complement 如果一个元素再 c 中，是删除还是保留
* @param from 开始位置
* @param end 结束位置
* @return
*/
boolean batchRemove(Collection<?> c, boolean complement,
final int from, final int end) {
// 校验 c 不是 null
Objects.requireNonNull(c);
final Object[] es = elementData;
int r;
// Optimize for initial run of survivor 优化
// 想在删除逻辑前线判断elementData中到底有没有 c 中的元素，但有不想重复遍历
// 这里做的是 找到第一个不符合 complement 的元素的位置 r ，然后结束遍历
for (r = from;; r++) {
if (r == end)
return false;
if (c.contains(es[r]) != complement)
break;
}
// w 标记 r 的位置，r + 1 指向下一个位置
int w = r++; // 注意，这里等价于 w = r; r = r + 1; (i++ 和 ++i 的区别）
try {
for (Object e; r < end; r++)
// 如果 r 位置的元素符合 complement ，将 r 位置的元素写入 w 位置的元素，w 向后挪一位
// 如果不符合，w 不动，进行下次循环
if (c.contains(e = es[r]) == complement)
es[w++] = e;
} catch (Throwable ex) {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
// 如果 cntains()方法抛出异常，则将 r 位置后的数据写到 w 位置后
// 这样我们剩余没有遍历的元素挪过去之后覆盖了跳过的元素，保证数组中不会多出来一些奇怪的元素
System.arraycopy(es, r, es, w, end - r);
w += end - r;
// 把异常继续抛出去
throw ex;
} finally {
// 增加修改次数
modCount += end - w;
// 尾部无用元素赋值为null
shiftTailOverGap(es, w, end);
}
return true;
}
/**
* 在数组 hi 和 lo 的位置各剪一刀，丢掉 hi 和 lo 中间的部分，然后把 hi 这一头和
* lo 那一头连起来
*
* @param es 数组
* @param lo 开始位置
* @param hi 结束位置
*/
private void shiftTailOverGap(Object[] es, int lo, int hi) {
// 从 hi 位置开始的元素移动到 lo 位置后
System.arraycopy(es, hi, es, lo, size - hi);
// 将末尾没用的位置置空
for (int to = size, i = (size -= hi - lo); i < to; i++)
es[i] = null;
}
批量移除元素的大致执行过程
批量移除给定范围内的多个元素 void removeRange(int fromIndex, int toIndex)
/**
* 批量移除 [fromIndex, toIndex) （前闭后开）范围内的多个元素
*/
protected void removeRange(int fromIndex, int toIndex) {
// 参数不正确
if (fromIndex > toIndex) {
throw new IndexOutOfBoundsException(
outOfBoundsMsg(fromIndex, toIndex));
}
// 修改次数+1
modCount++;
// 该方法见上文
shiftTailOverGap(elementData, fromIndex, toIndex);
}
根据条件移除元素 boolean removeIf(Predicate<? super E> filter)
略...
4.6 查找单个元素
int indexOf(Object o) 查找第一个指定元素的索引
public int indexOf(Object o) {
return indexOfRange(o, 0, size);
}
int indexOfRange(Object o, int start, int end) {
Object[] es = elementData;
// o 为null的情况
if (o == null) {
for (int i = start; i < end; i++) {
if (es[i] == null) {
return i;
}
}
// o 不为null的情况
} else {
for (int i = start; i < end; i++) {
if (o.equals(es[i])) {
return i;
}
}
}
// 没找到返回 -1
return -1;
}
int indexOf(Object o) 查找最后一个指定元素的索引
public int lastIndexOf(Object o) {
return lastIndexOfRange(o, 0, size);
}
int lastIndexOfRange(Object o, int start, int end) {
Object[] es = elementData;
if (o == null) {
for (int i = end - 1; i >= start; i--) { // 倒序
if (es[i] == null) {
return i;
}
}
} else {
for (int i = end - 1; i >= start; i--) {
if (o.equals(es[i])) {
return i;
}
}
}
return -1;
}
int indexOf(Object o) 获得指定位置的元素
public E get(int index) {
// 校验
Objects.checkIndex(index, size);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
4.7 设置指定位置的元素
E set(int index, E element)
public E set(int index, E element) {
// 校验
Objects.checkIndex(index, size);
// 记录旧值
E oldValue = elementData(index);
// 赋值新值
elementData[index] = element;
// 返回旧值
return oldValue;
}
5 其他方法
5.1 转换为数组
Object[] toArray() 转换为Object[]
// ArrayList.java
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
// Arrays.java
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
Object[] toArray() 转换为给定泛型的数组
public <T> T[] toArray(T[] a) {
// 如果传入的数组大小没有 size 大
if (a.length < size)
// Make a new array of a's runtime type, but my contents:
// 直接复制一个新数组返回
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
// 把 elementData 的数据复制到 a 中
System.arraycopy(elementData, 0, a, 0, size);
// 如果 a 的长度 大于 size ，就。。把 size 位置设置为 null ？？？
if (a.length > size)
a[size] = null;
return a;
}
对中间a[size] = null的疑惑作者在方法注释中有写到：
* <p>If the list fits in the specified array with room to spare
* (i.e., the array has more elements than the list), the element in
* the array immediately following the end of the collection is set to
* {@code null}. (This is useful in determining the length of the
* list <i>only</i> if the caller knows that the list does not contain
* any null elements.)
如果调用者明确知道数组中没有空元素，那么这对于确定list的length很有帮助。emmm...插入null值作为一个标记..或许调用者可以在遍历数组时判断元素为空就不再遍历了？？
5.2 求哈希值
int hashCode()
public int hashCode() {
// 记录开始前数组修改次数
int expectedModCount = modCount;
// 获取哈希值
int hash = hashCodeRange(0, size);
// 并发修改校验
checkForComodification(expectedModCount);
return hash;
}
int hashCodeRange(int from, int to) {
final Object[] es = elementData;
// 校验
if (to > es.length) {
throw new ConcurrentModificationException();
}
// 计算hash值
int hashCode = 1;
for (int i = from; i < to; i++) {
Object e = es[i];
// 为什么要乘31，看下文参考资料
hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
}
return hashCode;
}
/**
* 并发修改校验，如果操作前数组的修改次数和操作后的修改次数不一致，
* 则抛出异常
*/
private void checkForComodification(final int expectedModCount) {
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
参考资料：田小波的技术博客——科普：String hashCode 方法为什么选择数字31作为乘子
5.3 判断相等
boolean equals(Object o)
public boolean equals(Object o) {
// 与自己本身相比，直接返回 true
if (o == this) {
return true;
}
// 非 List 类型，直接返回 false
if (!(o instanceof List)) {
return false;
}
// 记录当前数组修改次数
final int expectedModCount = modCount;
// ArrayList can be subclassed and given arbitrary behavior, but we can
// still deal with the common case where o is ArrayList precisely
// 根据类型是否是ArrayList，选择不同的比较方式
// ArrayList可以遍历数组，性能更优，而其他List只能用迭代器。
boolean equal = (o.getClass() == ArrayList.class)
? equalsArrayList((ArrayList<?>) o)
: equalsRange((List<?>) o, 0, size);
// 并发修改校验
checkForComodification(expectedModCount);
return equal;
}
private boolean equalsArrayList(ArrayList<?> other) {
// 记录传入list的修改次数
final int otherModCount = other.modCount;
final int s = size;
boolean equal;
// 先判断 size 是否相等
if (equal = (s == other.size)) {
final Object[] otherEs = other.elementData;
final Object[] es = elementData;
// 校验并发修改
if (s > es.length || s > otherEs.length) {
throw new ConcurrentModificationException();
}
// 遍历，比较每个对应元素是否相等
for (int i = 0; i < s; i++) {
if (!Objects.equals(es[i], otherEs[i])) {
equal = false; // 如果不相等跳出循环
break;
}
}
}
// 校验传入list的并发修改
other.checkForComodification(otherModCount);
return equal;
}
boolean equalsRange(List<?> other, int from, int to) {
final Object[] es = elementData;
// 并发修改校验
if (to > es.length) {
throw new ConcurrentModificationException();
}
// 用迭代器遍历逐个对比
var oit = other.iterator();
for (; from < to; from++) {
// 如果oit没有下一个元素或当前元素不相等，直接返回 false
if (!oit.hasNext() || !Objects.equals(es[from], oit.next())) {
return false;
}
}
// 返回oit是否还有剩余的元素。如果还有当然是不相等的
return !oit.hasNext();
}
5.4 克隆
Object clone()
public Object clone() {
try {
// 调用父类克隆方法
ArrayList<?> v = (ArrayList<?>) super.clone();
// 拷贝新数组
v.elementData = Arrays.copyOf(elementData, size);
// 修改次数置为 0
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
// 实现Cloneable接口后不会再发生了
throw new InternalError(e); // JVM 意外内部错误
}
}
5.5 清空
void clear()
public void clear() {
// 修改次数 + 1
modCount++;
// 遍历置空 倒序
final Object[] es = elementData;
for (int to = size, i = size = 0; i < to; i++)
es[i] = null;
}
5.6 序列化与反序列化
void writeObject(java.io.ObjectOutputStream s) 序列化
@java.io.Serial
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
int expectedModCount = modCount;
// 序列化 非静态，非 transient 属性
s.defaultWriteObject();
// 写入 size ，为了兼容 clone() 方法 ？？？
s.writeInt(size);
// Write out all elements in the proper order.
// 逐个写入元素
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
// 并发修改校验
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
elementData是加了transient关键字的，序列化时会只序列化size大小的真实使用的数组，不会序列化elementData预留出的那一部分。节省时间和空间。
void readObject(java.io.ObjectOutputStream s)
@java.io.Serial
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// 反序列化 非静态，非 transient 属性
s.defaultReadObject();
// Read in capacity
// 读取 size ，但忽略不用了
s.readInt(); // ignored
if (size > 0) {
// like clone(), allocate array based upon size not capacity
// emmm....
SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size);
Object[] elements = new Object[size];
// 逐个读取元素
for (int i = 0; i < size; i++) {
elements[i] = s.readObject();
}
elementData = elements;
} else if (size == 0) {
// size 是 0 的话使用空数组
elementData = EMPTY_ELEMENTDATA;
} else {
throw new java.io.InvalidObjectException("Invalid size: " + size);
}
}
6 End
省略了一些不常用的或简单的方法，以及逻辑重点不在ArrayList中的方法（比如sort()排序）。
