深度解析ArrayList：灵活高效的动态数组实现-六虎

在 Java 调集结构中，ArrayList 是一个常用而强壮的类，它提供了动态数组的完成，答应在运行时动态调整数组的巨细。 ArrayList 是 List 接口的完成类，根据动态数组的数据结构。它能够存储恣意类型的目标，并提供了丰富的办法，包含增加、删去、遍历等，使其在各种场景下都能发挥重要作用。

arrayList.jpg

底层数据结构

ArrayList 的底层数据结构是动态数组，其容量是动态调整的。这意味着 ArrayList 能够根据需要自动增长或缩小。

比方有一个ArrayList,size = 3;

arrayList.png

ArrayList特色源码如下：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;
    // 默许初始容量
    private static final int DEFAULT_CAPACITY = 10;
    // 空数组实例，用于空 ArrayList 的初始值
    private static final Object[] EMPTY_ELEMENTDATA = {};
    // 默许巨细的空数组实例，用于默许初始容量的 ArrayList
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    // 存储ArrayList元素的数组。
    // ArrayList的容量便是这个数组的长度。
    // 任何elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空ArrayList，
    // 在增加第一个元素时会扩展为DEFAULT_CAPACITY。
    transient Object[] elementData; // non-private to simplify nested class access
    // ArrayList 的巨细（元素的数量）
    private int size;
    //带初始化容量参数的结构办法
    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;
    }
    .
    .
    .
}

从源码能够看到，elementData数组是实践存储元素的当地。size变量盯梢ArrayList的巨细。当你向ArrayList中增加元素时，它们会存储在elementData数组中，并相应地更新size。

对于 ArrayList 中的 elementData 字段，它被声明为 transient 的意图是在序列化时避免将数组内容直接序列化到耐久存储中。这是由于 ArrayList 的实践元素或许只占用数组的一部分，而不是整个数组。在反序列化时，elementData 会在结构目标时被从头初始化。

在 ArrayList 类中，详细的反序列化进程是通过完成 readObject 办法来完成的。在该办法中，elementData 被从头赋值，以便在反序列化后正确恢复 ArrayList 目标。

以下是 ArrayList 中的关键部分，用于反序列化：

private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    // 将 elementData 初始化为 EMPTY_ELEMENTDATA
    elementData = EMPTY_ELEMENTDATA;
    // Read in size, and any hidden stuff
    s.defaultReadObject();
    // Read in capacity
    s.readInt(); // ignored
    if (size > 0) {
        // be like clone(), allocate array based upon size not capacity
        int capacity = calculateCapacity(elementData, size);
        SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
        ensureCapacityInternal(size);
        Object[] a = elementData;
        // Read in all elements in the proper order.
        for (int i=0; i<size; i++) {
            a[i] = s.readObject();
        }
    }
}

初始化容量

在运用 new ArrayList() 初始化时，ArrayList 的内部数组 elementData 初始化为一个空数组（EMPTY_ELEMENTDATA），并在增加第一个元素时才进行实践的初始化和分配。默许情况下，ArrayList 的初始容量为 10，即创建一个长度为 10 的空数组。当向 ArrayList 增加元素时，假如容量不足，会触发扩容机制，将数组长度扩展为原来的 1.5 倍。


//带初始化容量参数的结构办法
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;
}

扩容机制

ArrayList 的扩容机制是在 ensureCapacityInternal 和 grow 办法中完成的。当元素个数达到当时容量的 75% 时，会触发扩容，将数组长度扩展为原来的 1.5 倍。

当咱们向ArrayList 中增加元素(调用add()或许addAll())时,都调用了一个ensureCapacityInternal（）办法

咱们来看源码：

add()

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

addAll()

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

从源码能够看到，这两个办法都调用了ensureCapacityInternal（）这个办法，参数是当时list的长度加上要刺进的目标个数（单个目标的话为1，目标调集的话是调集的长度），既调集增加元素所需最小的长度

ensureCapacityInternal（）

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

ensureExplicitCapacity() 办法的入参是calculateCapacity（）（参数是存储实践元素的数组和调集增加元素所需最小的长度）办法处理后的值。

calculateCapacity（）

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

当时办法回来的值是假如源调集是空的，则回来默许容量（10）和元素调集增加元素所需最小的长度值比较，值大的一个，若不为空则回来minCapacity。

_20230828230112.png

ensureExplicitCapacity()

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

grow()

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);
}

咱们来详细解读下这段代码

int oldCapacity = elementData.length;

获取当时数组的容量，也便是elementData数组的长度，即当时存储元素的数组长度。

int newCapacity = oldCapacity + (oldCapacity >> 1);

核算新的容量。这里运用位运算右移1位（相当于除以2）的方式，将当时容量扩展1.5倍。

if (newCapacity – minCapacity < 0)

查看核算得到的新容量是否满足最小容量要求。假如不满足，则将新容量设置为最小容量minCapacity。

if (newCapacity – MAX_ARRAY_SIZE > 0)

查看新容量是否超过了最大数组容量约束。MAX_ARRAY_SIZE是ArrayList内部定义的一个常量，表明数组的最大容量。假如新容量超过这个约束，就调用hugeCapacity(minCapacity)办法来获得一个足够大的容量。

_20230828230251.png

_20230828230304.png

elementData = Arrays.copyOf(elementData, newCapacity);

运用Arrays.copyOf()办法将原有的elementData数组复制到一个新数组中，新数组的容量为核算得到的新容量newCapacity。这完成了实践的数组扩容操作。

特色

随机访问元素效率高，由于底层是数组。

增加、删去元素效率较低，由于或许需要移动元素。

答应存储重复元素。

答应存储 null 元素。

支撑动态调整容量。

适用场景

适用于频频读取元素和随机访问的场景。

不适用于频频增加和删去元素的大规模操作，由于这或许导致功能下降。

ArrayList不是线程安全的，不适合在多线程环境下运用。

总结：

ArrayList 是 Java 调集结构中一款强壮而灵敏的动态数组完成，它的规划和功能特色使得它在许多场景下都能发挥重要作用。在实践开发中，根据详细需求挑选适宜的调集类是至关重要的，而 ArrayList 无疑是一个常用的挑选。

通过本文的深度解析，希望读者能更全面地了解 ArrayList，并在实践项目中充分发挥其优势，提高代码的效率和可维护性。

深度解析ArrayList：灵活高效的动态数组实现

底层数据结构

初始化容量

扩容机制

特色

适用场景

总结：

相关文章

微软开源DeepSpeed Chat，人人可快速训练百亿、千亿级ChatGPT大模型

Android Profiler (二)应用之分析内存泄露

一步一图带你深入理解 Linux 虚拟内存管理

JS 数据结构与算法——数组/列表

作者信息