您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
ArrayList 是 Java 集合框架中最常用的数据结构之一，它基于动态数组实现，提供了高效的随机访问和动态扩容能力。本文将深入分析 ArrayList 的动态扩容机制，探讨其源码实现、扩容策略、性能影响以及相关的优化策略。
ArrayList 的内部结构主要由以下几个部分组成：
elementData: 一个 Object[] 数组，用于存储实际的数据元素。size: 一个 int 类型的变量，表示当前 ArrayList 中实际存储的元素数量。modCount: 一个 int 类型的变量，用于记录 ArrayList 结构修改的次数，主要用于迭代器的快速失败机制。transient Object[] elementData; // 存储元素的数组
private int size; // 当前元素数量
protected transient int modCount = 0; // 结构修改次数
ArrayList 提供了多个构造函数，允许用户指定初始容量或使用默认容量。
// 默认构造函数，初始容量为10
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 指定初始容量的构造函数
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);
}
}
// 使用集合初始化的构造函数
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
this.elementData = EMPTY_ELEMENTDATA;
}
}
ArrayList 的添加操作主要通过 add(E e) 方法实现。该方法首先检查当前数组是否已满，如果已满则触发扩容操作，然后将新元素添加到数组的末尾。
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 确保容量足够
elementData[size++] = e; // 添加元素
return true;
}
ArrayList 的扩容操作在以下情况下触发：
add(E e) 方法时，如果当前数组已满（即 size == elementData.length），则需要扩容。addAll(Collection<? extends E> c) 方法时，如果当前数组容量不足以容纳新添加的所有元素，则需要扩容。ArrayList 的扩容过程主要通过 grow(int minCapacity) 方法实现。该方法首先计算新的容量，然后创建一个新的数组并将原数组中的元素复制到新数组中。
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 新容量为原容量的1.5倍
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity); // 复制元素到新数组
}
在扩容过程中，Arrays.copyOf() 方法用于将原数组中的元素复制到新数组中。该方法内部调用了 System.arraycopy()，这是一个本地方法，具有较高的性能。
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
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;
}
ArrayList 的默认扩容策略是将容量扩大为原来的 1.5 倍。这种策略在大多数情况下能够平衡内存使用和性能。
int newCapacity = oldCapacity + (oldCapacity >> 1); // 新容量为原容量的1.5倍
用户可以通过构造函数指定 ArrayList 的初始容量，从而避免频繁扩容。
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);
}
}
在某些场景下，用户可以通过手动调整 ArrayList 的容量来优化性能。例如，在已知需要添加大量元素时，可以提前调用 ensureCapacity(int minCapacity) 方法，避免频繁扩容。
public void ensureCapacity(int minCapacity) {
if (minCapacity > elementData.length) {
grow(minCapacity);
}
}
ArrayList 的扩容操作的时间复杂度为 O(n)，其中 n 是当前数组的长度。这是因为在扩容过程中需要将原数组中的元素复制到新数组中。
ArrayList 的扩容操作的空间复杂度为 O(n)，其中 n 是新数组的长度。这是因为在扩容过程中需要创建一个新的数组来存储元素。
频繁的扩容操作会导致性能下降，因为每次扩容都需要复制大量元素。因此，在实际使用中，应尽量避免频繁扩容，可以通过提前设置合适的初始容量或手动调整容量来优化性能。
ArrayList 并没有提供自动缩容的机制，但用户可以通过调用 trimToSize() 方法手动将 ArrayList 的容量调整为当前元素数量，从而减少内存占用。
public void trimToSize() {
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
ArrayList 不是线程安全的，如果在多线程环境下使用 ArrayList，可能会导致数据不一致或其他并发问题。为了在多线程环境下使用 ArrayList，可以使用 Collections.synchronizedList() 方法将其包装为线程安全的列表。
List<String> synchronizedList = Collections.synchronizedList(new ArrayList<>());
ArrayList 的动态扩容机制是其高效性能的关键之一。通过分析其源码，我们了解了 ArrayList 的扩容触发条件、扩容过程、扩容策略以及性能影响。在实际使用中，合理设置初始容量、避免频繁扩容以及手动调整容量是优化 ArrayList 性能的重要手段。同时，ArrayList 的线程安全性问题也需要在使用时特别注意。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。