ArrayList源码分析

ArrayList概述

ArrayList 是一种变长的集合类，基于数组实现
由于 ArrayList 底层基于数组实现，非常适用于对元素进行查找，效率非常高
ArrayList 允许空值和重复元素，当往 ArrayList 中添加的元素数量大于其底层数组容量时，会通过扩容机制重新生成一个更大的数组
ArrayList 是非线程安全类，并发环境下多个线程同时操作 ArrayList，会引发不可预知的错误

ArrayList结构

源码分析

    // 序列化id
    private static final long serialVersionUID = 8683452581122892189L;
    
    //默认初始化容量
    private static final int DEFAULT_CAPACITY = 10;
    
    //默认的空的数组，这个主要是在构造方法初始化一个空数组的时候使用
    private static final Object[] EMPTY_ELEMENTDATA = {};
    
    //一个空对象，如果使用默认构造函数创建，则默认对象内容默认是该值
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
    // 这个是实际存储元素的数组,不参与序列化
    transient Object[] elementData; // non-private to simplify nested class access
    
    //实际ArrayList的大小/集合中元素的个数
    private int size;

ArrayList构造方法

无参构造方法

public ArrayList() {
        //如果没有传入初始化容量，则使用空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA
        //使用这个数组是在添加第一个元素的时候就会扩容到默认大小10
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

带int类型的构造函数

public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            //参数大于0 elementData初始化为initialCapacity大小的数组
            this.elementData = new Object[initialCapacity];
            //参数等于0，elementData初始化为空数组
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            //参数小于0，抛出异常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

参数为Collection类型的构造器

public ArrayList(Collection<? extends E> c) {
        //调用c.toArray()将collection对象转换成数组，然后将数组赋值elementData
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            //c.toArray()可能不会正确地返回一个 Object[]数组，那么使用Arrays.copyOf()方法
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            //如果c是空集合，则初始化为空数组EMPTY_ELEMENTDATA
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

add(E e)

public boolean add(E e) {
        //检查是否需要扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //把元素放到最后一位
        elementData[size++] = e;
        return true;
    }

private void ensureCapacityInternal(int minCapacity) {
        //判断elementData数组是不是为空数组
        //使用的无参构造的时候,elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            //如果是,size+1(第一次调用add的时候size+1)和DEFAULT_CAPACITY比较
            //minCapacity  = 10
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        
        ensureExplicitCapacity(minCapacity);
    }

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        //如果size+1 > elementData.length证明数组已经放满，则增加容量，调用grow()
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

grow(minCapacity)扩容

private void grow(int minCapacity) {
        //oldCapacity为旧数组的容量
        int oldCapacity = elementData.length;
        // newCapacity = oldCapacity +（oldCap+oldCap >> 1 : 即更新为旧容量的1.5倍）
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 如果新的容量还小于minCapacity，那就让新容量等于minCapacity
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //如果新容量已将超过最大容量了，则使用最大容量。
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 最后将调用Arrays.copy将生成一个新容量大小的数组，并将原来数组值放入
        //底层调用System.arraycopy(Object src,  int  srcPos,Object dest, int destPos,int length);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

$\color{red}{oldCapacity >> 1 右移运算符比如：oldCapacity = 10 ，转换为二进制 = 1010 右移一位：101 等于十进制： 5}$

add（int index，E element）

添加元素到指定位置

public void add(int index, E element) {
        //确保插入的位置小于等于当前数组长度，并且不小于0，否则抛出异常
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        //检查是否需要扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //将index位置及以后所有元素统一向后挪一个位置,index位置处空出来
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        //将元素插入到index的位置
        elementData[index] = element;
        //size + 1
        size++;
    }

调用add

System.arraycopy 方法

参数	说明
Object src	原数组
int srcPos	从原数据的起始位置开始
Object dest	目标数组
int destPos	目标数组的开始起始位置
int length	要copy的数组的长度

get（int index）方法

获取指定索引位置的元素

public E get(int index) {
        //如果索引大于实际数组长度就抛异常
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        //返回数组index位置的元素
        return (E) elementData[index];
    }

remove(int index)

删除指定索引位置的元素

public E remove(int index) {
        //如果索引大于实际数组长度就抛异常
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        //修改次数自增一
        modCount++;
        //获取要移除索引位置的元素
        E oldValue = (E) elementData[index];
        //总共要移动的元素的数量
        int numMoved = size - index - 1;
        if (numMoved > 0)
            //如果要移动的数量大于0，那么index之后的所有元素向前移一个位置
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        //将最后面的一个元素置空，好让gc回收
        elementData[--size] = null; // clear to let GC do its work
        //返回旧值
        return oldValue;
    }

<font color = red>调用这个方法不会缩减数组的长度，只是将最后一个数组元素置空！

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 {
            for (int index = 0; index < size; index++)
                //遍历整个数组，获取元素第一次出现的位置，并将其快速删除
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

private void fastRemove(int index) {
        modCount++;
        //如果index不是最后一位，则将index之后的元素往前挪一位
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        //将最后面的一个元素置空，好让gc回收
        elementData[--size] = null; // clear to let GC do its work
    }

fastRemove(int index)相比较remove(int index)少了检查索引越界的操作

clear()

添加操作次数（modCount），将数组内的元素都置空，等待垃圾收集器收集，不减小数组容量

public void clear() {
        modCount++;

        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            //将数组内的元素都置空
            elementData[i] = null;

        size = 0;
    }

以上就是JDK 1.8 ArrayList的主要方法，在ArrayList内部还有一些其它的方法,有兴趣的小伙伴可以自行阅读

补充

JDK1.7的构造方法

ArrayList中维护了Object[] elementData，初始容量为10

    public ArrayList() {
            this(10);
     }

/**
     * Constructs an empty list with the specified initial capacity.
     *
     * @param  initialCapacity  the initial capacity of the list
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
    public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
    }

jdk7与jdk8区别：

jdk7 相当是饿汉式，创建对象时，初始化数组容量为10
jdk8 相当是懒汉式，创建对象时，没有初始化容量为10，而是在添加时才去初始容量为10

总结

ArrayList内部使用数组存储元素，当数组长度不够时使用grow()扩容，每次增加原来的1.5倍，ArrayList不会进行缩容
.ArrayList支持随机访问，通过索引访问元素极快
ArrayList添加元素到尾部极快
ArrayList添加元素到中间比较慢
ArrayList从尾部删除元素极快
ArrayList从中间删除元素比较慢，因为要移动元素

ArrayList底层是object数组，所以ArrayList具有数组的查询速度快的优点以及增删速度慢的缺点，线程不安全。