ArrayList源码分析

文章目录

• ArrayList源码分析
• • 一、整体架构
  • • 1. 结构图
    • 1. 使用时的注意事项
    • 1. 基本过程分析
  • 二、源码分析
  • • 1. 成员属性
    • 1. 构造函数
    • • 2.1 无参数初始化
      • 2.2 指定大小初始化
      • 2.3 指定初始数据初始化
    • 1. 成员方法
    • • 3.1 add(E e)方法
      • 3.2 remove(Object o)方法
      • 3.3 get(int index)方法

一、整体架构

• ArrayList是一种以数组实现的List，与数组相比，它具有动态扩展的能力，因此也可称之为动态数组

• 继承体系

  

  • ArrayList实现了List，提供了基础的添加、删除、遍历等操作
  • ArrayList实现了RandomAccess，提供了随机访问的能力，也就是可以通过角标访问元素
  • ArrayList实现了Cloneable，可以被克隆
  • ArrayList实现了Serializable，可以被序列化

1. 结构图

• 图中展示的是长度为 10 的数组，index 表示数组的下标，从 0 开始计数，elementData 表示数组本身

2. 使用时的注意事项

• ArrayList可以添加（多个）null值

• size、isEmpty、get、set、add(E e) (添加到末尾) 方法时间复杂度是 O (1)

  • add(int index, E element) (添加到指定位置) 时间复杂度是 O (n)，因为要将插入位置之后的元素后移
  • remove() 时间复杂度是 O (n)，因为要将删除位置之后的元素前移

• 是线程不安全的，效率较高，如果想要线程安全但损失一部分效率可以使用Vector替换

  • 只有当 ArrayList 作为共享变量时，才会有线程安全问题，当 ArrayList 是方法内的局部变量时，是没有线程安全问题的
  • ArrayList 有线程安全问题的本质是因为 ArrayList 在进行添加、扩容等各种操作时，都没有加锁，而且自身的 elementData、size、modConut 这些变量并非是可见的（volatile），所以如果多个线程对这些变量进行操作时，可能会有值被覆盖的情况

• 增强 for 循环，或者使用迭代器迭代过程中，如果数组大小被改变，会快速失败，抛出异常

  • 比如下面这段代码，会抛出 ConcurrentModificationException 异常（并发修改异常）

    ArrayList<String> list = new ArrayList<>();
    list.add("贾玲");
    list.add("贾冰");
    list.add("贾岛");
    //获取集合迭代器
    Iterator<String> iterator = list.iterator();
    //遍历集合元素
    while (iterator.hasNext()) { 
        String name = iterator.next();
        if(name.equals("贾冰")) { 
            //改变集合元素个数
            list.add("假货");
        }
    }

  • 原因分析

    • 调用 list.iterator(); 方法创建迭代器时，会执行 expectedModCount = modCount;， modcount 表示ArrayList集合被修改的次数，每执行一次add方法，就会将modCount+1，此时的 modCount 和 expectedModCount 值为3（添加了三个元素）
    • 当执行到 list.add("假货"); 时，modCount值为4，但此时expectedModCount值为3

    • 调用 iterator.next(); 方法时，会调用next方法中的 checkForComodification(); ，这个方法中有一行代码

      if (modCount != expectedModCount)
          throw new ConcurrentModificationException();

    • 由于 4 != 3，故抛出异常

3. 基本过程分析

• ArrayList中维护了一个Object类型的数组elementData

• 创建ArrayList对象时，如果使用的是空参构造器，则初始elementData容量为0

  • 第一次添加元素时，将elementData扩容为10，再次扩容时，将elementData扩容为1.5倍

• 创建ArrayList对象时，如果使用的是指定大小的构造器

  • 初始elementData容量为指定大小，如果需要扩容，将elementData扩容为1.5倍

二、源码分析

1. 成员属性

//默认容量为10
private static final int DEFAULT_CAPACITY = 10;
//空数组，如果构造器指定的容量为0时使用
private static final Object[] EMPTY_ELEMENTDATA = { };
//空数组，构造器为空参时使用，添加第一个元素的时候会重新初始为默认容量大小10
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = { };
//存储元素的数组
transient Object[] elementData; 
//数组中元素的个数，注意不是elementData数组的长度
//没有使用volatile修饰，非线程安全的
private int size;
//数组的最大容量，Integer类型的最大整数-8
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//AbstractList类中的属性
//统计当前数组被修改的次数，数组结构有变动，就会+1
protected transient int modCount = 0;

2. 构造函数

2.1 无参数初始化

public ArrayList() { 
    //如果没有传入初始容量，则使用空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA
    //添加第一个元素的时候会扩容到默认大小10
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

2.2 指定大小初始化

初始容量如果大于0就初始化elementData为指定大小，如果等于0就使用EMPTY_ELEMENTDATA空数组，如果小于0抛出异常

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

2.3 指定初始数据初始化

会使用拷贝把参数集合的元素拷贝到elementData数组中，如果参数集合元素个数为0，则初始化elementData数组为EMPTY_ELEMENTDATA空数组

public ArrayList(Collection<? extends E> c) { 
    //将参数集合转换成数组赋值给elementData，elementData长度与参数c一致
    elementData = c.toArray();
    //如果给定的集合c有数据
    if ((size = elementData.length) != 0) { 
        //如果集合元素类型不是Object类型，将其转换成Object类型
        if (elementData.getClass() != Object[].class) { 
            //调用Arrays.copyOf方法
            elementData = Arrays.copyOf(elementData, size, Object[].class);
        }
    } 
    //如果给定的集合c没有数据
    else { 
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

Arrays.copyOf方法源码如下：

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) { 
    @SuppressWarnings("unchecked")
    //要将复制后的元素放在copy数组中，即copy是目标数组
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    //调用arraycopy方法
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

System.arraycopy 方法源码如下：

此方法是native本地方法

/** * @param src 被拷贝的数组 * @param srcPos 从源数组哪里开始拷贝 * @param dest 目标数组 * @param destPos 从目标数组哪个索引位置开始放被拷贝的元素 * @param length 从源数组拷贝的长度 * 此方法是没有返回值的 */
public static native void arraycopy(Object src, int srcPos,
                                    Object dest, int destPos,
                                    int length);

问题：为什么 c.toArray() 返回的有可能不是Object[]类型呢？

• Collection集合的toArray()源码 Object[] toArray();

• 看下述代码

  public class Test { 
      public static void main(String[] args) { 
          Collection<String> collection = new MyList();
          System.out.println(collection.toArray().getClass());
          //class [Ljava.lang.String;
          //不是Object[]类型
      }
  }
  class MyList extends ArrayList<String> { 
      @Override
      public String[] toArray() { 
          return new String[]{ "我爱", "学习"};
      }
  }

3. 成员方法

3.1 add(E e)方法

• 判断是否需要扩容，如果需要则执行扩容操作

  • 扩容会先新建一个符合预期容量的新数组，然后把旧数组的数据拷贝过去
• 添加元素到末尾，平均时间复杂度为 O(1)

add(E e) 方法源码如下：

public boolean add(E e) { 
    //调用ensureCapacityInternal判断数组能否放下添加的那个元素，不能的话则扩容
    ensureCapacityInternal(size + 1);
    //添加元素到末尾
    elementData[size++] = e;
    return true;
}

ensureCapacityInternal 方法源码如下：

private void ensureCapacityInternal(int minCapacity) { 
    //调用calculateCapacity得到数组的目标容量
    //判断如果数组是空的（第一次扩容），则得到默认容量10，否则使用size + 1的容量
    //调用ensureExplicitCapacity确定数组的最终容量，如果目标容量 > 当前容量，则扩容，否则不扩容
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

calculateCapacity 方法源码如下：

private static int calculateCapacity(Object[] elementData, int minCapacity) { 
    //如果是空数组（第一次扩容），就初始化为默认大小10
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

ensureExplicitCapacity 方法源码如下：

private void ensureExplicitCapacity(int minCapacity) { 
    //对数组执行了add方法，计数器+1
    modCount++;
    //elementData.length表示此时还没有扩容的数组的容量
    //minCapacity表示将要被扩容的容量（期望的容量）
    //也就是说如果此时数组的容量还没有达到期望的容量，就要执行grow方法进行真正的扩容操作
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

grow 方法源码如下：

private void grow(int minCapacity) { 
    //参数minCapacity表示期望容量
    //记录未扩容时的数组的容量，方便计算原数组的1.5倍
    int oldCapacity = elementData.length;
    //新容量为旧容量+旧容量的一半，也就是旧容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //如果扩容后的值<期望值，则将期望值作为扩容后的值
    //比如第一次扩容时，0的1.5倍还是0，当然要扩容为期望值10
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    //如果扩容后的值比数组的最大容量还大，调用hugeCapacity进行判断：
    //如果目标容量大于数组最大容量，则返回Integer的最大值
    //如果目标容量没有达到数组最大容量，则返回数组最大容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    //调用Arrays.copyOf将原数组的元素复制到扩容后的新数组中
    //Arrays.copyOf方法之前已讲解过，不再赘述
    elementData = Arrays.copyOf(elementData, newCapacity);
}

hugeCapacity 方法源码如下：

private static int hugeCapacity(int minCapacity) { 
    if (minCapacity < 0) 
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
}

需要注意的地方：

• 什么时候需要扩容？

  • 期望容量（初次为10，其余为size + 1） > 目前数组容量
• 扩容的规则并不是翻倍，是原来容量大小 + 容量大小的一半，即原来容量的 1.5 倍
• ArrayList 中的数组的最大值是 Integer.MAX_VALUE，超过这个值，JVM 就不会给数组分配内存空间了
• 新增时，并没有对值进行严格的校验，所以 ArrayList 是允许 null 值的
• 没有任何锁控制，所以这些操作是线程不安全的
• 对于 add(int index, E element) 方法，也就是将元素插入到指定位置，需要判断index是否越界，判断是否需要扩容，还需要将插入位置之后的元素全部往后挪一位，代码基本与 add(E e) 一致，不再赘述
• 对于 addAll(Collection c) 方法，也就是将参数c的元素全部添加到原数组的尾部，需要求出c的长度，判断是否需要扩容，代码基本与 add(E e) 一致，不再赘述

3.2 remove(Object o)方法

ArrayList删除元素有很多种方式，比如根据数组索引删除、根据值删除或批量删除等等，原理和思路都差不多，这里选取根据值删除方式来进行源码的讲解

remove(Object o) 方法源码如下：

删除集合中第一个取值为o的元素，删除成功需要将后面的元素全部向前挪一位，删除失败返回false

public boolean remove(Object o) { 
    //如果要删除的值是null，找到第一个值是null的元素将其删除
    if (o == null) { 
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) { 
                //调用fastRemove方法删除
                fastRemove(index);
                return true;
            }
    }
    //如果要删除的值不为null，找到第一个和要删除的值相等的元素将其删除
    else { 
        for (int index = 0; index < size; index++)
            //根据equals方法判断是否相等，调用fastRemove方法删除
            //因为调用equals，故需要将null值分开判断，否则出现空指针异常
            if (o.equals(elementData[index])) { 
                fastRemove(index);
                return true;
            }
    }
    //删除失败返回false
    return false;
}

fastRemove 方法源码如下：

private void fastRemove(int index) { 
    //删除元素，计数器加1
    modCount++;
    //numMoved表示删除位置之后有多少个元素需要向前挪动
    //假设长度为5，删除位置是1，那么需要将后面的3个元素向前挪动
    int numMoved = size - index - 1;
    if (numMoved > 0)
        //通过复制的方式将元素向前挪动
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    //数组最后一个位置赋值null，帮助GC
    elementData[--size] = null;
}

需要注意的地方：

• 新增的时候没有对 null 进行校验，所以删除的时候也是允许删除 null 值的
• 找到值在数组中的索引位置是通过 equals 来判断的，如果数组元素不是基本类型，需要关注 equals 的具体实现
• ArrayList删除元素的时候并没有缩容，只是将元素前移后空出的最后一个位置赋予null值，方便回收

3.3 get(int index)方法

获取指定索引位置的元素，时间复杂度为O(1)

get(int index) 方法源码如下：

public E get(int index) { 
    //越界检查
    rangeCheck(index);
    //调用elementData方法
    return elementData(index);
}
//越界检查方法如下
private void rangeCheck(int index) { 
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//elementData方法如下
E elementData(int index) { 
    return (E) elementData[index];
}