ArrayList源码解析

在平时Java,存储数据需要用到列表，而大多时候都能用到ArrayList，比如Mybatis查询数据列表，返回列表都是ArrayList，很多数据的存放也用到了ArrayList。

jdk 版本： 1.8

ArrayList 是基于大小可变的数组实现，并允许添加null值, 根据下标就能数据查询快。数组一旦初始化就确定好了大小，如果需要添加数据，就需要做数据的复制，这些操作比较耗时。

前言

ArrayList查询数据直接根据下标获取数据，而数据的添加和删除涉及数组的复制，主要用到了两个方法：

• System.arraycopy
• Arrays.copyOf

System.arraycopy

arraycopy(Object src, int srcPos,Object dest, int destPos,int length) 将数组的src，从起始位置srcPos到最后的数据。复制给dest数组，起始位置为destPos，长度为length

将数组 src 从srcPos起始长度为length的数据赋值给数组dest的起始为destPos

Arrays.copyOf

Arrays.copyOf也是调用System.arraycopy方法：

 public static int[] copyOf(int[] original, int newLength) {
    int[] copy = new int[newLength];
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

首先创建一个新的数组copy，将original数组全部复制给copy数组。

主要的实例变量：

// 底层数组
transient Object[] elementData;
// 数组个数大小
private int size;
// 默认空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

• ArrayList是基于数组的一个实现， elementData就是底层的数组。
• size 是记录数组的个数。

新建一个ArrayList实例：

List<Integer> list = new ArrayList<>();

首先调用无参构造方法，直接赋值一个空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA。

添加数据

添加数据有两个方法：

• add(E e) 直接添加在数组尾部。
• add(int index, E element) 根据下标添加数据。

add(E e)

在列表尾部添加数据：

/**
 * Appends the specified element to the end of this list.
 */
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

ensureCapacityInternal 判断添加数据后的容量是否足够，如果不够，做扩容操作。

private void ensureCapacityInternal(int minCapacity) {
  ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
      return Math.max(DEFAULT_CAPACITY, minCapacity);
  }
  return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
  modCount++;

  // overflow-conscious code
  if (minCapacity - elementData.length > 0)
      grow(minCapacity);
}

ensureCapacityInternal先调用calculateCapacity,然后再调用ensureExplicitCapacity。

calculateCapacity 当前数组为null时，就返回10 和 minCapacity 的最大值，否则返回minCapacity。这个方法就是返回数组的大小。

ensureExplicitCapacity 判断 minCapacity 大于 elementData.length 做扩容处理，这里重点将 grow 方法：

private void grow(int minCapacity) {
    // overflow-conscious code
    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);
}

group 主要做了两件事：

• 长度扩大到原来的 1.5倍
• 拷贝数组到新长度的数组

做完判断是否要做扩容之后，直接在size位置上赋值要添加的元素，然后size再自增。

elementData[size++] = e;

add 方法主要有两个步骤：

• 判断是否要进行扩容，新添加数据数组长度大于现有的数组长度，进行 1.5的扩容。
• 在数组 size下标赋值数据。

add(int index, E element)

此添加数据是在指定的下标添加数据。

public void add(int index, E element) {
    // 下标是否越界
    rangeCheckForAdd(index);
    // 判断是否要扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 复制i到size的数据到i+1 到size +1
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

add(int index, E element) 在index下标添加数据，

• 首先判断 index 是否在 0 ~size之间。
• 判断是否要扩容，需要扩容，进行 1.5倍扩容。
• 数据迁移,把 index以后的数据全部往后移动一位。
• 赋值 index 下标数据。

获取数据

获取数据只有通过数组下标获取数据 get(int index)：

public E get(int index) {
  //检查是否超过数组范围 
  rangeCheck(index);
  
  return elementData(index);
}

@SuppressWarnings("unchecked")
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;
}

判断要删除数据是否为null:

• 为空，判断 elementData[index]是否为空。
• 不为空，判断元素 equals是否匹配 elementData[index]。

上面判断都为true时，调用fastRemove方法：

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
}

移动数组数据，index+1 以及之后的数据往前移动一位，最后一位size-1赋值为null。

remove(int index)

根据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;
}