竟然还有人说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有了更深层次的了解,下篇一块学习一下LinkedList的源码。

商匡云商
Logo
对比商品
  • 合计 (0)
对比
0
购物车