Felix's Blog
Series

ArrayList

felix.shao2025-02-16

ArrayList

简述

核心内容
  • 数据结构。
  • 初始化(构造函数)。
  • 添加元素。
  • 移除元素。
  • 查找。
  • 扩容(含自动扩容)。
ArrayList 简介

 ArrayList 是 JDK1.2 开始支持的。
 ArrayList 是一种线性数据结构，它的底层是用数组实现的，相当于动态数组。与 Java 中的数组相比，它的容量能动态增长。类似于 C 语言中的动态申请内存，动态增长内存。
 当创建一个数组的时候，就必须确定它的大小，系统会在内存中开辟一块连续的空间，用来保存数组，因此数组容量固定且无法动态改变。ArrayList 在保留数组可以快速查找的优势的基础上，弥补了数组在创建后，要往数组添加元素的弊端。
 ArrayList 的一些特性汇总如下：

  1. 元素存放的数据与放进去的顺序相同，允许放入 null 元素。
  2. 除该类未实现同步外，其余跟 Vector 大致相同。
  3. 每个 ArrayList 都有一个容量（capacity），表示底层数组的实际大小，容器内存储元素的个数不能多于当前容量。当向容器中添加元素时，如果容量不足，容器会自动增大底层数组的大小。
  4. 快速查找：在物理内存上采用顺序存储结构，因此可根据索引快速的查找元素。

详述

ArrayList 类图array_list_diagram.png
  • AbstractList 提供了 List 接口的默认实现（个别方法为抽象方法）。
  • List 接口定义了列表必须实现的方法。
  • 实现了 RandomAccess 接口：提供了随机访问功能。RandmoAccess 是 Java 中用来被 List 实现，为 List 提供快速访问功能的。在 ArrayList 中，我们即可以通过元素的序号快速获取元素对象；这就是快速随机访问。
  • 实现了 Cloneable 接口：可以调用 Object.clone 方法返回该对象的浅拷贝。
  • 实现了 java.io.Serializable 接口：可以启用其序列化功能，能通过序列化去传输。未实现此接口的类将无法使其任何状态序列化或反序列化。序列化接口没有方法或字段，仅用于标识可序列化的语义。
数据结构和核心方法
public class ArrayList<E> ...{

    // 保存 ArrayList 中数据的数组
    transient Object[] elementData;

    // ArrayList 中实际数据的数量   
    private int size;

    public boolean add(E e)...

    public boolean addAll(Collection<? extends E> c)...

    public E set(int index, E element)...

    public E get(int index)...

    public E remove(int index)...

    public void trimToSize()...

}

 数据结构主要是 elementData、size。

  • elementData 存储 ArrayList 内的元素，size 表示它包含的元素的数量。其中 transient 是因为 Java 的 serialization 提供了一种持久化对象实例的机制。当持久化对象时，可能有一个特殊的对象数据成员，我们不想用 serialization 机制来保存它。为了在一个特定对象的一个域上关闭 serialization，可以在这个域前加上关键字 transient。

TIP

 ArrayList 中 elementData 为什么被 transient 修饰?
 答案可参考ArrayList 中 elementData 为什么被 transient 修饰open in new window。

初始化

 ArrayList 提供了三种方式的构造器，可以构造一个指定初始容量的空列表、构造一个默认初始容量为 10 的空列表以及构造一个包含指定 collection 的元素的列表，这些元素按照该 collection 的迭代器返回它们的顺序排列的。

/** 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 构造函数。默认构造一个空的集合，在add时会扩容。 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

/** 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 {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

TIP

 ArrayList 中默认的初始化容量是 10，通过跟踪调试源码发现，public ArrayList()...默认应该是 0，在 add 时，会进行最小容量为 10 的扩容处理。

添加元素-add
/** 添加一个元素，直接添加到数组末尾 */
public boolean add(E e) {
    // 扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

/** 在指定索引添加一个元素 */
public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 将数组原 index 到最后的数据后移移位，然后 index 索引处替换为添加的元素
    System.arraycopy(elementData, index, elementData, index + 1,
                        size - index);
    elementData[index] = element;
    size++;
}

/** 检查元素索引是否合理 */
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
添加元素-addAll
/** 在末尾索引处开始添加集合的所有元素 */
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;

    // 并发时的 fail-fast 机制
    // 未实际验证：从代码上看，多个线程 checkForComodification 都通过后，各自的 parent.addAll... 还是可以正常执行不会报错的，但是结果不会达到预期的效果
    checkForComodification();
    parent.addAll(parentOffset + index, c);
    this.modCount = parent.modCount;
    this.size += cSize;
    return true;
}

/** 以下是其父类 (AbstractList) 的方法 */
public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);
    boolean modified = false;
    for (E e : c) {
        add(index++, e);
        modified = true;
    }
    return modified;
}
移除元素-remove
/** 移除指定索引上的元素
 *  删除操作是 add() 操作的逆过程，需要将删除点之后的元素向前移动一个位置。需要注意的是为了让 GC 起作用，必须显式的为最后一个位置赋 null 值
 */
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;
}

/** 移除指定的元素 */
public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

/** 快速移除指定索引的元素 */
private void fastRemove(int index) {
    modCount++;
    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
}
查找元素-get
/** 查找元素 */
public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

E elementData(int index) {
    return (E) elementData[index];
}
扩容(含自动扩容)

 每当向数组中添加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求。数组扩容通过一个公开的方法 ensureCapacity(int minCapacity) 来实现。在实际添加大量元素前，我也可以使用 ensureCapacity 来手动增加 ArrayList 实例的容量，以减少递增式再分配的数量。
 数组进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长大约是其原容量的 1.5 倍。这种操作的代价是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时，要在构造 ArrayList 实例时，就指定其容量，以避免数组扩容的发生。或者根据实际需求，通过调用 ensureCapacity 方法来手动增加 ArrayList 实例的容量。

/** 扩容方法入口 */
public void ensureCapacity(int minCapacity) {
    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 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);
}

/** 分配的数组的最大大小，尝试分配更大的数组可能会导致 OutOfMemoryError: 请求的数组大小超过 VM 限制 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/** 真实扩容处理，容量增加为原来的 1.5 倍 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    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);
}

/** 数组容量溢出情况处理 */
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}
其他方法-trimToSize
/** 将底层数组的容量调整为当前列表保存的实际元素的大小 */
public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
            ? EMPTY_ELEMENTDATA
            : Arrays.copyOf(elementData, size);
    }
}
其他方法-indexOf、lastIndexOf
/** 获取元素的第一次出现的 index */
public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

/** 获取元素的最后一次出现的 index */
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;
}
其他方法-toArray
public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

总结

TIP

  • size(), isEmpty(), get(), set() 方法均能在常数时间内完成。
  • add() 方法的时间开销跟插入位置有关，addAll() 方法的时间开销跟添加元素的个数成正比。其余方法大都是线性时间。
  • 为追求效率，ArrayList 没有实现同步（synchronized），如果需要多个线程并发访问，用户可以手动同步，也可使用 Vector 替代。

参考文献

Last Updated 2/18/2025, 2:43:17 PM
ON THIS PAGE