转载

Java 集合系列1、细思极恐之ArrayList

ArrayList底层数据结构为 动态数组 ，所以我们可以将之称为数组队列。 ArrayList 的依赖关系：

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

从依赖关系可以看出，ArrayList 首先是一个链表，其次，他具有链表的相关功能，支持快速（固定时间）定位资源位置。可以进行拷贝操作，同时支持序列化。这里我们需要重点关注的是 AbstractLit 以及 RandomAccess 。这个类，一个是定义了链表的基本属性，以及确定我们链表中的常规动作。而RandomAccess 主要是提供了快速定位资源位置的功能。

2、ArrayList 成员变量

/**
     * Default initial capacity.数组默认大小
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     空队列
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
        如果使用默认构造方法，则默认对象内容是该值
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
        用于存储数据
     */
    transient Object[] elementData; 

     // 当前队列有效数据长度
      private int size;

     // 数组最大值
     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

在ArrayList 的源码中，主要有上述的几个成员变量：

elementData ：动态数组，也就是我们存储数据的核心数组
DEFAULT_CAPACITY：数组默认长度，在调用默认构造器的时候会有介绍
size：记录有效数据长度，size（）方法直接返回该值
MAX_ARRAY_SIZE：数组最大长度，如果扩容超过该值，则设置长度为 Integer.MAX_VALUE

拓展思考： EMPTY_ELEMENTDATA 和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 都是两个空的数组对象，他们到底有什么区别呢？我们在下一节讲解构造方法的时候，会做详细对比。

3、构造方法

ArrayList中提供了三种构造方法：

ArrayList()
ArrayList(int initialCapacity)
ArrayList（Collection c）

根据构造器的不同，构造方法会有所区别。我们在平常开发中，可能会出现在默认构造器内部调用了 ArrayList（int capacity）这种方式，但是ArrayList 中对于 不同的构造器的内部实现都有所区别 ，主要跟上述提到的成员变量有关。

3.1 ArrayList（）

在源码给出的注释中这样描述：构造一个初始容量为十的空列表

/**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

从源码可以看到，它只是将 elementData 指向了 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的存储地址，而 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 其实是一个空的数组对象，那么它为什么说创建一个默认大小为10 的列表呢？

或者我们从别的角度思考一下，如果这个空的数组，需要添加元素，会怎么样？

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  //确认内部容量
        elementData[size++] = e;
        return true;
    }
    
    private void ensureCapacityInternal(int minCapacity) {
        // 如果elementData 指向的是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的地址
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            设置默认大小 为DEFAULT_CAPACITY
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //确定实际容量
        ensureExplicitCapacity(minCapacity);
    }
    
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // 如果超出了容量，进行扩展
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    
    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、add（E e）：添加元素，首先会判断 elementData 数组的长度，然后设置值

2、ensureCapacityInternal（int minCapacity）：判断 element 是否为空，如果是，则设置默认数组长度

3、ensureExplicitCapacity（int minCapacity）：判断预期增长数组长度是否超过当前容量，如果过超过，则调用grow（）

4、grow(int minCapacity)：对数组进行扩展

回到刚才的问题：为什么说创建一个默认大小为10 的列表呢？或许你已经找到答案了～

3.2 ArrayList(int initialCapacity)

根据指定大小初始化 ArrayList 中的数组大小，如果默认值大于0，根据参数进行初始化，如果等于0，指向EMPTY_ELEMENTDATA 内存地址（与上述默认构造器用法相似）。如果小于0，则抛出IllegalArgumentException 异常。

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

拓展思考：为什么这里是用 EMPTY_ELEMENTDATA 而不是跟默认构造器一样使用 DEFAULTCAPACITY_EMPTY_ELEMENTDATA ？有兴趣的童鞋可以自己县思考，经过思考的知识，才是你的～

3.3 ArrayList（Collection c）

将Collection<T> c 中保存的数据，首先转换成数组形式（toArray（）方法），然后判断当前数组长度是否为0，为 0 则只想默认数组（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;
        }
    }

3.4 总结

上述的三个构造方法可以看出，其实每个构造器内部做的事情都不一样，特别是默认构造器与 ArrayList(int initialCapacity) 这两个构造器直接的区别，我们是需要做一些区别的。

ArrayList（）：指向 DEFAULTCAPACITY_EMPTY_ELEMENTDATA ，当链表使用的时候，才会进行初始化，会通过判断是不是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 这个对象而设置数组默认大小。
ArrayList(int initialCapacity)：当 initialCapacity >0 的时候，设置该长度。如果 initialCapacity =0，则指向 EMPTY_ELEMENTDATA 在使用的时候，并不会设置默认数组长度。

因此 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 与 EMPTY_ELEMENTDATA 的本质区别就在于，会不会设置默认的数组长度。

4、添加方法（Add）

ArrayList 添加了四种添加方法：

add(E element)
add(int i , E element)
addAll(Collection<? extends E> c)
addAll(int index, Collection<? extends E> c)

4.1 add(E element)

首先看add（T t）的源码：

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // 元素个数加一，并且确认数组长度是否足够 
        elementData[size++] = e;		//在列表最后一个元素后添加数据。
        return true;
    }

结合默认构造器或其他构造器中，如果默认数组为空，则会在 ensureCapacityInternal（）方法调用的时候进行数组初始化。这就是为什么默认构造器调用的时候，我们创建的是一个空数组，但是在注释里却介绍为长度为10的数组。

4.2 add（int i , T t）

public void add(int index, E element) {
    // 判断index 是否有效
        rangeCheckForAdd(index);
    // 计数+1，并确认当前数组长度是否足够
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index); //将index 后面的数据都往后移一位
        elementData[index] = element; //设置目标数据
        size++;
    }

这个方法其实和上面的add类似，该方法可以按照元素的位置，指定位置插入元素，具体的执行逻辑如下：

1）确保数插入的位置小于等于当前数组长度，并且不小于0，否则抛出异常

2）确保数组已使用长度（size）加1之后足够存下下一个数据

3）修改次数（modCount）标识自增1，如果当前数组已使用长度（size）加1后的大于当前的数组长度，则调用grow方法，增长数组

4）grow方法会将当前数组的长度变为原来容量的1.5倍。

5）确保有足够的容量之后，使用System.arraycopy 将需要插入的位置（index）后面的元素统统往后移动一位。

6）将新的数据内容存放到数组的指定位置（index）上

4.3 addAll(Collection<? extends E> c)

public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

addAll() 方法，通过将collection 中的数据转换成 Array[] 然后添加到elementData 数组，从而完成整个集合数据的添加。在整体上没有什么特别之初，这里的collection 可能会抛出控制异常 NullPointerException 需要注意一下。

4.4 addAll(int index，Collection<? extends E> c)

public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount

        int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);

        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

与上述方法相比，这里主要多了两个步骤，判断添加数据的位置是不是在末尾，如果在中间，则需要先将数据向后移动 collection 长度的位置。

5、删除方法（Remove）

ArrayList 中提供了五种删除数据的方式：

remove（int i）
remove（E element）
removeRange（int start,int end）
clear（）
removeAll（Collection c）

5.1、remove（int i）:

删除数据并不会更改数组的长度，只会将数据重数组种移除，如果目标没有其他有效引用，则在GC 时会进行回收。

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; // 让指针最后指向空，进行垃圾回收
        return oldValue;
    }

5.2、remove（E element）:

这种方式，会在内部进行 AccessRandom 方式遍历数组，当匹配到数据跟 Object 相等，则调用 fastRemove（）进行删除

public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

fastRemove( ): fastRemove 操作与上述的根据下标进行删除其实是一致的。

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
    }

5.3、removeRange（int fromIndex, int toIndex）

该方法主要删除了在范围内的数据，通过System.arraycopy 对整部分的数据进行覆盖即可。

protected void removeRange(int fromIndex, int toIndex) {
        modCount++;
        int numMoved = size - toIndex;
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);

        // clear to let GC do its work
        int newSize = size - (toIndex-fromIndex);
        for (int i = newSize; i < size; i++) {
            elementData[i] = null;
        }
        size = newSize;
    }

5.4、clear（）

直接将整个数组设置为 null ，这里不做细述。

5.5、removeAll（Collection c）

主要通过调用：

private boolean batchRemove(Collection<?> c, boolean complement) {
        //获取数组指针
        final Object[] elementData = this.elementData;
        int r = 0, w = 0;
        boolean modified = false;
        try {
            for (; r < size; r++)
                //根据 complement 进行判断删除或留下
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
            // 进行数据整理
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            if (w != size) {
                // clear to let GC do its work
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }

在retainAll（Collection c）也有调用，主要作用分别为，删除这个集合中所包含的元素和留下这个集合中所包含的元素。

拓展思考

清楚ArrayList 的删除方法后，再结合我们常用的删除方式，进行思考，到底哪些步骤会出问题，我们通常会选择变量链表，如果匹配，则删除。我们遍历的方式有以下几种：

foreach()：主要出现 ConcurrentModificationException 异常
for(int i;**;i++)：主要出现相同数据跳过，可参考：https://blog.csdn.net/sun_flower77/article/details/78008491
Iterator 遍历：主要出现 ConcurrentModificationException 可参考：https://www.cnblogs.com/dolphin0520/p/3933551.html

避免 ConcurrentModificationException 的有效办法是使用 Concurrent包下面的 CopyOnWriteArrayList ，后续会进行详细分析

6、toArray（）

ArrayList提供了2个toArray()函数：

Object[] toArray()
T[] toArray(T[] contents)

调用 toArray() 函数会抛出“java.lang.ClassCastException”异常，但是调用 toArray(T[] contents) 能正常返回 T[]。

toArray() 会抛出异常是因为 toArray() 返回的是 Object[] 数组，将 Object[] 转换为其它类型(如如，将Object[]转换为的Integer[])则会抛出“java.lang.ClassCastException”异常，因为Java不支持向下转型。

toArray（）源码：

public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }

7、subList（）

如果我们在开发过程中有需要获取集合中的某一部分的数据进行操作，我们可以通过使用SubList（）方法来进行获取，这里会创建ArrayList 的一个内部类 SubList（）。

SubList 继承了 AbstractList，并且实现了大部分的 AbstractList 动作。

需要注意的是，SubList 返回的集合中的某一部分数据，是会与原集合相关联。即当我们对Sublist 进行操作的时候，其实还是会影响到原始集合。我们来看一下 Sublist 中的 add 方法：

public void add(int index, E e) {
        rangeCheckForAdd(index);
            checkForComodification();
            parent.add(parentOffset + index, e);
            this.modCount = parent.modCount;
            this.size++;
        }

可以看到，Sublist 中的加操作，其实还是调用了 parent（也就是原集合）中的加操作。所以在使用subList方法时，一定要想清楚，是否需要对子集合进行修改元素而不影响原有的list集合。

总结

ArrayList总体来说比较简单，不过ArrayList还有以下一些特点：

ArrayList自己实现了序列化和反序列化的方法，因为它自己实现了 private void writeObject(java.io.ObjectOutputStream s)和 private void readObject(java.io.ObjectInputStream s) 方法
ArrayList基于数组方式实现，无容量的限制（会扩容）
添加元素时可能要扩容（所以最好预判一下），删除元素时不会减少容量（若希望减少容量，trimToSize()），删除元素时，将删除掉的位置元素置为null，下次gc就会回收这些元素所占的内存空间。
线程不安全
add(int index, E element)：添加元素到数组中指定位置的时候，需要将该位置及其后边所有的元素都整块向后复制一位
get(int index)：获取指定位置上的元素时，可以通过索引直接获取（O(1)）
remove(Object o)需要遍历数组
remove(int index)不需要遍历数组，只需判断index是否符合条件即可，效率比remove(Object o)高
contains(E)需要遍历数组
使用iterator遍历可能会引发多线程异常