关于java:竟然还有人说ArrayList是2倍扩容今天带你手撕ArrayList源码

ArrayList 是咱们开发中最罕用到的汇合，然而很多人对它的源码并不理解，导致面试时，面试官问的略微深刻的问题，就无奈作答，明天咱们一起来探索一下 ArrayList 源码。

1. 简介

• ArrayList 底层是数组，容许元素是 null，可能动静扩容
• size、isEmpty、get、set、add 等办法工夫复杂度都是 O (1)
• 非线程平安，并发批改时，会抛出 ConcurrentModificationException

2. 初始化

// 初始容量
private static final int DEFAULT_CAPACITY = 10;

// 空数组
private static final Object[] EMPTY_ELEMENTDATA = {};

// 默认空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

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

// 无参初始化，默认是空数组
public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}

// 有参初始化，指定容量大小
public ArrayList(int initialCapacity) {if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException("Illegal Capacity:"+initialCapacity);
    }
}

切记： 无参初始化的时候，默认是空数组，并没有初始化容量大小，容量是在第一次增加元素的才进行初始化。

3. 增加元素

public boolean add(E e) {
  // 确保数组容量够用，size 是元素个数
  ensureCapacityInternal(size + 1);
  // 间接赋值
  elementData[size++] = e;
  return true;
}

// 确保数组容量够用
private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

// 计算所需最小容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
      // 如果数组等于空数组，最小容量为 10
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
      // 如果所需最小容量大于数组长度，就进行扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

看一下扩容逻辑：

// 扩容，就是把旧数据拷贝到新数组外面
private void grow(int minCapacity) {
  int oldCapacity = elementData.length;
  // oldCapacity >> 1 是把 oldCapacity 除以 2，意思是 1.5 倍扩容
  int newCapacity = oldCapacity + (oldCapacity >> 1);

  // 如果扩容后的容量小于最小容量，扩容后的容量就等于最小容量
  if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;

  // 如果扩容后的容量大于 Integer 的最大值，就用 Integer 最大值
  if (newCapacity - MAX_ARRAY_SIZE > 0)
    newCapacity = hugeCapacity(minCapacity);
 
  // 扩容并赋值给原数组
  elementData = Arrays.copyOf(elementData, newCapacity);
}

能够看到：

• 扩容是以原容量的 1.5 倍扩容，并不是翻倍扩容
• 最大容量是 Integer 的最大值
• 增加元素时，没有对元素校验，能够是 null

再看一下数组拷贝的逻辑，这里都是 Arrays 类外面的办法了：

/**
 * @param original  原数组
 * @param newLength 新的容量大小
 */
public static <T> T[] copyOf(T[] original, int newLength) {return (T[]) copyOf(original, newLength, original.getClass());
}

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    // 创立一个新数组，容量是新的容量大小
    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 类的数组拷贝办法，是 native 办法：

/**
 * @param src     原数组
 * @param srcPos  原数组的开始地位
 * @param dest    指标数组
 * @param destPos 指标数组的开始地位
 * @param length  被拷贝的长度
 */
public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);

4. 删除单个元素

public boolean remove(Object o) {
      // 判断要删除的元素是否为 null
    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 void fastRemove(int index) {
    modCount++;
      // 计算须要挪动的元素的个数
    int numMoved = size - index - 1;
    if (numMoved > 0)
          // 从 index+ 1 地位开始拷贝，也就是前面的元素整体向左挪动一个地位
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
      // 数组最初一个元素赋值为 null，避免会导致内存透露
    elementData[--size] = null;
}

能够晓得，删除元素，就是遍历数组，循环比拟是否等于目标值。如果相等，就把该地位前面的元素整体向左挪动一个地位，再把数组最初一个元素赋值为 null。

5. 批量删除

// 批量删除 ArrayList 和汇合 c 都存在的元素
public boolean removeAll(Collection<?> c) {
    // 非空校验
    Objects.requireNonNull(c);
    // 批量删除
    return batchRemove(c, false);
}

private boolean batchRemove(Collection<?> c, boolean complement){final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {for (; r < size; r++)
            if (c.contains(elementData[r]) == complement)
                // 把须要保留的元素左移
                elementData[w++] = elementData[r];
    } finally {
                // 当出现异常的时候，可能不相等
        if (r != size) {
            // 1：可能是下面的 for 循环呈现了异样
            // 2：可能是其它线程增加了元素
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
          // 把不须要保留的元素赋值为 null
        if (w != size) {for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

能够晓得，批量删除的时候，只会进行一次数组拷贝，比用 for 循环单个删除效率更高，所以删除一批元素的时候，尽量用 removeAll() 办法。

5. 总结

本文剖析了 ArrayList 的初始化、put、add、remove、动静扩容等办法的底层源码，置信大家对于 ArrayList 有了更深层次的理解。