附图：

timg.jpg

一： 结构关系

public class ArrayList<E> 
extends AbstractList<E> 
implements List<E>,RandomAccess, Cloneable, Serializable {

ArrayList结构.png

二： 介绍

(1)：List 接口的大小可变数组的实现。实现了所有可选列表操作，并允许包括 null 在内的所有元素。
(2)：ArrayList是基于动态数组实现的，数组具有按索引查找的特性，所以访问很快，适合经常查询的数据。
(3)： 由于其依赖于数组，所以它查询快，增删慢（维护索引）
(4)：不是线程安全的

三： 重要知识点

（1）：重要属性
（2）：ArrayList的创建：即构造器
（3）：往ArrayList中添加对象：即add(E)方法
（4）：获取ArrayList中的单个对象：即get(int index)方法
（5）：删除ArrayList中的对象：即remove(E)方法
（6）：遍历ArrayList中的对象：即iterator，在实际中更常用的是增强型的for循环去做遍历
（7）：判断对象是否存在于ArrayList中：contain(E)
（8）：ArrayList中对象的排序：主要取决于所采取的排序算法

四：源码介绍

4.1重要属性：

   //序列号
    private static final long serialVersionUID = 8683452581122892189L;


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

    /** 
     * 一个空数组 
     * - 当用户指定该 ArrayList 容量为 0 时，返回该空数组 
     * - ArrayList(int initialCapacity) 
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /** 
     * ArrayList基于数组实现，用该数组保存数据, ArrayList 的容量就是该数组的长度 
     * - 该值为EMPTY_ELEMENTDATA 时，当第一次添加元素进入 ArrayList 中时，数组将扩容值 DEFAULT_CAPACITY(10) 
     */
    private transient Object[] elementData;

    //ArrayList实际存储的数据数量 
    private int size;

注意

（1）：transient关键字的作用：在采用Java默认的序列化机制的时候，被该关键字修饰的属性不会被序列化。
（2）：ArrayList类实现了java.io.Serializable接口，即采用了Java默认的序列化机制
（3）：上面的elementData属性采用了transient来修饰，表明其不使用Java默认的序列化机制来实例化，但是该属性是ArrayList的底层数据结构，在网络传输中一定需要将其序列化，之后使用的时候还需要反序列化，那不采用Java默认的序列化机制，那采用什么呢？直接翻到源码的最下边有两个方法，
（4）：发现ArrayList自己实现了序列化和反序列化的方法

ArrayList自己的序列化方法：
private void writeObject(java.io.ObjectOutputStream s)
            throws java.io.IOException
ArrayList自己的反序列化方法：
private void readObject(java.io.ObjectInputStream s)
            throws java.io.IOException, ClassNotFoundException 

ArrayList自己的序列化和反序列化的方法.png

4.2创建一个ArrayList：

ArrayList的构造有两个：
（1）：new ArrayList<String>()
在我们执行new ArrayList<String>()时，会调用上边的无参构造器，创造一个容量为10的对象数组。  

（2）：new ArrayList<String>(int size)
在我们执行new ArrayList<String>(2)时，会调用上边的public ArrayList(int initialCapacity)，创造一个容量为2的对象数组。

源码：

    /** 
     * 无参构造函数： 
     * - 创建一个 空的 ArrayList，此时其内数组缓冲区 elementData = {}, 长度为 0 
     * - 当元素第一次被加入时，扩容至默认容量 10 
     */
    public ArrayList() {
        super();
        this.elementData = EMPTY_ELEMENTDATA;//默认空数组
    }


    /**
     * 有参构造： 
     * 创建一个初试容量的、空的ArrayList 
     * - 可能报错： java.lang.OutOfMemoryError: Requested array size exceeds VM limit 
     * @param  initialCapacity  初始容量 
     * @throws IllegalArgumentException 当初试容量值非法(小于0)时抛出 
     */
    public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
        //创建对应容量的数组
        this.elementData = new Object[initialCapacity];
    }

注意

在实际使用中，如果我们能对所需的ArrayList的大小进行判断，有两个好处：
    1:节省内存空间（eg.我们只需要放置两个元素到数组，new ArrayList<String>(2)）
    2:避免数组扩容（下边会讲）引起的效率下降（eg.我们只需要放置大约37个元素到数组，new ArrayList<String>(40)）
    3:另外ArrayList是动态数组可以从构造函数中看出，存放元素的elementData是一个数组，同时被初始化
    4：ArrayLIst的默认初始化容量是10，这个是容量，并不是ArrayList的初始化大小，更不能等同于size，而是elementData[]这个数组的大小，而size指的是数组里面存放有数据的   数量，也就是list的大小
    5：当容量不够时候（ensureCapacityInternal(size + 1)），会调用相应的扩容方法(private void grow(int minCapacity))

构造函数源码.png

4.3向ArrayList中添加元素：

ArrayList的add方法有两个：
（1）：public boolean add(E e) //末尾追加
在我们执行List.add("元素")方法时，会将“元素”添加到集合末尾

（2）：public void add(int index, E element) //对应索引追加
在我们执行List.add(index，"元素")方法时，会将“元素”添加到集合的index索引处

add（E e）是直接往数组最后增加数据，而后者则是往指定的index增加数据

源码：
    /** 
     * 添加新值到 list 末尾 
     * @param e 添加的值 
     * @return <tt>true</tt> 
     */  
    public boolean add(E e) {  
        // 确定ArrayList的容量大小---严谨  
        // 注意：size + 1，保证资源空间不被浪费，按当前情况，保证要存多少个元素，就只分配多少空间资源  
        ensureCapacityInternal(size + 1);  // Increments modCount!!  
        // 添加 e 到 ArrayList 中，然后 size 自增 1  
        elementData[size++] = e;  
        return true;  
    }

    /** 
     * 插入方法，其实应该命名为 insert() 比较合理 
     * - 在指定位置插入新元素，原先在 index 位置的值往后移动一位 
     * @param 要插入的位置 
     * @param 要插入的元素 
     * @throws IndexOutOfBoundsException {@inheritDoc} 
     */  
    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++;  
    }

添加细节

add（E e）是直接往数组最后增加数据，而后者则是往指定的index增加数据。在增加的过程中，根 据索引来增加数据的add方法，首先要判断index越界的问题。接下来，就是两者 ensureCapacityInternal(size + 1)。看名字也很容易知道，这个方法是为了确保容量够，接下来来看这个方法是怎么做的。如下图所示，这个方法的参数minCapacity接受传入的（size+1）,然后判断这个数组elementData是否为空。这个数组为空的时候，返回DEFAULT_CAPACITY和minCapacity的最大值。这个时候就可以理解，为什么说默认容量是10。因为他每次增加元素时候，是和DEFAULT_CAPACITY来比较的。不够的时候才会扩充。接下来调用了ensureExplicitCapacity方法。如果数据的数量超过了elementData数组 长度，说明容量不够了，就执行grow方法，扩容。

保证容量方法.png

接下里看看，它是怎么扩容的。进入grow(int minCapacity)方法，这个minCapacity指是（size+1）。如下图所示，先将现在的容量放入oldCapacity，然后将其右移1位，相当于除以2，然后在加上原来的容量，其实就是1.5倍。说白了就是每次扩充原来容量的一半。扩充完毕后，检查这个新容量是不是太大了。如果比MAX_ARRAY_SIZE大，那就将其设置为Integer.MAX_VALUE. 那么问题来了，MAX_ARRAY_SIZE是多大？干啥的？

扩容方法.png

MAX_ARRAY_SIZE是在该类里面定义的一个常量，可以看到它比Integer.MAX.VALUE少8。那么新的问题来了，为什么减去8？首先英文的注释写的很清楚了，为了避免OOM异常。但是为什么减去8，减去4行不？减去2呢？
我们知道，数组除了存放数据外，还有一个length属性，说白了，减去8是为了存数组的长度。

2017-09-19_164245.png

这些都做完后，调用Arrays.copy()方法，将数据进行拷贝。从这里也可以看出扩容是很影响性能的。

4.4从ArrayList中移除元素：

ArrayList的remove方法有两个：
（1）：public E remove(int index)//按照索引删除
在我们执行public E remove（int index）方法后，移除指定索引位置的元素：index 之后的所有元素依次左移一位 

（2）：public boolean remove(Object o)//根据元素删除
在我们执行public boolean remove(Object o)方法后，删除 ArrayList 中的一个指定元素（符合条件的索引最低）

源码：
     /** 
     * 移除指定索引位置的元素：index 之后的所有元素依次左移一位 
     * @param index  
     * @return 被移出的元素 
     * @throws IndexOutOfBoundsException {@inheritDoc} 
     */  
    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 个  
            System.arraycopy(elementData, index+1, elementData, index, numMoved);  
        elementData[--size] = null;// 将最后一个元素置空  
  
        return oldValue;  
    }

    /** 
     * 删除 ArrayList 中的一个指定元素（符合条件的索引最低） 
     * - 只会删除一个 
     * - 删除的那个元素，是符合条件的结果中索引号最低的那个 
     * - 若不包含要删除的元素，则返回 false 
     *  
     * 相比 remove(index)：该方法并没有进行越界检查，即调用 rangeCheck()  
     *  
     * @param o 要删除的元素 
     * @return <tt>true</tt> ? ArrayList中包含该元素，删除成功：不包含该元素，删除失败 
     */  
    public boolean remove(Object o) {  
        if (o == null) {  
            for (int index = 0; index < size; index++)  
                if (elementData[index] == null) {  // 判断是否存储了 null   
                    fastRemove(index);  
                    return true;  
                }  
        } else {  
             // 遍历ArrayList，找到“元素o”，则删除，并返回true  
            for (int index = 0; index < size; index++)  
                if (o.equals(elementData[index])) {// 利用 equals 判断两对象值是否相等（equals 比较值，== 比较引用）  
                    fastRemove(index);  
                    return true;  
                }  
        }           
        return false;  
    }

4.5给ArrayList添加一个集合：

ArrayList的addAll方法有两个：
（1）：public boolean addAll(Collection<? extends E> c)//将一个集合的所有元素顺序添加（追加）到 lits 末尾 
源码

    /**  
     * 将一个集合的所有元素顺序添加（追加）到 lits 末尾 
     * - ArrayList 是线程不安全的。 
     * - 该方法没有加锁，当一个线程正在将 c 中的元素加入 list 中，但同时有另一个线程在更改 c 中的元素，可能会有问题 
     * @param c collection containing elements to be added to this list 
     * @return <tt>true</tt> ？ list 元素个数有改变时，成功：失败 
     * @throws NullPointerException 当 c 为 null 时 
     */  
    public boolean addAll(Collection<? extends E> c) {  
        Object[] a = c.toArray();// 若 c 为 null，此行将抛出空指针异常  
        int numNew = a.length;// 要添加的元素个数  
        ensureCapacityInternal(size + numNew);// 扩容，Increments modCount  
        System.arraycopy(a, 0, elementData, size, numNew);// 添加  
        size += numNew;  
          
        return numNew != 0;  
    }

（2）：public boolean addAll(int index, Collection<? extends E> c)//从 index 位置开始，将集合 c 中的元素添加到ArrayList 
源码：
    /** 
     * 从 index 位置开始，将集合 c 中的元素添加到ArrayList 
     * - 并不会覆盖掉在 index 位置原有的值 
     * - 类似于 insert 操作，在 index 处插入 c.length 个元素（原来在此处的 n 个元素依次右移） 
     * @param index 插入位置 
     * @param c  
     * @return <tt>true</tt> ？ list 元素个数有改变时，成功：失败 
     * @throws IndexOutOfBoundsException {@inheritDoc} 
     * @throws NullPointerException 当 c 为 null 时 
     */  
    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;  
    }

注意

System.arraycopy()方法定义如下：

public static native void arraycopy(Object src,  int  srcPos, Object dest, int destPos,  int length);

将数组src从下标为srcPos开始拷贝，一直拷贝length个元素到dest数组中，在dest数组中从destPos开始加入先的srcPos数组元素。

4.6设置ArrayList中某个元素：

（1）：public E set(int index, E e)// 设置新值，返回旧值  
源码：
       public E set(int index, E e) {  
            rangeCheck(index);// 越界检查  
            checkForComodification();  
            E oldValue = ArrayList.this.elementData(offset + index);  
            ArrayList.this.elementData[offset + index] = e;  
            return oldValue;  
        }

4.7从ArrayList中获取元素：

（1）：public E get(int index)获取对应索引下的元素
源码：
    /** 
     * 获取指定位置的元素：从 0 开始计数 
     * @param  index 元素索引 
     * @return 存储在 index 位置的元素 
     * @throws IndexOutOfBoundsException {@inheritDoc} 
     */
    public E get(int index) {
        rangeCheck(index);// 检查是否越界  
        return elementData(index);
    }

五：线程安全问题

    ArrayList是线程不安全的，查看源码可以发现其方法都不是原子性操作，以添加方法add()为例。
    add(E)操作分两步：先尾部添加元素，在修改集合容量加一。

因为是两步，所以必然存在线程争抢切换导致错误数据，例如A线程先向集合中添加了一个元素，准备修改集合容量时，这时B线程争抢到了执行权，A线程挂起，B线程又添加了一个元素，这时A线程又抢回执行权，修改容量加一。整个过程向集合中添加了两个元素，而容量只增加了一，导致错误数据。

看测试源码：

/**
 * ClassName: TestArrayList
 * @author lvfang
 * @Desc: TODO
 * @date 2017-9-20
 */
public class TestArrayList implements Runnable {    
    private ArrayList<Integer> arry = null; 
    public TestArrayList(ArrayList<Integer> arry){
        this.arry = arry;
    }
    
    @Override
    public void run() {
        for(int i=0;i<10;i++) arry.add(1);
        System.out.println(arry.size());    
    }
    
    /**
     * arrayList线程安全测试
     * @param args
     */
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        //启动100个线程，每个线程向集合中添加10条数据，最终应该是1000，但结果不是
        for (int i = 0; i < 100; i++) {
            new Thread(new TestArrayList(list)).start();
        }
    }
}



解决方案：
（1）：修改为原子性操作，使用synchronized关键字
（2）：使用Collections.synchronizedList()

额外对比：
ArrayList与LinkedList；这两个都是接口List下的一个实现，用法都一样，但用的场所的有点不同，ArrayList适合于进行大量的随机访问的情况下使用，LinkedList适合在表中进行插入、删除时使用，二者都是非线程安全，解决方法同上（为了避免线程安全，以上采取的方法，特别是第二种，其实是非常损耗性能的）。

六：总结

ArrayList是基于动态数组实现的，随机存取快，但是在增删时候，需要数组的拷贝复制，这个时候明显劣势。

添加元素时可能要扩容（所以最好预判一下），删除元素时不会减少容量（若希望减少容量，trimToSize()），删除元素时，将删除掉的位置元素置为null，下次gc就会回收这些元素所占的内存空间。

它不是线程安全的。

它能存放null值。

ArrayList的默认初始化容量是10，每次扩容时候增加原先容量的一半，也就是变为原来的1.5倍