ArrayList源码解读

NullPointer

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;

    /**
     * ArrayList的元素的数组缓冲区存储（存放ArrayList集合的元素）
     * transient：只能用来修饰字段，在对象序列化的过程中，带有此修饰符修饰的字段是不会被序列化的
     * 例如：User类有userName和transient password，那么序列化User类的时候password是不会被序列化的，所以反序列化拿出password也是null
     */
    private transient Object[] elementData;

    /**
     * 数组的长度
     *
     * @serial
     */
    private int size;

    /**
     * 带参构造器：需要传入一个初始容量，默认构造器是10字节，此构造器可以自定义大小。
     *
     * @param  initialCapacity  初始容量
     * @throws IllegalArgumentException 若初始容量小于0，则抛出异常
     */
    public ArrayList(int initialCapacity) {
        //调用父类构造器
            super();
            //若初始容量小于0，则抛出异常。
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        //若初始容量大于等于0，则new一个容量为initialCapacity的Object数组，并赋给elementData数组
        this.elementData = new Object[initialCapacity];
    }

    /**
     * 空构造器，默认占用是个字节，意思就是：当我们new ArrayList();的时候其实new出来的集合是占用十字节的空间的
     */
    public ArrayList() {
            //调用带参构造器，并初始容量为10
        this(10);
    }

    /**
     * 带参构造器：传入一个集合，然后将传入的集合赋给elementData，长度赋给size
     *
     * @param c 传入的集合
     */
    public ArrayList(Collection<? extends E> c) {
            //将传入的集合转化为数组，赋给elementData
        elementData = c.toArray();
        //将传入的集合的长度赋给size
        size = elementData.length;
        //c.toArray可能返回的不是Object数组，有时候会存在这个bug。(see 6260652)，所以加此判断
        if (elementData.getClass() != Object[].class)
                //若elementData（c.toArray()）不是数组类型，则进行数组的复制，复制的类型为Object数组
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

    /**
     * 将数组缓冲区大小调整到实际ArrayList存储元素的大小，释放掉add时候扩充1.5倍后产生的那些null
     * 即：elementData = Arrays.copyOf(elementData, size);
     * 该方法由用户手动调用，以减少空间资源浪费的目的。
     */
    public void trimToSize() {
            //modCount是AbstractList的属性，protected transient int modCount = 0;
            //modCount好比计数器，每次对List进行增删操作modCount都会进行++操作
        modCount++;
        //将数组缓冲区大小(可能比size大，因为扩充1.5倍后用null占位，也可能如调用默认构造函数后，刚添加一个元素，此时 elementData.length = 10，而 size = 1)赋值给oldCapacity
        int oldCapacity = elementData.length;
        //如果实际大小小于数组缓冲区大小
        if (size < oldCapacity) {
                //通过这一步，可以使得空间得到有效利用，而不会出现资源浪费的情况
                //将数组缓冲区elementData变为实际存储大小。
            elementData = Arrays.copyOf(elementData, size);
        }
    }

    /**
     * 检查数组是否需要进行扩容
     * @param minCapacity：最小容量
     */
    private void ensureCapacityInternal(int minCapacity) {
        modCount++;
        // 防止溢出代码：确保指定的最小容量大于数组缓冲区当前的长度
        //若最小容量大于当前数组缓冲区长度，则对数组进行1.5倍扩容，否则出现数组下标越界异常。
        if (minCapacity - elementData.length > 0)
                //1.5倍扩容
            grow(minCapacity);
    }

    /**
     * 数组缓冲区（elementData）的最大存储容量
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
     * 扩容，以确保ArrayList至少能存储minCapacity个元素
     */
    private void grow(int minCapacity) {
        // 将缓冲区长度复制给oldCapacity
        int oldCapacity = elementData.length;
        //将原有缓冲区长度进行1.5倍扩容
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 若 newCapacity 依旧小于 minCapacity  
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // 若 newCapacity 大于最大存储容量，则进行大容量分配  
        if (newCapacity - MAX_ARRAY_SIZE > 0)
                //进行大容量分配  
            newCapacity = hugeCapacity(minCapacity);
        // 对数组进行扩容
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    /**
     * 大容量分配，最大分配Integer.MAX_VALUE
     * @param minCapacity
     * @return
     */
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

    /**
     * 返回数组的长度
     */
    public int size() {
        return size;
    }

    /**
     * 判断集合是否为空
     *
     * @Return true：数组长度为0；false：数组长度不为0
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 判断集合中是否包含此元素
     *
     * @return true：包含；false：不包含
     */
    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

    /**
     * 返回第一次出现的指定元素的索引,-1代表此元素不再集合内
     */
    public int indexOf(Object o) {
            //如果传入的数据是null
        if (o == null) { //判断null是为了防止空指针
                //遍历集合
            for (int i = 0; i < size; i++)
                    //如果集合中存在null元素，则返回null在此集合中的位置
                if (elementData==null)
                    return i;
        } else {//如果传入的数据不是null
                //遍历集合
            for (int i = 0; i < size; i++)
                    //如果集合中存在传入的此元素，则返回此元素在集合中的位置
                if (o.equals(elementData))
                    return i;
        }
        return -1;
    }

    /**
     * 返回最后一次出现的指定元素的索引,-1代表此元素不再集合内
     */
    public int lastIndexOf(Object o) {
            //如果传入的数据是null
        if (o == null) { //判断null是为了防止空指针
                //遍历集合，从最后一个往前面遍历，目的是找到最后一次出现的指定元素的位置
            for (int i = size-1; i >= 0; i--)
                    //如果集合中存在null元素，则返回null在此集合中的位置
                if (elementData==null)
                    return i;
        } else {//如果传入的数据不是null
                //遍历集合，从最后一个往前面遍历，目的是找到最后一次出现的指定元素的位置
            for (int i = size-1; i >= 0; i--)
                    //如果集合中存在传入的此元素，则返回此元素在集合中的位置
                if (o.equals(elementData))
                    return i;
        }
        return -1;
    }

    /**
     * 返回一个浅拷贝的ArrayList
     *
     */
    public Object clone() {
        try {
            @SuppressWarnings("unchecked")
                ArrayList<E> v = (ArrayList<E>) super.clone();
            //复制数组elementData到v.elementData
            v.elementData = Arrays.copyOf(elementData, size);
            //数组变化的次数设置为0
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError();
        }
    }

    /**
     * 将集合转化为Object数组
     */
    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }

    /**
     * 根据下标从集合中取出元素
     */
    public E get(int index) {
            //检查是否会发生异常
        rangeCheck(index);
        //直接返回数组中第index个位置的元素值
        return elementData(index);
    }

    /**
     * 在第index位置插入element元素
     *
     * @param index 集合中第index位置
     * @param element 插入的新元素
     * @return 插入新元素之前的集合中第index位置元素
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E set(int index, E element) {
            //检查是否会发生异常
        rangeCheck(index);
        //先从集合中取出下标为index的的元素值，赋值给oldValue
        E oldValue = elementData(index);
        //将新元素重新赋值给elementData[index]
        elementData[index] = element;
        //返回插入新元素之前的集合中第index位置元素（旧数据）
        return oldValue;
    }

    /**
     * 将元素添加到集合
     *
     * @param e 元素
     */
    public boolean add(E e) {
            //数组扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //有了上一步的操作，此步骤就不会出现数组下标越界的情况
        elementData[size++] = e;
        return true;
    }

    /**
     * 在指定位置插入指定元素
     *
     * @param 指定位置
     * @param 元素
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public void add(int index, E element) {
            //检查异常
        rangeCheckForAdd(index);
            //数组扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //System.arraycopy(src, srcPos, dest, destPos, length);
        //第一个是要复制的数组，第二个是从要复制的数组的第几个开始，第三个是复制到那，四个是复制到的数组第几个开始，最后一个是复制长度
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

    /**
     * 从集合中移除下标为index的元素
     *
     * @param 自定义下标
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E remove(int index) {
        //检查异常
            rangeCheck(index);

        modCount++;
        //找到index的元素值
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        //将最后一个元素设置为null
        elementData[--size] = null; // Let gc do its work
        //返回被移除的值
        return oldValue;
    }

    /**
     * 清空数组
     */
    public void clear() {
        modCount++;

        //循环当前数组
        for (int i = 0; i < size; i++)
                //将数组的每一个元素都设置为null
            elementData = null;
        //长度设置为0
        size = 0;
    }

    /**
     * 安全措施：检查是否会发生数组下标越界异常
     */
    private void rangeCheck(int index) {
            //如果传入的长度大于数组的长度，则抛出异常
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    /**
     * 安全措施：检查是否会发生数组下标越界异常
     */
    private void rangeCheckForAdd(int index) {
            //如果传入的长度大于数组的长度，或小于0则抛出异常
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
}

InvictusLee

厉害了我的哥！

NullPointer

InvictusLee 发表于 2016-11-15 11:48
厉害了我的哥！

以后我会定期发送源代码解读或者读书知识总结，共同学习

liujm23

学习了 谢谢楼主分享

kydi.y

总结的很好，谢谢分享！

NullPointer

kydi.y 发表于 2016-11-15 12:03
总结的很好，谢谢分享！

共同学习

NullPointer

liujm23 发表于 2016-11-15 11:54
学习了 谢谢楼主分享

共同学习

wwwmaopu1201

大神  膜拜一下  热心值必须都给你

tiancaizaizuo

必须支持

NullPointer

psx1lin 发表于 2016-11-15 22:53
学习了 谢谢楼主分享

共同学习