揭秘ArrayList:深入探索Java的动态数组艺术
1. 概述
ArrayList
是 Java 集合框架(Java Collections Framework)的一部分,它是一个可以动态增长和缩小的数组实现类。ArrayList
类提供了对列表(List
)接口的实现,它使用数组作为其数据结构的基础,允许存储任意数量的元素,并且提供了各种方法来操作这些元素。
2. 用途
- 动态数组:
ArrayList
提供了一个可以动态增长的数组,这意味着您可以在运行时向列表中添加或删除元素,而无需担心数组的固定大小限制。 - 存储和检索数据:
ArrayList
可以用于存储任何类型的对象(通过泛型指定),并且提供了各种方法来检索、添加、删除和修改这些对象。这使得ArrayList
成为存储和管理数据的强大工具。 - 队列操作:虽然
ArrayList
不是专门为队列操作设计的,但它可以很容易地实现队列(FIFO,先进先出)的基本操作。您可以使用add()
方法在列表的末尾添加元素,并使用remove(0)
或poll()
(如果ArrayList
被包装在LinkedList
中)来从列表的开头删除元素。 - 栈操作:类似地,
ArrayList
也可以实现栈(LIFO,后进先出)的基本操作。您可以使用add()
方法在列表的末尾添加元素,并使用remove(size() - 1)
来从列表的末尾删除元素。 - 数据排序和搜索:
ArrayList
可以与 Java 的排序和搜索算法(如Collections.sort()
和Collections.binarySearch()
)一起使用,以便对列表中的元素进行排序和搜索。 - 与其他集合类交互:
ArrayList
是 Java 集合框架的一部分,因此它可以与其他集合类(如HashSet
、LinkedList
、TreeSet
等)进行交互。例如,您可以将ArrayList
的元素添加到HashSet
中以删除重复项,或者将ArrayList
的元素复制到LinkedList
中以改变其遍历顺序。
3. 数据结构
ArrayList
的数据结构是基于数组的(Array-backed
)。它内部使用一个动态增长的数组来存储元素。这个数组可以随着元素的添加而自动扩容,以容纳更多的元素。
4. 底层实现原理
4.1 工作原理
- 数据结构
ArrayList
的底层数据结构是一个动态数组,这意味着它可以像传统数组一样通过索引来访问元素,但其大小(容量)不是固定的。当向ArrayList
中添加元素时,如果当前容量不足以容纳新元素,它会自动增长其内部数组的大小。
- 动态扩容
- 当向
ArrayList
中添加元素并且其当前容量已满时,ArrayList
会创建一个新的、更大的数组,并将旧数组中的元素复制到新数组中。新的容量通常是原始容量的某个倍数(例如1.5倍),但这不是固定的,并且可能因JVM实现的不同而有所差异。这个过程称为“扩容”或“重新分配”。
- 当向
- 容量与大小
ArrayList
有两个重要的属性:容量(capacity
)和大小(size
)。容量是指ArrayList
内部数组的长度,它表示ArrayList
最多可以容纳多少元素。而大小则是指ArrayList
当前实际存储的元素数量。在添加元素时,如果当前大小小于容量,则直接添加;如果当前大小等于容量,则触发扩容操作。
- 随机访问
ArrayList
支持基于索引的快速访问。由于ArrayList
底层是数组实现的,因此可以通过索引在O(1)时间复杂度内获取或设置元素的值。这是ArrayList
相对于其他基于链表的数据结构(如LinkedList
)的一个主要优势。
- 线程安全性
- ArrayList不是线程安全的。如果在多线程环境下同时访问和修改同一个ArrayList实例,可能会导致数据不一致或其他并发问题。因此,在多线程环境中使用ArrayList时,需要额外的同步措施来确保线程安全。
- 序列化与克隆
ArrayList
实现了Serializable
接口和Cloneable
接口,因此它支持序列化和克隆操作。序列化可以将ArrayList
对象转换为字节流,以便在网络传输或持久化到磁盘等场景中使用。克隆则可以创建一个与原始ArrayList
具有相同内容和结构的新ArrayList
对象。
总的来说,ArrayList
通过动态数组来实现动态扩容和基于索引的快速访问等功能,使其成为Java集合框架中非常常用和实用的一个类。
4.2 源码分析
在 JDK 1.8 中,ArrayList
的实现与之前的版本相比,并没有发生大的结构变化,但仍然是基于动态数组(Object
数组)的。下面我将对 JDK 1.8 中 ArrayList
的一些关键源码部分进行分析。
- 首先,
ArrayList
的主要成员变量包括
private static final int DEFAULT_CAPACITY = 10; // 默认初始容量
private static final Object[] EMPTY_ELEMENTDATA = {}; // 用于默认构造函数的空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 用于带有默认初始容量的构造函数的空数组
// 用于存储元素的数组
transient Object[] elementData; // non-private to simplify nested class access
// 实际存储的元素数量
private int size;
// ... 其他成员变量和方法 ...
注意,elementData
是 ArrayList
用于存储元素的数组,size
是实际存储的元素数量(不同于数组的 length
)。
- 接下来是构造函数的实现
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() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 还有其他构造函数,例如使用集合来初始化的构造函数
- 在
add
方法中,当列表已满时,ArrayList
会自动扩容
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 增量扩容前检查容量
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
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);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
- 在
get
方法中,根据索引直接访问数组元素
public E get(int index) {
rangeCheck(index); // 检查索引是否越界
return elementData(index);
}
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
- 在
remove
方法中,除了删除指定位置的元素外,还需要将后续元素前移
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
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
return oldValue;
}
以上是 ArrayList
中一些关键方法的简化实现。注意,这里省略了一些错误处理、边界检查和类型安全的代码,但已经足够说明 ArrayList
的基本工作原理了。在 JDK 1.8 中,ArrayList
的实现依然高效且稳定,是 Java 中最常用的集合类之一。
4.3 扩容机制
ArrayList
的扩容机制是其在动态调整大小以适应元素增长时的关键特性。当向 ArrayList
中添加元素并且当前数组的大小不足以容纳新元素时,ArrayList
会自动创建一个新的数组,并将现有元素复制到新数组中。以下是对 ArrayList
扩容机制的详细介绍,并结合源码进行分析。
概述
- 确定扩容大小:在添加元素之前,
ArrayList
会检查当前数组的大小是否足够容纳新元素。如果不够,就需要扩容。扩容时,ArrayList
会计算出一个新的容量,通常是当前容量的 1.5 倍(向上取整),但同时也会考虑需要的最小容量(minCapacity
)。 - 创建新数组:使用
Arrays.copyOf()
方法创建一个新的数组,其大小为计算出的新容量。这个方法会将原数组的内容复制到新数组中。 - 引用新数组:将
ArrayList
的elementData
引用指向新数组,这样后续添加的元素就会存储在新数组中。
源码分析
ensureCapacityInternal(int minCapacity)
:此方法检查当前容量是否足够,如果不够则调用grow(int minCapacity)
方法进行扩容。
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
这里特别处理了默认构造函数创建的空数组的情况,将其初始容量设为 DEFAULT_CAPACITY(10)。
grow(int minCapacity)
:此方法实际执行扩容操作。
private void grow(int minCapacity) {
// overflow-conscious code
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);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
这里计算了新的容量 newCapacity
,并将其与 minCapacity
和 MAX_ARRAY_SIZE
进行比较以确保其合理性。然后使用 Arrays.copyOf()
方法将原数组的内容复制到新数组中。
hugeCapacity(int minCapacity)
:此方法用于处理当所需容量大于MAX_ARRAY_SIZE
时的特殊情况。
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
如果所需容量大于 MAX_ARRAY_SIZE
,则将新容量设为 Integer.MAX_VALUE
,否则保持为 MAX_ARRAY_SIZE
。注意,这里的 MAX_ARRAY_SIZE
通常是 Integer.MAX_VALUE - 8`,因为数组还需要一些额外的空间来存储其他元数据。
总结
ArrayList
的扩容机制允许它在添加元素时自动调整大小,从而避免了预先分配过多内存导致的浪费。同时,通过计算合适的新容量并使用 Arrays.copyOf()
方法进行数组复制,ArrayList
能够在保证性能的同时实现动态扩容。
4.4 ArrayList 的有序性
概述
-
ArrayList
是 Java 集合框架中的一个重要类,它实现了List
接口,用于存储动态数组中的元素。由于ArrayList
内部是使用数组来存储元素的,所以它天然就是有序的,即元素的插入顺序和它们在列表中的位置是一致的。 -
ArrayList
的有序性主要体现在以下几个方面:- 元素的插入顺序:当你向
ArrayList
中添加元素时,这些元素会按照你添加它们的顺序被存储在数组中。 - 元素的访问顺序:你可以通过索引(从 0 开始)来访问
ArrayList
中的元素,并且这些元素会按照它们在数组中的顺序被访问。 - 迭代器的遍历顺序:当你使用迭代器(如
Iterator
或ListIterator
)来遍历ArrayList
时,元素会按照它们在列表中的顺序被遍历。
- 元素的插入顺序:当你向
源码分析
- 元素的插入
- 当你使用
add(E e)
方法向ArrayList
中添加元素时,实际上是将元素添加到数组的末尾。这是通过计算当前数组的长度,然后将新元素存储在长度为size
的位置,并将size
加一来实现的。
- 当你使用
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 确保容量足够
elementData[size++] = e; // 在数组末尾添加元素,并更新大小
return true;
}
- 元素的访问
- 你可以通过
get(int index)
方法来访问ArrayList
中的元素。这个方法通过检查索引的有效性,然后直接返回数组中对应索引位置的元素。
- 你可以通过
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 确保容量足够
elementData[size++] = e; // 在数组末尾添加元素,并更新大小
return true;
}
- 迭代器的遍历
ArrayList
提供了iterator()
和listIterator()
方法来创建迭代器,用于遍历列表中的元素。这些迭代器会按照元素在列表中的顺序(即插入顺序)来遍历它们。- 迭代器的实现是在内部类中完成的,例如
Itr
(实现了Iterator<E>
接口)和ListItr
(实现了ListIterator<E>
接口)。这些内部类维护了一个当前索引cursor
,用于跟踪遍历的位置。在每次迭代时,它们都会返回当前索引位置的元素,并将索引向前移动一位。
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
// ... 其他方法和字段 ...
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
// ... 其他方法 ...
}
- 在这个例子中,
next()
方法会返回当前索引位置的元素,并将索引向前移动一位。由于索引是按照元素在数组中的顺序来递增的,所以迭代器也会按照元素的插入顺序来遍历它们。.
总结
- 由于
ArrayList
内部使用数组来存储元素,并且数组的索引是连续的,所以ArrayList
能够保持元素的有序性。无论是插入、访问还是遍历元素,都会按照它们在数组中的位置(即插入顺序)来进行。这种有序性使得ArrayList
非常适合用于需要保持元素顺序的场景。
5. 优缺点
5.1 优点
- 动态大小
ArrayList
可以根据需要自动地增长和缩小其容量。这意味着在添加或删除元素时,你不需要担心数组的大小问题。当添加元素导致当前容量不足时,ArrayList
会自动扩容;当删除元素导致容量过大时,虽然ArrayList
不会立即缩小容量(因为这涉及到复制操作,可能会很昂贵),但在后续的添加操作中,如果满足条件,它可能会减少容量。
- 有序性
ArrayList 保证了元素的插入顺序与它们在列表中的位置一致。这使得
ArrayList` 非常适合需要保持元素顺序的场景。
- 快速访问
- 由于
ArrayList
使用数组作为底层数据结构,因此它提供了基于索引的快速访问功能。获取和设置特定索引位置的元素的时间复杂度为 O(1)。
- 由于
- 迭代方便
ArrayList
实现了Iterable
接口,因此可以方便地使用for-each
循环进行迭代。此外,它还提供了iterator()
和listIterator()
方法来创建迭代器,以不同的方式遍历列表中的元素。
- 容量预测
- 在创建
ArrayList
时,可以指定一个初始容量。这有助于在知道大致元素数量的情况下优化性能,因为可以避免不必要的扩容操作。
- 在创建
- 线程不安全但效率高
ArrayList
不是线程安全的,这意味着在多线程环境中,如果不采取适当的同步措施,可能会遇到并发修改异常或数据不一致的问题。然而,这也使得ArrayList
在单线程环境中的性能非常高效,因为没有额外的线程安全开销。
- 兼容性
ArrayList
实现了List
接口,因此可以与任何期望List
的代码兼容。此外,它还提供了许多List
接口中定义的方法的实现,如add()
,remove()
,get()
,set()
,indexOf()
,lastIndexOf()
,subList()
, 等等。
- 易于使用
ArrayList
的 API 设计得非常直观和易用,使得开发者能够轻松地添加、删除、访问和修改列表中的元素。
总之,ArrayList
提供了许多有用的功能和优点,使得它在许多需要动态数组功能的场景中成为首选的数据结构。然而,在需要线程安全或更复杂的集合操作时,可能需要考虑使用其他集合类,如 Vector
、CopyOnWriteArrayList
或并发集合类(如 ConcurrentHashMap 的键集或值集)。
5.2 缺点
- 性能开销:当进行动态扩展时,
ArrayList
可能需要创建一个新的数组,并将旧数组的元素复制到新数组中,这会导致一定的性能开销,尤其是在大型数据集上。 - 内存占用:
ArrayList
会为每个元素分配内存,因此当存储大量数据时,可能会占用较大的内存空间。如果内存是一个有限资源,这可能会成为一个问题。 - 不适合频繁插入和删除:在
ArrayList
中插入或删除元素时,可能需要将后续元素的位置进行调整,这会导致性能下降。特别是在列表的开头或中间位置插入或删除元素时,这种性能问题更为明显。对于频繁执行插入和删除操作的情况,LinkedList
可能更适合。 - 随机访问效率:虽然
ArrayList
可以通过索引进行随机访问,但在大型数据集中,随机访问时性能可能较差,因为需要遍历较多的元素。 - 缺乏内建排序支持:
ArrayList
不具备内建的排序功能,因此如果需要对列表中的元素进行排序,需要手动实现或使用额外的排序算法。 - 类型不安全:在
ArrayList
中,所有的元素都被视为Object
类型,因此在使用值类型数据时,会涉及到装箱和拆箱操作,这可能会导致性能问题。装箱是将值类型转换为Object
类型的过程,而拆箱则是从Object
类型中提取值类型的过程。为了避免这个问题,可以使用泛型(Generic
)来指定元素的类型。
综上所述,虽然 ArrayList
具有许多优点,但在某些特定场景下,它的缺点可能会导致性能问题或不便。因此,在选择使用 ArrayList
时,需要根据具体的应用场景和需求进行权衡和选择。
6. 注意事项
- 初始容量:
- 在创建
ArrayList
时,如果知道大概要存储多少元素,可以通过指定初始容量来避免不必要的扩容操作。ArrayList
默认初始容量为10,但在某些情况下,你可能需要设置一个更大的初始容量。
- 在创建
- 扩容机制
ArrayList
的扩容机制是通过创建一个新的数组,并将旧数组的元素复制到新数组来实现的。扩容时,新数组的容量通常是旧容量的1.5倍(或者更大,取决于JVM实现)。这意味着在扩容时会有一定的性能开销。因此,如果可能的话,尽量避免频繁地触发扩容操作。
- 线程安全
ArrayList
不是线程安全的。如果你在多线程环境中使用ArrayList
,并且多个线程同时修改列表,那么可能会遇到并发修改异常或数据不一致的问题。为了线程安全,你可以使用Collections.synchronizedList()
来包装你的ArrayList
,或者使用Vector
(尽管Vector
的性能通常较差),或者使用并发集合类如CopyOnWriteArrayList
(适用于读多写少的场景)。
- 遍历和修改
- 在遍历
ArrayList
时,如果修改了列表的结构(如添加、删除元素),可能会抛出ConcurrentModificationException
。为了避免这个问题,可以使用迭代器(Iterator
或ListIterator
)的remove()
方法来删除元素,或者使用并发集合类。
- 在遍历
- 内存占用
ArrayList
会为其元素分配内存空间。如果存储的是大对象或大量元素,那么ArrayList
可能会占用大量的内存。在设计系统时,要注意内存使用的限制,并考虑使用更节省内存的数据结构或策略。
- 性能考虑
- 对于频繁插入和删除操作的场景,
ArrayList
可能不是最佳选择。在这种情况下,LinkedList
可能更适合,因为它在插入和删除操作上具有更好的性能。
- 对于频繁插入和删除操作的场景,
- 避免使用索引以外的访问方式
- 虽然
ArrayList
提供了get(int index)
和set(int index, E element)
等基于索引的访问方法,但在某些情况下,你可能需要遍历整个列表来查找元素。这可能会导致性能问题,特别是当列表很大时。如果可能的话,尽量使用索引来访问元素。
- 虽然
- 正确处理空指针异常
- 在使用
ArrayList
时,要注意检查空指针异常。例如,在调用get(int index)
方法时,如果索引越界,则会抛出IndexOutOfBoundsException
。同样,在遍历列表时,如果使用了迭代器,并且在迭代过程中修改了列表结构,则可能会抛出ConcurrentModificationException
。
- 在使用
- 泛型的使用
- 使用泛型可以避免类型不安全的问题,并提高代码的可读性和可维护性。在创建
ArrayList
时,尽量指定元素的类型参数。
- 使用泛型可以避免类型不安全的问题,并提高代码的可读性和可维护性。在创建
- 序列化
- 如果你的
ArrayList
需要被序列化(例如,通过网络传输或保存到文件中),那么要注意ArrayList
及其元素的序列化行为。默认情况下,ArrayList
实现了Serializable
接口,因此可以被序列化。但是,如果你的元素类型不是可序列化的,那么整个列表将无法被序列化。在这种情况下,你需要确保元素类型也是可序列化的,或者实现自定义的序列化逻辑。
- 如果你的
7. 总结
ArrayList
作为Java集合框架中的核心类之一,它以其动态扩展、基于索引的快速访问和易用的API赢得了开发者的青睐。然而,在使用 ArrayList
时,我们也需要注意其潜在的性能开销、线程安全性以及内存占用等问题。虽然 ArrayList
在大多数情况下能够满足需求,但在处理大量数据、频繁插入删除操作或者多线程环境下,我们需要谨慎评估其是否是最优选择。总之,ArrayList
是一个功能强大的工具,但在使用时需根据具体场景进行权衡和选择。
原文地址:https://blog.csdn.net/m0_51176516/article/details/139028542
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!