1. ArrayList的继承与实现

ArrayList **implements **List，RandomAccess，Cloneable、java.io.Serializable
extends **AbstractList**
image.png

2. 源码分析

2.1. 成员变量与成员方法

2.1.1. 成员变量

  1. 默认初始容量
  2. private static final int DEFAULT_CAPACITY = 10;
  4. 为空的实例对象
  5. private static final Object[] EMPTY_ELEMENTDATA = {};
  7. 空参构造的初始数组
  8. private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
  10. ArrayList中用来存放元素的数组。
  11. transient Object[] elementData;
  13. ArrayList中存放元素的数量。
  14. private int size;

2.1.2. 成员方法

ensureCapacity(int minCapacity)：手动扩容，只要扩容的大小大于等于1.5倍扩容量或（空数组情况下）10，就可以进行扩容。

  • 如果是空数组则要用DEFAULT_CAPACITY和minCapacity进行比较，如果minCapacity比DEFAULT_CAPACITY要小，则手动扩容失败。

  • 如果不是空数组，则只要minCapacity>0，就进入下一个方法进行扩容判断。

    1. //用于实时的手动扩容
    2. public void ensureCapacity(int minCapacity) {
    3.   //
    4.   int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
    5.       ? 0 : DEFAULT_CAPACITY;
    7.   if (minCapacity > minExpand) {
    8.       ensureExplicitCapacity(minCapacity);
    9.   }
    10. }

2.2. 构造方法

  1. 空参构造
  2. 有参——传入初始容量
  3. 有参——传入另一个Collection实现类

    空参构造的ArrayList数组大小为0，会在第一次放入元素进行扩容，将数组容量调整到10； 有参构造传入int数作为数组容量，如果传入数大于0，则会直接创建等大小的数组； 有参构造传入Collection实现类，将该实现类转换为数组，并判断是否存在长度和类型的问题。

  1. //无参构造
  2. public ArrayList() {
  3.     this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  4. }
  6. //有参——传入初始容量
  7. public ArrayList(int initialCapacity) {
  8.     if    (initialCapacity > 0) {
  9.         this.elementData = new Object[initialCapacity];
  10.     }else if(...
  11. }
  13. //传入一个Collection实现类
  14. public ArrayList(Collection<? extends E> c) {
  15.     elementData = c.toArray();
  16.     if((size = elementData.length) != 0) {
  17.         if(elementData.getClass() != Object[].class) 
  18.             elementData = Arrays.copyOf(elementData, size, Object[].class);
  19.     } else {
  20.         this.elementData = EMPTY_ELEMENTDATA;
  21.     }
  22. }

2.3. add()

2.3.1. add(E e) 添加

add(E e)时会在放入元素之前检测数组的容量，判断是否需要扩容
空数组会进行扩容，容量为默认初始容量10；
非空数组如果数组已满，也会进行扩容，扩容后大小为原来的1.5倍； 

  1. public boolean add(E e) {
  2.     //检测数组容量
  3.     ensureCapacityInternal(size + 1);  // Increments modCount!!
  4.     //添加元素
  5.     elementData[size++] = e;
  6.     return true;
  7. }
  9. //不明白为什么要多加这一层方法
  10. private void ensureCapacityInternal(int minCapacity) {
  11.     ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
  12. }
  14. private static int calculateCapacity(Object[] elementData, int minCapacity) {
  15.     //计算数组容量，传入数组和size+1
  16.     //如果此时数组还是一个初始的空数组，返回max(10,size+1)，应该就是直接返回10.
  17.     if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
  18.         return Math.max(DEFAULT_CAPACITY, minCapacity);
  19.     }
  20.     //如果不是空数组，就返回size+1
  21.     return minCapacity;
  22. }
  24. private void ensureExplicitCapacity(int minCapacity) {
  25.     modCount++;
  27.     // 如果size+1>数组的长度（放入这个新的元素前数组已经装满），则进行扩容
  28.     if (minCapacity - elementData.length > 0)
  29.         grow(minCapacity);
  30. }
  32.     private void grow(int minCapacity) {
  33.         // overflow-conscious code
  34.         int oldCapacity = elementData.length;
  35.         //新数组长度为原来的1.5倍
  36.         int newCapacity = oldCapacity + (oldCapacity >> 1);
  37.         //用于空参构造，初次创建（newCapacity = 0+0）
  38.         if (newCapacity - minCapacity < 0)
  39.             newCapacity = minCapacity;
  40.         //如果原长度的1.5倍大于Integer.MAX_VALUE-8，则返回Integer.MAX_VALUE或MAX_VALUE-8
  41.         if (newCapacity - MAX_ARRAY_SIZE > 0)
  42.             newCapacity = hugeCapacity(minCapacity);
  43.         //扩容{1,2,3} -> {1,2,3,0,0,0}
  44.         elementData = Arrays.copyOf(elementData, newCapacity);
  45.     }

2.3.2. add(E e , int index) 插入

会在指定位置插入元素，当前位置及其右边元素全部右移。

  1. public void add(int index, E element) {
  2.     rangeCheckForAdd(index); //判断索引是否超出size范围，如果超出直接报错
  4.     ensureCapacityInternal(size + 1);  // 判断是否需要扩容
  5.     //将数组index开始的size-index长度的元素复制到index+1的位置
  6.     System.arraycopy(elementData, index, elementData, index + 1,
  7.                      size - index);
  8.     elementData[index] = element;
  9.     size++;
  10. }

2.4. get(int index) 获取

获取指定索引的元素。

public E get(int index) {
    rangeCheck(index);//判断索引是否超出size范围，如果超出直接报错

    return elementData(index);//返回索引对应元素
}

2.5. set(int index, E e) 替换

替换指定位置元素（必须得是size范围内的索引，并替换索引位置元素）

public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

2.6. remove() 删除

2.6.1. remove(int index)

删除index索引的元素，将左边的元素全部左移一位，返回删除元素。

public E remove(int index) {
    rangeCheck(index);
    modCount++;
    E oldValue = elementData(index);
    //计算需要左移元素的数量
    int numMoved = size - index - 1;
    //如果有需要左移的元素（删除的不是最后一个元素），将所有左边的元素左移
    if (numMoved > 0)
        将elementData中index+1位置开始的numMoved个元素移动到index位置
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

2.6.1. remove(Object o)

正序遍历数组，删除第一个与o相同的对象（用了equals方法），返回True/False

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])) {
                //和remove(index)差不多，省略了(返回值和检测index是否越界)
                fastRemove(index);
                return true;
            }
    }
    return false;
}

2.7. clear() 清空数组

遍历数组的size范围，所有位置全部置为null。

3. 面试题

3.0. ArrayList的数据结构是如何实现的？

ArrayList底层维护了一个可动态扩容的数组，它的增删改查就是对数组的增删改查。
有以下特性：

  1. 快速查找（时间复杂度O(1)）
  2. 容量动态增加（每次数组长度扩容为原来的1.5倍）

    3.1. ArrayList 实现了哪些接口，继承了什么类？

    ArrayList 继承了AbstractList类，实现了List、RandomAccess、Cloneable、Serializable接口。

    RandomAccess 快速访问标记接口，表示查找速度O(1) Cloneable 接口，实现了Cloneable接口，调用clone()方法产生深拷贝（克隆的对象与原对象地址值不同） Serializable接口，可序列化

3.2. ArrayList的初始容量，扩容方式？

  • 如果是空参构造的ArrayList对象，底层数组会在第一次add()值时扩容到默认大小10。
  • 如果是有参构造的ArrayList对象：

如果参数设置大于0，则会在构造方法中就创建对应大小的数组；
如果参数设置小于等于0，与空参构造同。

  • 当使用add方法添加或插入元素之前会先检测数组长度：

如果数组长度为0，则扩容到10；
如果数组长度不为0，则扩容到原来1.5倍；
如果扩容后的数组长度>Integer.MAX_VALUE-8，则将其扩容到Integer.MAX_VALUE。

  • 扩容的底层实现是使用Arrays.copyOf()方法，实现浅拷贝——新建一个原数组大小1.5倍大小的数组，将原数组的数据拷贝到新数组中。

3.3. 如何尽量避免数组扩容？

预估要保存元素的数量

  • 利用有参构造，在构造ArrayList对象的时候就指定容量大小；
  • 利用ArrayList的 ensureCapacity( int minCapacity)方法，实时地指定容量大小；

3.4. remove()方法是如何实现的？

remove()方法有两个重载方法，分别是根据index和根据对象删除元素。

  • 根据index删除元素：
    1. 首先判断index是否超出size范围，没有超出就获取该元素；
    2. 然后将该元素右边所有的元素向左复制（System.arraycopy(…)）；
    3. 并将size-1，将最后一个元素位置置空；
    4. 返回被删除元素。
  • 根据Object删除元素：
    1. 判断输入对象，如果不为空就从头遍历；
    2. 使用equals方法判断两个元素是否相等，如果相等就调用fastRemove(index)方法；
    3. fastRemove(index)方法与remove(index)类似；
    4. 返回True/False；

3.5. ArrayList线程是否安全

ArrayList线程写操作不安全，会触发ConcurrentModificationException异常，只能在单线程的环境下使用。
多线程的环境有如下两个方法：
1.使用 Collections.synchronizedList(new ArrayList<>())获取一个线程安全的List类对象；
2.使用 new CopyOnWriteArrayList<>() 创建一个线程安全的List类对象；

CopyOnWrite 指写入时复制，COW 计算机程序设计领域的一种优化策略；
多线程调用List时，写入会覆盖，容易造成数据问题，所以写入时要避免覆盖；
读写分离；
CopyOnWrite 底层使用的是Lock 而不是 synchronized，所以效率比Vector要高（Vector底层使用的是synchronized）；

3.6. 快速失败机制

快速失败是指某个线程在迭代集合类的时候，不允许其他线程修改该集合类的内容，不然会出现ConcurrentModificationException异常，这个时候该迭代器就快速失败了。
值得注意的是：用iterator迭代Collection的时候，iterator就是另起的一条线程，此时如果用Collection.remove()的方法，则是从主线程中对Collection进行修改，故触发了快速失败。而使用迭代器自带的iterator.remove()则不会造成快速失败。

3.7. 什么时候用到了浅复制？

1.动态扩容的时候调用Arrays.copyOf()方法实现浅复制；
2.插入元素的时候调用System.arraycopy()方法实现了浅复制;
3.删除元素的时候调用System.arraycopy()方法实现了浅复制。
使用浅复制的操作复杂度会较高，所以ArrayList不适合插入或删除元素。