JDK17源码系列-ArrayList源码解读

JDK17源码系列-ArrayList接口源码解读

1.List集合接口类图
在这里插入图片描述
2.ArrayList详细类图
ArrayList继承了AbstractList实现了List、Serializable等接口，实现Serializable接口使得ArrayList类的对象可以串行化，串行化后，对象可以进行网络传输，也可以保存到文件。

3.ArrayList底层使用了数组作为存储结构，默认存储容量为10

// 源码
transient Object[] elementData; // 默认数组存储结构
private static final int DEFAULT_CAPACITY = 10; // 默认存储大小

4.构造函数

public ArrayList()

// 源码  生成一个默认的空的数组，所以第一次添加元素时就进行了扩容操作，
// 扩容操作是比较耗费性能的，因此不推荐使用空的构造函数，
// 推荐使用public ArrayList(int initialCapacity)，初始容量尽量使用默认值10， 避免空间浪费  
public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

public ArrayList(int initialCapacity)

// 源码 生成一个指定初始容量的动态数组
public ArrayList(int initialCapacity) {if (initialCapacity > 0) { // 如果指定容量大于0 则初始化一个指定大小的动态数组this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA; // 如果指定容量为0 返回一个空的数组} else {throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);}
}

public ArrayList(Collection<? extends E> c)

// 源码  初始化一个包含指定集合的动态数组
public ArrayList(Collection<? extends E> c) {Object[] a = c.toArray();    // 将指定的集合转换为数组//否则 调用数组工具类中的copyOf函数进行数组拷贝if ((size = a.length) != 0) {  if (c.getClass() == ArrayList.class) {elementData = a;} else {// 否则 调用数组工具类中的copyOf函数进行数组拷贝elementData = Arrays.copyOf(a, size, Object[].class); }} else {// replace with empty array.elementData = EMPTY_ELEMENTDATA;  // 如果指定集合大小为0 则初始化一个空数组}
}

public void trimToSize() 空间压缩

// 源码
public void trimToSize() {modCount++;if (size < elementData.length) {// 当size小于存储空间大小时，// 将通过调用数组拷贝方法(底层调用的是System.arraycopy)，实现空间压缩elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size);}
}

添加元素（增）

public boolean add(E e) 添加元素

// 源码
public boolean add(E e) {modCount++;add(e, elementData, size); // 调用私有方法addreturn true;
}private void add(E e, Object[] elementData, int s) {// 如果数组元素个数等于数组长度，进行动态扩容， 否则直接添加元素， 数组元素个数+1if (s == elementData.length) elementData = grow();elementData[s] = e;size = s + 1;
}

public void add(int index, E element)

// 源码 将元素添加到指定位置
public void add(int index, E element) {// 检查索引是否合法rangeCheckForAdd(index);modCount++;final int s;Object[] elementData;// 如果当前数组元素个数与数组长度相等，则进行动态扩容if ((s = size) == (elementData = this.elementData).length)elementData = grow();// 数组拷贝， 将elementData数组中起始位置为index后的所有元素向后移动一位   System.arraycopy(elementData, index,elementData, index + 1,s - index);elementData[index] = element;  // 将指定元素添加到index位置上size = s + 1;  // 数组元素个数+1
}

System.arrayCopy是个本地方法，由cpp实现，调用的是jvm.cpp文件中的JVM_ArrayCopy
在这里插入图片描述
JVM_ArrayCopy源码实现（不再向下探究了，有兴趣的小伙伴可以自己去读jvm源码）

public boolean addAll(Collection<? extends E> c) 添加整个集合

// 源码
public boolean addAll(Collection<? extends E> c) {Object[] a = c.toArray();modCount++;int numNew = a.length;if (numNew == 0)   // 如果添加的集合为空是不允许添加的，即添加失败return false;Object[] elementData;final int s;// 如果添加集合的长度大于当前数组所剩空间，则进行扩容操作if (numNew > (elementData = this.elementData).length - (s = size))elementData = grow(s + numNew);System.arraycopy(a, 0, elementData, s, numNew); // 扩容后将需要添加的集合元素拷贝到新数组中size = s + numNew;  // 数组元素个数为原数组元素个数+新添加集合元素的个数return true;
}

public boolean addAll(int index, Collection<? extends E> c) 在指定索引位置添加集合

// 源码
public boolean addAll(int index, Collection<? extends E> c) {// 检查索引是否合法rangeCheckForAdd(index);Object[] a = c.toArray(); // 将集合c转换一个临时数组amodCount++;int numNew = a.length;   if (numNew == 0)   // 同样，不允许添加空集合return false;Object[] elementData;final int s;// 同上当添加集合的长度大于当前数组所剩空间，则进行扩容操作if (numNew > (elementData = this.elementData).length - (s = size))elementData = grow(s + numNew);int numMoved = s - index; // 计算需要移动的元素个数// 如果需要移动的元素个数大于0， 则将当前数组(扩容后)索引位置为index后的每个元素向后移动numNew个单位if (numMoved > 0)System.arraycopy(elementData, index,elementData, index + numNew,numMoved);// 拷贝添加的集合a到当前数组的index索引位置                     System.arraycopy(a, 0, elementData, index, numNew);size = s + numNew; // 当前数组元素个数 = 原数组个数 + 添加的集合元素个数return true;
}

查询数据(查)

public E get(int index) 获取指定索引位置的元素

// 源码
public E get(int index) {// 检查索引是否合法Objects.checkIndex(index, size);return elementData(index);  // 返回数组元素
}E elementData(int index) {return (E) elementData[index];
}

更新数据(改)

public E set(int index, E element) 更新指定索引位置的元素

public E set(int index, E element) {// 检查索引位置是否合法, 如果索引位置大于元素个数，则抛出数组越界异常Objects.checkIndex(index, size);E oldValue = elementData(index);elementData[index] = element; // 更新数组索引index的数据return oldValue; // 返回更新前的老数据
}public static <X extends RuntimeException>int checkIndex(int index, int length,BiFunction<String, List<Number>, X> oobef) {if (index < 0 || index >= length)throw outOfBoundsCheckIndex(oobef, index, length);return index;
}

删除数据(删)

public E remove(int index) 删除指定索引位置元素

// 源码
public E remove(int index) {// 检查索引位置是否合法Objects.checkIndex(index, size);// 申明一个不可变的临时数组final Object[] es = elementData;// 快速删除fastRemove(es, index);return oldValue; // 返回删除后的数据
}// 快速删除
private void fastRemove(Object[] es, int i) {modCount++;final int newSize;// 如果当前数组元素个数-1仍大于索引，则将当前数组索引位置index+1之后的元素拷贝到当前数组的index位置，拷贝元素个数为newSize - indexif ((newSize = size - 1) > i) System.arraycopy(es, i + 1, es, i, newSize - i);es[size = newSize] = null;  // 将最后索引位置置空// 简单理解就是index+1后的所有元素向前移动一位， 然后将数组最后一位置空
}

public boolean remove(Object o) 删除指定元素

// 源码
public boolean remove(Object o) {final Object[] es = elementData;final int size = this.size;int i = 0;found: {// 如果指定删除的对象为空，则查找数组中第一个为空的索引，然后调用fastRemove删除if (o == null) { for (; i < size; i++)if (es[i] == null)break found;} else {//  否则查找数组中第一个与目标值相等的索引位置，然后调用fastRemove删除for (; i < size; i++)if (o.equals(es[i]))break found;}return false;}fastRemove(es, i);return true;
}

public boolean removeAll(Collection<?> c) 删除指定集合(批量删除)

// 源码
public boolean removeAll(Collection<?> c) {return batchRemove(c, false, 0, size);
}
// 批量删除
boolean batchRemove(Collection<?> c, boolean complement, final int from, final int end) {Objects.requireNonNull(c); // 不允许删除空集合final Object[] es = elementData;int r;for (r = from;; r++) {if (r == end) return false; // 如果起始位置等于截止位置，则删除失败if (c.contains(es[r]) != complement) // 查找第一个匹配元素的索引位置break;}int w = r++;try {// 从r的位置截止到end为止，查找集合c中不包含的元素（即不需要删除的数据）for (Object e; r < end; r++)if (c.contains(e = es[r]) == complement)es[w++] = e; // 将r位置的元素赋值为不需要删除的元素e} catch (Throwable ex) {System.arraycopy(es, r, es, w, end - r);w += end - r;throw ex;} finally {modCount += end - w; // 计算修改的次数shiftTailOverGap(es, w, end); // 将删除元素的索引位置中置为空}return true;
}
//通过向下滑动下列元素，消除从低到高的间隙
private void shiftTailOverGap(Object[] es, int lo, int hi) {System.arraycopy(es, hi, es, lo, size - hi);for (int to = size, i = (size -= hi - lo); i < to; i++)es[i] = null;
}

10.public int indexOf(Object o) 获取元素的索引位置

// 源码
public int indexOf(Object o) {return indexOfRange(o, 0, size);
}
int indexOfRange(Object o, int start, int end) {Object[] es = elementData;// 如果查找元素为空，则返数组中第一个为空（如果有的话）的索引值if (o == null) {for (int i = start; i < end; i++) {if (es[i] == null) {return i;}}} else {// 否则返回数组中第一个与之匹配的索引值for (int i = start; i < end; i++) {if (o.equals(es[i])) {return i;}}}// 如果没有找到，返回-1return -1;
}

11.public int lastIndexOf(Object o) 获取元素最后出现的索引位置

//源码
public int lastIndexOf(Object o) {return lastIndexOfRange(o, 0, size);
}
int lastIndexOfRange(Object o, int start, int end) {Object[] es = elementData;// 如果查找元素为空if (o == null) {// 从数组尾部开始查找，返回第一个数组元素为空（如果有的话）的索引值for (int i = end - 1; i >= start; i--) {if (es[i] == null) {return i;}}} else {// 否则，从数组尾部开始查找，返回第一个与之匹配的元素的索引值for (int i = end - 1; i >= start; i--) {if (o.equals(es[i])) {return i;}}}// 如果没找到，则返回-1return -1;
}

11.private Object[] grow() 动态扩容函数

// 源码
private Object[] grow() {return grow(size + 1); // 最小容量为原数组长度+1
}private Object[] grow(int minCapacity) {int oldCapacity = elementData.length; //原数组长度// 如果原数组长度大于0 或 原数组非空if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {// 获取扩容后的数组长度int newCapacity = ArraysSupport.newLength(oldCapacity,minCapacity - oldCapacity, /* minimum growth */  // 扩容的最小长度oldCapacity >> 1           /* preferred growth */); // 扩容为原数组容量的2倍// 将原数组拷贝到扩容后的数组中        return elementData = Arrays.copyOf(elementData, newCapacity);} else {// 返回一个初始容量为指定扩容的容量与默认容量间最大值的数组return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];}
}// 获取扩容后的长度
public static int newLength(int oldLength, int minGrowth, int prefGrowth) {// preconditions not checked because of inlining// assert oldLength >= 0// assert minGrowth > 0// 预设长度为原数组容量 + 最小扩容容量与原数组容量的2倍之间的最大值（每次扩容为原来长度的2倍）int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow// 如果预设容量大于0 且小于等于Integer.MAX_VALUE - 8 则返回预设长度if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {return prefLength;} else {// 否则重置容量return hugeLength(oldLength, minGrowth);}
}private static int hugeLength(int oldLength, int minGrowth) {// 预设扩容后的容量为原数组长度 + minGrowth (指定的扩容长度)int minLength = oldLength + minGrowth;if (minLength < 0) { // overflowthrow new OutOfMemoryError("Required array length " + oldLength + " + " + minGrowth + " is too large");}// 如果指定的扩容长度小于等于Integer.MAX_VALUE - 8 ，返回 Integer.MAX_VALUE - 8else if (minLength <= SOFT_MAX_ARRAY_LENGTH) { return SOFT_MAX_ARRAY_LENGTH;} else {return minLength; // 否则返回预设扩容的容量（比Index.Max_VALUE还大）}
}//所以设置一个比较合适的初始化容量， 避免不断地扩容

12.public boolean contains(Object o) 判断集合中是否包含指定元素

// 源码
public boolean contains(Object o) {return indexOf(o) >= 0;
}

public void ensureCapacity(int minCapacity) 手动扩容

// 为什么有了自动扩容，还需要手动扩容呢， 因为当我们ArrayList未初始化时或初始化容量不太合适时，
// 此时有需要添加大量元素， ArrayList就会多次自动扩容， 这样非常影响效率，因此我们可以显示调用
// public void ensureCapacity(int minCapacity) 来避免频繁扩容， 提高效率public void ensureCapacity(int minCapacity) {// 如果指定的容量大于当前数组的长度且当前数组不为空并且指定的容量大于默认容量，此时进行扩容if (minCapacity > elementData.length&& !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA&& minCapacity <= DEFAULT_CAPACITY)) {modCount++;grow(minCapacity);}
}

示例：

       Object obj = new Object();ArrayList<Object> list1 = new ArrayList<>();long startTime = System.currentTimeMillis();for (int i = 0; i < 1000000; i++) {list1.add(obj); // 这种方式会在添加过程中多次扩容，效率较低}System.out.println(System.currentTimeMillis() - startTime);ArrayList<Object> list2 = new ArrayList<>();long startTime2 = System.currentTimeMillis();list2.ensureCapacity(1000000); // 显式设置容量，避免频繁扩容for (int i = 0; i < 1000000; i++) {list2.add(obj); // 这种方式效率更高，因为已经预分配了足够的空间}System.out.println(System.currentTimeMillis() - startTime2);

打印结果：
在这里插入图片描述
14.ArrayList转数组

// 源码 实际也是调用的数组拷贝
public Object[] toArray() {return Arrays.copyOf(elementData, size);
}
public <T> T[] toArray(T[] a) {if (a.length < size) return (T[]) Arrays.copyOf(elementData, size, a.getClass());System.arraycopy(elementData, 0, a, 0, size);if (a.length > size)a[size] = null;return a;
}