前言

• ArrayList是大家代码中经常使用的数据结构，但是ArrayList底层是怎么实现的，大家知道吗？
• 今天带大家对ArrayList源码进行剖析，了解其底层数据结构。

目录

捕获.PNG

1.概述

先来学习一下官方文档：

Resizable-array implementation of the <tt>List</tt> interface. Implements
all optional list operations, and permits all elements, including
<tt>null</tt>. In addition to implementing the <tt>List</tt> interface,
this class provides methods to manipulate the size of the array that is
used internally to store the list. (This class is roughly equivalent to
<tt>Vector</tt>, except that it is unsynchronized.)

1. 动态数组，会自动扩容，允许元素为null。
2. ArrayList不是同步的，也就是说不是线程安全的，要实现同步可以使用Vector或者调用Collections的相关方法：

List list = Collections.synchronizedList(new ArrayList(...))

2.源码分析

2.1 关键成员变量解释

    //默认初始容量
    private static final int DEFAULT_CAPACITY = 10;

    //空数组, 当用户指定该 ArrayList 容量为 0 时，返回该空数组
    //例如：ArrayList<String> a = new ArrayList<String>(0);
    private static final Object[] EMPTY_ELEMENTDATA = {};

    //空数组，当调用ArrayList的无参构造函数时，返回该空数组
    //例如：ArrayList<String> a = new ArrayList<String>();
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    //真正用于存储数据的数组
    transient Object[] elementData; 

    //数组中元素的个数，注意不是数组的长度
    private int size;

2.2 构建方法分析

//传入初始初始容量，根据初始容量进行处理：大于0则创建长度为initialCapacity的数组，并赋值给elementData；
//等于0则把空数组EMPTY_ELEMENTDATA赋值给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);
        }
    }

    // 创建一个 空的 ArrayList，此时其内数组缓冲区 elementData = {}, 长度为 0
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_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;
        }
    }

2.3 add() 方法解析

• add方法是了解集合底层结构的关键，通过分析元素的插入过程能过够知道底层的实现。

    public boolean add(E e) {
        // 动态扩容的关键
        ensureCapacityInternal(size + 1);  // Increments modCount!!
       //在size+1的位置进行赋值
         elementData[size++] = e;
        return true;
    }

    private void ensureCapacityInternal(int minCapacity) {
      //使用无参构造函数创建ArrayList实例时第一次调用add()会进入这里，初始容量为10，
      //第二次调用add()就不会了，原因是： 第一次调用add()方法时会
      //调用elementData = Arrays.copyOf(elementData, newCapacity)，此时elementData 会指向新的数组，不是指向DEFAULTCAPACITY_EMPTY_ELEMENTDATA
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
       //第一次调用add()时，minCapacity  = 10，lementData.length = 0，调用grow方法
      //第二次调用add()时，minCapacity = size + 1，等于2，而elementData.length =10，不会调用grow方法。以此类推。
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    private void grow(int minCapacity) {
        // overflow-conscious code
      //每次扩容新的数组长度是原来的1.5倍
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
      //调用add()只能增加一个元素，但是扩容后数组长度是原来的1.5倍，通常情况下不会出现newCapacity - minCapacity < 0的情况，
      //出现这种情况的原因有：
      //1.无参构造函数第一次调用add()时，此时newCapacity = 0，minCapacity  = 10；之后再也不会出现这种情况了
      //2.有参构造参数初始容量 = 0 ，然后前2次调用add()时，或者初始容量 = 1，第一次调用add时，具体原因思考一下就明白了
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
      //判断数组长度是否超出MAX_ARRAY_SIZE 
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        //创建一个长度为newCapacity的新数组，并把数组的数据复制在对应的位置上
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

Arrays.copyOf 方法

public static <T> T[] copyOf(T[] original, int newLength) {
        return (T[]) copyOf(original, newLength, original.getClass());
    }

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
        //根据class的类型是否是 Object[] 来决定是 new 还是反射去构造一个长度为newLength的数组
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        //将数组数据复制新创建的数组中，复制的长度为Math.min(original.length, newLength)，避免数组越界
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

2.4 get()方法解析

 public E get(int index) {
        //检测范围
        rangeCheck(index);
        //返回下标为index的元素
        return elementData(index);
    }
 private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
 E elementData(int index) {
        return (E) elementData[index];
    }

3.与Vector比较

3.1 构造函数比较

    public Vector(int initialCapacity, int capacityIncrement) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }
    public Vector(int initialCapacity) {
        this(initialCapacity, 0);
    }
    public Vector() {
        this(10);
    }

• 无论调用哪个构造函数最终都会调用Vector(int initialCapacity, int capacityIncrement)，其中initialCapacity为初始容量，capacityIncrement为每次数组扩容增加的数组长度，由此可以发现有2处不同的地方：

• Vector调用无参构造时直接初始话一个长度为10的数组，而ArrayList调用无参构造函数时初始化一个空数组，直到首次调用add()方法才创建一个长度为10的数组

• Vector可以指定每次扩容增加多少长度，而ArrayList无法指定

3.2 add()方法比较

public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }
private void ensureCapacityHelper(int minCapacity) {
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;  
        //注意这里扩容后新的数组长度的变化
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

• Vector的add（）方法使用关键字synchronized 修饰，所以是线程安全的，而ArrayList不是线程安全的，其实除了add方法，几乎Vector的所有方法都使用synchronized修饰，Vector是线程同步的，但是效率很低，一般不赞成使用。
• Vector扩容多少根据capacityIncrement而定，capacityIncrement为0时则数组长度变为原来的两倍，不为0则在原来的数组长度上增加capacityIncrement，而ArrayList每次扩容长度变为原来的1.5倍

总结

1. ArrayList底层是动态数组，，每次扩容数组长度变为原来的1.5倍。
2. ArrayList按数组下标访问get(i)，或者在末尾插入元素，效率很高，但是在中间位置删除元素，插入元素，以及扩容都需要调用System.arraycopy()来操作元素，性能比较差。