数据结构--ArrayList实现原理及简析

ArrayList定义

ArrayList是基于List接口实现的大小可变的数组，元素允许为任意属性包括null。同时非有序，非同步(线程不安全)。主要用于装载数据。

ArrayList底层实现是数组。

因此它最擅长的是：

• 按索引随机访问
• 尾部追加元素

而对于中间位置频繁插入、删除这类需要搬移元素的场景，ArrayList通常就不是最优选择。

ArrayList的重要参数分析

//ArrayList 默认容量为10
private static final int DEFAULT_CAPACITY = 10;
//用于ArrayList 空实例时的共享空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//用于默认大小 共享空数组实例
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};
//存储ArrayList元素的数据缓冲区，ArrayList的容量是此数据缓冲区的长度
transient Object[] elementData;
//ArrayList包含的元素个数
private int size;

ArrayList初始化

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
      //创建初始容量为 initialCapacity 的数组
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
       // 初始容量为0  引用空数组实例s
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

//构造一个默认10位的数组
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;
    }
}

在ArrayList初始化中，如果不是设置了初始容量，那么数据并不会进行初始化，等到第一次add()时进行初始化。

默认构造器之所以不一上来就分配长度为10的数组，而是先共用一个空数组对象，本质上是为了减少空集合的内存占用。只有真正发生第一次插入时，才会把容量膨胀到默认值10。

ArrayList插入数据 - add()

ArrayList<String> list =new ArrayList<>();
list.add("Android");

add(E e)源码

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //在数组对应位置 放入数据
    elementData[size++] = e;
    return true;
}

ensureCapacitInternal()用来判定是否需要扩充来存储数据

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

//未初始化则 返回10  初始化完成 则是传递进来的值
 private static int calculateCapacity(Object[] elementData, int minCapacity) {
     //此时用的是默认构造器 构造的ArrayList
     if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
         return Math.max(DEFAULT_CAPACITY, minCapacity);
     }
     return minCapacity;
 }

 private void ensureExplicitCapacity(int minCapacity) {
    //修改数量 +1 
     modCount++;

     // 确保数组的容量，如果不够需要进行扩容 未初始化时 elementData.length == 0
     if (minCapacity - elementData.length > 0)
         grow(minCapacity);
 }

grow()用来进行数组扩容

private void grow(int minCapacity) {
    // 当前数组的容量
    int oldCapacity = elementData.length;
    //新数组扩容至原来的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //未初始化 min为10
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    //超出上限 则长度变为 Integer.MAX_VALUE
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 复制元素到新的数组中
    elementData = Arrays.copyOf(elementData, newCapacity);
}

扩容为1.5倍并不是随便选的：如果每次只扩一点点，扩容会太频繁；如果每次扩太多，又会浪费较多空间。1.5倍更像是在“减少扩容次数”和“控制额外空间浪费”之间做的折中。

add(int index,E element)

public void add(int index, E element) {
    // 判断 index 有没有超出索引的范围
    rangeCheckForAdd(index);
    // 和之前的操作是一样的，都是保证数组的容量足够
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 将指定位置及其后面数据向后移动一位
    System.arraycopy(elementData, index, elementData, index + 1,size - index);
    // 将该元素添加到指定的数组位置
    elementData[index] = element;
    // ArrayList 的大小改变
    size++;
}

rangeCheckForAdd() 判断要插入数据的index是否超过当前存储数据的上限size

private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

这里的关键代价在于System.arraycopy()：只要不是尾部追加，而是在中间或头部插入，就需要把后面的元素整体后移，因此这一类插入操作的时间复杂度通常是O(n)。

ArrayList获取数据 - get()

list.get(0);

get()源码

public E get(int index) {
    //判定index位置是否在范围内
    rangeCheck(index);

    return elementData(index);
}

get(index)之所以快，是因为底层数组支持通过下标直接定位到内存中的对应位置，因此随机访问的时间复杂度通常可以看作O(1)。

ArrayList删除数据 - remove()

list.remove(0);
//删除内容
list.remove("Android")

remove(int index)源码

public E remove(int index) {
    //检查index有没有超出范围
    rangeCheck(index);

    modCount++;
    //保存需要删除的数据 可以返回旧值
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        //把删除的位置后一位数据 向前移
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    //设置原位置元素为null  方便释放内存
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

remove(Object o)源码

public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        //如果有元素值 == o 找到对应的位置 并移除
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
}

无论是remove(int index)还是删除中间某个对象，一旦删除位置不是尾部，就需要把后续元素整体前移，所以删除操作在平均情况下同样更接近O(n)。

ArrayList清空数据 - clear()

list.clear()

clear()源码

public void clear() {
    modCount++;

    // 数组内所有元素置null
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

clear()做的事情主要是：

• 把当前有效元素位置置为null，帮助垃圾回收
• 将size重置为0

但它不会自动把底层数组容量缩回初始大小。也就是说，清空之后如果再次插入元素，很多时候仍然会复用原来的数组空间。

拓展

ArrayList和LinkedList的区别?

ArrayList

• 基于数组实现，可以用索引实现快速查找。是动态数组，相比于数组容量可以实现动态增长。
• ArrayList可以插入null。
• ArrayList初始容量为10，以1.5倍大小进行扩容。
• ArrayList不是线程安全。如果想线程安全可以通过Collections.synchronizeList()包裹ArrayList，实质上是对ArrayList的所有操作加了锁。推荐使用CopyOnWriteArrayList。
• 在顺序添加数据以及查找和访问数据上有优势，再删除和插入数据上 需要进行数组复制操作。

LinkdedList

• 基于链表实现，是双向链表，增删速度快。是一个双向循环链表，也可以被当做堆栈、队列使用。
• LinkedList比ArrayList更占内存，由于节点存储了数据以及前后两节点的引用
• LinkedList是线程不安全，也可以通过Collections.synchronizeList()包括LinkedList，推荐使用ConcurrentLinkedQueue
• 在数据的删除和插入上有优势

不过这里也不能把“LinkedList增删一定更快”理解得过于绝对。链表在真正插入/删除节点时改指针的成本较低，但前提是已经定位到目标位置。如果还要先遍历很长一段链表去找位置，那么这部分查找成本同样不可忽略。

ArrayList及LinkedList在插入数据上的比较

• 在头部插入数据：ArrayList需要进行一次数组复制(System.arrayCopy)而LinkedList只要遍历找到头部为止即可。所以LinkedList高效。
• 在中部插入数据
  • 插入位置越靠前：LinkedList效率越高
  • 插入位置靠中间：LinkedList的遍历是从两边开始的，往中靠效率越低。
  • 插入位置越靠后：ArrayList效率越高
• 在尾部插入数据：ArrayList可能需要触发扩容操作，导致速度不如LinkedList。当数据量大时，ArrayList不会去频繁的进行扩容，效率就会高于LinkedList。

整体上看：

• 随机访问和尾部追加：通常ArrayList更合适
• 明确知道节点位置后的局部插入删除：链表更有优势
• 但在真实工程里，很多场景下ArrayList仍然比LinkedList更常用，因为遍历局部性和访问模式通常更友好

ArrayList的序列化

transient可以关闭被修饰字段的序列化。

elementData是通过transient修饰的，那么内部的elementData是无法被序列化的。所以ArrayList内部实现了序列化及反序列化的一系列工作。

modCount在这里也值得一起理解：它记录的是集合的结构性修改次数。像add()、remove()、clear()这类会改变元素个数或内部结构的操作，都会修改modCount。迭代器和序列化等流程会拿它做一致性校验，这也是fail-fast机制的重要基础。

//保存ArrayList中的实例状态到序列中
private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();

    // Write out size as capacity for behavioural compatibility with clone()
    s.writeInt(size);

    // Write out all elements in the proper order.
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }

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

private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    elementData = EMPTY_ELEMENTDATA;

    // Read in size, and any hidden stuff
    s.defaultReadObject();

    // Read in capacity
    s.readInt(); // ignored

    if (size > 0) {
        // be like clone(), allocate array based upon size not capacity
        int capacity = calculateCapacity(elementData, size);
        SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
        ensureCapacityInternal(size);

        Object[] a = elementData;
        // Read in all elements in the proper order.
        for (int i=0; i<size; i++) {
            a[i] = s.readObject();
        }
    }
}

观察源码可知，只是序列化了ArrayList中已存在的元素，而非整个数组。