ArrayList源码剖析(jdk1.8)

其实ArrayList的源码核心就是它的扩容机制，其他代码相对简单，所以这里只分析它的

add(E e)

方法

类图

public class ArrayList<E> 
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable,java.io.Serializable
           

几个重要的属性

// 默认的初始容量
    private static final int DEFAULT_CAPACITY = 10;
    // 共享的空数组实例
    private static final Object[] EMPTY_ELEMENTDATA = {};
     // 也是一个共享的空数组实例，跟第一次添加扩容多少息息相关
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    // 内部维护的一个数组缓冲区
    transient Object[] elementData; // non-private to simplify nested class access
    // ArrayList中元素的数量
    private int size;
    // 防止内存溢出
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
           

构造方法都干了些啥

• 无参构造

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

• 带指定容量的构造器

public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            // 创建一个Object类型的数组，并让this.elementData指向它
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
           

• 带Collection集合参数的构造器，将指定的集合转换成数组并让elementData 指向它。暂时不用管它

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

前两个构造器只干一件事，就是给ArrayList中的数组赋值；

其实第三个也差不多

添加

public boolean add(E e) {
        // 判断是否需要扩容
        ensureCapacityInternal(size + 1); 
        // 把元素e放到数组中下标为size的位置，并将size加1
        elementData[size++] = e;
        return true;
    }
           

下面看下

ensureCapacityInternal(size + 1)

方法如何实现的

// minCapacity = size + 1 就是当前集合中的元素数量加1
private void ensureCapacityInternal(int minCapacity) {
        // 这个条件只有当不指定初始容量且第一次添加时才成立
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            // 取默认容量和minCapacity 的最大值
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }
           

下面看下

ensureExplicitCapacity(minCapacity)

如何实现的

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

接着往下看

grow(minCapacity)

// 扩容
private void grow(int minCapacity) {
        // 旧数组长度
        int oldCapacity = elementData.length;
        // 新数组容量 = 1.5倍的旧数组长度
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 调整新数组容量
        // 如果新数组容量小于minCapacity，则使用minCapacity作为新数组容量
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 将旧数组中元素拷贝到新数组中，然后elementData指向新数组    
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
// 大容量   
private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }    
           

至此，添加的源码看完，有点懵，minCapacity 到底是个什么东西，变来变去的，下面实例分析一下

（一）无参构造的情况

第一种情况，向ArrayList中添加第一个元素

第一次添加，minCapacity = 1

elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA条件满足

注意：这里比较的是地址，在构造方法中是赋值过的，所以条件成立

所以，minCapacity会使用初始容量10，没问题

if条件满足，进入grow方法

所以添加第一个元素时，数组的长度会变成10，size变为1

第二种情况，向ArrayList中添加第二个元素

可以看出，第二次添加就不会再走扩容了，由此我们推出当minCapacity增加到11（也就是ArrayList中元素有10个，已满）的时候才会扩容

第三种情况，添加第十一个元素

扩容，数组长度变成15了

总结一下：

• 注意：以下结论是对于无参构造而言的
• 第一次添加时，ArrayList会执行扩容，将内部维护的数组长度变为默认的初始容量值10；
• 当ArrayList中元素添加满时，会再次触发扩容；
• 每次扩容都是原来的1.5倍。

那么，如果指定了初始容量又会如何呢？

（二）指定初始容量的情况

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取两个特殊值，看一下

第一种情况，initialCapacity = 5 ，第一次添加

第一种情况，initialCapacity = 5 ，第六次添加

扩容，扩容后容量为7

第二种情况，initialCapacity = 0 ，第一次添加会扩容，扩容后容量为1

第二种情况，initialCapacity = 0 ，第二次添加又会扩容，扩容后容量为2

这样做导致每次添加元素都会扩容，所以说指定初始容量为0是个非常愚蠢的操作

总结一下：

• 当指定初始容量时
• 如果指定初始容量为0，会导致每次添加元素都会扩容，不建议这么做
• 如果指定的初始容量大于0，当ArrayList中的元素达到指定容量，就会触发扩容，可以根据实际业务的数据量进行选择，减少扩容次数，可以提升效率

问题

• 为什么会定义两个除了名称完全一样的空数组属性？

  private static final Object[] EMPTY_ELEMENTDATA = {};

  private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

  

  

  ① 当不指定初始容量时，第一次添加，

  elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA

  条件成立，设置初始容量为默认容量，将数组长度扩容为10；

  ② 当只当初始容量为0时，第一次添加，

  elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA

  条件不成立，初始容量就是0，将数组长度扩容为1；

  所以这两个属性是用来区分在指定初始容量为0和不指定初始容量两种情况下，需要扩容多少的

• 为什么ArrayList是线程不安全的？

  我们再来看一下

  add(E e)

  方法

public boolean add(E e) {
        // 1. 判断是否需要扩容，如果元素已满，则需要扩容
        ensureCapacityInternal(size + 1); 
        // 2. 将指定元素放到数组相应位置
        elementData[size++] = e;
        return true;
    }
           

case1: 下标越界

• 假设size=9，再添加一个元素集合就满了（底层数组长度为10），下一次添加就需要扩容了；
• 线程A，B同时进入ensureCapacityInternal判断是否需要扩容，两个线程得到的结果都是不需要扩容；
• 接下来线程A往下标为9的位置放了一个元素，再将size加1，没有问题；
• 紧接着线程B，拿到size，此时size已经被A修改为10了，然后，B往下标为10的位置放元素，下标越界。

  

case2: 数据覆盖，丢失

elementData[size++] = e;不是一个原子操作，可以分解为

① elementData[size] = e;

② size = size + 1;

• 假设size=1，线程A执行到第①行给下标为1的位置设置了一个元素A，还没来得及执行第②行，这个时候线程B拿到的size还是1，线程B继续向下标为1的地方设置了一个不同的值B，将A覆盖
• 线程A执行② ，size=2
• 线程B执行②，size=3
• 所以下标为1的位置的元素将会是B，下标为2的位置的元素将是null