深入剖析ArrayList数据结构：源码和扩容机制

前语

ArrayList是Java中常用的数据结构之一，它完成了List接口，能够动态地增加或删去元素。在实践开发中，咱们经常运用ArrayList来存储和操作数据。本文将从源码和扩容机制两个方面来详细介绍ArrayList的完成原理。

一、ArrayList源码剖析

ArrayList的源码位于java.util包中，它是一个数组完成的动态列表。在ArrayList中，元素是按照刺进顺序存储的，能够依据索引访问元素。

界说

ArrayList界说如下：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

能够看到，ArrayList完成了List接口，并承继了AbstractList抽象类。其间，List接口界说了大部分操作办法，而AbstractList供给了默认的完成。

  • RandomAccess 是一个标志接口，表明完成这个接口的 List 集合是支撑快速随机访问的。在 ArrayList 中，咱们即能够经过元素的序号快速获取元素对象，这就是快速随机访问。
  • ArrayList 完成了 Cloneable 接口 ，即覆盖了函数clone()，能被克隆。
  • ArrayList 完成了 java.io.Serializable接口，这意味着ArrayList支撑序列化，能经过序列化去传输。

成员变量

ArrayList的成员变量包含：

在ArrayList中，主要有三个成员变量：

// 默认初始容量
private static final int DEFAULT_CAPACITY = 10;
// 存储元素的数组
private transient Object[] elementData;
// 元素的数量
private int size;

能够看到，elementData是存储元素的数组，size是元素的数量。transient关键字表明该成员变量不会被序列化。

结构函数

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);
    }
}
// 运用默认初始容量
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

能够看到，在指定初始容量的结构函数中，假如initialCapacity大于0，则新建一个elementData数组，创立一个指定容量的ArrayList；假如等于0，则运用空数组EMPTY_ELEMENTDATA；不然抛出反常。而在运用无参结构函数创立ArrayList时，实践上初始化赋值的是一个空数组，当真实对数组进行增加元素操作时，才真实分配容量，即向数组中增加第一个元素时，数组容量扩为10。

PS:JDK6 new 无参结构的ArrayList对象时，直接创立了长度是 10 的Object[]数组 elementData 。

办法

ArrayList的办法包含：

增加元素

ArrayList供给了多个增加元素的办法，最常用的是以下两个：

// 在末尾增加元素
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // 保证容量满足
    elementData[size++] = e;  // 增加元素
    return true;
}
// 在指定方位刺进元素
public void add(int index, E element) {
    rangeCheckForAdd(index);  // 查看下标是否越界
    ensureCapacityInternal(size + 1);  // 保证容量满足
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);  // 移动元素
    elementData[index] = element;  // 刺进新元素
    size++;  // 元素数量+1
}

在增加元素时，首要需求保证容量满足，即调用ensureCapacityInternal办法进行判别和扩容操作。然后，依据是在末尾增加元素仍是在指定方位刺进元素，别离进行增加操作。

删去元素

ArrayList供给了多个删去元素的办法，最常用的是以下两个：

// 经过下标删去元素
public E remove(int index) {
    rangeCheck(index);  // 查看下标是否越界
    modCount++;  // 修改次数+1
    E oldValue = elementData(index);  // 获取要删去的元素
    int numMoved = size - index - 1;
    if (numMoved > 0) {
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);  // 移动元素
    }
    elementData[--size] = null;  // 将最终一个元素置为null
    return oldValue;  // 返回要删去的元素
}
// 从列表中删去指定元素的第一个出现（假如存在）。 假如列表不包含该元素，则它不会更改。
// 返回true，假如此列表包含指定的元素
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;
}

二、扩容机制剖析

ArrayList的扩容机制是其完成的一个重要特点。在源码中，咱们能够看到扩容办法ensureCapacityInternal()和grow()的完成。当增加元素时，假如当时容量缺乏，则会调用ensureCapacityInternal()办法进行扩容。该办法会先判别当时数组是否为空，假如为空，则将容量设置为默认值10；不然，将容量设置为当时容量的1.5倍。假如扩容后的容量仍然不行，则直接运用所需的容量。假如所需的容量超越了最大容量，则抛出OutOfMemoryError反常。

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
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);
}

在grow()办法中，首要核算新的容量newCapacity，它是原有容量oldCapacity的1.5倍。然后，判别新容量是否满足，假如不行，则运用所需的容量。假如所需的容量超越了最大容量，则抛出OutOfMemoryError反常。最终，运用Arrays.copyOf()办法将原有数组复制到新数组中。

总结

ArrayList是Java中最常用的集合之一，它是一个动态数组，能够主动扩容。在本文中，咱们深入剖析了ArrayList的完成原理，包含源码和扩容机制。咱们了解到，ArrayList的源码包含成员变量、结构函数和办法。ArrayList的扩容机制是在元素数量超越当时容量时，创立一个新的数组，并将原数组中的元素复制到新数组中。新数组的容量是原数组容量的1.5倍。假如新数组的容量小于指定的最小容量，则运用指定的最小容量。