ArrayList源码分析
ArrayList 是 Java Collections Framework 中的一个重要类，用于动态数组的实现。它属于 java.util 包，并且实现了 List 接口。ArrayList 提供了对元素的有序访问和动态调整大小的能力，使其成为在 Java 中常用的集合类之一。
基本特点
- 动态数组：
- ArrayList 使用一个内部的数组来存储元素。这个数组的大小会根据需要动态调整，当元素数量超过当前数组的容量时，ArrayList 会自动扩展数组的大小。
- 有序存储：
- 元素按插入顺序存储。可以通过索引位置（从0开始）来访问和操作元素。
- 支持重复元素：
- ArrayList 允许存储重复的元素。在列表中，多个相同的元素是被允许的。
- 线程不安全：
- ArrayList 是非同步的，这意味着它不是线程安全的。如果多个线程同时访问一个 ArrayList，并且至少有一个线程修改了列表结构，则需要外部同步来保证线程安全。
- 允许 null 元素：
- ArrayList 允许包含 null 元素。
首先我们来看一下构造函数
// Android-note: 也可以从 java.util.Collections 访问
// 非私有字段，以简化嵌套类的访问
transient Object[] elementData;
/**
* ArrayList 的大小（包含的元素数量）。
*
* @serial
*/
private int size;
/**
* 使用指定的初始容量构造一个空的 ArrayList。
*
* @param initialCapacity 列表的初始容量
* @throws IllegalArgumentException 如果指定的初始容量为负值
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
// 如果初始容量大于 0，初始化内部数组
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// 如果初始容量为 0，使用一个空的预设数组
this.elementData = EMPTY_ELEMENTDATA;
} else {
// 如果初始容量为负值，抛出非法参数异常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
自动扩容
每当向数组中添加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求。数组扩容通过一个公开的方法ensureCapacity(int minCapacity)来实现。在实际添加大量元素前，我也可以使用ensureCapacity来手动增加ArrayList实例的容量，以减少递增式再分配的数量。
数组进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长大约是其原容量的1.5倍。这种操作的代价是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时，要在构造ArrayList实例时，就指定其容量，以避免数组扩容的发生。或者根据实际需求，通过调用ensureCapacity方法来手动增加ArrayList实例的容量。
/**
* Increases the capacity of this {@code ArrayList} instance, if
* necessary, to ensure that it can hold at least the number of elements
* specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
public void ensureCapacity(int minCapacity) {
if (minCapacity > elementData.length
&& !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
&& minCapacity <= DEFAULT_CAPACITY)) {
modCount++;
grow(minCapacity);
}
}
这段代码用于确保数组有足够的容量存储新元素。如果 ArrayList 的当前容量不足以容纳指定的最小容量 (minCapacity)，则会扩大其容量。如果传入的 minCapacity 大于当前内部数组的长度(elementData.length)，则说明数组当前的容量不足以容纳指定的元素。假设有一个 ArrayList，其内部数组 elementData 的长度为 10（即 elementData.length == 10）。如果此时传入的 minCapacity 为 15，这表示我们希望 ArrayList 至少能存储 15 个元素。但是，当前的数组长度只有 10，也就是最多只能存储 10 个元素，显然是无法满足这个要求的，因此需要扩容。每当 ArrayList 的结构被修改时（例如扩容、添加或删除元素），modCount 会增加。如果上述条件为真，那么调用 grow(minCapacity) 方法来扩展内部数组的容量，以确保它至少能够容纳 minCapacity 大小。
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
* @throws OutOfMemoryError if minCapacity is less than zero
*/
private Object[] grow(int minCapacity) {
int oldCapacity = elementData.length;
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);
} else {
return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
}
}
这行代码调用了 ArraysSupport.newLength 方法来计算新的容量 (newCapacity)。 oldCapacity 是当前容量。
- minCapacity - oldCapacity 是需要的最小增长量。
- oldCapacity >> 1 是首选的增长量（当前容量的 50%，通过右移一位计算）。
- ArraysSupport.newLength 将根据这些参数返回一个新的容量，确保数组至少能容纳 minCapacity 个元素，并通常以指数方式增长。
add(), addAll()
跟C++ 的vector不同，ArrayList没有 push_back()方法，对应的方法是 add(E e)，ArrayList也没有 insert()方法，对应的方法是 add(int index, E e)。这两个方法都是向容器中添加新元素，这可能会导致capacity不足，因此在添加元素之前，都需要进行剩余空间检查，如果需要则自动扩容。扩容操作最终是通过 grow()方法完成的。
// 添加元素的方法，适用于索引位置的检查已经在调用方法中完成的情况
private void add(E e, Object[] elementData, int s) {
// 如果当前元素数量等于数组长度，说明数组已满，需要扩容
if (s == elementData.length)
// 扩容数组
elementData = grow();
// 将元素添加到数组的下一个空位
elementData[s] = e;
// 更新列表的大小
size = s + 1;
}
// 向列表的末尾添加一个元素
public boolean add(E e) {
// 更新修改计数，表示对列表结构的更改（用于检测并发修改）
modCount++;
// 调用私有的 add 方法执行添加操作
add(e, elementData, size);
// 返回 true，表示元素成功添加
return true;
}
// 在指定索引位置插入元素
public void add(int index, E element) {
// 检查索引是否合法，如果不合法抛出 IndexOutOfBoundsException
rangeCheckForAdd(index);
// 更新修改计数，表示对列表结构的更改
modCount++;
final int s;
Object[] elementData;
// 如果当前大小等于数组长度，说明数组已满，需要扩容
if ((s = size) == (elementData = this.elementData).length)
// 扩容数组
elementData = grow();
// 将从索引位置开始的元素向右移动一位，为新元素腾出位置
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);
// 在指定索引位置插入新元素
elementData[index] = element;
// 更新列表的大小
size = s + 1;
}
add(int index, E e)需要先对元素进行移动，然后完成插入操作，也就意味着该方法有着线性的时间复杂度。
// 将指定集合中的所有元素添加到列表末尾
public boolean addAll(Collection<? extends E> c) {
// 将集合转换为数组，方便后续处理
Object[] a = c.toArray();
// 更新修改计数，表示对列表结构的更改（用于检测并发修改）
modCount++;
// 获取要添加的新元素的数量
int numNew = a.length;
// 如果集合为空，没有新元素要添加
if (numNew == 0)
// 返回 false，表示没有任何元素被添加
return false;
Object[] elementData;
final int s;
// 如果新元素的数量大于列表剩余的空间
if (numNew > (elementData = this.elementData).length - (s = size))
// 扩容数组以容纳所有新元素
elementData = grow(s + numNew);
// 将新元素从数组 a 复制到 elementData 的末尾
System.arraycopy(a, 0, elementData, s, numNew);
// 更新列表的大小
size = s + numNew;
// 返回 true，表示元素成功添加
return true;
}
// 在指定索引位置插入指定集合中的所有元素
public boolean addAll(int index, Collection<? extends E> c) {
// 检查索引是否合法，如果不合法抛出 IndexOutOfBoundsException
rangeCheckForAdd(index);
// 将集合转换为数组，方便后续处理
Object[] a = c.toArray();
// 更新修改计数，表示对列表结构的更改
modCount++;
// 获取要添加的新元素的数量
int numNew = a.length;
// 如果集合为空，没有新元素要添加
if (numNew == 0)
// 返回 false，表示没有任何元素被添加
return false;
Object[] elementData;
final int s;
// 如果新元素的数量大于列表剩余的空间
if (numNew > (elementData = this.elementData).length - (s = size))
elementData = grow(s + numNew); // 扩容数组以容纳所有新元素
// 计算需要移动的元素数量
int numMoved = s - index;
// 如果插入位置后有元素
if (numMoved > 0)
// 将现有元素从插入位置开始向后移动，为新元素腾出空间
System.arraycopy(elementData, index,
elementData, index + numNew,
numMoved);
// 将新元素从数组 a 复制到插入位置
System.arraycopy(a, 0, elementData, index, numNew);
// 更新列表的大小
size = s + numNew;
// 返回 true，表示元素成功添加
return true;
}
set()
既然底层是一个数组ArrayList的 set() 方法也就变得非常简单，直接对数组的指定位置赋值即可。
public void set(E e) {
// 如果 lastRet 小于 0，表示 set 操作不合法，抛出 IllegalStateException
if (lastRet < 0)
throw new IllegalStateException();
// 检查列表是否在迭代过程中被修改（并发修改检测）
checkForComodification();
try {
// 调用外部 ArrayList 实例的 set 方法，替换 lastRet 位置的元素为 e
ArrayList.this.set(lastRet, e);
} catch (IndexOutOfBoundsException ex) {
// 如果捕获到 IndexOutOfBoundsException，抛出 ConcurrentModificationException
// 这通常意味着列表结构在迭代期间被意外修改了
throw new ConcurrentModificationException();
}
}
get()
get() 方法同样很简单，唯一要注意的是由于底层数组是Object[]，得到元素后需要进行类型转换。
public E get(int index) {
// 检查索引是否合法。该方法会验证索引是否在合法范围内（0 到 size - 1）
Objects.checkIndex(index, size);
// 检查在迭代过程中是否发生了并发修改。如果列表在迭代期间被修改，可能会抛出 ConcurrentModificationException
checkForComodification();
// 从内部存储中获取元素
return root.elementData(offset + index);
}
remove()
public E remove(int index) {
// 检查索引是否合法。该方法会验证索引是否在合法范围内（0 到 size - 1）
Objects.checkIndex(index, size);
// 检查在迭代过程中是否发生了并发修改。如果列表在迭代期间被修改，可能会抛出 ConcurrentModificationException
checkForComodification();
// 从内部存储中删除元素并获取删除的元素
E result = root.remove(offset + index);
// 更新列表的大小和修改计数
updateSizeAndModCount(-1);
// 返回被删除的元素
return result;
}
indexOf(), lastIndexOf()
获取元素的第一次出现的index:
public int indexOf(Object o) {
// 调用 root 的 indexOfRange 方法查找对象 o 在指定范围内的索引位置
int index = root.indexOfRange(o, offset, offset + size);
// 检查在迭代过程中是否发生了并发修改。如果列表在迭代期间被修改，可能会抛出 ConcurrentModificationException
checkForComodification();
// 如果找到对象 o，返回调整后的索引（相对于列表的起始位置），否则返回 -1
return index >= 0 ? index - offset : -1;
}
public int lastIndexOf(Object o) {
// 调用 root 的 lastIndexOfRange 方法查找对象 o 在指定范围内的最后一个索引位置
int index = root.lastIndexOfRange(o, offset, offset + size);
// 检查在迭代过程中是否发生了并发修改。如果列表在迭代期间被修改，可能会抛出 ConcurrentModificationException
checkForComodification();
// 如果找到对象 o，返回调整后的索引（相对于列表的起始位置），否则返回 -1
return index >= 0 ? index - offset : -1;
}
- indexOf(Object o) 方法用于查找对象 o 在列表中第一次出现的位置。如果找到该对象，返回其索引；否则返回 -1。它先调用 root.indexOfRange 方法来找到对象的索引，然后调整返回值以适应列表的实际起始位置。
- lastIndexOf(Object o) 方法用于查找对象 o 在列表中最后一次出现的位置。如果找到该对象，返回其索引；否则返回 -1。它先调用 root.lastIndexOfRange 方法来找到对象的最后出现位置，然后调整返回值以适应列表的实际起始位置。
Fail-Fast机制（快速失败）:
Fail-Fast 机制 是一种在迭代过程中检测并发修改的策略，用于确保数据结构的一致性和可靠性。这个机制的核心思想是，当集合在迭代过程中被修改（例如通过添加、删除元素），而这种修改可能会影响到当前的迭代操作时，系统会立即报告错误，而不是在出现潜在的问题时才发现。
为什么不能在迭代过程中修改集合？
- 一致性和正确性：
- 当你在迭代集合时，如果集合的结构发生了变化（如添加、删除元素），可能会导致迭代器对集合的状态不再准确。比如，元素的数量、顺序或者位置可能已经改变，这使得迭代器可能在不一致的状态下继续访问集合，导致错误的结果或者抛出异常。
- 数据完整性：
- 修改集合结构（例如，添加或删除元素）可能会破坏迭代器对集合的假设。这些假设通常包括元素的数量和位置。在这种情况下，迭代器可能会尝试访问不存在的元素，或者无法正确地处理集合的变化，从而导致数据的完整性问题。
Fail-Fast 机制的工作原理
- 修改检测：
- 当你创建一个迭代器来遍历集合时，Fail-Fast 机制会在每次操作（如添加或删除元素）后检查集合的结构是否发生了变化。
- 这种检测通常通过一个修改计数器（例如 modCount）实现。每次对集合进行结构修改时（如 add, remove 方法），计数器会递增。
- 迭代器在遍历时会检查当前的修改计数器值与迭代器创建时的计数器值是否一致。如果发现不一致，则抛出 ConcurrentModificationException。
- 即时反馈：
- 如果在迭代过程中发现集合被修改，Fail-Fast 机制会立即抛出异常，例如 ConcurrentModificationException。这样可以在代码执行时立刻发现并发修改问题，从而避免难以追踪的错误和不一致的状态。
代码示例
这个示例展示了如何在遍历 ArrayList 时修改列表，触发快速失败机制：
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class FailFastExample {
public static void main(String[] args) {
// 创建一个 ArrayList 并添加一些元素
List<String> list = new ArrayList<>();
list.add("One");
list.add("Two");
list.add("Three");
// 获取列表的迭代器
Iterator<String> iterator = list.iterator();
// 在迭代过程中修改列表（这将引发 ConcurrentModificationException）
while (iterator.hasNext()) {
String item = iterator.next();
System.out.println("Current item: " + item);
// 在迭代过程中修改列表
if ("Two".equals(item)) {
list.remove(item); // 修改列表的结构
}
}
}
}
那么我们如何解决呢？
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class SafeModificationExample {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("One");
list.add("Two");
list.add("Three");
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
String item = iterator.next();
if ("Two".equals(item)) {
iterator.remove(); // 使用 Iterator 的 remove 方法安全删除元素
}
}
System.out.println("Updated list: " + list); // 输出: Updated list: [One, Three]
}
}
Iterator 提供了一个 remove 方法，允许你在遍历集合时安全地删除当前迭代的元素。这是最简单和最常用的解决方法。
ArrayList 是非同步的，这意味着它不是线程安全的。如果多个线程同时访问一个 ArrayList，并且至少有一个线程修改了列表结构，则需要外部同步来保证线程安全。那么如何外部同步来保证线程安全呢?
1. 使用 synchronized 关键字
最直接的方法是使用 synchronized 关键字来对操作 ArrayList 的代码块进行同步。这样可以确保在同一时间只有一个线程可以执行这些操作，从而避免并发修改的问题。
示例代码：
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class SynchronizedArrayListExample {
private final List<String> list = new ArrayList<>();
// 用于同步的对象
private final Object lock = new Object();
public void add(String element) {
synchronized (lock) {
// 添加元素时进行同步
list.add(element);
}
}
public void remove(String element) {
synchronized (lock) {
// 删除元素时进行同步
list.remove(element);
}
}
public String get(int index) {
synchronized (lock) {
// 获取元素时进行同步
return list.get(index);
}
}
public static void main(String[] args) {
SynchronizedArrayListExample example = new SynchronizedArrayListExample();
example.add("One");
example.add("Two");
// 输出: Two
System.out.println(example.get(1));
example.remove("One");
}
}
2. 使用 Collections.synchronizedList
Collections.synchronizedList 方法可以将普通的 ArrayList 转换为线程安全的列表。这个方法会返回一个线程安全的列表，其所有方法都被同步。
示例代码：
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class SynchronizedListExample {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
List<String> synchronizedList = Collections.synchronizedList(list);
synchronizedList.add("One");
synchronizedList.add("Two");
// 访问同步列表时，通常需要在同步块中进行迭代
synchronized (synchronizedList) {
for (String item : synchronizedList) {
System.out.println(item); // 输出: One Two
}
}
}
}
3. 使用 CopyOnWriteArrayList
CopyOnWriteArrayList 是 Java 并发包 (java.util.concurrent) 提供的一个线程安全的 List 实现。它通过在每次修改时创建数组的副本来确保线程安全，因此适合于读多写少的场景。
示例代码：
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;
public class CopyOnWriteArrayListExample {
public static void main(String[] args) {
List<String> list = new CopyOnWriteArrayList<>();
list.add("One");
list.add("Two");
// CopyOnWriteArrayList 允许在遍历时安全地修改列表
for (String item : list) {
// 输出: One Two
System.out.println(item);
// 允许在迭代时安全地修改
list.remove("One");
}
// 输出剩余的元素
System.out.println(list); // 输出: [Two]
}
}
评论区