Java SDK源码剖析之ArrayList篇章（第四部分）

文章标题：

Java SDK源码解读之ArrayList相关内容（第四部分）

文章内容：

目录

• 1. 定义
• 2. 使用方式
• 3. 原理探究
  • 3.1. uml关系
  • 3.2. 构造机制
  • 3.3. 添加元素方法
  • 3.3.1. 保障容量满足新增需求
  • 3.3.2. 将元素放置到数组末尾位置
  • 3.4. 按索引删除元素方法
  • 3.4.1. 将索引位置之后的数组元素向前移动
  • 3.4.2. 更新元素数量（数组不自动缩容）
  • 3.5. 按元素内容删除方法
  • 3.5.1. 首先定位要删除元素的索引
  • 3.5.2. 将索引位置之后的数组元素向前移动
  • 3.5.3. 更新元素数量（数组不自动缩容）
• 4. ConcurrentModificationException相关
  • 4.1. 原因剖析
  • 4.2. 解决办法

1. 定义

它是基于数组实现的、能够动态扩容的顺序存储结构，具有有序特性且允许元素重复

2. 使用方式

public class ArrayListDemo
{
    public static void main(String[] args)
    {
        ArrayList<Integer> listInstance = new ArrayList<>();
        listInstance.add(1);
        listInstance.add(2);

        System.out.println(listInstance);

        listInstance.remove(0);
        listInstance.remove(Integer.valueOf(2));

    }
}

3. 原理探究

3.1. uml关系

可以看出ArrayList实现了List接口，具备克隆和序列化能力，同时支持通过索引快速访问元素

3.2. 构造机制

采用Object类型的数组作为底层存储，初始长度为0

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    //默认初始容量为10，当使用无参构造时初始容量为0，首次扩容会达到10
    private static final int DEFAULT_CAPACITY = 10;

    //无元素时使用的空数组
    private static final Object[] EMPTY_ELEMENTDATA = {};
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    //底层存储元素的Object数组
    transient Object[] elementData; 

    //数组中实际元素的数量
    private int size;

    public ArrayList() {
        //默认使用空数组初始化
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
}

3.3. 添加元素方法

• 不扩容时时间复杂度为O（1），扩容时为O（N）

public boolean add(E element) {
    //确保容量足够容纳新元素
    ensureCapacityInternal(size + 1);  // 增加修改计数!!
    //将元素放置到数组末尾并更新元素数量
    elementData[size++] = element;
    return true;
}

3.3.1. 保障容量满足新增需求

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

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    //使用无参构造创建的实例初始容量为0，首次扩容为10
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return 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);
}

private static int hugeCapacity(int minCapacity) {
    //容量溢出情况处理
    if (minCapacity < 0) // 溢出
        throw new OutOfMemoryError();
    //根据情况返回最大可能容量
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

3.3.2. 将元素放置到数组末尾位置

//简单赋值并更新元素数量
elementData[size++] = element;

3.4. 按索引删除元素方法

• 时间复杂度为O（N）

public E remove(int index) {
    //检查索引有效性
    rangeCheck(index);

    modCount++;
    //保存要删除的元素以便返回
    E removedValue = elementData(index);

    //计算需要移动的元素数量
    int movedCount = size - index - 1;
    if (movedCount > 0)
        //将后面的元素向前移动
        System.arraycopy(elementData, index+1, elementData, index,
                         movedCount);
    //数组实际大小未变，但需更新元素数量并清理原位置
    elementData[--size] = null; // 让GC回收空间

    return removedValue;
}

3.4.1. 将索引位置之后的数组元素向前移动

//计算需要移动的元素个数
int movedCount = size - index - 1;
if (movedCount > 0)
    //将后面的元素复制到前面
    System.arraycopy(elementData, index+1, elementData, index,
                     movedCount);

3.4.2. 更新元素数量（数组不自动缩容）

//数组大小未实际改变，但需更新元素数量并清理原位置
elementData[--size] = null; // 让GC回收空间

3.5. 按元素内容删除方法

• 时间复杂度为O（N）

public boolean remove(Object target) {
    //处理目标为null的情况
    if (target == null) {
        for (int idx = 0; idx < size; idx++) {
            if (elementData[idx] == null) {
                fastRemove(idx);
                return true;
            }
        }
    } else {
        for (int idx = 0; idx < size; idx++) {
            if (target.equals(elementData[idx])) {
                fastRemove(idx);
                return true;
            }
        }
    }
    return false;
}

3.5.1. 首先定位要删除元素的索引

for (int idx = 0; idx < size; idx++)
{
//...
}

上述代码主要是遍历查找目标元素的索引，时间复杂度为O（N），找到索引后执行删除操作，如下：

快速删除方法

private void fastRemove(int index) {
    modCount++;
    //计算需要移动的元素数量
    int movedCount = size - index - 1;
    if (movedCount > 0)
        //将后面的元素向前移动
        System.arraycopy(elementData, index+1, elementData, index,
                         movedCount);
    //更新元素数量并清理原位置
    elementData[--size] = null; // 让GC回收空间
}

该方法逻辑与按索引删除元素的逻辑类似

3.5.2. 将索引位置之后的数组元素向前移动

//计算需要移动的元素个数
int movedCount = size - index - 1;
if (movedCount > 0)
    //将后面的元素复制到前面
    System.arraycopy(elementData, index+1, elementData, index,
                     movedCount);

3.5.3. 更新元素数量（数组不自动缩容）

//更新元素数量并清理原位置
elementData[--size] = null; // 让GC回收空间

4. ConcurrentModificationException相关

参考：fail-fast.md

public class ConcurrentModificationDemo
{
    public static void main(String[] args)
    {
        List<String> stringList = new ArrayList<>();
        for (int i = 0; i < 1000; i++)
        {
            stringList.add(String.valueOf(i));
        }

        for (String item : stringList)
        {
            stringList.remove(item);//会抛出java.util.ConcurrentModificationException异常
        }
    }
}

上述代码运行时会抛出ConcurrentModificationException异常

4.1. 原因剖析

在遍历（增强for循环本质是迭代器遍历）过程中执行删除操作会触发快速失败机制，这是由于modCount和expectedCount不一致导致的

4.2. 解决办法

使用JUC包下支持fail-safe机制的CopyOnWriteArrayList