ArrayList源码

toArray()

1. toArray()空参方法
   将新分配一个大小为容器大小的数组作为返回。
   该方法为Array和Collection的桥梁
2. toArray(T[] a)
   根据参数a的大小进行判断
   1. 若参数a的size小于list的大小，则新分配一个数组，且数组类型为a的类型
   2. 否则将list的内容赋给a数组。另外，如果a的长度大于list长度（等于的话就无事发生）还会将null赋给a[size]。

扩容/add(E e)的逻辑

按照代码的顺序，逻辑分为以下几步

1. 先调用ensureCapacityInternal(size+1)，该方法就一行为：```java private void ensureCapacityInternal(int minCapacity) {

    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));

   } ```

2. 进入calculateCapacity（elementData，minCapacity）
   先通过elementDate是否为默认容量的空容器，如果是则返回默认长度（10）和作为参数传进去的长度（size+1）较大值
   若elementDate已经被初始化了，则返回传进去参数的值(size+1)```java private static int calculateCapacity(Object[] elementData, int minCapacity) {

    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;

   } ```

3. 进入ensureExplicitCapacity(minCapacity)

   1. modCount++，扩容操作也算那个结构性改变
   2. 若传进去的参数长度大于elementData长度，则调用grow(minCapacity)

      private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
      }

4. 进入grow(minCapacity)
   主要为三步，newCapacity分别为不同的值

   1. 若newCapacity大于oldCapacity，将oldCapacity的1.5倍赋给newCapacity。
   2. 若此时的newCapacity还比参数minCapacity还小，则将minCapacity赋给newCapacity。
   3. 若此时newCapacity比MAX_ARRAY_SIZE（Integer.MAX_VALUE）要大，则调用hugeCapacity(minCapacity)，返回值传给newCapacity。

确定了最后的newCapacity之后，使用Arrays.copyOf(element,newCapacity)。

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        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);
    }

1. hugeCapacity(minCapacity)
   先判断minCapacity是否小于0(这里小于零指超过了整型最大的正数范围)，若超过了抛出OutOfMemoryError
   若没超过（此时应该介于MAX_ARRAY_SIZE和Integer.MAX_VALUE之间），则返回Integer.MAX_VALUE。```java private static int hugeCapacity(int minCapacity) {

    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;

   } ```

ArrayList删除逻辑

1. remove（int index）```java public E remove(int index) {

    //检查是否超过size
    rangeCheck(index);
    //该操作为结构性改变
    modCount++;
    //提取出oldvalue作为return
    E oldValue = elementData(index);
    //计算出需要移动多少个元素
    int numMoved = size - index - 1;
    if (numMoved > 0)
        //5个参数的意思：源数组，原数组读开始位置，目的数组，目的数组写开始位置，移动数量
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
    return oldValue;

   } ```

2. remove（Object o）```java public boolean remove(Object o) {

    //判断对象是否为Null
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                //fastRemove作用见下面的源码解释
                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 } ```

Arrays.copyof()和System.arraycopy()方法的区别

1. copyof不需要目的数组，而是新建一个数组，作为返回值
2. arraycopy需要目的数组，将源数组拷贝进目的数组中，并且可以指定源数组拷贝起点，拷贝长度和目的数组起始下标

ArrayList需要注意的：

1. ensureCapacity(int minCapacity)
   在一次性添加大量元素前，最好使用ensureCapacity(int minCapacity)方法来一次性扩大容器的容量，以免去数次的在增量时扩大数组所带来的复制操作。
2. trimToSize()
   去掉多余的数组容量，将容量设置为当前实际数组的size。
3. get(int index)和set(int index)方法都会在实际get和set之前进行rangeCheck(index)，保证不超出范围。
4. ArrayList可以add(null)。