揭秘Java中的瑞士军刀——ArrayList源码解析

/**
 * 编写一个ArrayList的简单实用demo
 * ArrayList 的常见方法包括：
 *     add(element):添加元素
 *     get(index):获取下标元素
 *     remove(index):移除下标对应元素
 *     set(index,element):将index处的元素修改为element
 */
public static void main(String[] args) {
    // 创建 ArrayList 的对象
    ArrayList data = new ArrayList();
    // 添加元素
    data.add("Java面试教程");
    // 构造随机数并进行添加
    Random rnd = new Random();

    System.out.println("随机20个数字添加进入data集合");
    for (int i = 0; i < 20; i++) {
        data.add(rnd.nextInt(1000));
    }
    // 取出ArrayList里的元素进行打印
    System.out.println("取出ArrayList里的元素进行打印");
    for (int i = 0; i < data.size(); i++) {
        System.out.print(data.get(i) + "  ");
    }
    // 修改1号index成的元素为了不起
    System.out.println();
    data.set(1, "了不起");
    System.out.println("修改1号index成的元素为了不起：data.set(1, \"了不起\")");
    for (int i = 0; i < data.size(); i++) {
        System.out.print(data.get(i) + "  ");
    }
    System.out.println("");
    // 移除“了不起”元素
    System.out.println("移除“了不起”元素：data.remove(1)");
    data.remove(1);
    for (int i = 0; i < data.size(); i++) {
        System.out.print(data.get(i) + "  ");
    }
    System.out.println("");
}

// ArrayList 初始化时默认大小为10
private static final int DEFAULT_CAPACITY = 10;

// 用于空实例的共享空数组实例。其实就是直接初始化的话一个空数组
private static final Object[] EMPTY_ELEMENTDATA = {};

//构造一个具有指定初始容量的空列表,初始化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);
    }
}
//构造一个初始容量为10的空列表。
//如果不传入大小的话就默认大小是10，那么这里就有一个问题：
//我们上面插入的元素超过了10，继续插入元素就会进行拷贝扩容，性能不是特别高。
//所以我们一般情况下初始化时给定一个比较靠谱的数组大小，避免到时候导致元素不断拷贝
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

public boolean add(E e) {
    // 增量modCount
    ensureCapacityInternal(size + 1);  
    elementData[size++] = e;
    return true;
}
//这个方法用于确保ArrayList的容量足够容纳新元素。它首先调用ensureExplicitCapacity(calculateCapacity(elementData, minCapacity))来确定所需的最小容量
private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//这个方法用于计算ArrayList的容量。如果传入的elementData是默认的空元素数组，则返回默认容量和最小容量中的较大值；否则，返回传入的最小容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
}
//这个方法用于确保ArrayList的容量足够容纳新元素。它首先增加modCount（用于记录集合修改次数），然后检查是否需要扩容。如果需要的最小容量减去当前数组长度大于0，就调用grow(minCapacity)方法进行扩容操作。
private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
}

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++;
}
//这个方法用于检查给定的索引是否在有效范围内。如果索引大于当前列表的大小或小于0，就会抛出IndexOutOfBoundsException异常。
private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//这个方法用于确保ArrayList的容量足够容纳新元素。它首先调用ensureExplicitCapacity(calculateCapacity(elementData, minCapacity))来确定所需的最小容量
private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//这个方法用于计算ArrayList的容量。如果传入的elementData是默认的空元素数组，则返回默认容量和最小容量中的较大值；否则，返回传入的最小容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
}
//这个方法用于确保ArrayList的容量足够容纳新元素。它首先增加modCount（用于记录集合修改次数），然后检查是否需要扩容。如果需要的最小容量减去当前数组长度大于0，就调用grow(minCapacity)方法进行扩容操作。
private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
}

public void add(E e) {
    checkForComodification();
    try {
        int i = cursor;
        ArrayList.this.add(i, e);
        cursor = i + 1;
        lastRet = -1;
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}
//它用于检查对ArrayList的修改是否被其他线程同时进行
final void checkForComodification() {
    //通过比较modCount（表示ArrayList在当前方法调用之前被修改的次数）和expectedModCount（表示ArrayList在进入该方法时期望的修改次数）来判断是否有并发修改发生
    //果两者不相等，说明在当前方法调用期间有其他线程对ArrayList进行了修改，而当前线程没有获取到正确的数据状态，因此抛出ConcurrentModificationException异常。
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

public E set(int index, E element) {
    rangeCheck(index);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}
//这个方法用于检查给定的索引是否在有效范围内。如果索引小于0或大于等于ArrayList的大小，将抛出IndexOutOfBoundsException异常。
private void rangeCheck(int index) {
    if (index < 0 || index >= this.size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

public void set(E e) {
    if (lastRet < 0)
        throw new IllegalStateException();
    checkForComodification();

    try {
        ArrayList.this.set(lastRet, e);
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

public E get(int index) {
    rangeCheck(index);
    checkForComodification();
    return ArrayList.this.elementData(offset + index);
}
//这个方法用于检查给定的索引是否在有效范围内。如果索引超出范围，它将抛出一个IndexOutOfBoundsException异常。
private void rangeCheck(int index) {
    if (index < 0 || index >= this.size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//这个方法用于检查ArrayList是否被并发修改。如果在调用此方法时ArrayList正在被修改（例如，其他线程正在添加或删除元素），那么它将抛出一个ConcurrentModificationException异常。
private void checkForComodification() {
    if (ArrayList.this.modCount != this.modCount)
        throw new ConcurrentModificationException();
}
//这是获取指定索引位置元素的主要逻辑。首先，它会计算偏移量（offset）与索引的和，得到实际的数组下标。然后，它会调用ArrayList的内部方法elementData()来获取该下标位置的元素，并将其返回。
E elementData(int index) {
    return (E) elementData[index];
}

public void remove() {
    if (lastRet < 0)
        throw new IllegalStateException();
    checkForComodification();

    try {
        ArrayList.this.remove(lastRet);
        cursor = lastRet;
        lastRet = -1;
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

public E remove(int index) {
    // 进行index是否越界的判断
    rangeCheck(index);
    checkForComodification();
    E result = parent.remove(parentOffset + index);
    this.modCount = parent.modCount;
    this.size--;
    return result;
}

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;
    return oldValue;
}

//这个方法用于检查给定的索引是否在有效范围内。如果索引超出范围，它将抛出一个IndexOutOfBoundsException异常。
private void rangeCheck(int index) {
    if (index < 0 || index >= this.size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//这是获取指定索引位置元素的主要逻辑。首先，它会计算偏移量（offset）与索引的和，得到实际的数组下标。然后，它会调用ArrayList的内部方法elementData()来获取该下标位置的元素，并将其返回。
E elementData(int index) {
    return (E) elementData[index];
}

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

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

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // 这里做了位运算，相当于数组扩容了1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 随后进行元素拷贝
    elementData = Arrays.copyOf(elementData, newCapacity);
}