Java集合（二）：ArrayList

Catalogue

1. 1 初始化
2. 2 add(E e)
3. 3 add(int index, E element)
4. 4 remove(int index)
5. 5 get(int index)
6. 6 遍历
7. 7 总结
8. 参考资料

注意
本系列文章是笔者在参考了大量优秀文章的基础上的理解，由于水平有限，难免会出现错误，望批评指正，同时我也会把自己最新的理解及时更新到文章中去。最后，我会在文中注明参考文章，特别感谢这些无私奉献的作者。

1 初始化

ArrayList的初始化有三种方式。

第一种方式:

//private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

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

其中，DEFAULTCAPACITY_EMPTY_ELEMENTDATA 是一个空数组，elementData 就是代表该 ArrayList 的数组元素。

第二种方式:

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 时，增加了新建数组的逻辑。

第三种方式:

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

这个方式有一点复杂度，我们来一步一步分析它。首先，调用c.toArray()语句将传入的集合转化成数组并赋值给elementData。之后当数组长度为0时，直接赋值空数组，否则判断当前数组是不是Object[]类型的数组，如果不是，则重新新建一个Object数组，并将新数组赋值给elementData。

那么，为什么要if (elementData.getClass() != Object[].class)呢?

我们来看一个场景：

List<String> list = Arrays.asList("item01", "item02");
Object[] objects = list.toArray();
objects[0] = new Object();

这段代码运行后，会抛出 java.lang.ArrayStoreException异常，该异常说明objects已经是一个有确定类型的数组了，该类型是String，而现在要把父类Object塞进去，显然是不可以的。

基于上面的分析，我们来换一种写法试试。

List<String> list = Arrays.asList("item01", "item02");
List<String> listCopy = new ArrayList<>(list);
Object[] objects = listCopy.toArray();
objects[0] = new Object();

运行不报错了。这就是第三种方式中为什么要判断数组类型是否是Object[]类型的原因，为的就是保证数组的类型一定是Object[]类型，这样将list转化成数组后可以接受类型为Object的元素，满足了 Java 的多态要求。

2 add(E e)

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

该方法的作用是添加元素到数组尾部。

ensureCapacityInternal(size + 1)方法有两个作用，一个是增加 modCount 的计数（该变量是保证fast-fail的关键）,另一个是扩容判断。

我们一路跟踪，来到下面的方法。

private void ensureExplicitCapacity(int minCapacity) {
       modCount++;

       // overflow-conscious code
       if (minCapacity - elementData.length > 0)
           grow(minCapacity);
   }

当最小需要的空间(minCapacity)大于数组当前的大小时，则执行 grow 方法扩容。

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

这里首先将新的容量扩大到原来的1.5倍，如果仍然小于minCapacity，则将新的容量大小直接赋值为 minCapacity，紧接着看新的容量是否大于了MAX_ARRAY_SIZE（MAX_ARRAY_SIZE ==Integer.MAX_VALUE - 8）,如果大于，还要执行 hugeCapacity 方法重新计算新的容量，最后基于新的容量将原来的值赋值到新数组上。

注意，看到这里，不知道屏幕前的你有没有发现，ArrayList无论是在初始化还是在扩容过程中，都是确保了
elementData 永远是Oject[]类型的数组，这样做就是为了以后将该List转化为数组后，可以接受Object类型的元素，而不是只能接受具体类型的元素。

3 add(int index, E element)

该方法的作用是在特定位置插入元素。

public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

具体流程是，检查index是否越界->扩容检查->将index之后的元素往后移->将 element 赋值到 index 位置->数组 size 加 1。

4 remove(int index)

public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        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
        return oldValue;

原理和add(int index, E element)类似，核心都是通过System.arraycopynative方法实现。

5 get(int index)

public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

E elementData(int index) {
        return (E) elementData[index];
    }

获取元素更简单，直接根据 index 返回数组对应位置的元素即可。

6 遍历

对于ArrayList的遍历方式主要有两种。

第一种:

for (int i=0;i<size;i++) {
            System.out.println(list.get(i));
        }

第二种:

for (String s : list) {
            System.out.println(s);
        }

那么这两种方式有什么区别呢??

对于第二种方式是一种增强型的for循环，我们反编译一下代码。

ArrayList var0 = new ArrayList();
Iterator var1 = var0.iterator();

while(var1.hasNext()) {
      String var2 = (String)var1.next();
      System.out.println(var2);
}

可以发现，在循环之前先创建了一个 Iterator 对象，下面我们看一下这个 iterator 方法干了啥。

public Iterator<E> iterator() {
        return new Itr();
    }

Itr 是 ArrayList 的内部类，让我们继续追踪 Itr 类。

 private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;

        Itr() {}

        public boolean hasNext() {
            return cursor != size;
        }

        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
///////////////////////////////省略下面的代码

}

前面说到，如果我们修改了 ArrayList ， modCount 就会加 1。所以，如果在迭代过程中修改了 Arraylist，之后再调用 next 方法时，由于 expectedModCount 没有改变而 modCount 已经改变了，这时就会抛出 ConcurrentModificationException 异常，这也是fast-fail的原理。

如果我们就是希望在迭代过程中修改列表中的元素，可以使用 Itr 中的 remove 或者 ArrayList 另一个内部类 ListItr 的相应方法。

7 总结

ArrayList 的特征：
1、ArrayList 并不是一个线程安全的集合。如果集合的增删操作需要保证线程的安全性，可以考虑使用 CopyOnWriteArrayList 或者使collections.synchronizedList(List l)函数返回一个线程安全的ArrayList类，或者使用 Vector ,不过因为性能太低，Vector 已经废弃。
2、ArrayList 底层是一个动态扩容的数组结构。
3、允许存放重复数据，存储顺序按照元素的添加顺序。
4、允许存放（不止一个） null 元素。
5、ArrayList 扩容、删除以及插入到 index 位置的操作最终都是通过 System.arraycopy 来实现的，扩容时不仅涉及数组中内容的拷贝，而且还需要产生新的数组，所以会耗费性能。所以在需要频繁增删操作的场景下可优先考虑 LinkList 而不是 ArrayList。

知识拓展
System.arraycopy 是一个 native 方法，是用来复制数组的。它的复制方式不是用遍历的方式，而是直接复制内存，所以性能上会优于一般的遍历式复制。具体的可参考这篇文章，对于文章中提到的多维数组的复制，笔者没看懂，以后遇到这种场景再来复盘。

---

参考资料

搞懂 Java ArrayList 源码