浅谈ArrayList扩容机制

一、前言

java中标准数组是定长的，在数组被创建之后，它们不能被加长或缩短。这就意味着在创建数组时需要知道数组的所需长度，但有时我们需要动态程序中获取数组长度。ArrayList就是为此而生的。

ArrayList类又称动态数组，同时实现了Collection和List接口，其内部数据结构由数组实现，因此可对容器内元素实现快速随机访问。但因为ArrayList中插入或删除一个元素需要移动其他元素，所以不适合在插入和删除操作频繁的场景下使用。

二、成员变量

// 默认的容量大小（常量） private static final int DEFAULT_CAPACITY = 10; // 定义的空数组（final修饰，大小固定为0） private static final Object[] EMPTY_ELEMENTDATA = { 
   }; // 定义的默认空容量的数组（final修饰，大小固定为0） private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = { 
   }; // 定义的不可被序列化的数组，实际存储元素的数组 transient Object[] elementData; // 数组中元素的个数 private int size; 

三、构造方法

3.1 无参构造

public ArrayList() { 
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } 

elementData被赋予了默认空容量的数组，也就是说其容量此时是0，元素个数size为默认值0。

3.2 指定容量大小的构造方法

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

当initialCapacity > 0时，会在堆上new一个大小为initialCapacity的数组，然后将其引用赋给elementData，此时ArrayList的容量为initialCapacity，元素个数size为默认值0。

当initialCapacity = 0时，elementData被赋予了默认空数组，因为其被final修饰了，所以此时ArrayList的容量为0，元素个数size为默认值0。

当initialCapacity < 0时，会抛出异常。

3.3 初始化数据的构造方法

public ArrayList(Collection<? extends E> c) { 
    elementData = c.toArray(); if ((size = elementData.length) != 0) { 
    // c.toArray might (incorrectly) not return Object[] (see ) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { 
    // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; } } 

传入Collection元素列表后，构造方法首先会将其转化为数组，将其索引赋给elementData。

如果此数组的长度为0，会重新赋予elementData为空数组，此时ArrayList的容量是0，元素个数size为0。

如果此数组的长度大于0，会更新size的大小为其长度，也就是元素的个数，然后执行里面的程序。大家对里面的代码可能不理解，让我们等会看下面解析。执行完后此时ArrayList的容量为传入序列的长度，也就是size的大小，同时元素个数也为size，也就是说，此时ArrayList是满的。

让我们来看看下面的代码，然后再去理解上面 if 语句的代码：

public class Test { 
    public static void main(String[] args) { 
    // 1.创建Student对象数组 Student[] students = new Student[] { 
    new Student("小明", 18), new Student("小李", 19), new Student("小张", 21) }; // 2.将其赋值给Object对象数组 Object[] objects = students; // 3.执行if语句前，打印数组的class System.out.println("执行前：" + objects.getClass()); // 4.执行上面的代码 if (objects.getClass() != Object[].class) { 
    objects = Arrays.copyOf(objects, objects.length, Object[].class); } // 5.执行if语句后，打印数组的class System.out.println("执行后：" + objects.getClass()); } } 

二、扩容机制

2.1 源码

ArrayList扩容发生在add()方法调用的时候，下面是add()方法的源码

public boolean add(E e) { 
    ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } 

ensureCapacityInternal()是用来扩容的，形参为最小扩容量：当前容量+1

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

扩容之前首先要获得当前容量，即calculateCapacity方法，如果数组为空，则容量为默认容量10

private static int calculateCapacity(Object[] elementData, int minCapacity) { 
    //如果传入的是数组则最小容量取默认容量与minCapacity之间的最大值 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
    return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } 

获取当前容量后，需要判断是否需要扩容，即ensureExplicitCapacity

private void ensureExplicitCapacity(int minCapacity) { 
    //快速报错机制 modCount++; // 如果最小需要空间比当前数组容量大，则需要扩容 if (minCapacity - elementData.length > 0) //扩容 grow(minCapacity); } 

ArrayList扩容的关键方法grow()

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); // 调用Arrays.copyOf方法将elementData数组指向新的内存空间时newCapacity的连续空间 // 并将elementData的数据复制到新的内存空间 elementData = Arrays.copyOf(elementData, newCapacity); } 

从此方法中我们可以清晰的看出其实ArrayList扩容的本质就是计算出新的扩容数组的size后实例化，并将原有数组内容复制到新数组中去。

2.2 扩容分析

1. 第一种情况，当ArrayList的容量为0时，此时添加元素的话，需要扩容，三种构造方法创建的ArrayList在扩容时略有不同：

   （1） 无参构造，创建ArrayList后容量为0，添加第一个元素后，容量变为10，当插入第11个元素时，才会扩容。

   （2）传容量构造，当参数为0时，创建ArrayList后容量为0，添加第一个元素后，容量为1，此时ArrayList是满的，下次添加元素时需正常扩容。

   （3）传列表构造，当列表为空时，创建ArrayList后容量为0，添加第一个元素后，容量为1，此时ArrayList是满的，下次添加元素时需正常扩容。

2. 当ArrayList的容量大于0，并且ArrayList是满的时，此时添加元素的话，进行正常扩容，每次扩容到原来的1.5倍。

三、总结

• ArrayList的底层数据结构是数组，所以查找遍历快，增删慢。
• ArrayList可随着元素的增长而自动扩容，正常扩容的话，每次扩容到原来的1.5倍。
• ArrayList的线程是不安全的。