记阅读ArrayList源码

基本介绍

1. ArrayList****集合介绍
   1. List底层基于动态数组实现
2. 数组结构介绍
   1. 增删慢：每次删除元素都需要更改数组长度，拷贝以及移动元素位置
   2. 查询快：由于数组在内存中是一块连续空间，因此可以根据地址+索引的方式快速获取对应位置上的元素

ArrayList的类图

首先进入ArrayList源码后，ctrl+alt+u打开类图

可以清除的看到，ArrayList继承了AbstracList,并且还实现了三个接口，从它的代码中也可以看出来

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

继承关系分析

Serializable标记性接口

介绍:类的序列化由实现java.io.Serializable接口的类启用。不实现此接口的类将不会使任何状态序列化或反序列化。可序列化类的所有子类型都是可序列化的，序列化接口没有方法或字段，仅用于标识可串行化的语义

序列化：将对象的数据写入到文件（写对象）

反序列化：将文件中对象的数据读取出来（读对象）

Cloneable标记性接口

介绍:一个类实现Cloneable接口来指示Object.clone()方法，该方法对于该类的实例进行字段的复制是合法的。在不实现Cloneable接口的实例上调用对象的克隆方法会导致异常CloneNotSupportedException被抛出。简言之：克隆就是依据已有的数据，创造一份新的完全一样的数据拷贝

克隆的前提条件

• 被克隆对象所在的类必须实现Cloneable接口
• 必须重写clone()方法

底层实现

/**
 * Returns a shallow copy of this <tt>ArrayList</tt> instance.  (The
 * elements themselves are not copied.)
 *
 * @return a clone of this <tt>ArrayList</tt> instance
 */
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);
    }
}

可以看到通过调用clone()方法，返回了一个ArrayList对象

v.elementData = Arrays.copyOf(elementData, size);
   public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) 
   {
       @SuppressWarnings("unchecked")
       T[] copy = ((Object)newType == (Object)Object[].class)
           ? (T[]) new Object[newLength]
           : (T[]) Array.newInstance(newType.getComponentType(), newLength);
       System.arraycopy(original, 0, copy, 0,
                        Math.min(original.length, newLength));
       return copy;
   }

我们原来数组中的数据通过System.arraycopy方法被拷贝到copy数组中，并将这个数组返回

RandomAccess

1. 由List实现使用，以表明它们支持快速（通常为恒定时间）随机访问
2. 此接口的主要目的是允许算法更改其行为，以便在应用于随机访问列表或顺序访问列表时提供良好的性能

ArrayList构造方法源码

• ArrayList() 构造一个初始容量为10的空列表

/**
 * Constructs an empty list with an initial capacity of ten.
 */
//构造一个初始容量为10的数组
//DEFAULTCAPACITY_EMPTY_ELEMENTDATA：默认的空容量的数组
//elementData：集合真正存储数据的容器
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

• ArrayList(int initialCapacity) 构造具有指定初始容量的空列表

/**
 * 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) {
    if (initialCapacity > 0) {
        //如果传进来的变量大于0，则初始化一个指定容量的空数组
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        //传进来的变量=0，则不去创建新的数组，直接将已创建的EMPTY_ELEMENTDATA空数组传给ArrayList
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        //传进来的指定数组容量不能<0
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }

• ArrayList(Collection<? extends E> c) 构造一个包含指定集合的元素的列表，按照它们由集合的迭代器返回的顺序

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public ArrayList(Collection<? extends E> c) {
    //将构造方法中的参数转换成数组形式，其底层是调用了System.arraycopy（）
    elementData = c.toArray();
    //将数组的长度赋值给size
    if ((size = elementData.length) != 0) {
        //检查elementData是不是Object[]类型，不是的话将其转换成Object[].class类型
        if (elementData.getClass() != Object[].class)
            //数组的创建与拷贝
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        //size为0，则把已创建好的空数组直接给它
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

ArrayList中的各个变量

//长度为0的空数组
private static final Object[] EMPTY_ELEMENTDATA = {};

//默认容量为0的空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//集合存元素的数组
transient Object[] elementData;

//集合的长度
private int size;

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

基础方法

添加方法

• add(E e)将指定的元素追加到此列表的末尾

每增加一个元素，都要判断增加后容量是否达到了规定的最大容量值，如果达到就触发扩容操作grow

在扩容操作中，设置新容量为老容量的1.5倍（****int newCapacity = oldCapacity + (oldCapacity >> 1)），如果新容量小于所需容量，则新容量等于所需容量（newCapacity = minCapacity），如果新容量比规定的最大值还要大，则新容量等于最大容量newCapacity = hugeCapacity(minCapacity);将原数组拷贝进长度为新容量的新数组中

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
//将指定的元素追加到此列表的末尾
public boolean add(E e) {
    //每增加1个元素，数组所需容量+1，并检查增加数组容量后是否要扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //添加元素
    elementData[size++] = e;
    return true;
}


private void ensureCapacityInternal(int minCapacity) {
    //如果是默认的DEFAULTCAPACITY_EMPTY_ELEMENTDATA数组
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        //将两者之中的最大值改为新的容量
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    //检查是否需要扩容
    ensureExplicitCapacity(minCapacity);
}


private void ensureExplicitCapacity(int minCapacity) {
    //记录操作次数
    modCount++;

    /*
    elementData.length：原集合中实际的元素数量
    minCapacity：集合的最小容量
    */
    if (minCapacity - elementData.length > 0)
        //扩容的核心方法
        grow(minCapacity);
}

private void grow(int minCapacity) {
    //获取为添加元素之前的集合元素数量，设置为oldCapacity
    int oldCapacity = elementData.length;
    //右移位运算符：oldCapacity>>1=oldCapacity/2
    //新容量为原有容量的1.5倍
    //扩容的核心代码
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //第一次add时newCapacity为0，故newCapacity - minCapacity会小于0
    //如果新容量比所需要的容量还小
    if (newCapacity - minCapacity < 0)
        //新容量就等于所需要的容量
        newCapacity = minCapacity;
    //如果新容量比规定的最大容量还大，最新容量等于最大容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    //将原数组拷贝到一个更大容量的数组中
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

• add(int index, E element)在此列表中的指定位置插入指定的元素

检查传入index是否符合规则

判断数组是否需要进行扩容

创建新数组，并将原数组元素进行拷贝，拷贝原理是使index之后的元素向后移动一位，将index位置空出，再在该位置填充元素

元素个数+1

public void add(int index, E element) {
        //判断所传入的索引是否符合规则（既不能<0，也不能大于原数组容量）
        rangeCheckForAdd(index);
        //数组所需容量+1，并判断增加元素之后是否需要扩容
        ensureCapacityInternal(size + 1);
        //数组元素拷贝，index之后的元素向后移一位，把index的位置空了出来
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        //在index位置上填充要插入的元素
        elementData[index] = element;
        //元素个数+1
        size++;
    }
    //判断index是否符合规则
    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

• addAll(Collection<? extends E> c) 按指定集合的Iterator返回的顺序将指定集合中的所有元素追加到此列表的末尾

将原集合转换为数组形式

判断数组是否需要扩容

将传进来的集合元素拷贝到原集合的末尾

元素个数变化

public boolean addAll(Collection<? extends E> c) {
    //将有数据的集合c转换成数组形式
    Object[] a = c.toArray();
    //将数据集合长度赋值给numNew
    int numNew = a.length;
    //判断增加元素后是否需要扩容
    ensureCapacityInternal(size + numNew);
    //将a拷贝进elementData最后
    System.arraycopy(a, 0, elementData, size, numNew);
    //数组中元素个数=原数组中元素个数+新数组中元素个数
    size += numNew;
    //c容量为0则返回false，容量不为0则返回true
    return numNew != 0;
}

• addAll(int index, Collection<? extends E> c)将指定集合中的所有元素插入到此列表中，从指定的位置开始

将原集合转换为数组形式

判断数组是否需要扩容

记录下需要有多少元素进行移动

如果有元素需要移动，新数组中index之后的所有元素向后移动numNew位

对数组进行填充

数组元素个数变化

public boolean addAll(int index, Collection<? extends E> c) {
    //判断index是否符合规则
    rangeCheckForAdd(index);

    //将要添加的集合转为数组形式
    Object[] a = c.toArray();
    //将数组长度赋给numNew
    int numNew = a.length;
    //判断增加元素之后是否需要扩容
    ensureCapacityInternal(size + numNew);  \
            //记录有多少位元素需要向后移动
    int numMoved = size - index;
    //如果有元素需要移动
    if (numMoved > 0)
        //进行数组拷贝,这一步只是进行移动操作，并没有添加数据，将数组中index之后的所有元素向后移动numNew位
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);
            //进行数组填充，将集合c中的元素从数组index处开始填充
    System.arraycopy(a, 0, elementData, index, numNew);
    //数组中元素个数=原数组中元素个数+新数组中元素个数
    size += numNew;
    //返回c集合是否为空的布尔值
    return numNew != 0;
}

set(int index, E element)

根据索引修改集合元素

    public E set(int index, E element) {
        //判断索引是否符合规则，索引不能超过数组长度
        rangeCheck(index);
                //获得下标处的元素
        E oldValue = elementData(index);
        //修改索引处的元素值
        elementData[index] = element;
        //将旧的元素值返回
        return oldValue;
    }

        //校验索引
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
//获得下标处的元素
    E elementData(int index) {
        return (E) elementData[index];
    }

get(int index)

获得索引处的元素值

    /**
     * Returns the element at the specified position in this list.
     *
     * @param  index index of the element to return
     * @return the element at the specified position in this list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }
//校验索引范围
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
//返回索引处元素
    E elementData(int index) {
        return (E) elementData[index];
    }

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 remove method that skips bounds checking and does not
 * return the value removed.
 */
private void fastRemove(int index) {
    //对集合的实际修改次数+1
    modCount++;
    //计算要移动的元素的个数
    int numMoved = size - index - 1;
    //如果移动的元素的个数>0
    if (numMoved > 0)
        //移动元素
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    //将要删除的元素置为null，就是为了尽快被垃圾回收机制回收
    elementData[--size] = null; 
}

ArrayList中使用迭代器遍历时删除元素会爆ConcurrentModificationException()并发修改异常的原因：这种情况只出现在要删除的元素位于集合尾部的时候

当要删除的元素在集合的倒数第二个位置的时候，不会产生并发修改异常，因为在调用hashNext方法的时候，光标的值和集合的长度一样，那么就会返回false,因此就不会再去调用next方法获取集合的元素，既然不会调用next方法，那么底层就不会产生并发修改异常

集合每次调用add方法的时候，实际修改次数变量的值都会自增一次

在获取迭代器的时候，集合只会执行一次将时机修改集合的次数赋值给预期修改集合的次数

集合在删除元素的时候也会针对实际修改次数进行自增的操作

clear()

清空集合

public void clear() {
    //修改次数
    modCount++;

    //将数组中的每个元素都设为null
    for (int i = 0; i < size; i++)
        elementData[i] = null;
            //数组元素个数清空
    size = 0;
}

其他一些公共的方法，像toString（）还有迭代器。