1. 概述

ArrayList本质上是一个数组, 它内部通过对数组的操作实现了 List 功能, 所以 ArrayList 又被叫做动态数组. 每个 ArrayList 实例都有容量, 会自动扩容. 它可添加 null, 有序可重复, 线程不安全.Vector 和ArrayList内部实现基本是一致的, 除了 Vector 添加了 synchronized 保证其线程安全.

1.1 继承体系

2. 源码解析

2.1 属性

/**
 * 默认初始容量
 */
private static final int DEFAULT_CAPACITY = 10;
 
/**
 * 初始容量为 0 时,elementData 指向此对象(空元素对象)
 */
private static final Object[] EMPTY_ELEMENTDATA = {};
 
/**
 * 调用 ArrayList()构造方法时,elementData 指向此对象(默认容量空元素对象)
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
 
/**
 * 用于存储集合元素, 非 private 类型能够简化内部类的访问(在编译阶段)
 */
transient Object[] elementData;
 
/**
 * 包含的元素个数
 */
private int size;

为什么 DEFAULT_CAPACITY 这种变量为什么要声明为 private static final 类型

private是为了把变量的作用范围控制在类中.

static修饰的变量是静态变量.JVM只会为静态变量分配一次内存. 这样无论对象被创建多少次, 此变量始终指向的都是同一内存地址. 达到节省内存, 提升性能的目的.

final修饰的变量在被初始化后, 不可再被指向别的内存地址, 以防变量的地址被篡改.

2.2 构造方法

无参构造方法

public ArrayList() {
        // 无参构造器方法, 将 elementData 指向 DEFAULTCAPACITY_EMPTY_ELEMENTDATA
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

指定容量构造方法

public ArrayList(int initialCapacity) {if (initialCapacity > 0) {
        //initialCapacity 大于 0 时, 将 elementData 指向新建的 initialCapacity 大小的数组.
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        //initialCapacity 为空时, 将 elementData 指向 EMPTY_ELEMENTDATA
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity:" +
                initialCapacity);
    }
}

指定集合构造方法

public ArrayList(Collection<? extends E> c) {
    // 将 elementData 指向 c 转换后的数组
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {//c.toArray 可能不会返回 Object[], 所以需要手动检查下. 关于这点, 会单独讲解下, 看 3.3
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // 如果 elementData.length 为 0, 将 elementData 指向 EMPTY_ELEMENTDATA.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

ArrayList的无参构造方法使用频率是非常高的, 在第一次添加元素时, 会将 capacity 初始化为 10. 在我们知道 ArrayList 中需要存储多少元素时, 使用指定容量构造方法, 可避免扩容带来的运行开销, 提高程序运行效率. 当我们需要复用 Collection 对象时, 使用指定集合构造方法.

2.3 插入

2.3.1 添加元素到列表尾部

add(E e)源码

// 将指定的元素添加到列表的末尾
public boolean add(E e) {
    // 确保内部容量, 如果容量不够则计算出所需的容量值.
    ensureCapacityInternal(size + 1);
    // 将元素插入到数组尾部,size 加一.
    elementData[size++] = e;
    return true;
}

add(E e)方法的平均时间复杂度是O(1). 它的流程大体上分为两步:

1. 保证内部容量可用;
2. 将元素添加到数组尾部;

第一步就是自动扩容机制, 具体分析参看2.3.3.

第二步则是在确保有可用容量的基础上, 在尾部添加元素, 如下图:

2.3.2 将元素插入到指定位置

add(int index, E element)源码

// 在列表的指定位置上添加指定元素, 在添加之前将在此位置上的元素及其后面的元素向右移一位.
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);
    // 将新元素插入到 index 处.
    elementData[index] = element;
    // 元素个数加一.
    size++;
}
 
// 检查索引是否越界
private void rangeCheckForAdd(int index) {if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

add(int index, E element)的平均时间复杂度是O(N). 所以在大容量的集合中不要频繁使用此方法, 否则可能会产生效率问题. 在指定位置添加元素的流程如下图所示:

2.3.3 自动扩容

ensureCapacityInternal(int minCapacity)源码

    // 是否需要扩容
    private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
 
    // 计算容量
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        // 如果 elementData 指向 DEFAULTCAPACITY_EMPTY_ELEMENTDATA, 返回 DEFAULT_CAPACITY 和 minCapacity 中的较大值.
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        // 否则直接返回 minCapacity
        return minCapacity;
    }
 
    // 确保明确的容量
    private void ensureExplicitCapacity(int minCapacity) {
        // 修改次数加一
        modCount++;
 
        // 如果 minCapacity 大于 elementData 数组长度, 那么进行扩容.
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
 
    // 要分配的最大数组大小
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 
    /**
     * 增加容量确保数组至少能够容纳最小容量参数指定的元素个数.
     *
     * @param minCapacity 所需的最小容量
     */
    private void grow(int minCapacity) {
        // 声明 oldCapacity 为 elementData 长度
        int oldCapacity = elementData.length;
        // 将 newCapacity 声明为 oldCapacity 的 1.5 倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 如果 newCapacity 小于 minCapacity, 将 newCapacity 指向 minCapacity
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // 如果 newCapacity 超出了最大数组长度, 调用 hugeCapacity()方法计算 newCapacity.
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 根据 newCapacity 生成一个新的数组, 并将 elementData 老数据放入 elementData 中.
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
 
    /**
     *
     * @param minCapacity 最小容量
     * @return 计算后的容量
     */
    private static int hugeCapacity(int minCapacity) {
        // 如果 minCapacity 小于 0, 抛出内存溢出异常.
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        // 比较得出所需容量
        return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
    }

自动扩容的流程参看上面代码, 总结几个要点:

• 如果使用的是 new ArrayList() 构造方法, 在添加第一个元素时, 容量会被设置为 DEFAULT_CAPACITY(10) 大小.
• 容量会被扩容为之前的 1.5 倍
• 如果扩容后的容量大于 MAX_ARRAY_SIZE, 那么将Integer.MAX_VALUE 作为容量.

2.4 删除

remove(int index)

    // 移除指定索引位置元素
    public E remove(int index) {
        //index 越界检查
        rangeCheck(index);
 
        modCount++;
        // 获取将要删除的元素
        E oldValue = elementData(index);
        // 获取将要移动的元素个数
        int numMoved = size - index - 1;
        if (numMoved > 0)
            // 将 index 之后的元素向左移一位
            System.arraycopy(elementData, index + 1, elementData, index,
                    numMoved);
        //size 减一, 并将 elementData 数组最后一个元素指向 null, 让 GC 进行操作
        elementData[--size] = null; // clear to let GC do its work
 
        return oldValue;
    }
 
    @SuppressWarnings("unchecked")
    E elementData(int index) {return (E) elementData[index];
    }

remove(Object o)

    // 删除指定元素
    public boolean remove(Object o) {
        // 如果对象为 null, 删除数组中的第一个为 null 的元素. 没有 null 元素的话则不会变化
        if (o == null) {for (int index = 0; index < size; index++)
                if (elementData[index] == null) {fastRemove(index);
                    return true;
                }
        } else {
            // 删除数组中的第一个为 o 的元素, 没有则不操作.
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {fastRemove(index);
                    return true;
                }
        }
        return false;
    }
 
    // 省略了越界检查, 而且不会返回被删除的值, 反映了 JDK 将性能优化到极致.
    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
    }

删除操作的平均时间复杂度是O(N), 其主要步骤是:

1. 将索引后面的元素向左移一位;
2. 数组的最后一个元素赋值为null;
3. size减一;

具体步骤如下图所示:

2.5 遍历

ArrayList实现了 RandomAccess 接口.RandomAccess是标识接口, 标识实现类能够快速随机访问存储元素. 因为 ArrayList 的底层是数组, 通过下标 index 访问. 所以在 ArrayList 元素量较大时, 应当使用普通 for 循环, 也就是通过下标进行访问. 而 LinkedList 此层是链表, 不具备快速随机访问的能力, 因此没有实现 RandomAccess 接口, 推荐使用 forEach 遍历 (也就是Iterator 遍历).

测试代码:

@Test
public void test6() {
    // 实现了 RandomAccess 接口，底层是数组的 ArrayList 测试
    List<Long> arrayList = new ArrayList<>(150000000);
    Random random = new Random();
    // 为了更好的展示测试结果, 避免程序运行时间过长,arrayList 和 linkedList 添加元素的个数不同.
    for (int i = 0; i < 100000000; i++) {arrayList.add(random.nextLong());
    }
    System.out.println("======ArrayList======");
    traverseByLoop(arrayList);
    traverseByIterator(arrayList);
 
    System.out.println("======LinkedList======");
    // 没有实现 RandomAccess 接口, 底层是链表的 LinkedList 测试
    LinkedList<Long> linkedList = new LinkedList<>();
    for (int i = 0; i < 100000; i++) {linkedList.add(random.nextLong());
    }
    traverseByLoop(linkedList);
    traverseByIterator(linkedList);
}
 
// 普通 for 循环进行遍历
public void traverseByLoop(List<Long> list) {long startTime = System.currentTimeMillis();
    for (int i = 0; i < list.size(); i++) {list.get(i);
    }
    long endTime = System.currentTimeMillis();
    System.out.println("RandomAccess 遍历用时:" + (endTime - startTime) + "ms");
}
 
//Iterator 遍历
public void traverseByIterator(List<Long> list) {long startTime = System.currentTimeMillis();
    Iterator<Long> iterator = list.iterator();
    while (iterator.hasNext()) {iterator.next();
    }
    long endTime = System.currentTimeMillis();
    System.out.println("Iterator 遍历用时:" + (endTime - startTime) + "ms");
}

运行 test6() 方法, 控制台输出:

======ArrayList======
RandomAccess 遍历用时:4ms
Iterator 遍历用时:10ms
======LinkedList======
RandomAccess 遍历用时:5572ms
Iterator 遍历用时:3ms

3. 其它细节

3.1fail-fast机制

在 Iterator 被创建后, 如果 List 对象不是调用 iterator 的remove()或 add(Object obj) 方法更改内部结构.iterator就会抛出 ConcurrentModificationException. 以此避免在迭代过程中List 对象不可知的变化. 这个机制只能用来侦测异常的操作, 并不能作为并发操作的保障. 在 JDK1.5 新增的 forEach 循环, 其本质就是用迭代器遍历. 下面用 forEach 语法来对 fail-fast 机制进行测试.

@Test
public void test1() {List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3));
    for (Integer num : list) {if (1 == num) {list.remove(num);
        }
    }
    System.out.println(list);
}

由于在遍历过程中调用了 List 的remove()方法, 导致程序检测到非法修改, 抛出异常.

3.2fail-fast失效

在 forEach 中删除 List 的倒数第二个元素,fail-fast不会生效.

@Test
public void test2() {List<Integer> list = new ArrayList<>(Arrays.asList(1, 2));
 
    for (Integer num : list) {if (1 == num) {list.remove(num);
        }
    }
    System.out.println(list);
}

forEach是 java 的语法糖, 为了搞清楚为啥出现上面的问题, 我们将上面的代码转换为 Iterator 遍历.

@Test
public void test3() {List<Integer> list = new ArrayList<>(Arrays.asList(1, 2));
 
    Iterator<Integer> iterator = list.iterator();
 
    while (iterator.hasNext()) {Integer next = iterator.next();
        if (1 == next) {list.remove(next);
        }
    }
 
    System.out.println(list);
}

首先看看 list.iterator() 的源码, 看看这个 Iterator 是啥?

public Iterator<E> iterator() {return new Itr();
}

Itr类是 ArrayList 的内部类, 咱来看看源码.

private class Itr implements Iterator<E> {
    // 下一个要返回元素的索引, 默认为 0.
    int cursor;
    // 之前返回元素的索引, 默认为 -1.
    int lastRet = -1;
    // 保存创建时 modCount 的值
    int expectedModCount = modCount;
 
    Itr() {}
 
    public boolean hasNext() {return cursor != size;}
 
    @SuppressWarnings("unchecked")
    public E next() {
        //fail-fast 检测
        checkForComodification();
        // 将 i 值声明为 cursor
        int i = cursor;
        //index 越界检查
        if (i >= size)
            throw new NoSuchElementException();
 
        Object[] elementData = ArrayList.this.elementData;
        // 如果 i 值大于等于当前数组的长度,fail-fast
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        // 光标加一
        cursor = i + 1;
        // 对 lastRet 赋值并返回值.
        return (E) elementData[lastRet = i];
    }
 
    // 每次操作时比较 expectedModCount 和 modCount 的值, 若不一致, 抛出 ConcurrentModificationException
    final void checkForComodification() {if (modCount != expectedModCount)
            throw new ConcurrentModificationException();}
}

从 while (iterator.hasNext()) 开始分析, 第一次进入 hasNext() 方法.cursor为 0,size为 2, 返回 true, 进入循环体. 然后进入next() 方法, 正常执行,cursor变为 1 ,lastRet变为 0. 然后开始执行 ArrayList 的remove()方法,modCount变为 1,size变为 1 . 这时候再进入第二次循环, 执行 hasNext() 方法,cursor是 1 ,size也是 1 , 返回 false, 退出循环体. 因此fail-fast 失效. 所以不要在 forEach 循环中使用非 Iterator 的方法进行增删操作,fail-fast也不能完全避免数据被更改的风险, 从源头规避风险是首选.

3.3c.toArray()返回非Object[]

在 ArrayList 的集合构造器源码中有 c.toArray might (incorrectly) not return Object[] 这句注释. 就上网查了下这个问题. 我们先来看下代码:

@Test
public void test5() {
    // 获取并输出 Object 数组类型
    Object[] objArr = new Object[0];
    //class [Ljava.lang.Object;
    System.out.println(objArr.getClass());
 
    // 通过 Arrays.asList()方法构建 List 对象. 该对象的 class 不是 Object[]类型.
    List<Integer> list1 = Arrays.asList(1, 2, 3);
    //class [Ljava.lang.Integer;
    System.out.println(list1.toArray().getClass());
 
    // 通过 new ArrayList 构造器创建 List 对象
    ArrayList<Integer> list2 = new ArrayList<>(Arrays.asList(4, 5, 6));
    //class [Ljava.lang.Object;
    System.out.println(list2.toArray().getClass());
}

控制台输出:

class [Ljava.lang.Object;
class [Ljava.lang.Integer;
class [Ljava.lang.Object;

可以看到通过 Arrays.asList(1, 2, 3) 创建的对象 class 不是 Object[] 类型. 至于具体原因不再分析, 感兴趣的朋友研究下哈.

3.4elementData为啥定义为transient

ArrayList自己根据 size 序列化真实的元素, 而不是根据数组的长度序列化元素, 减少了空间占用.

4. 参考

田小波 -ArrayList 源码分析

彤哥读源码 - 死磕 java 集合之 ArrayList 源码分析

IT 从业者说 -RandomAccess 这个空架子有何用？