Java集合系列之ArrayList

1、ArrayList简介   ArrayList的底层是数组队列，相当于动态数组。与Java中的数组相比，它的容量能动态增长。在添加大量元素前，应用程序可以使用ensureCapacity操作来增加ArrayList实例的容量。这可以减少递增式再分配的数量。这样解决了数组在初始化的时候必须要指定大小，且后续操作中无法修改数组的大小的缺点。
  • ArrayList继承于AbstractList，实现了List，RandomAccess，Cloneable，Java.io.Serializable这些接口。数据结构中线性表进行顺序存储，插入删除元素的时间复杂度为O（n），求表长以增加元素。取第i元素的时间复杂度为O(1);它是一个数组队列，提供了相关的添加、删除、修改、遍历等功能。
  • ArrayList实现了RandonAccess接口，RandomAccess是一个标志接口，表明实现这个接口的List集合是支持快速随机访问的。在ArrayList中，我们可以通过元素的序号快速获取元素对象，这就是快速随机访问。
  • ArrayList实现了Cloneable接口，即覆盖了函数clone(),能被克隆。
  • ArrayList实现了java.io.Serializable接口，这意味ArrayList支持序列化，能通过序列化去传输。
  • ArrayList中操作不是线程安全的，所以单线程中的才使用ArrayList，而多线程中使用CopyOnWriteArrayList。
  2、ArrayList源码 
public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;
    /**
     * 默认初始容量大小为10
     */
    private static final int DEFAULT_CAPACITY = 10;
    /**
     * 空对象数组（用于空实例）。
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};
     //用于默认大小空实例的共享空数组实例。
      //我们把它从EMPTY_ELEMENTDATA数组中区分出来，以知道在添加第一个元素时容量需要增加多少。
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    /**
     * 保存ArrayList数据的数组，底层用数组实现
     */
    transient Object[] elementData; // non-private to simplify nested class access
    /**
     * ArrayList 所包含的元素个数
     */
    private int size;
    /**
     * 带初始容量参数的构造函数。（用户自己指定容量）
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            //创建initialCapacity大小的数组
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            //创建空数组
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
    /**
     *默认构造函数，DEFAULTCAPACITY_EMPTY_ELEMENTDATA 为0.初始化为10，也就是说初始其实是空数组 当添加第一个元素的时候数组容量才变成10
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    /**
     * 构造一个包含指定集合的元素的列表，按照它们由集合的迭代器返回的顺序。
     */
    public ArrayList(Collection<? extends E> c) {
        //
        elementData = c.toArray();
        //如果指定集合元素个数不为0
        if ((size = elementData.length) != 0) {
            // c.toArray 可能返回的不是Object类型的数组所以加上下面的语句用于判断，
            //这里用到了反射里面的getClass()方法
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 用空数组代替
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }
}

可以看到ArrayList的内部存储结构就是一个Object类型的数组，因此它可以存放任意类型的元素。在构造ArrayList的时候，如果传入初始大小那么它将新建一个指定容量的Object数组，如果不设置初始大小那么它将不会分配内存空间而是使用空的对象数组，在实际要放入元素时再进行内存分配。下面再看看它的增删改查方法。

//增(添加)
public boolean add(E e) {
    //添加前先检查是否需要拓展数组, 此时数组长度最小为size+1
    ensureCapacityInternal(size + 1);
    //将元素添加到数组末尾
    elementData[size++] = e;
    return true;
}
//增(插入)
public void add(int index, E element) {
    //插入位置范围检查
    rangeCheckForAdd(index);
    //检查是否需要扩容
    ensureCapacityInternal(size + 1);
    //挪动插入位置后面的元素
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    //在要插入的位置赋上新值
    elementData[index] = element;
    size++;
}
//删
public E remove(int index) {
    //index不能大于size
    rangeCheck(index);
    modCount++;
    E oldValue = elementData(index);
    int numMoved = size - index - 1;
    if (numMoved > 0) {
        //将index后面的元素向前挪动一位
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    }
    //置空引用
    elementData[--size] = null;
    return oldValue;
}
//改
public E set(int index, E element) {
    //index不能大于size
    rangeCheck(index);
    E oldValue = elementData(index);
    //替换成新元素
    elementData[index] = element;
    return oldValue;
}
//查
public E get(int index) {
    //index不能大于size
    rangeCheck(index);
    //返回指定位置元素
    return elementData(index);
}
每次添加一个元素到集合中都会先检查容量是否足够，否则就进行扩容。
  1. 增(添加)：仅是将这个元素添加到末尾。操作快速。
  2. 增(插入)：由于需要移动插入位置后面的元素，并且涉及数组的复制，所以操作较慢。 
  3. 删：由于需要将删除位置后面的元素向前挪动，也会设计数组复制，所以操作较慢。
  4. 改：直接对指定位置元素进行修改，不涉及元素挪动和数组复制，操作快速。
  5. 查：直接返回指定下标的数组元素，操作快速。
通过源码看到，由于查找和修改直接定位到数组下标，不涉及元素挪动和数组复制所以较快，而插入删除由于要挪动元素，涉及到数组复制，操作较慢。并且每次添加操作还可能进行数组扩容，也会影响到性能。下面我们看看ArrayList是怎样动态扩容的。检查是否需要扩容的ensureCapacityInternal函数：   
private void ensureCapacityInternal(int minCapacity) {
    //如果此时还是空数组
    if (elementData == EMPTY_ELEMENTDATA) {
        //和默认容量比较, 取较大值
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    //数组已经初始化过就执行这一步
    ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    //如果最小容量大于数组长度就扩增数组
    if (minCapacity - elementData.length > 0) {
        grow(minCapacity);
    }
}
//集合最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//增加数组长度
private void grow(int minCapacity) {
    //获取数组原先的容量,oldCapacity为旧容量，newCapacity为新容量
    int oldCapacity = elementData.length;
    //新数组的容量, 在原来的基础上增加一半
    //位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍，
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //检验新的容量是否小于最小容量
    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();
        //对minCapacity和MAX_ARRAY_SIZE进行比较
        //若minCapacity大，将Integer.MAX_VALUE作为新数组的大小
        //若MAX_ARRAY_SIZE大，将MAX_ARRAY_SIZE作为新数组的大小
        //MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

每次添加元素前会调用ensureCapacityInternal这个方法进行集合容量检查。在这个方法内部会检查当前集合的内部数组是否还是个空数组，如果是就新建默认大小为10的Object数组。如果不是则证明当前集合已经被初始化过，那么就调用ensureExplicitCapacity方法检查当前数组的容量是否满足这个最小所需容量，不满足的话就调用grow方法进行扩容。在grow方法内部可以看到，每次扩容都是增加原来数组长度的一半，扩容实际上是新建一个容量更大的数组，将原先数组的元素全部复制到新的数组上，然后再抛弃原先的数组转而使用新的数组。

    需要注意的是：   1、java 中的length 属性是针对数组说的,比如说你声明了一个数组,想知道这个数组的长度则用到了 length 这个属性. 2、java 中的length()方法是针对字 符串String说的,如果想看这个字符串的长度则用到 length()这个方法. 3、java 中的size()方法是针对泛型集合说的,如果想看这个泛型有多少个元素,就调用此方法来查看!     3、其他函数源码 
/**
     *返回此列表中的元素数。
     */
    public int size() {
        return size;
    }
    /**
     * 如果此列表不包含元素，则返回 true 。
     */
    public boolean isEmpty() {
        //注意=和==的区别
        return size == 0;
    }
    /**
     * 如果此列表包含指定的元素，则返回true 。
     */
    public boolean contains(Object o) {
        //indexOf()方法：返回此列表中指定元素的首次出现的索引，如果此列表不包含此元素，则为-1
        return indexOf(o) >= 0;
    }
    /**
     *返回此列表中指定元素的首次出现的索引，如果此列表不包含此元素，则为-1
     */
    public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                //equals()方法比较
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }
    /**
     * 返回此列表中指定元素的最后一次出现的索引，如果此列表不包含元素，则返回-1。.
     */
    public int lastIndexOf(Object o) {
        if (o == null) {
            for (int i = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }
    /**
     * 返回此ArrayList实例的浅拷贝。 （元素本身不被复制。）
     */
    public Object clone() {
        try {
            ArrayList<?> v = (ArrayList<?>) super.clone();
            //Arrays.copyOf功能是实现数组的复制，返回复制后的数组。参数是被复制的数组和复制的长度
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // 这不应该发生，因为我们是可以克隆的
            throw new InternalError(e);
        }
    }
    /**
     *以正确的顺序（从第一个到最后一个元素）返回一个包含此列表中所有元素的数组。
     *返回的数组将是“安全的”，因为该列表不保留对它的引用。 （换句话说，这个方法必须分配一个新的数组）。
     *因此，调用者可以自由地修改返回的数组。 此方法充当基于阵列和基于集合的API之间的桥梁。
     */
    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }
    /**
     * 以正确的顺序返回一个包含此列表中所有元素的数组（从第一个到最后一个元素）;
     *返回的数组的运行时类型是指定数组的运行时类型。 如果列表适合指定的数组，则返回其中。
     *否则，将为指定数组的运行时类型和此列表的大小分配一个新数组。
     *如果列表适用于指定的数组，其余空间（即数组的列表数量多于此元素），则紧跟在集合结束后的数组中的元素设置为null 。
     *（这仅在调用者知道列表不包含任何空元素的情况下才能确定列表的长度。）
     */
    @SuppressWarnings("unchecked")
    public  T[] toArray(T[] a) {
        if (a.length < size)
            // 新建一个运行时类型的数组，但是ArrayList数组的内容
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
            //调用System提供的arraycopy()方法实现数组之间的复制
        System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }
    // Positional Access Operations
    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }
    /**
     * 返回此列表中指定位置的元素。
     */
    public E get(int index) {
        rangeCheck(index);
        return elementData(index);
    }
    /**
     * 用指定的元素替换此列表中指定位置的元素。
     */
    public E set(int index, E element) {
        //对index进行界限检查
        rangeCheck(index);
        E oldValue = elementData(index);
        elementData[index] = element;
        //返回原来在这个位置的元素
        return oldValue;
    }
    /**
     * 将指定的元素追加到此列表的末尾。
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //这里看到ArrayList添加元素的实质就相当于为数组赋值
        elementData[size++] = e;
        return true;
    }
    /**
     * 在此列表中的指定位置插入指定的元素。
     *先调用 rangeCheckForAdd 对index进行界限检查；然后调用 ensureCapacityInternal 方法保证capacity足够大；
     *再将从index开始之后的所有成员后移一个位置；将element插入index位置；最后size加1。
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //arraycopy()这个实现数组之间复制的方法一定要看一下，下面就用到了arraycopy()方法实现数组自己复制自己
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }
    /**
     * 删除该列表中指定位置的元素。 将任何后续元素移动到左侧（从其索引中减去一个元素）。
     */
    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);
        elementData[--size] = null; // clear to let GC do its work
      //从列表中删除的元素
        return oldValue;
    }
//注意：有了垃圾收集器并不意味着一定不会有内存泄漏。对象能否被GC的依据是是否还有引用指向它，上面代码中如果不手动赋null值，除非对应的位置被其他元素覆盖，否则原来的对象就一直不会被回收。
    /**
     * 从列表中删除指定元素的第一个出现（如果存在）。 如果列表不包含该元素，则它不会更改。
     *返回true，如果此列表包含指定的元素
     */
    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) {
        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 void clear() {
        modCount++;
        // 把数组中所有的元素的值设为null
        for (int i = 0; i < size; i++)
            elementData[i] = null;
        size = 0;
    }
    /**
     * 按指定集合的Iterator返回的顺序将指定集合中的所有元素追加到此列表的末尾。
     */
    public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }
    /**
     * 将指定集合中的所有元素插入到此列表中，从指定的位置开始。一次添加多个元素，根据位置不同也有两个把本，一个是在末尾添加的,一个是在指定位置插入与add()方法类似
     */
    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;
    }
    /**
     * 从此列表中删除所有索引为fromIndex （含）和toIndex之间的元素。
     *将任何后续元素移动到左侧（减少其索引）。
     */
    protected void removeRange(int fromIndex, int toIndex) {
        modCount++;
        int numMoved = size - toIndex;
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);
        // clear to let GC do its work
        int newSize = size - (toIndex-fromIndex);
        for (int i = newSize; i < size; i++) {
            elementData[i] = null;
        }
        size = newSize;
    }
    /**
     * 检查给定的索引是否在范围内。
     */
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    /**
     * add和addAll使用的rangeCheck的一个版本
     */
    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    /**
     * 返回IndexOutOfBoundsException细节信息
     */
    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }
    /**
     * 从此列表中删除指定集合中包含的所有元素。
     */
    public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        //如果此列表被修改则返回true
        return batchRemove(c, false);
    }
    /**
     * 仅保留此列表中包含在指定集合中的元素。
     *换句话说，从此列表中删除其中不包含在指定集合中的所有元素。
     */
    public boolean retainAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, true);
    }
 
 
    /**
     * 从列表中的指定位置开始，返回列表中的元素（按正确顺序）的列表迭代器。
     *指定的索引表示初始调用将返回的第一个元素为next 。 初始调用previous将返回指定索引减1的元素。
     *返回的列表迭代器是fail-fast 。
     */
    public ListIterator listIterator(int index) {
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("Index: "+index);
        return new ListItr(index);
    }
    /**
     *返回列表中的列表迭代器（按适当的顺序）。
     *返回的列表迭代器是fail-fast 。
     */
    public ListIterator listIterator() {
        return new ListItr(0);
    }
    /**
     *以正确的顺序返回该列表中的元素的迭代器。
     *返回的迭代器是fail-fast 。
     */
    public Iterator iterator() {
        return new Itr();
    }
  4.1、ArrayList的构造函数（三种方式来初始化） 
/**
 * 默认初始容量大小
*/
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
*默认构造函数，使用初始容量10构造一个空列表(无参数构造)
*/
public ArrayList()
{
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 带初始容量参数的构造函数。（用户自己指定容量）
*/
public ArrayList(int initialCapacity)
{
    if (initialCapacity > 0)  //初始容量大于0
    {
        //创建initialCapacity大小的数组
        this.elementData = new Object[initialCapacity];
    }
    else if (initialCapacity == 0)    //初始容量等于0
    {
        //创建空数组
        this.elementData = EMPTY_ELEMENTDATA;
    }
    else    //初始容量小于0，抛出异常
    {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}
 
/**
*构造包含指定collection元素的列表，这些元素利用该集合的迭代器按顺序返回
*如果指定的集合为null，throws NullPointerException。
*/
public ArrayList(Collection<? extends E> c)
{
    elementData = c.toArray();
    if ((size = elementData.length) != 0)
    {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }
    else
    {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

以无参数构造方法创建 ArrayList 时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为10。

  4.2、扩容机制： 以无参数构造方法创建 ArrayList 为例:   1）add方法()： 
/**
* 将指定的元素追加到此列表的末尾。
*/
public boolean add(E e)
{
    //添加元素之前，先调用ensureCapacityInternal方法
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //这里看到ArrayList添加元素的实质就相当于为数组赋值
    elementData[size++] = e;
    return true;
}
  2). ensureCapacityInternal()方法 可以看到add方法 首先调用了ensureCapacityInternal(size + 1)，添加元素时使用 ensureCapacityInternal() 方法来保证容量足够，如果不够时，需要使用 grow() 方法进行扩容，新容量的大小为 oldCapacity + (oldCapacity >> 1)，也就是旧容量的 1.5 倍。 
//得到最小扩容量
private void ensureCapacityInternal(int minCapacity)
{
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
    {
        // 获取默认的容量和传入参数的较大值
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

注意：当要add进第1个元素时，minCapacity为1，在Math.max()方法比较后，minCapacity 为10。

  3). ensureExplicitCapacity()方法 如果调用ensureCapacityInternal()方法就一定会进过（执行）这个方法。 
//判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity)
{
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        //调用grow方法进行扩容，调用此方法代表已经开始扩容了
        grow(minCapacity);
}
分析一下上述流程：  
  • 当add第1个元素到 ArrayList 时，elementData.length 为0 （因为还是一个空的 list），因为执行了 ensureCapacityInternal()方法 ，所以 minCapacity 此时为10。此时，minCapacity - elementData.length > 0 成立，所以会进入 grow(minCapacity)方法。
  • 当add第2个元素时，minCapacity 为2，此时elementData.length(数组容量)在添加第一个元素后扩容成10了。此时，minCapacity - elementData.length > 0 不成立，所以不会进入(执行)grow(minCapacity)方法。
  • 添加第3、4···到第10个元素时，依然不会执行grow方法，数组容量都为10。
  • 直到添加第11个元素，minCapacity(为11)比elementData.length(为10)要大。再次进入grow方法进行扩容。
  4).grow()方法 
/**
* 要分配的最大数组大小
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* ArrayList扩容的核心方法。
*/
private void grow(int minCapacity)
{
    // oldCapacity为旧容量，newCapacity为新容量
    int oldCapacity = elementData.length;
    //将oldCapacity 右移一位，其效果相当于oldCapacity / 2，
    //位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍，
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量，
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
 
    // 如果新容量大于 MAX_ARRAY_SIZE,进入(执行) hugeCapacity()方法来比较 minCapacity 和MAX_ARRAY_SIZE，
    //如果minCapacity大于最大容量，则新容量则为Integer.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 Integer.MAX_VALUE - 8。
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

int newCapacity = oldCapacity + (oldCapacity >> 1),所以 ArrayList 每次扩容之后容量都会变为原来的 1.5 倍！(JDK1.6版本以后)JDk1.6版本时，扩容之后容量为 1.5 倍+1！

grow()方法当add第1个元素时，oldCapacity 为0，经比较后第一个if判断成立，newCapacity = minCapacity(为10)。但是第二个if判断不会成立，即newCapacity 不比 MAX_ARRAY_SIZE大，则不会进入 hugeCapacity`方法。数组容量为10，add方法中 return true,size增为1。当add第11个元素进入grow方法时，newCapacity为15，比minCapacity（为11）大，第一个if判断不成立。新容量没大于数组最大size，不会进入hugeCapacity方法。数组容量扩为15，add方法中return true，size增为11。以此类推。 补充：java 中的length属性是针对数组说的，比如说你声明了一个数组，想知道这个数组的长度则用到了length这个属性。 java 中的length()方法是针对字符串的，如果想看这个字符串的长度则用到length()这个方法。 java 中的size()方法是针对泛型集合说的，如果想看这个泛型有多少个元素，就调用此方法来查看。   5).hugeCapacity()方法。 从上面grow()方法源码我们知道： 如果新容量大于MAX_ARRAY_SIZE,进入(执行)hugeCapacity()方法来比较minCapacity和 MAX_ARRAY_SIZE，如果minCapacity大于最大容量，则新容量则为Integer.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 Integer.MAX_VALUE - 8。为什么减掉8？因为有些虚拟机在数组中保留了一些头信息。避免内存溢出！ 
private static int hugeCapacity(int minCapacity)
{
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    //对minCapacity和MAX_ARRAY_SIZE进行比较
    //若minCapacity大，将Integer.MAX_VALUE作为新数组的大小
    //若MAX_ARRAY_SIZE大，将MAX_ARRAY_SIZE作为新数组的大小
    //MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
  6)、System.arraycopy()和Arrays.copyOf()方法 阅读源码的话，我们就会发现ArrayList中大量调用了这两个方法。比如：我们上面讲的扩容操作以及add(int index, E element)、toArray()等方法中都用到了该方法！System.arraycopy()方法 
/**
* 在此列表中的指定位置插入指定的元素。
*先调用 rangeCheckForAdd 对index进行界限检查；然后调用 ensureCapacityInternal 方法保证capacity足够大；
*再将从index开始之后的所有成员后移一个位置；将element插入index位置；最后size加1。
*/
public void add(int index, E element)
{
    rangeCheckForAdd(index);
    ensureCapacityInternal(size + 1);//Increments modCount!!
    //arraycopy()方法实现数组自己复制自己
    //elementData:源数组;index:源数组中的起始位置;elementData：目标数组；index + 1：目标数组中的起始位置； size - index：要复制的数组元素的数量；
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}
  我们写一个简单的方法测试以下： 
public class ArraycopyTest
{
    public static void main(String[] args)
    {
        // TODO Auto-generated method stub
        int[] a = new int[10];
        a[0] = 0;
        a[1] = 1;
        a[2] = 2;
        a[3] = 3;
        System.arraycopy(a, 2, a, 3, 3);
        a[2]=99;
        for (int i = 0; i < a.length; i++)
        {
            System.out.println(a[i]);
        }
    }
}
输出结果：
0 1 99 2 3 0 0 0 0 0
  Arrays.copyOf()方法 
/**
  以正确的顺序返回一个包含此列表中所有元素的数组（从第一个到最后一个元素）; 返回的数组的运行时类型是指定数组的运行时类型。
  */
public Object[] toArray()
{
    //elementData：要复制的数组；size：要复制的长度
    return Arrays.copyOf(elementData, size);
}
  使用 Arrays.copyOf()方法主要是为了给原有数组扩容，测试代码如下： 
public class ArrayscopyOfTest
{
    public static void main(String[] args)
    {
        int[] a = new int[3];
        a[0] = 0;
        a[1] = 1;
        a[2] = 2;
        int[] b = Arrays.copyOf(a, 10);
        System.out.println("b.length"+b.length);
    }
}
输出结果：
10
两者联系和区别
  • 联系:看两者源代码可以发现copyOf()内部实际调用了System.arraycopy()方法
  • 区别:arraycopy()需要目标数组，将原数组拷贝到你自己定义的数组里或者原数组，而且可以选择拷贝的起点和长度以及放入新数组中的位置 copyOf()是系统自动在内部新建一个数组，并返回该数组。
7)、ensureCapacity方法 ArrayList 源码中有一个ensureCapacity方法, ArrayList 内部没有被调用过，所以很显然是提供给用户调用的，那么这个方法有什么作用呢？增加此 ArrayList 实例的容量，以确保它至少可以容纳由minimum capacity参数指定的元素数。最好在 add 大量元素之前用 ensureCapacity 方法，以减少增量重新分配的次数。 
/**
如有必要，增加此 ArrayList 实例的容量，以确保它至少可以容纳由minimum capacity参数指定的元素数。
*
* @param   minCapacity   所需的最小容量
*/
public void ensureCapacity(int minCapacity)
{
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                    // any size if not default element table
                    ? 0
                    // larger than default for default empty table. It's already
                    // supposed to be at default size.
                    : DEFAULT_CAPACITY;
    if (minCapacity > minExpand)
    {
        ensureExplicitCapacity(minCapacity);
    }
}

最好在 add 大量元素之前用ensureCapacity方法，以减少增量重新分配的次数。我们通过下面的代码实际测试以下这个方法的效果：

public class EnsureCapacityTest
{
    public static void main(String[] args)
    {
        ArrayList list = new ArrayList();
        final int N = 10000000;
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < N; i++)
        {
            list.add(i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("使用ensureCapacity方法前："+(endTime - startTime));
    }
}
运行结果：
使用ensureCapacity方法前：2158



通过运行结果，我们可以看出向ArrayList添加大量元素之前最好先使用ensureCapacity方法，以减少增量重新分配的次数。


8). 删除元素

需要调用System.arraycopy()将index+1后面的元素都复制到index位置上。



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);
    elementData[--size] = null; // clear to let GC do its work
    return oldValue;
}





5、内部类
ArrayList有四个内部类，其中的Itr是实现了Iterator接口，同时重写了里面的hasNext()，next()，remove()等方法；其中的ListItr继承Itr，实现了ListIterator接口，同时重写了hasPrevious()，nextIndex()，previousIndex()，previous()，set(E e)，add(E e)等方法，所以这也可以看出了 Iterator和ListIterator的区别:ListIterator在Iterator的基础上增加了添加对象，修改对象，逆向遍历等方法，这些是Iterator不能实现的。



  private class Itr implements Iterator  
  private class ListItr extends Itr implements ListIterator  
  private class SubList extends AbstractList implements RandomAccess  
  static final class ArrayListSpliterator implements Spliterator  





SubList 这个类中单独定义了 set、get、size、add、remove 等方法。当我们调用 subList 方法的时候，会通过调用 SubList 的构造函数创建一个SubList，那么看下这个构造函数做了哪些事情：



SubList(AbstractList parent, int offset, int fromIndex, int toIndex) {
    this.parent = parent;
    this.parentOffset = fromIndex;
    this.offset = offset + fromIndex;
    this.size = toIndex - fromIndex;
    this.modCount = ArrayList.this.modCount;
}




可以看到，这个构造函数中把原来的 List 以及该 List 中的部分属性直接赋值给自己的一些属性了。


也就是说，SubList 并没有重新创建一个 List，而是直接引用了原有的 List（返回了父类的视图），只是指定了一下他要使用的元素的范围而已（fromIndex（包含），到 toIndex（不包含））。
所以，为什么不能讲 subList 方法得到的集合直接转换成 ArrayList 呢？因为SubList 只是 ArrayList 的内部类，他们之间并没有集成关系，故无法直接进行强制类型转换。
 
6、ArrayList使用demo



import java.util.ArrayList;
import java.util.Iterator;
public class ArrayListDemo {
    public static void main(String[] srgs){
         ArrayList arrayList = new ArrayList();
         System.out.printf("Before add:arrayList.size() = %d\n",arrayList.size());
         arrayList.add(1);
         arrayList.add(3);
         arrayList.add(5);
         arrayList.add(7);
         arrayList.add(9);
         System.out.printf("After add:arrayList.size() = %d\n",arrayList.size());
         System.out.println("Printing elements of arrayList");
         // 三种遍历方式打印元素
         // 第一种：通过迭代器遍历
         System.out.print("通过迭代器遍历:");
         Iterator it = arrayList.iterator();
         while(it.hasNext()){
             System.out.print(it.next() + " ");
         }
         System.out.println();
         // 第二种：通过索引值遍历
         System.out.print("通过索引值遍历:");
         for(int i = 0; i < arrayList.size(); i++){
             System.out.print(arrayList.get(i) + " ");
         }
         System.out.println();
         // 第三种：for循环遍历
         System.out.print("for循环遍历:");
         for(Integer number : arrayList){
             System.out.print(number + " ");
         }
         // toArray用法
         // 第一种方式(最常用)
         Integer[] integer = arrayList.toArray(new Integer[0]);
         // 第二种方式(容易理解)
         Integer[] integer1 = new Integer[arrayList.size()];
         arrayList.toArray(integer1);
         // 抛出异常，java不支持向下转型
         //Integer[] integer2 = new Integer[arrayList.size()];
         //integer2 = arrayList.toArray();
         System.out.println();
         // 在指定位置添加元素
         arrayList.add(2,2);
         // 删除指定位置上的元素
         arrayList.remove(2);    
         // 删除指定元素
         arrayList.remove((Object)3);
         // 判断arrayList是否包含5
         System.out.println("ArrayList contains 5 is: " + arrayList.contains(5));
         // 清空ArrayList
         arrayList.clear();
         // 判断ArrayList是否为空
         System.out.println("ArrayList is empty: " + arrayList.isEmpty());
    }
}



 
7、总结
 
ArrayList中比较常用的方法做了分析，其中有些值得注意的要点：
1. ArrayList底层实现是基于数组的，因此对指定下标的查找和修改比较快，但是删除和插入操作比较慢。
2. 构造ArrayList时尽量指定容量，减少扩容时带来的数组复制操作，如果不知道大小可以赋值为默认容量10。
3. 每次添加元素之前会检查是否需要扩容，每次扩容都是增加原有容量的一半。
4. 每次对下标的操作都会进行安全性检查，如果出现数组越界就立即抛出异常。
5. ArrayList的所有方法都没有进行同步，因此它不是线程安全的
 
 参考：https://www.cnblogs.com/CarpenterLee/p/5419880.html

 
						  
					  
						
							


						

							
							
			java集合							
						



						

						
						


						

						
					
					

					
					

						
相关

						

				
						
			

																
								

										
Java核心技术读书笔记9-3 Java集合相关算法与遗留集合

									
									

								 

        

								

							
							

																
								

										
Java核心技术读书笔记9-1 Java集合概述

									
									

								 

        

								

							
							

																
								

										
java集合源码详解

									
									

								 

        

								

							
							

																
								

										
老哥，您看我这篇Java集合，还有机会评优吗？

									
									

								 

        

								

							
							

																
								

										
java集合

									
									

								 

        

								

							
							

																
								

										
Java集合框架Collection(1)ArrayList的三种遍历方法

									
									

								 

        

								

							
							

																
								

										
java集合框架

									
									

								 

        

								

							
							

																
								

										
Java集合

									
									

								 

        

								

							
							

																
								

										
Java集合的快速失败机制 “fail-fast”

									
									

								 

        

								

							
							

																
								

										
Java集合(七)--基于jdk1.8的HashMap源码

									
									

								 

        

								

							
							

																
								

										
深入java集合学习1-集合框架浅析

									
									

								 

        

								

							
							

																
								

										
java集合-尚硅谷学习笔记

									
									

								 

        

								

							
							
            
            
            
                                    
           
  			
						

					

					
				

				

														
					
					

					
									

					
									   
标签

										

										
    
										

									

										
										

									

					

					
				


			
		
		
		
			


						





	

	
一品网 冀ICP备14022925号-6