ArrayList源码分析

List

实质上是一个有序的Collection,因传统数组的一系列缺点诞生的(不可扩容、只能存储基本类型等)，有了List，基本类型会被包装成引用类型，并且支持扩容等操作。

List接口中的方法

下面是List接口中定义的一系列的方法,其中JDK8中引入了接口默认方法的语法。

    //返回存储元素的个数
    int size();
    //返回是否为空集合
    boolean isEmpty();
    //返回是否包含对象o
    boolean contains(Object o);
    //获取迭代器
    Iterator<E> iterator();
    //转化成对象数组
    Object[] toArray();
    //转化成指定对象类型的数组
    <T> T[] toArray(T[] a);
    //添加一个元素到集合中
    boolean add(E e);
    //从集合中移除一个元素
    boolean remove(Object o);
    //是否包含某个集合
    boolean containsAll(Collection<?> c);
    //把一个集合添加到当前集合中
    boolean addAll(Collection<? extends E> c);
    //从指定Index开始添加一个集合
    boolean addAll(int index, Collection<? extends E> c);
    //移除某个集合
    boolean removeAll(Collection<?> c);
    //保留某个集合
    boolean retainAll(Collection<?> c);
    //清空集合
    void clear();
    //判断是否相等
    boolean equals(Object o);
    int hashCode();
    //根据索引取元素
    E get(int index);
    //设置某个索引Index的元素为element
    E set(int index, E element);
    //插入某个元素,在索引index处
    void add(int index, E element);
    //根据索引index移除元素
    E remove(int index);
    //返回对象o的索引
    int indexOf(Object o);
    //返回对象o最后一次出现的位置
    int lastIndexOf(Object o);
    //ListIterator是只能用在List及其子类的,而Iterator可以用在Set、Map上.并且支持逆序遍历
    ListIterator<E> listIterator();
    ListIterator<E> listIterator(int index);
    //取某个区间的元素成一个新的集合
    List<E> subList(int fromIndex, int toIndex);

//JDK8中新增加的接口默认方法：
default void replaceAll(UnaryOperator<E> operator) {
        Objects.requireNonNull(operator);
        final ListIterator<E> li = this.listIterator();
        while (li.hasNext()) {
            li.set(operator.apply(li.next()));
        }
    }
default void sort(Comparator<? super E> c) {
        Object[] a = this.toArray();
        Arrays.sort(a, (Comparator) c);
        ListIterator<E> i = this.listIterator();
        for (Object e : a) {
            i.next();
            i.set((E) e);
        }
    }
    //利用现在计算机并行处理的特点,可以并行遍历的Iterator
 default Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, Spliterator.ORDERED);
    }

ArrayList

概述:ArrayList底层是一个动态扩容的Object[] element数组,允许存放多个Null，允许重复数据，并且它不是一个线程安全的集合，如果增删操作需要线程安全可以使用CopyOnWriteArrayList或者使用synchronozed(List l)函数返回一个线程安全的ArrayList。
类的继承源码如下：

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

介绍：

• 继承AbstractList实现List也就代表要实现上面的所示的一系列的方法
• RandomAccess和Cloneable以及Serializable都是标记接口,分别代表ArrayList具备随机快速访问的功能(列如get(index))、可以被clone(下面会介绍,其实就是调用Array.copyOf)、可以被序列化用于网络间的传输和持久化。这三个标记接口没有抽象方法,只是标记支持这种功能。

 public Object clone() {
        try {
            ArrayList<?> v = (ArrayList<?>) super.clone();
            //调用此方法实现浅克隆（克隆后的数组内发生变化,之前的数组也会变）
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
    }

ArrayList的成员

    /**
     * 默认底层数组容量
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 用于空实例的共享空数组实例,当使用ArrayList(0)或者任何使得集合长度为0的操作elementData数组会指向它
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * 一个共享数组实例,第一次add()的时候使用它判断数组大小是否设置为DEFAULT_CAPACITY
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 存储ArrayList的数组缓冲区,ArrayList的实际容量就是此数组的长度 
     * transient关键字标识无法被序列化
     */
    transient Object[] elementData;
    /**
     * 记录底层数组内现在存储了多少元素
     */
    private int size;

ArrayList的构造方法

//无参构造方法:构造一个空的List,仅仅是把底层的数组指向了上面所说的空的共享数组中
//但是JDK源码中说是默认长度为10,是因为第一次add的时候发现是空的就会赋值10，见下面的源码
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
//指定容量的构造方法
public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
        //长度大于0，就new一个Object数组赋值给elementData
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
        //长度等于0就使用EMPTY_ELEMENTDATA
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
        //长度小于0抛异常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

    /**
     * 构造一个包含指定集合元素的列表，元素的顺序按迭代器的顺序
     */
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            //如果作为构造方法的集合长度不为0,
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            //c.toArray可能不返回Object[]类型的数组,所以这里判断下,如果返回的是Object数组在elementData = c.toArray();这步已经赋值好了，如果返回的不是object数组,把元素copy进去
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 构造参数长度为0,直接赋值空数组,不用自己new一个空的数组放进去了
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

• 无参构造仅仅是将底层的elementData数组指向了那个空的共享数组，但是下面那句翻译过来就是初始长度是10，是因为我们这里虽然是0，但是在add()数组的时候会进行
• 这个初始容量的长度将作为集合底层数组的长度，如果长度为0就用默认的那个初始为0的。一般使用此构造方法都是在我们预先确定ArrayList将装多少元素的情况。虽然ArrayList有着自己的一套动态扩容机制，但是扩容带来的内存开销还是不可避免的，所以如果我们确定长度最好用这个而不是用扩容去实现。

---

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

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

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        //在这里判断了，如果当前数组是默认的空数组，就取默认的长度赋值给数组长度，默认是10，所以刚刚的构造方法实际上默认给了长度为10的长度
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

ArrayList方法

Object[] Collection.toArray()

Collection是集合框架的超类,其实Collection.toArray()是给具体的集合子类实现的，这就说明不同的集合可能有不同的实现。他用来将一个集合转化为一个Object数组，事实上并不一定是Object数组,比如下面的第一个输出,调用的是toArray方法就是这个内部对于Collection.toArray的实现，a.clone() 这里的clone并不会改变一个数组的类型，所以当原始数组中放的是String类型时输出的也是String而不是Object

public class TestToArray {
    public static void main(String[] args) {
        List<String> list = Arrays.asList("abc","2dd");
        //java.util.Arrays$ArrayList    Arrays的内部类
        System.out.println(list.getClass());

        Object[] objects = list.toArray();
        //[Ljava.lang.String  并不是一个Object
        System.out.println(objects.getClass());
    }
}

Arrays.copyOf

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
        //根据class类型是否是Object[] 来决定是new还是反射去构建泛型数组
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        //最后使用Systen.arraycopt这个native方法，去实现最终的数组赋值,newLength如果比original.length大的时候多余的空间会赋值null（就是说取2者小的赋值,多的默认null）
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

eg:如下代码:
这个把集合作为构造参数的构造器实质上就是把一个集合中的元素塞到ArrayList的底层数组中

  String[] arrString = {"qwe","dfg"};
        Object[] copyOf = Arrays.copyOf(arrString,5,Object[].class);
        System.out.println(Arrays.toString(copyOf));//[qwe, dfg, null, null, null]

ArrayList扩容动作

在上面介绍成员的时候写下了一个int size,在这里可以用到了,size用来标识集合当前元素个数,初始为0.
，从第一次add()说起:

 public boolean add(E e) {
         //检查当前底层数组容量,如果容量不够则扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //数组的索引位置size++处存放元素e
        elementData[size++] = e;
        return true;
    }

调用add方法总会调用ensureCapacityInternal来判断是否需要进行数组的扩容,参数为当前集合的长度+1.

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

//进行扩容检查的方法
 private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        //如果是无参构造方法构造的集合第一次添加元素的时候,minCapacity会被赋值为10
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //这个minCapatity将被用来下面方法的扩容操作
        return minCapacity;
    }
  
    private void ensureExplicitCapacity(int minCapacity) {
        //操作数+1，CAS思想防止并发访问
        modCount++;
        // 如果当前容量小于添加元素后的长度小,则进行grow扩容操作
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
 

首次添加的时候,size = 0,添加一个元素 size + 1 = 1,1-0>0，所以需要进行grow操作扩容。minCapacity参数表示扩容后元素的个数，也就是说，扩容后，实际长度要大于等于这个长度才行。
其实,grow()方法才是执行扩容动作的.之前的一系列的操作都是为了检查容量是否满足,如果满足则不会扩容,但是不满足就要进行扩容了。看下grow()的源码

private void grow(int minCapacity) {
        //原始的容量
        int oldCapacity = elementData.length;
        //新的容量=原始的容量*1.5
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果新的容量 < 要扩容的容量 则新的容量就等于要扩容的容量
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //如果新的容量大于最大值就要进一步比较minCapacity与MAX_ARR的大小了
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        //使用Arrays.copyOf构建一个长度为新的长度的新数组并将elementData指向新数组
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

/**
 * 比较 minCapacity 与 Integer.MAX_VALUE - 8 的大小如果大则放弃-8的设定，
 * 设置为Integer.MAX_VALUE 
 */
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

实际上扩容：

• 每次扩容大小为原来的1.5倍int newCapacity = oldCapacity + (oldCapacity >> 1);
• 扩容的过程实际上就是把原来的数组元素拷贝到一个新的使用新长度的数组中。所以频繁的扩容肯定不是最好的选择，会带来性能的开销。这也是为什么我们建议在定义的时候指定容量。

添加方法,往指定的角标处添加,源码如下,过程也非常简单,先检查输入的角标是否越界,然后看是否需要扩容,然后从index开始向后移动一位,这样原来的index的位置就可以插入新的元素了。

public void add(int index, E element) {
        //检查角标是否越界
        rangeCheckForAdd(index);
        //扩容检查
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //调用native方法拷贝数组从index往后移动1位,空出来了角标位index的位置
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        index位置赋值元素
        elementData[index] = element;
        size++;
    }

指定位置插入.png

之前都是在说add方法,也就是往集合中放,那么删除肯定也要说下了

移除指定的元素:
实际上,无论是移除指定元素还是移除首次出现的元素，都使用System.arrayCopy将index之后的元素前移一位,并释放最后一位index==size的元素。

public boolean remove(Object o) {
        if (o == null) {
        //如果要删除的元素为Null,这个可以用内存地址null判断
            for (int index = 0; index < size; index++)
                //遍历数组,得到第一个为null的元素删除然后返回true
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            //要删除的不为null,就要用equals判断了
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        //没找到元素,删除失败返回false
        return false;
    }

    //移除元素  同remove(index)
  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
    }

删除指定角标处的元素源码如下：

public E remove(int index) {
      //角标检查,只检查了Index是否大于等于size,因为Index的取值应该是[0,size-1],如果小于0了，抛出的异常是数组的异常不是ArrayList的异常,(实际的元素个数小于等于数组的长度size<=length,所以检查size)
        rangeCheck(index);
        modCount++;
        //角标的值
        E oldValue = elementData(index);
        //需要移动的长度
        int numMoved = size - index - 1;
        if (numMoved > 0)
        //从Index+1开始向前移动一位
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
         //最后一位赋值为Null,等待回收
        elementData[--size] = null; // clear to let GC do its work
        //返回旧值
        return oldValue;
    }

新增和移除基本介绍完了,那么修改也一起说下:
修改是使用set方法，思路是先减产角标合法性,然后取出角标元素,进行set值

public E set(int index, E e) {
            //角标检查
            rangeCheck(index);
            //并发修改检查
            checkForComodification();
            //下表取数据使用elementDate(index)方法
            E oldValue = ArrayList.this.elementData(offset + index);
            ArrayList.this.elementData[offset + index] = e;
            return oldValue;
        }
//并发修改检查
private void checkForComodification() {
            if (ArrayList.this.modCount != this.modCount)
                throw new ConcurrentModificationException();
        }
 E elementData(int index) {
        return (E) elementData[index];
    }

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

查询的话就比较简单了,检查完了之后直接返回底层数组的指定索引处的元素

public E get(int index) {
        rangeCheck(index);
        return elementData(index);
    }

扩展延伸

ArrayList集合的toArray

ArrayList的Object[] toArray方法及重载函数<T>T[] toArray(T[]) a是接口Collection的方法,ArrayList实现了这2个方法用来把集合转化为数组。二者的不同之处在于后者可以指定数组的类型,前者返回的就是一个Object[]的类型。在实现上,前者仅仅调用了一次Arrays.copyOf()方法将集合中元素拷贝到一个新的Object[]中返回。而后者的出现,可以让我们在传入时确定返回时的类型，也就是说如果我们传入了一个指定类型的标志数组作为参数,toArray(T[] a)方法最终会返回这个类型的包含集合元素的新数组：

1. 如果a.length<size就是说当前集合元素的个数大于a中的将产生一个和toArray()一样返回的一个新的数组。
2. 如果a.length==size将不会产生新的数组直接返回a
3. 如果a.length>size也不会产生新数组,但是值得注意a[size] = null;这句改变了原数组中index=size位置的元素被设置为Null

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

  public <T> T[] toArray(T[] a) {
        if (a.length < size)
            // Make a new array of a's runtime type, but my contents:
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
        System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }

线程安全性

其实它的线程不安全主要是因为add操作不是原子操作造成的，由上源码可以看到

1. elementData[size++] = e并不是一个原子的操作，是分2步执行的，elementData = e和size++，单线程执行的话肯定不会有问题，多线程情况下，可能会出现一个线程的值覆盖了另一个线程的值
   a. 列表为empty，size=0
   b. 线程A执行完elementData[size] = e之后挂起。A把"a"放在了下标为0的位置，此时size=0
   c. 线程B执行elementData[size] = e，因为此时size=0,所以B把“b”放在了下标为0的位置，也是刚好把A的数据给覆盖掉了。
   d. 线程B对size+1 = 1, 线程A对size+1=2
   这样子，当线程A和线程B都执行完之后理想情况下应该是“a”在下标为0的位置，"b"在下标为1的位置。而实际情况是下标为0 的是“b”，为1的null。
2. ArrayList默认数组大小为10(上面分析过了，第一次add的时候)，假设现在已经添加进去9个元素,size=9。
   a. 线程A执行完add函数中的扩容操作ensureCapacityInternal(size + 1);因为某些原因挂起了。
   b. 线程B开始执行，校验数组容量发现不需要扩容，于是把b放在了下标为9的位置，且size+1,此时size=10
   c. 线程A接着执行，尝试把"a"放在下标为10的位置，因为size=10,但因为数组还没扩容，最大下标为9(size=10)，然后执行elementData[size++] = e就抛出ArrayIndexOutOfBoundsException

---

上面说了一堆线程如何不安全云云~，那么肯定有解决的方法的：
1、对ArrayList的操作加锁
2、使用Collections提供的synchronizedList进行包装
3、使用Vector
但是都是效率比较低下的。如果在读多写少的情况下可以考虑CopyOnWriteArrayList
原理：CopyOnWriteArrayList的整个操作都是在锁的保护下进行的，这样做事为了避免在多线程并发add的时候复制出来多个副本数据会乱，导致最终的数据并非期望的数据。

    public boolean add(E e) {
        //首先获取一把锁
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            //得到本身的数组
            Object[] elements = getArray();
            //本身数组的长度
            int len = elements.length;
            //把本身数组的长度+1复制到新的数组中
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            //位置存放e
            newElements[len] = e;
            //让底层数组指向新的数组实现添加
            setArray(newElements);
            return true;
        } finally {
            //无论上面的结果如何结束了释放锁
            lock.unlock();
        }
    }

通过上面的源码基本了解到，所有的写操作都是产生了一个新的数组，并且通过锁保证安全性。如果读的话分为：

1. 如果写操作未完成，取的是原数组的数据
2. 如果写操作完成，但是没执行到引用指向新数组的方法setArray()，读取的还是原数组
3. 写操作完成了，并且指向了新的数组，直接取新数组中的数据

上面说了它保证线程安全的一些优点,但是肯定有缺点的

1. 每一次写入都会产生一个新的数组，在内存方面消耗比较大，如果原数组内容多的话可能导致young gc或者full gc
2. 不能用于实时读的场景，像拷贝数组、新增元素都需要时间，所以调用一个set方法后读取的数据可能还是老的数据，虽然是最终一致性，但是还是没法满足实时性的要求。

场景:CopyOnWriteArrayList适合读多写少的场景，它带给我们一些新的思想：比如读写分离、最终一致性、使用另外的空间解决并发冲突

至此ArrayList基本介绍的差不多了,大部分都是之前学习的时候有记录一些笔记,第一篇分享的文章，自己收货很多。