ArrayList源码解析
2021/7/16 14:05:55
本文主要是介绍ArrayList源码解析，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
ArrayList
可调节列表容量大小的，基于数组实现的容器，元素可以是 null，该类大致上同 vector相似，但没有同步
其中 size(), isEmpty(), get(), set(), iterator(), listIterator()等方法都是 O(1)的时间复杂度；add()方法是 O(N)的时间复杂度
每个 ArrayList实例都有一个 容量（Capacity），即内部维护的数组最多存储元素的数量
当有元素加入到 ArrayList中的时候，它的容量能实现自动增长，可以使用 ensureCapacity()方法保证容量足够
我们不能保证通过 快速失败机制来维护它的线程安全
一些初始化的信息
/**
* 一些初始化的信息
*/
// 序列化 ID
private static final long serialVersionUID = 8683452581122892189L;
// 初始容量
private static final int DEFAULT_CAPACITY = 10;
// 用于空实例的共享数组实例
private static final Object[] EMPTY_ELEMENTDATA = {};
// 用于默认大小的空实例的数组，区别于 EMPTY_ELEMENTDATA[] 数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 真实存储 ArrayList元素的数组缓冲区，其长度即为 ArrayList的容量，在第一次添加元素时就会扩展为 DEFAULT_CAPACITY
transient Object[] elementData;
// ArrayList的实际长度（保存的元素的个数）
private int size;
// 当前 ArrayList被结构化修改的次数，结构化修改指的是 修改了列表长度或者以某种方式扰乱了列表使之在迭代时不安全的操作
// 该字段由 Iterator或者 ListIterator或返回以上二者的方法使用，如果这个值发生了意料之外的改变，迭代器就会报并发修改异常。这提供了快速失败解决方案
// 在其子类下使用 modCound是可选择的（protected修饰了），如果子类希望提供快速失败的迭代那么它也可以在它的 add()等结构化修改方法中修改 modCount的值，单次的结构修改方法的调用最多只能修改一次 modCount的值；但是如果不希望提供 快速失败 的迭代器，子类可以忽略 modCount
// 我之前一直以为 modCount定义在 迭代器中。。。，现在才知道定义在被迭代的对象内
protected transient int modCount; // 定义在 AbstractList中
// 列表最大能分配的量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
构造方法
/**
* 构造方法
*/
// 空参构造
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 有参构造，指定集合的长度创建一个 ArrayList
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
// 依据输入的大小，初始化 elementData[] 数组（真实存储元素的数组）
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// 使用默认的大小（也就是 10）
this.elementData = EMPTY_ELEMENTDATA;
} else {
// 针对负数等随便输入的东西，报错非法参数异常（非法的初始容量：xxx）
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
// 有参构造，指定一个已有的集合创建 ArrayList（原集合内的元素会添加到 新建的ArrayList中），此时 ArrayList的长度等于 传入的集合的长度
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 {
// 如果传参的集合为空，当前 ArrayList的 elementData[]数组就是空的
this.elementData = EMPTY_ELEMENTDATA;
}
}
针对 第三种构造方法的实验：
- 传入非空的集合，发现 ArrayList的容量等于传入的集合内的元素个数（因为在 ArrayList内部 elementData是 private修饰的，且未提供 get方法，所以使用 反射暴力获取其长度）
- 传入空集合，ArrayList长度也为 0
-
有一个很有趣的点：
- 空参创建 ArrayList时，其 容量为 0，而一旦往里面加入元素之后，容量就会变成 10（默认容量）
- 而针对传入 集合作为参数的构造器创建的 ArrayList，当作为参数的集合为空时，ArrayList的容量为 0；但是向 ArrayList内添加元素之后，容量就是添加的元素的个数，不是 ArrayList默认的扩容规则
-
针对这个问题继续进行实验：
-
向两个arraylist内分别添加 13个元素，发现 由集合传参构造的 ArrayList的容量依旧等于传参个数；空参构造的 ArrayList容量符合正常的扩容规则，即 原容量 * 1.5
-
常见方法
void trimToSize()
缩减列表的大小为当前已存的元素的个数
public void trimToSize() {
// 因为调整列表的容量是结构化修改，所以需要变更 modCount的值
modCount++;
// 如果当前的元素数 小于 最大容量
if (size < elementData.length) {
// 修改最大容量为当前元素的个数
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
// 使用这种写法来实现数组变小： elementData = Arrays.copyOf(elementData, size) 感觉好神奇啊。。
}
}
void ensureCapacity(int minCapacity)
增加当前列表的容量，至少是达到能够容纳所有元素的容量
public void ensureCapacity(int minCapacity) { // elementData和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA（就是一个空数组）相等时 minExpand = 10，否则等于 0 // 意思就是说，只有刚开始，ArrayList还没添加元素的时候，minExpand会是 10；添加过元素之后它就不干净了，minExpand = 0 了 int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) // any size if not default element table ? 0 // larger than default for default empty table. It's already // supposed to be at default size. : DEFAULT_CAPACITY; // 至少你调整后的容器大小不能比元素数量小，对吧。。 if (minCapacity > minExpand) { // 定义放在下面 ensureExplicitCapacity(minCapacity); }}// 主要为了底层数组扩容private void ensureExplicitCapacity(int minCapacity) { // 因为是结构性的修改，所以需要改变 modCount的值 modCount++; // overflow-conscious code // 判断一下要不要扩容，如果改变之后的容量大于当前数组最大容量，就要扩容了呀 if (minCapacity - elementData.length > 0) // 定义放在下面 grow(minCapacity);}// 底层 ArrayList扩容的方法，其实就是 elementData[]数组扩大的方法private void grow(int minCapacity) { // overflow-conscious code // 获取原来的容量 int oldCapacity = elementData.length; // 获取常规的扩容大小 int newCapacity = oldCapacity + (oldCapacity >> 1); // 如果常规扩容之后还不够大，索性就你要多少就给你多少吧 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; // MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8，也就是说如果你要的容量很大，那么就调用 另一个方法 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);}// 索求得太多了呀。。。private static int hugeCapacity(int minCapacity) { // 判断 minCapacity是否小于0 ？ if (minCapacity < 0) // overflow throw new OutOfMemoryError(); // MAX_VALUE = 0x7fffffff；MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8 = 0x7fffffff - 8 ... return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;}
int size()
返回当前列表的元素个数
注意：
- 这里返回的是 元素的个数，而不是 列表的 容量
- 列表的 容量（Capacity）默认只能通过 elementData[]数组的 length获取，但是 elementData[]是 private修饰的，所以只能通过 反射（至少我只会反射获取）
public int size() { // 返回当前 list的 elment的数量 // private int size; 保存 list的实际元素个数 return size;}
// 反射获取 elementData[]数组的方法
public static int getArrayListCapacity(ArrayList<?> arrayList) {
Class<ArrayList> arrayListClass = ArrayList.class;
try {
Field field = arrayListClass.getDeclaredField("elementData");
field.setAccessible(true);
Object[] objects = (Object[]) field.get(arrayList);
return objects.length;
} catch (NoSuchFieldException e) {
e.printStackTrace();
return -1;
} catch (IllegalAccessException e) {
e.printStackTrace();
return -1;
}
}
boolean isEmpty()
判断 列表是否为空
public boolean isEmpty() {
return size == 0;
}
boolean contains(Object o)
判断列表中是否包含与指定值相同的元素，如果有，则返回 true；否则，返回 false
public boolean contains(Object o) { // 定位传参值的位置，具体解释在下一个 return indexOf(o) >= 0;}
int indexOf(Object o)
返回在列表中 与指定值相等的元素 第一次出现索引位置；如果 该值不存在，就返回 -1
public int indexOf(Object o) {
// 先判断 o是否为 null
if(o == null) {
// 如果是 null，就遍历检索整个 elementData[]数组，寻找 null值，返回数组下标
for(int i = 0; i < size; i++) {
if(elementData[i] == null) {
return i;
}
}
} else {
// 否则，遍历 elementData[]数组，调用 equals()方法，判断是否存在等值元素，返回数组下标
for(int i = 0; i < size; i++) {
if(o.equals(elmentData[i])) {
return i;
}
}
}
// 如果都没找到，就返回 -1
return -1;
}
int lastIndexOf(Object o)
类似 indexOf(Object o)方法，只是返回的是 列表中元素最后出现的 数组下标；如果列表中不存在，则返回 -1
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;}
Object clone()
返回一个列表实例的浅克隆拷贝，即声明了另一个指向 堆中列表的引用
也就是说，如果你在 list1中修改了某个元素，那么在 list中也会变化，因为二者指向同一个地址
public Object clone() { try { // 调用 Object类下的 clone()方法，强转为一个 ArrayList ArrayList<?> v = (ArrayList<?>) super.clone(); // 拷贝新列表中的 elmentData[]数组 v.elementData = Arrays.copyOf(elmentData, size); // 设置新数组的 modCount次数为 0 v.modCount = 0; return v; } catch(CloneNotSupportedException e) { // this shouldn't happen, since we are cloneable throw new InternelError(e); }}
Debug后发现：
如果要实现深克隆，可以采用如下代码，将具体的内部的元素也克隆一份
@Test
public void testClone2() throws CloneNotSupportedException {
ArrayList<Student> list = new ArrayList<>();
list.add(new Student("张三", 23));
list.add(new Student("李四", 24));
ArrayList<Student> listCopy1 = (ArrayList<Student>) list.clone();
System.out.println(list == listCopy1);
System.out.println(list.equals(listCopy1));
ArrayList<Student> listCopy2 = new ArrayList<>();
for (Student student : list) {
listCopy2.add((Student) student.clone());
}
System.out.println(listCopy2);
}
Object[] toArray()
返回一个新的数组，包含了列表中的所有的元素（依照列表内的顺序排列）
返回的数组和原来的列表无关，也就是说，对数组内元素的修改不影响列表内元素的值
该方法充当了 集合类和 数组类之间的桥梁
public Object[] toArray() { return Arrays.copyOf(elementData, size);}
<T> T[] toArray(T[] a)
类似上面的那个方法，也会把 列表转换成 数组
区别在于，这个数组不再是 Object类型，而是指定的类型
- 如果列表内的元素符合传入的参数，那么就会以那个参数作为数组元素类型
- 如果不符合，则会新建一个以运行类型为数组类型的数组
如果传入的数组的容量大于列表的容量，则在数组中紧跟在列表最后一个元素之后的元素全部会被设置为 null
这样有助于确定列表的容量
@SuppressWarnings("unchecked")public <T> T[] toArray(T[] a) { // 如果传入的数组比列表小，就会返回一个和列表一样大的（注意 是 和列表一样大的）数组，也就是说会返回一个更大的数组 if(a.length < size) { return (T[]) Arrays.copyOf(elementData, size, a.getClass()); } // 如果数组的大小比列表大，就直接将 elementData[]中的值拷贝到 a[]即可，拷贝的长度为 size个，都是从 0开始拷贝 System.arrayCopy(elmentData, 0, a, 0, size); // 会有很神奇的一幕：如果数组比列表大(数组为10个单位，列表长3个单位)，且数组已经初始化了，则：arr[0] ~ arr[3]都是列表中的值，arr[4]会变成 null，arr[5] ~ arr[9] 是数组的原来的值；估计是为了方便之后遍历判断吧 if(a.length > size) { a[size] = null; } return a;}
这部分源码比较难
-
泛型方法
-
定义泛型方法需要在返回值前加上泛型参数，如：
public <T> T[] method(T a) { ... } -
描述 类时，使用
E，如：ArrayList<E>，它与泛型方法中的T不同 -
父类对象能够显示的强制转换为子类对象的前提是：该对象本质上是子类（或者孙子类等）对象
// o是一个子类对象 String的引用Object o = new String("abc");// 此时，强转不会出错String s = (String) o;// 但是如果如下定义，o不是子类对象的引用o = new Object();// 此时就会出错s = (String) o;/*也就是说，至少要有多态那样的样子，父类引用指向子类对象之后，父类引用才能够使用强制类型转换变回子类引用*/ -
数组也是对象，由 JVM提供定义和初始化。但是 Object[] 和 String[] 之间没有继承关系，但是 它们之间存在协变，使得数组对象也能像子父类一样转换（Java中的强制类型转换一般针对的只是单个对象，数组的强转一般都不好使）
Object[] o = new String[]{"abc"}; String[] s = (String[]) o; // 此时不会出错 o = new Object[]{}; s = (String[]) o; // 此时会出错
-
-
而之所以 将方法名定义为
public <T> T[] toArray(T[] a)，是由于泛型会在编译期被擦除，实际上 ArrayList中 elementData[]数组就是一个 Object[]数组transient Object[] elementData;- 那为什么不把方法名写成
public E toArray()呢？因为 泛型E会被擦除，方法实际返回的仍然是 Object[] 而不是 String[]，最后是由编译器分析 列表对象声明后追加强制转换到结果上的，但是这样的转换是不能进行的！ - 但是当加入了参数
T[] t之后，会在插入时就把每个元素逐个强制转换为 String，再加入到一个 String[]数组中，然后返回 Object[]，再由编译器强转为 String[]，而这么做是可行的！
- 那为什么不把方法名写成
-
Arrays.copyOf()这个方法有很多重载形式-
public static <T> T[] copyOf(T[] original, int newLength)：指定长度进行数组拷贝，空的部分用 null来填充，这样能保证定长；两个数组能保证内部元素相同 -
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType)：将原来 U类型的数组，复制成指定长度的 T类型的数组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; } -
public static byte[] copyOf(byte[] original, int newLength、public static short[] copyOf(short[] original, int newLength)、public static int[] copyOf(int[] original, int newLength)、public static long[] copyOf(long[] original, int newLength)、public static char[] copyOf(char[] original, int newLength)、public static float[] copyOf(float[] original, int newLength)、public static double[] copyOf(double[] original, int newLength)、public static boolean[] copyOf(boolean[] original, int newLength)：就直接指定了数组拷贝的类型/** * 以 int型拷贝为例 */ public static int[] copyOf(int[] original, int newLength) { int[] copy = new int[newLength]; System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy; }
-
-
System.arraycopy(elmentData, 0, a, 0, size)是一个本地方法，方法原型为：public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);src：源数组srcPos：源数组中开始复制的下标值dest：目标数组destPos：目标数组中开始复制的下标值length：复制多少个元素
E get(int index)
返回列表中 指定位置的元素
public E get(int index) { // 检查索引是否正常，定义放在下面 rangeCheck(index); // 返回 elementData[]数组中，该下标的元素 return elementData(index);}private void rangeCheck(int index) { // 如果指定的值大于数组的最大下标，就抛出异常 if(index >= size) { // 抛出异常，outOfBoudnsMsg()方法定义放在下面 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }}private String outOfBoundsMsg(int index) { return "Index: " + index + ", Size: " + size;}
E set(int index, E element)
使用传入的参数，替换指定位置的元素，并返回原来的值
public E set(int index, E element) {
// 同 get()方法一样，先检查 index是不是比 size小
rangeCheck(index);
// 获取该位置上原来的值
E oldValue = elementData[index];
// 在 elementData[]数组中替换该位置下的值
elementData[index] = element;
// 返回原来的值
return oldValue;
}
boolean add(E e)
在列表的末尾添加元素，事实上就是在 elementData[]数组中添加下一个值
public boolean add(E e) {
// 判断列表容量够不够，实际判断 elementData[]数组里还有没有多余的空闲空间
ensureCapacityInternal(size + 1); // increments modCount
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
// 确保容量够用，calculateCapacity()计算扩容
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 如果列表是默认空参构造创建的，并且本次是第一次 add
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 那么会直接把容量加到 10
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 否则就正常 +1就行
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
// 结构化修改，增加该值，保证该集合是快速失败的
modCount++;
// overflow-conscious code
// 判断是否会溢出
if (minCapacity - elementData.length > 0)
// 如果会溢出，就需要扩容了（也就是说 原有的 size+1 > capacity了，装不下了）
grow(minCapacity);
}
// grow()方法在之前的 ensureCapacity(int minCapacity)方法中解释过了
void add(int index, E element)
在列表的指定位置插入指定的元素
public void add(int index, E element) {
// 专门为这个 add()方法写了一个检查范围的函数，面子够大的。。
rangeCheckForAdd(index);
// 确定容量
ensureCapacityInternal(size + 1); // increments modCount !!
// 复制数组，将从插入位置之后开始的内容全部后移一位
System.arraycopy(elementData, index, elementData, index + 1, size - index);
// 设置值
elementData[index] = element;
size++;
}
private void rangeCheckForAdd(int index) {
// 如果要插入的索引 大于 当前最大索引 或者 小于0
if (index > size || index < 0)
// 抛出异常
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
对比 E set(int index, E element)方法：
- set()方法单纯的改变原来的值，add()方法会在原有的列表内部（注意是已有元素列表的里面，index<size的情况下）添加元素
- 看起来 add()方法更适合用来进行 插排等排序操作
- 因为 add()方法会对向数组内添加额外的元素所以，需要检验扩容 ensureCapacity()
E remove(int index)
移除列表中指定位置的元素，数组中后续的元素都会左移一位，并且返回被移除的元素
public E remove(int index) {
// 检查索引越界
rangeCheck(index);
// 结构化修改，变更 modCount的值
modCount++;
// 获取旧的值
E oldValue = elementData(index);
// 计算需要移动的数字的个数
int numMoved = size - index - 1;
if(numMoved > 0) {
// 通过数组拷贝的形式，将从待移除位置开始往后的所有元素前移一位
System.arraycopy(elementData, index+1, elementData, index, numMoved);
}
// 将最后一个元素置为 null（因为数组拷贝的关系，在 elementData[size-1] 和 elementData[size-2]中存的都是最后一个值，重复了）
elementData[--size] = null; // clear to let GC do its work
// 返回旧的值
return oldValue;
}
boolean remove(Object o)
如果列表中存在和指定的值相同的元素，那么就移除其中第一个出现的元素，返回 true；
如果不存在，啥都不干，返回 false
public boolean remove(Object o) {
// 如果待移除的元素是 null
if(o == null) {
// 遍历整个列表寻找 null值
for(int index = 0; index < size; index++) {
if(elementData[index] == null) {
// 通过索引移除，只是在 fastRemove()基本可以保证索引的合规
fastRemove(index);
return true;
}
}
// 如果元素不是 null
} else {
// 同样遍历列表，通过 equals()方法进行判断
for(int index = 0; index < size; index++) {
if(o.equals(elementData[index])) {
// 快速移除
fastRemove(index);
return true;
}
}
}
// 没找到呀，那就返回 false吧
return false;
}
// 对比 E remove(int index)方法，删去了索引越界检查和旧值返回
private void faseRemove(int index) {
// 修改 modCount值
modCount++;
// 计算需要移动的元素的个数
int numMoved = size - index - 1;
if(numMoved > 0) {
// 通过数组拷贝进行移动
System.arraycopy(elementData, index+1, elementData, index, numMoved);
}
// 把最后一个重复的项设置为 null
elementData[--size] = null // clear to let GC do its work
}
void clear()
清除列表中的所有元素
public void clear() {
// 修改 modCount的值
modCount++;
// 遍历整个数组，把把每个引用都设置为 null
// clear to let GC do its work
for(int i = 0; i < size; i++) {
elementData[i] = null;
}
// 设置列表的长度为 0（列表为空）
size = 0;
}
.
boolean addAll(Collection<? extends E> C)
将作为参数传入的集合内的元素 全部添加到 elementData[]数组的尾部
public boolean addAll(Collection<? extends E> c) {
// 将传入参数的集合转为数组
Object[] a = c.toArray();
// 获取待插入的元素的个数
int numNew = a.length;
// 确保容量足够，也就是说保证 elementData[]数组能够存下 size+newNum个元素
ensureCapacityInternal(size + newNum); // Increments modCount
// 通过数组复制进行插入，将 a[]数组从 0索引开始的 newNum个元素复制到 elementData[]数组中从 size开始的位置
System.arraycopy(a, 0, elementData, size, newNum);
// 修改当前集合中元素的个数
size+=numNew;
// 返回集合是否插入成功，如果传入的集合长度为0，则被认为插入失败
return numNew != 0;
}
boolean 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;
// 确保列表中元素位置够用，即 capacity >= size+numNew
ensureCapacityInternal(size + numNew); // Increments modCount
// 计算指定索引之后的元素每个需要移动几位
int numMoved = size - index;
if(numMoved > 0) {
// 通过数组拷贝的方式，先将列表的 elementData[]数组中的部分元素后移
System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
}
// 通过数组拷贝的方式，将指定集合中的元素拷贝到当前 elementData[]数组中，实现 addAll的效果
System.arraycopy(a, 0, elementData, index, numNew);
// 更新列表中元素的个数
size += numNew;
// 返回是否添加正常
return numNew != 0;
}
boolean removeAll(Collection<?> c)
移除当前列表中，同时存在与指定集合中的元素
public boolean removeAll(Collection<?> c) {
// 判断集合 c引用非空
Obejcts.retuireNonNull(c);
// 调用批量删除的方法，并且返回最终结果
return batchRemove(c, false);
}
public static <T> T requireNonNull(T obj) {
// 如果参数是 null，就抛出异常
if(obj == null) {
throw new NullPointerException();
}
return obj;
}
private boolean batchRemove(Collection<?> c, boolean complement) {
// 创建一个局部变量，作为 elementData[]的副本
final Object[] elementData = this.elementData;
// r用于遍历整个数组，w用于对具体的位置进行修改
int r = 0, w = 0;
// 修改标志位
boolean modified = false;
try {
// 遍历整个 elementData[]数组
for(; r < size; r++) {
// 传入集合中是否存在和 列表中值相同的元素，通过 complement决定是删去相同的元素还是不同的元素
if(c.contains(elementData[r]) == complement) {
// 通过值的覆盖实现，如果 complement = false
// 也就是说当满足以上条件时，数组内的元素不在集合中，将r处的值赋给w处，w和r都后移一位；
// 如果不满足条件，即元素需要删除，就让 w不动，r后移
// 这样可以实现：把需要移除的数据都替换掉，不需要移除的数据前移
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
// w之前的所有元素都是需要保留的元素，其之后的元素都可以重复的，就可以删去了
for(int i = w; i < size; i++) {
elementData[i] = null;
}
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
举个栗子
通过 Debug，我们能看到：
boolean retainAll(Collection<?> c)
在当前列表中，只保留在指定集合中出现过的元素
也就是说，保留交集
public boolean retainAll(Collection<?> c) {
// 保证 c不是 null
Objects.requireNonNull(c);
// 相比 removeAll()，这里将 complement值设置为 true，表示在执行 batchRemove()方法时，只会将指定集合中出现的内容保留
return batchRemove(c, true);
}
void writeObject(java.io.ObjectOutputStream s)
ArrayList的序列化方法，保存当前 list的实例状态并以流的形式写出去
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException {
// 先记录当前的 modCount值，方便与之后进行比较，保证在写出时内容没有改变过
// write out element count, and any hidden stuff
int expectedModCount = modCount;
// 写出流中的非静态和非瞬态的字段
s.defaultWriteObject();
// write out size as capacity for behavioural compatibility with clone()
// 将列表容量写出
s.writeInt(size);
// write out all elements in the proper order
// 循环遍历列表，将其中的每一个元素都写出
for(int i = 0; i < size; i++) {
s.writeObject(element[i]);
}
// 如果写完之后发现，中途有其他线程修改的了列表中的内容，就抛出并发修改异常
if(modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
void readObject(java.io.ObjectOutputStream s)
通过对象输入流反序列化一个对象，即重新构建一个 list
private void readObject(java.io.ObjectOutputStream s) throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// Read in size, and any hidden stuff
s.defaultReadObject();
// Read in capacity
s.readInt(); // ignored
if(size > 0) {
// be like clone(), allocate array based upon size not capacity
int capacity = calculateCapacity(elementData, size);
SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
ensureCapacityInternal(size);
Object[] a = elementData;
// Read in all elements in the proper order
for(int i = 0; i < size; i++) {
a[i] = s.readObject();
}
}
}
ListIterator<E> listIterator(int index)
返回一个从指定位置开始的列表迭代器
public ListIterator<E> listIterator(int index) {
// 判断索引值是否合理
if(index < 0 || index > size) {
throw new IndexOutOfBoundsException("Index: " + index);
}
return new ListItr(index);
}
ListIterator<E> listIterator()
返回一个包含全部元素的列表迭代器
public ListIterator<E> listIterator() {
// 直接返回全部元素的迭代器
return new ListItr(0);
}
Iterator<E> iterator()
返回一个包含全部元素的普通迭代器
public Iterator<E> iterator() {
return new Itr();
}
List<E> subList(int fromIndex, int toIndex)
根据给定的索引值，获取当前列表的子列表（两端元素都包含的，是闭区间）
但是，如果 fromIndex == toIndex，则会返回一个空集合
本质上是拷贝，子列表中对元素的非结构性修改会影响到父列表，反之同理
对子列表的操作和其他所有正常的 arraylist一样
可以采取如下方法移除列表中的部分元素：list.subList(from, to).clear()
public List<E> subList(int fromIndex, int toIndex) { // 检验起始索引和结束索引是否合理 subListRangeCheck(fromIndex, toIndex, size); // 构造一个新的列表类，SubList是 AbstractList的子类，和 ArrayList是兄弟关系 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 + ")"); }}
※void forEach(Consumer<? super E> action)
可以使用 forEach配合 lambda表达式
public void forEach(Consumer<? super E> action) {
// 判断非空引用
Objects.requireNonNull(action);
// 获取修改值
final int expectedModCount = modCount;
final E[] elementData = (E[]) this.elementData;
// 遍历每个元素，对每一个元素都调用 accpet()方法进行处理
for(int i = 0; modCount == expectedModCount && i < size; i++) {
action.accept(elementData[i]);
}
if(modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
※Spliterator<E> spliterator()
创建一个 延迟绑定和 快速失败的，确定大小的，且子迭代器也确定大小的，有序的一个可拆分迭代器，它也是用于迭代遍历数组的
但是有别于 Iterator，它用于并行操作，其数据源可以是数组、集合、IO通道或生成器函数
它可以单独遍历元素 tryAdvance()，也可以批量遍历元素 forEachRemainning()，并且可以调用trySplit()方法进行迭代器拆分，使之变成上一个 Spliterator的一半大小
每个 Spliterator实例中都定义了 int characteristics()方法，返回当前实例的一个特征集，这个集合包括：
public static final int ORDERED = 0x00000010：表示迭代器会按照其原始顺序迭代其中的元素public static final int DISTINCT = 0x00000001：表示迭代器中的元素是没有重复的public static final int SORTED = 0x00000004：表示迭代器是按照某种方式排序后顺序迭代其中的元素public static final int SIZED = 0x00000040：表示迭代器的元素是个数是确定的public static final int NONNULL = 0x00000100：表示迭代器中没有 null元素public static final int IMMUTABLE = 0x00000400：表示元素不可变public static final int CONCURRENT = 0x00001000：表示迭代器可多线程操作public static final int SUBSIZED = 0x00004000：表示子迭代器也是确定大小的
如果一个迭代器没有报告 IMMUTABLE或者 CONCURRENT特征时，其绑定数据源后会检查数据源的结构化改动
后绑定的迭代器指其 绑定数据源的行为 发生在其第一次遍历、第一次拆分、第一次查询大小时，而不是在迭代器创建后立刻绑定数据源。
和其它迭代器一样，绑定前对源的修改可以反应在迭代器遍历过程中，而绑定后的对源的修改会导致ConcurrentModificationException异常。
public Spliterator<E> spliterator() {
return new ArrayListSpliterator<>(this, 0, -1, 0);
}
boolean removeIf(Predicate<? super E> filter)
删除满足给定谓词条件的所有元素，默认使用 iterator遍历集合中的元素，并且使用 iterator.remove()删除匹配的元素
public boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
// figure out which elements are to be removed
// any exception thrown from the filter predicate at this stage
// will leave the collection unmodified
int removeCount = 0;
// BitMap的底层维护了一个 long[]数组
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;
// 如果存在需要移除的元素
if (anyToRemove) {
// 计算移除后，剩下的元素个数
final int newSize = size - removeCount;
// 遍历 bitSet，取出之前存入的需要删除的元素的索引
for (int i = 0, j = 0; (i < size) && (j < newSize); i++, j++) {
// nextClearBit()返回下一个空的位置，也就是说，把要保留的全部左移
i = removeSet.nextClearBit(i);
elementData[j] = elementData[i];
}
// 将多余的元素设置为null
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;
}
void replaceAll(UnaryOperator<E> operator)
通过 operator对每个元素进行加工，并将结果替换列表中原来的值
public void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final int expectedModCount = modCount;
final int size = this.size;
// 遍历每一个元素，对其进行 apply()方法的操作，并且再赋值给自己
for(int i = 0; expectedModCount == modCount && i < size; i++) {
elementData[i] = operator.apply((E) elementData[i]);
}
if(modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
// 函数式接口，代表对某一个操作数的一次操作，参数和返回值都必须是同一类型
@FunctionalInterface
public interface UnaryOperator<T> extends Function<T, T> {
static <T> UnaryOperator<T> identity() {
return t -> t;
}
}
void sort(Comparator<? super E> c)
通过传入的比较器对列表进行排序
public void sort(Comparator<? super E> c) {
final int expectedModCount = modCount;
// 底层调用数组的排序方法
Arrays.sort((E[]) elementData, 0, c);
if(modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
// 根据给定的比较准则（Comparator），在指定的范围内（范围 前开后闭），对数组内的元素进行排序
// 该排序是稳定的，相同值的元素不会发生交换
public static <T> void sort(T[] a, int fromIndex, int toIndex, Comparator<? super T> c) {
if(c == null) {
// 该方法内部也和下面的判断类似，只不过是使用默认的比较器实现
sort(a, fromIndex, toIndex);
} else {
// 底层为 mergeSort()归并排序，分而治之
rangeCheck(a.length, fromIndex, toIndex);
if(LegacyMergeSort.useRequested) {
// 底层为 binarySort()二叉排序
legacyMergeSort(a, fromIndex, toIndex, c);
} else {
TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0);
}
}
}
常用内部类
private Class Itr implements Iterator<E>
是对 AbstractList.Itr的一个优化版本
private class Itr implements Iterator<E> {
// 下一个元素的索引值
int cursor; // index of next element to return
// 上一个返回的元素的索引，如果没有就是 -1
int lastRet = -1; // index of last element returned; -1 if no such
// 并发修改控制字段
int expectedModCount = modCount;
// 空参构造
Itr() {
}
// 判断是否还有下一个元素，正常索引值为 0 ~ size-1，如果 cursor == size，则表示已经全部迭代完了
public boolean hasNext() {
return cursor != size;
}
// 获取下一个元素
@SuppressWarnings("unchecked")
public E next() {
// 判断并发修改状态
checkForComodification();
// 获取下一个将要返回的索引值
int i = cursor;
// 如果下一个索引超出了最大位置，就抛出异常
if (i >= size) {
throw new NoSuchElementException();
}
// 获取当前列表中的 elementData[]数组
Object[] elementData = ArrayList.this.elementData;
// 再检索一遍索引位置，能走到这一步说明前面的 if()判断已经通过了，如果这里通不过则表明，其他线程对列表进行了修改，需要抛出并发修改异常
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
// 修改指向下一个元素的指针
cursor = i + 1;
// 返回数组中位于该索引位置的元素，同时将 lastRet设置为当前索引，并且由于 elementData[]为 Object数组，所以进行强转
return (E) elementData[lastRet = i];
}
// 移除当前元素
public void remove() {
// 如果还没有调用过 next()，就直接 remove()了，就会抛出异常，因为 lastRet默认是 -1
if (lastRet < 0)
throw new IllegalStateException();
// 检查并发修改异常
checkForComodification();
try {
// 调用 list的 remove(int index)方法
ArrayList.this.remove(lastRet);
// 修改下一个索引地址的位置
cursor = lastRet;
lastRet = -1;
// 因为出现了列表元素的移除，在list中肯定会修改 modCount，这里就需要更新 expectedModCount的值
expectedModCount = modCount;
// 思考为什么会有可能出现下标越界异常？
// 如果出问题，肯定在 list.this.remove()方法里，即 lastRet越界了
// 但是正常情况下，lastRet勤勤恳恳，我们之前的代码已经保证了 lastRet > 0了
// 在具体调用 remove()方法里面，也会有 rangeCheck(index)
// 所以猜测肯定是其他线程干的，那么就需要抛出 并发修改异常了呀
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
// JDK8 流式编程
@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
// Consumer过程必须定义，否则就抛出异常
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
// 获取 elementData[]数组的引用
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
// 针对每个元素使用 accept()方法，具体的方法实现依据传入的参数 consumer
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]);
}
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}
// 判断是否出现并发修改情况
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
private class ListItr extends Itr implements ListIterator<E>
是 AbstractList.ListItr的一个优化版
private class ListItr extends Itr implements ListIterator<E> {
// 有参构造，设置开始迭代的位置
ListItr(int index) {
super();
cursor = index;
}
// 判断当前位置之前有没有元素了
public boolean hasPrevious() {
return cursor != 0;
}
// 获取下一个索引的位置（注意：cursor始终指向下一个索引）
public int nextIndex() {
return cursor;
}
// 前一个索引的位置
public int previousIndex() {
return cursor - 1;
}
// 获取前一个元素
@SuppressWarnings("unchecked")
public E previous() {
// 检查并发修改异常
checkForComodification();
// 设置前一个元素的索引
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[lastRet = i];
}
// 进行迭代时，可以直接对底层列表进行修改
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
// 通过调用 list的 set()方法，直接对 list中的值进行修改
ArrayList.this.set(lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
// 进行迭代时，在list中直接插入元素（注意：该位置之后的元素都会后移一位）
public void add(E e) {
checkForComodification();
try {
int i = cursor;
ArrayList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
// 修改 expectModCount，有种监守自盗的感觉，忽然
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}
private class SubList extends AbstractList<E> implements RandomAccess
ArrayList的切片类
private class SubList extends AbstractList<E> implements RandomAccess {
// 虽然AbstractList是抽象类，但这里只是声明，还没有实例化，所以不会报错
private final AbstractList<E> parent;
private final int parentOffset;
private final int offset;
int size;
// 有参构造，一般 parent就是 ArrayList了，所以可以看作是多态
SubList(AbstractList<E> parent,
int offset, int fromIndex, int toIndex) {
this.parent = parent;
this.parentOffset = fromIndex;
this.offset = offset + fromIndex;
this.size = toIndex - fromIndex;
this.modCount = ArrayList.this.modCount;
}
// 切片类的设置方法，设置具体某一索引位置的值
public E set(int index, E e) {
rangeCheck(index);
checkForComodification();
E oldValue = ArrayList.this.elementData(offset + index);
ArrayList.this.elementData[offset + index] = e;
return oldValue;
}
// 获取某一索引位置的元素
public E get(int index) {
rangeCheck(index);
checkForComodification();
return ArrayList.this.elementData(offset + index);
}
// 获取当前切片类的元素个数
public int size() {
checkForComodification();
return this.size;
}
// 向切片类添加元素
public void add(int index, E e) {
rangeCheckForAdd(index);
checkForComodification();
// 实际上会在 arraylist中添加，并且是在指定索引的位置添加（arraylist中的索引值 = 切片类索引值 + 切片的起始值）
parent.add(parentOffset + index, e);
this.modCount = parent.modCount;
this.size++;
}
// 在切片类中移除元素
public E remove(int index) {
rangeCheck(index);
checkForComodification();
// 实际移除 arraylist中的元素
E result = parent.remove(parentOffset + index);
this.modCount = parent.modCount;
this.size--;
return result;
}
// 范围移除
protected void removeRange(int fromIndex, int toIndex) {
checkForComodification();
parent.removeRange(parentOffset + fromIndex,
parentOffset + toIndex);
this.modCount = parent.modCount;
this.size -= toIndex - fromIndex;
}
// 集合添加
public boolean addAll(Collection<? extends E> c) {
return addAll(this.size, c);
}
// 从指定索引开始集合添加
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
int cSize = c.size();
if (cSize == 0)
return false;
checkForComodification();
parent.addAll(parentOffset + index, c);
this.modCount = parent.modCount;
this.size += cSize;
return true;
}
// 迭代
public Iterator<E> iterator() {
return listIterator();
}
public ListIterator<E> listIterator(final int index) {
checkForComodification();
rangeCheckForAdd(index);
final int offset = this.offset;
// 匿名内部类
return new ListIterator<E>() {
int cursor = index;
int lastRet = -1;
int expectedModCount = ArrayList.this.modCount;
public boolean hasNext() {
return cursor != SubList.this.size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= SubList.this.size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (offset + i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[offset + (lastRet = i)];
}
public boolean hasPrevious() {
return cursor != 0;
}
@SuppressWarnings("unchecked")
public E previous() {
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (offset + i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[offset + (lastRet = i)];
}
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = SubList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (offset + i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[offset + (i++)]);
}
// update once at end of iteration to reduce heap write traffic
lastRet = cursor = i;
checkForComodification();
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor - 1;
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
SubList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = ArrayList.this.modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(offset + lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void add(E e) {
checkForComodification();
try {
int i = cursor;
SubList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = ArrayList.this.modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (expectedModCount != ArrayList.this.modCount)
throw new ConcurrentModificationException();
}
};
}
// 对切片再做切片
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, offset, fromIndex, toIndex);
}
private void rangeCheck(int index) {
if (index < 0 || index >= this.size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private void rangeCheckForAdd(int index) {
if (index < 0 || index > this.size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private String outOfBoundsMsg(int index) {
return "Index: " + index + ", Size: " + this.size;
}
private void checkForComodification() {
if (ArrayList.this.modCount != this.modCount)
throw new ConcurrentModificationException();
}
// 搭配 forEachRemaining()使用
public Spliterator<E> spliterator() {
checkForComodification();
return new ArrayListSpliterator<E>(ArrayList.this, offset,
offset + this.size, this.modCount);
}
}
※ static final class ArrayListSpliterator<E> implements Spliterator<E>
实力不够讲不好
static final class ArrayListSpliterator<E> implements Spliterator<E> {
/*
* If ArrayLists were immutable, or structurally immutable (no
* adds, removes, etc), we could implement their spliterators
* with Arrays.spliterator. Instead we detect as much
* interference during traversal as practical without
* sacrificing much performance. We rely primarily on
* modCounts. These are not guaranteed to detect concurrency
* violations, and are sometimes overly conservative about
* within-thread interference, but detect enough problems to
* be worthwhile in practice. To carry this out, we (1) lazily
* initialize fence and expectedModCount until the latest
* point that we need to commit to the state we are checking
* against; thus improving precision. (This doesn't apply to
* SubLists, that create spliterators with current non-lazy
* values). (2) We perform only a single
* ConcurrentModificationException check at the end of forEach
* (the most performance-sensitive method). When using forEach
* (as opposed to iterators), we can normally only detect
* interference after actions, not before. Further
* CME-triggering checks apply to all other possible
* violations of assumptions for example null or too-small
* elementData array given its size(), that could only have
* occurred due to interference. This allows the inner loop
* of forEach to run without any further checks, and
* simplifies lambda-resolution. While this does entail a
* number of checks, note that in the common case of
* list.stream().forEach(a), no checks or other computation
* occur anywhere other than inside forEach itself. The other
* less-often-used methods cannot take advantage of most of
* these streamlinings.
*/
private final ArrayList<E> list;
// 每次 split()或者 advance()时，这个值都会变
private int index; // current index, modified on advance/split
// 栅栏，即index可遍历的上限
private int fence; // -1 until used; then one past last index
private int expectedModCount; // initialized when fence set
/**
* Create new spliterator covering the given range
*/
ArrayListSpliterator(ArrayList<E> list, int origin, int fence,
int expectedModCount) {
this.list = list; // OK if null unless traversed
this.index = origin; // 起始位置
this.fence = fence; // 上限
this.expectedModCount = expectedModCount;
}
// 强制初始化 fence的值
private int getFence() { // initialize fence to size on first use
int hi; // (a specialized variant appears in method forEach)
ArrayList<E> lst;
// 如果 fence < 0的话，表示初始化
if ((hi = fence) < 0) {
// 如果集合为 null，那么 fence也需要为 0
if ((lst = list) == null)
hi = fence = 0;
else {
expectedModCount = lst.modCount;
hi = fence = lst.size;
}
}
return hi;
}
// 进行子划分
public ArrayListSpliterator<E> trySplit() {
// 从当前迭代器的中间元素进行划分
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
// 返回从当前 index到 mid的子迭代器
return (lo >= mid) ? null : // divide range in half unless too small
new ArrayListSpliterator<E>(list, lo, index = mid,
expectedModCount);
}
// 针对当前索引指向的值，进行提前处理，Consumer是一个消费者
public boolean tryAdvance(Consumer<? super E> action) {
// 保证消费函数不可为 null
if (action == null)
throw new NullPointerException();
// 获取 fence和 index
int hi = getFence(), i = index;
if (i < hi) {
index = i + 1;
// 获取 i对应的元素
@SuppressWarnings("unchecked") E e = (E) list.elementData[i];
// 消费
action.accept(e);
if (list.modCount != expectedModCount)
throw new ConcurrentModificationException();
return true;
}
return false;
}
// 为每个对象都进行一次操作
public void forEachRemaining(Consumer<? super E> action) {
// i为下标，hi为fence，mc为预期已改变的大小
int i, hi, mc; // hoist accesses and checks from loop
ArrayList<E> lst;
Object[] a;
if (action == null)
throw new NullPointerException();
if ((lst = list) != null && (a = lst.elementData) != null) {
// 初始化变量
if ((hi = fence) < 0) {
mc = lst.modCount;
hi = lst.size;
} else
mc = expectedModCount;
if ((i = index) >= 0 && (index = hi) <= a.length) {
// 遍历所有元素，对每个元素都进行一次处理
for (; i < hi; ++i) {
@SuppressWarnings("unchecked") E e = (E) a[i];
action.accept(e);
}
if (lst.modCount == mc)
return;
}
}
throw new ConcurrentModificationException();
}
// 计算剩余容量
public long estimateSize() {
// 最大容量 - 已经消费过了的数据
return (long) (getFence() - index);
}
// 返回当前迭代器底层列表的特征值
public int characteristics() {
// 表示是 有序的、定长、子列表也定长的
return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
}
}
这篇关于ArrayList源码解析的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-11-02Java管理系统项目实战入门教程
- 2024-11-02Java监控系统项目实战教程
- 2024-11-02Java就业项目项目实战：从入门到初级工程师的必备技能
- 2024-11-02Java全端项目实战入门教程
- 2024-11-02Java全栈项目实战：从入门到初级应用
- 2024-11-02Java日志系统项目实战：初学者完全指南
- 2024-11-02Java微服务系统项目实战入门教程
- 2024-11-02Java微服务项目实战：新手入门指南
- 2024-11-02Java项目实战：新手入门教程
- 2024-11-02Java小程序项目实战：从入门到简单应用
