揭秘ArrayList:深入探索Java的动态数组艺术

发布于:2024-05-21 ⋅ 阅读:(28) ⋅ 点赞:(0)

1. 概述

ArrayList 是 Java 集合框架(Java Collections Framework)的一部分,它是一个可以动态增长和缩小的数组实现类。ArrayList 类提供了对列表(List)接口的实现,它使用数组作为其数据结构的基础,允许存储任意数量的元素,并且提供了各种方法来操作这些元素。


2. 用途

  1. 动态数组ArrayList 提供了一个可以动态增长的数组,这意味着您可以在运行时向列表中添加或删除元素,而无需担心数组的固定大小限制。
  2. 存储和检索数据ArrayList 可以用于存储任何类型的对象(通过泛型指定),并且提供了各种方法来检索、添加、删除和修改这些对象。这使得 ArrayList 成为存储和管理数据的强大工具。
  3. 队列操作:虽然 ArrayList 不是专门为队列操作设计的,但它可以很容易地实现队列(FIFO,先进先出)的基本操作。您可以使用 add() 方法在列表的末尾添加元素,并使用 remove(0) poll()(如果 ArrayList 被包装在 LinkedList 中)来从列表的开头删除元素。
  4. 栈操作:类似地,ArrayList 也可以实现栈(LIFO,后进先出)的基本操作。您可以使用 add() 方法在列表的末尾添加元素,并使用 remove(size() - 1) 来从列表的末尾删除元素。
  5. 数据排序和搜索ArrayList 可以与 Java 的排序和搜索算法(如 Collections.sort()Collections.binarySearch())一起使用,以便对列表中的元素进行排序和搜索。
  6. 与其他集合类交互ArrayList 是 Java 集合框架的一部分,因此它可以与其他集合类(如 HashSetLinkedListTreeSet 等)进行交互。例如,您可以将 ArrayList 的元素添加到 HashSet 中以删除重复项,或者将 ArrayList 的元素复制到 LinkedList 中以改变其遍历顺序。

3. 数据结构

ArrayList 的数据结构是基于数组的(Array-backed)。它内部使用一个动态增长的数组来存储元素。这个数组可以随着元素的添加而自动扩容,以容纳更多的元素。

在这里插入图片描述


4. 底层实现原理

4.1 工作原理
  1. 数据结构
    • ArrayList 的底层数据结构是一个动态数组,这意味着它可以像传统数组一样通过索引来访问元素,但其大小(容量)不是固定的。当向 ArrayList 中添加元素时,如果当前容量不足以容纳新元素,它会自动增长其内部数组的大小。
  2. 动态扩容
    • 当向 ArrayList 中添加元素并且其当前容量已满时,ArrayList 会创建一个新的、更大的数组,并将旧数组中的元素复制到新数组中。新的容量通常是原始容量的某个倍数(例如1.5倍),但这不是固定的,并且可能因JVM实现的不同而有所差异。这个过程称为“扩容”或“重新分配”。
  3. 容量与大小
    • ArrayList 有两个重要的属性:容量(capacity)和大小(size)。容量是指 ArrayList 内部数组的长度,它表示 ArrayList 最多可以容纳多少元素。而大小则是指 ArrayList 当前实际存储的元素数量。在添加元素时,如果当前大小小于容量,则直接添加;如果当前大小等于容量,则触发扩容操作。
  4. 随机访问
    • ArrayList 支持基于索引的快速访问。由于 ArrayList 底层是数组实现的,因此可以通过索引在O(1)时间复杂度内获取或设置元素的值。这是 ArrayList 相对于其他基于链表的数据结构(如 LinkedList)的一个主要优势。
  5. 线程安全性
    • ArrayList不是线程安全的。如果在多线程环境下同时访问和修改同一个ArrayList实例,可能会导致数据不一致或其他并发问题。因此,在多线程环境中使用ArrayList时,需要额外的同步措施来确保线程安全。
  6. 序列化与克隆
    • ArrayList 实现了 Serializable 接口和 Cloneable 接口,因此它支持序列化和克隆操作。序列化可以将 ArrayList 对象转换为字节流,以便在网络传输或持久化到磁盘等场景中使用。克隆则可以创建一个与原始 ArrayList 具有相同内容和结构的新 ArrayList 对象。

总的来说,ArrayList 通过动态数组来实现动态扩容和基于索引的快速访问等功能,使其成为Java集合框架中非常常用和实用的一个类。


4.2 源码分析

在 JDK 1.8 中,ArrayList 的实现与之前的版本相比,并没有发生大的结构变化,但仍然是基于动态数组(Object 数组)的。下面我将对 JDK 1.8 中 ArrayList 的一些关键源码部分进行分析。

  1. 首先,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;  
  
// ... 其他成员变量和方法 ...

注意,elementDataArrayList 用于存储元素的数组,size 是实际存储的元素数量(不同于数组的 length)。

  1. 接下来是构造函数的实现
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;  
}  
  
// 还有其他构造函数,例如使用集合来初始化的构造函数
  1. 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);  
}
  1. 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));  
}
  1. 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 扩容机制的详细介绍,并结合源码进行分析。

概述

  1. 确定扩容大小:在添加元素之前,ArrayList 会检查当前数组的大小是否足够容纳新元素。如果不够,就需要扩容。扩容时,ArrayList 会计算出一个新的容量,通常是当前容量的 1.5 倍(向上取整),但同时也会考虑需要的最小容量(minCapacity)。
  2. 创建新数组:使用 Arrays.copyOf() 方法创建一个新的数组,其大小为计算出的新容量。这个方法会将原数组的内容复制到新数组中。
  3. 引用新数组:将 ArrayListelementData 引用指向新数组,这样后续添加的元素就会存储在新数组中。

源码分析

  1. 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)。

  1. 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,并将其与 minCapacityMAX_ARRAY_SIZE 进行比较以确保其合理性。然后使用 Arrays.copyOf() 方法将原数组的内容复制到新数组中。

  1. 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 中的元素,并且这些元素会按照它们在数组中的顺序被访问。
    • 迭代器的遍历顺序:当你使用迭代器(如 IteratorListIterator)来遍历 ArrayList 时,元素会按照它们在列表中的顺序被遍历。

源码分析

  1. 元素的插入
    • 当你使用 add(E e) 方法向 ArrayList中添加元素时,实际上是将元素添加到数组的末尾。这是通过计算当前数组的长度,然后将新元素存储在长度为 size 的位置,并将 size 加一来实现的。
public boolean add(E e) {  
    ensureCapacityInternal(size + 1);  // 确保容量足够  
    elementData[size++] = e; // 在数组末尾添加元素,并更新大小  
    return true;  
}
  1. 元素的访问
    • 你可以通过 get(int index) 方法来访问 ArrayList 中的元素。这个方法通过检查索引的有效性,然后直接返回数组中对应索引位置的元素。
public boolean add(E e) {  
    ensureCapacityInternal(size + 1);  // 确保容量足够  
    elementData[size++] = e; // 在数组末尾添加元素,并更新大小  
    return true;  
}
  1. 迭代器的遍历
    • 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 优点
  1. 动态大小
    • ArrayList 可以根据需要自动地增长和缩小其容量。这意味着在添加或删除元素时,你不需要担心数组的大小问题。当添加元素导致当前容量不足时,ArrayList 会自动扩容;当删除元素导致容量过大时,虽然 ArrayList 不会立即缩小容量(因为这涉及到复制操作,可能会很昂贵),但在后续的添加操作中,如果满足条件,它可能会减少容量。
  2. 有序性
    • ArrayList 保证了元素的插入顺序与它们在列表中的位置一致。这使得 ArrayList` 非常适合需要保持元素顺序的场景。
  3. 快速访问
    • 由于 ArrayList 使用数组作为底层数据结构,因此它提供了基于索引的快速访问功能。获取和设置特定索引位置的元素的时间复杂度为 O(1)。
  4. 迭代方便
    • ArrayList 实现了 Iterable 接口,因此可以方便地使用 for-each 循环进行迭代。此外,它还提供了 iterator()listIterator() 方法来创建迭代器,以不同的方式遍历列表中的元素。
  5. 容量预测
    • 在创建 ArrayList 时,可以指定一个初始容量。这有助于在知道大致元素数量的情况下优化性能,因为可以避免不必要的扩容操作。
  6. 线程不安全但效率高
    • ArrayList 不是线程安全的,这意味着在多线程环境中,如果不采取适当的同步措施,可能会遇到并发修改异常或数据不一致的问题。然而,这也使得 ArrayList 在单线程环境中的性能非常高效,因为没有额外的线程安全开销。
  7. 兼容性
    • ArrayList 实现了 List 接口,因此可以与任何期望 List 的代码兼容。此外,它还提供了许多 List 接口中定义的方法的实现,如 add(), remove(), get(), set(), indexOf(), lastIndexOf(), subList(), 等等。
  8. 易于使用
    • ArrayList 的 API 设计得非常直观和易用,使得开发者能够轻松地添加、删除、访问和修改列表中的元素。

总之,ArrayList 提供了许多有用的功能和优点,使得它在许多需要动态数组功能的场景中成为首选的数据结构。然而,在需要线程安全或更复杂的集合操作时,可能需要考虑使用其他集合类,如 VectorCopyOnWriteArrayList 或并发集合类(如 ConcurrentHashMap 的键集或值集)。


5.2 缺点
  1. 性能开销:当进行动态扩展时,ArrayList 可能需要创建一个新的数组,并将旧数组的元素复制到新数组中,这会导致一定的性能开销,尤其是在大型数据集上。
  2. 内存占用ArrayList 会为每个元素分配内存,因此当存储大量数据时,可能会占用较大的内存空间。如果内存是一个有限资源,这可能会成为一个问题。
  3. 不适合频繁插入和删除:在ArrayList 中插入或删除元素时,可能需要将后续元素的位置进行调整,这会导致性能下降。特别是在列表的开头或中间位置插入或删除元素时,这种性能问题更为明显。对于频繁执行插入和删除操作的情况, LinkedList 可能更适合。
  4. 随机访问效率:虽然 ArrayList 可以通过索引进行随机访问,但在大型数据集中,随机访问时性能可能较差,因为需要遍历较多的元素。
  5. 缺乏内建排序支持ArrayList 不具备内建的排序功能,因此如果需要对列表中的元素进行排序,需要手动实现或使用额外的排序算法。
  6. 类型不安全:在ArrayList 中,所有的元素都被视为 Object 类型,因此在使用值类型数据时,会涉及到装箱和拆箱操作,这可能会导致性能问题。装箱是将值类型转换为 Object 类型的过程,而拆箱则是从 Object 类型中提取值类型的过程。为了避免这个问题,可以使用泛型(Generic)来指定元素的类型。

综上所述,虽然 ArrayList 具有许多优点,但在某些特定场景下,它的缺点可能会导致性能问题或不便。因此,在选择使用 ArrayList 时,需要根据具体的应用场景和需求进行权衡和选择。


6. 注意事项

  1. 初始容量
    • 在创建 ArrayList 时,如果知道大概要存储多少元素,可以通过指定初始容量来避免不必要的扩容操作。ArrayList 默认初始容量为10,但在某些情况下,你可能需要设置一个更大的初始容量。
  2. 扩容机制
    • ArrayList 的扩容机制是通过创建一个新的数组,并将旧数组的元素复制到新数组来实现的。扩容时,新数组的容量通常是旧容量的1.5倍(或者更大,取决于JVM实现)。这意味着在扩容时会有一定的性能开销。因此,如果可能的话,尽量避免频繁地触发扩容操作。
  3. 线程安全
    • ArrayList 不是线程安全的。如果你在多线程环境中使用 ArrayList ,并且多个线程同时修改列表,那么可能会遇到并发修改异常或数据不一致的问题。为了线程安全,你可以使用 Collections.synchronizedList() 来包装你的 ArrayList ,或者使用 Vector(尽管 Vector 的性能通常较差),或者使用并发集合类如 CopyOnWriteArrayList (适用于读多写少的场景)。
  4. 遍历和修改
    • 在遍历 ArrayList 时,如果修改了列表的结构(如添加、删除元素),可能会抛出 ConcurrentModificationException。为了避免这个问题,可以使用迭代器(IteratorListIterator)的 remove() 方法来删除元素,或者使用并发集合类。
  5. 内存占用
    • ArrayList 会为其元素分配内存空间。如果存储的是大对象或大量元素,那么 ArrayList 可能会占用大量的内存。在设计系统时,要注意内存使用的限制,并考虑使用更节省内存的数据结构或策略。
  6. 性能考虑
    • 对于频繁插入和删除操作的场景,ArrayList 可能不是最佳选择。在这种情况下,LinkedList 可能更适合,因为它在插入和删除操作上具有更好的性能。
  7. 避免使用索引以外的访问方式
    • 虽然 ArrayList 提供了 get(int index)set(int index, E element) 等基于索引的访问方法,但在某些情况下,你可能需要遍历整个列表来查找元素。这可能会导致性能问题,特别是当列表很大时。如果可能的话,尽量使用索引来访问元素。
  8. 正确处理空指针异常
    • 在使用 ArrayList 时,要注意检查空指针异常。例如,在调用 get(int index) 方法时,如果索引越界,则会抛出 IndexOutOfBoundsException 。同样,在遍历列表时,如果使用了迭代器,并且在迭代过程中修改了列表结构,则可能会抛出 ConcurrentModificationException
  9. 泛型的使用
    • 使用泛型可以避免类型不安全的问题,并提高代码的可读性和可维护性。在创建 ArrayList 时,尽量指定元素的类型参数。
  10. 序列化
    • 如果你的 ArrayList 需要被序列化(例如,通过网络传输或保存到文件中),那么要注意 ArrayList 及其元素的序列化行为。默认情况下,ArrayList 实现了 Serializable 接口,因此可以被序列化。但是,如果你的元素类型不是可序列化的,那么整个列表将无法被序列化。在这种情况下,你需要确保元素类型也是可序列化的,或者实现自定义的序列化逻辑。

7. 总结

ArrayList 作为Java集合框架中的核心类之一,它以其动态扩展、基于索引的快速访问和易用的API赢得了开发者的青睐。然而,在使用 ArrayList 时,我们也需要注意其潜在的性能开销、线程安全性以及内存占用等问题。虽然 ArrayList 在大多数情况下能够满足需求,但在处理大量数据、频繁插入删除操作或者多线程环境下,我们需要谨慎评估其是否是最优选择。总之,ArrayList是一个功能强大的工具,但在使用时需根据具体场景进行权衡和选择。