面试官让我讲ArrayList中add、addAll方法的源码...我下次再来

前言

点赞在看，养成习惯。

点赞收藏，人生辉煌。

点击关注【微信搜索公众号：编程背锅侠】，防止迷路。

ArrayList中的添加方法总结

方法名	描述
public boolean add(E e)	将指定的元素追加到此列表的末尾。
public void add(int index, E element)	在此列表中的指定位置插入指定的元素。
public boolean addAll(Collection<? extends E> c)	按指定集合的Iterator返回的顺序将指定集合中的所有元素 追加到此列表的末尾。
public boolean addAll(i nt index, Collection<? extends E> c)	将指定集合中的所有元素插入到此列表中，从指定的位置 开始。

public boolean add(E e) 添加单个元素

案例演示

@Test
public void test_add(){
	ArrayList<String> list = new ArrayList<>();
	// 这个add是怎么执行的？带着这个疑问看一下add的源码，撸ta
	list.add("洛洛");
}

源码分析

// e 要添加到此列表的元素
public boolean add(E e) {
  // 调用方法对内部容量进行校验
  // 加入元素前检查容量是否够用，size是数组中数据的个数，因为要添加一个元素，所以size+1，先判断size+1的这个数组能否放得下，就在这个方法中去判断是否【数组.length】是否够用了。
	ensureCapacityInternal(size + 1);  // Increments modCount!!
  // 将指定的元素添加到数组的尾部
	elementData[size++] = e;
	return true;
}

// 计算容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
	// 判断集合存数据的数组是否等于空容量的数组
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    // 通过最小容量和默认容量 求出较大值 (用于第一次扩容)，首次添加元素会进入到这个方法
		return Math.max(DEFAULT_CAPACITY, minCapacity);
	}
  // 不为空数组的容量
	return minCapacity;
}

private void ensureCapacityInternal(int minCapacity) {
  // 将calculateCapacity方法中计算出来的容量传递给ensureExplicitCapacity方法,继续校验
	ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private void ensureExplicitCapacity(int minCapacity) {
  // 实际修改集合次数++ (在扩容的过程中没用,主要是用于迭代器中)
	modCount++;

	// 判断最小容量 - 数组长度是否大于 0
	if (minCapacity - elementData.length > 0)
    // 将第一次计算出来的容量传递给核心扩容方法,参考下面的grow方法源码分析
		grow(minCapacity);
}

底层数组elementData中元素变化图解

• 添加2个元素以后底层数组中的元素
  
• 添加第三个元素查看究竟是如何添加的？
  

总结

• 使用该方法的话将导致指定位置后面的数组元素全部重新移动，即往后移动一位
• 1）确保数插入的位置小于等于当前数组长度，并且不小于0，否则抛出异常
• 2）确保数组已使用长度（size）加1之后足够存下 下一个数据
• 3）修改次数（modCount）标识自增1，如果当前数组已使用长度（size）加1后的大于当前的数组长度，则调用grow方法，增长数组
• 4）grow方法会将当前数组的长度变为原来容量的1.5倍。
• 5）确保有足够的容量之后，使用System.arraycopy 将需要插入的位置（index）后面的元素统统往后移动一位。
• 6）将新的数据内容存放到数组的指定位置（index）上

public void add(int index, E element) 在指定索引处添加元素

案例演示

@Test
public void test_add_c(){
	ArrayList<String> list = new ArrayList<>();
	list.add("洛洛00");
	list.add("洛洛01");
	list.add(1, "洛洛05");
  // 执行上面的指定索引的插入方法以后这个打印结果将会如何呢？
	list.forEach(System.out::println);
}

源码分析

public void add(int index, E element) {
  // 添加范围检查
	rangeCheckForAdd(index);
  // 调用方法检验是否要扩容,且让增量++
	ensureCapacityInternal(size + 1);  // Increments modCount!!
  // 参数解析的源码在下面，可以找一下
  // 将指定位置以及后面的元素，复制到目标数组中
	System.arraycopy(elementData, index, elementData, index + 1,
			size - index);
  // 插入指定位置元素
	elementData[index] = element;
  // 长度加1
	size++;
}

// 检查这个index是否在给定的集合的长度的范围内
private void rangeCheckForAdd(int index) {
  // 给定的index大于集合的长度或者小于0，抛出空指针异常
	if (index > size || index < 0)
		throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

// 计算容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
	// 判断集合存数据的数组是否等于空容量的数组
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    // 通过最小容量和默认容量 求出较大值 (用于第一次扩容)
		return Math.max(DEFAULT_CAPACITY, minCapacity);
	}
  // 返回最小容量
	return minCapacity;
}

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

private void ensureExplicitCapacity(int minCapacity) {
  // 实际修改集合的次数
	modCount++;

	// 如果再调用 add(index,element) 方法之前已经扩容,那么源码跟踪到此结束不会进行扩容。
	if (minCapacity - elementData.length > 0)
		grow(minCapacity);
}

底层数组elementData中元素变化图解

• 指定位置添加元素前数组拷贝的准备
  
• 指定位置添加元素数组拷贝后的数组
  

结论

将指定的元素插入此列表中的指定位置，并将当前处于该位置的元素（如果有的话）和随后的任何元素向右移动（在其索引中增加一个）。

public boolean addAll(Collection<? extends E> c)` 将集合的所有元素一次性添加到集合

案例演示

@Test
public void test_addAll(){
	ArrayList<String> list = new ArrayList<>();
	// 这个add是怎么执行的？
	list.add("洛洛00");
	list.add("洛洛01");
	list.add("洛洛02");
	list.add("洛洛03");
	list.add("洛洛04");

	ArrayList<String> all = new ArrayList<>();
	all.add("洛洛06");
	all.addAll(list);
	all.forEach(System.out::println);
}

源码分析

public boolean addAll(Collection<? extends E> c) {
  // 把集合的元素转存到Object类型的数组中
	Object[] a = c.toArray();
  // 记录数组的长度
	int numNew = a.length;
  // 调用方法检验是否要扩容,且让增量++
	ensureCapacityInternal(size + numNew);  // Increments modCount
  // 调用方法将a数组的元素拷贝到elementData数组中
	System.arraycopy(a, 0, elementData, size, numNew);
  // 新集合的长度为a数组的长度加上集合的长度
	size += numNew;
  // 只要a数组【numNew】的长度不等于0,即说明添加成功
	return numNew != 0;
}

// 计算容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
	// 判断集合存数据的数组是否等于空容量的数组
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    // 通过最小容量和默认容量 求出较大值 (用于第一次扩容)
		return Math.max(DEFAULT_CAPACITY, minCapacity);
	}
  // 返回最小容量
	return minCapacity;
}

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

private void ensureExplicitCapacity(int minCapacity) {
  // 实际修改集合的次数
	modCount++;

	// 如果再调用 add(index,element) 方法之前已经扩容,那么源码跟踪到此结束不会进行扩容。
	if (minCapacity - elementData.length > 0)
		grow(minCapacity);
}

底层数组elementData中元素变化图解

• 添加前数组中的元素
  
• 添加后的数组中的元素
  

结论

该方法是将指定的集合添加到集合的尾部。

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

案例演示

@Test
public void test_addAll_c(){
	ArrayList<String> list = new ArrayList<>(2);
	// 这个add是怎么执行的？
	list.add("洛洛00");
	list.add("洛洛01");
	list.add("洛洛02");
	list.add("洛洛03");
	list.add("洛洛04");
	list.add("洛洛05");

	ArrayList<String> all = new ArrayList<>();
	all.add("洛洛06");
	all.add("洛洛07");
	all.add("洛洛08");
	all.addAll(1, list);
	all.forEach(System.out::println);
}

源码分析

// index：要添加的指定位置，c：要添加的指定集合
public boolean addAll(int index, Collection<? extends E> c) {
  // 校验索引
	rangeCheckForAdd(index);

  // 将给定的集合转换成数组
	Object[] a = c.toArray();
  // 指定集合转为数组后的长度
	int numNew = a.length;
  // 确定当前的容量是否能够满足【原集合的size+指定集合的长度】目的就是为了给集合存储数据的数组进行扩容
	ensureCapacityInternal(size + numNew);  // Increments modCount
  
  // 计算要移动元素的个数，也就是插入位置及以后元素的个数
	int numMoved = size - index;
  // 移动元素的个数大于0，就将要移动的元素复制到指定位置
	if (numMoved > 0)
    // 复制要移动的元素到指定的位置，这一步的操作在原始数组中，给要添加的数组也留下了位置
		System.arraycopy(elementData, index, elementData, index + numNew,
				numMoved);
  // 复制指定的集合转为的数组到原始数组中
	System.arraycopy(a, 0, elementData, index, numNew);
  // 添加后的集合的长度
	size += numNew;
	return numNew != 0;
}

// 检查这个index是否在给定的集合的长度的范围内
private void rangeCheckForAdd(int index) {
  // 给定的index大于集合的长度或者小于0，抛出空指针异常
	if (index > size || index < 0)
		throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

// 计算容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
	// 判断集合存数据的数组是否等于空容量的数组
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    // 通过最小容量和默认容量 求出较大值 (用于第一次扩容)
		return Math.max(DEFAULT_CAPACITY, minCapacity);
	}
  // 返回最小容量
	return minCapacity;
}

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

private void ensureExplicitCapacity(int minCapacity) {
  // 实际修改集合的次数
	modCount++;

	// 如果再调用 add(index,element) 方法之前已经扩容,那么源码跟踪到此结束不会进行扩容。
	if (minCapacity - elementData.length > 0)
		grow(minCapacity);
}

底层数组elementData中元素变化图解

指定位置添加数组前的准备

指定位置添加数组后新的数组

结论

该方法是在指定位置添加一个集合。通过上面的两张图里面的elementData数组中的元素变化我们可以很清晰的了解是怎样将元素在数组中添加集合的。

grow扩容方法

// 扩容方法增加容量以确保其至少可以容纳最小容量参数指定的元素数。 minCapacity：最小的容量
private void grow(int minCapacity) {
	// 记录数组的实际长度,此时由于没有存储元素,长度为0
	int oldCapacity = elementData.length;
  // oldCapacity >> 1右移一位，新的容量为旧的容量的1.5倍
	int newCapacity = oldCapacity + (oldCapacity >> 1);
  // 判断新容量 - 最小容量是否小于0, 如果是第一次调用add方法必然小于0
	if (newCapacity - minCapacity < 0)
    // 将最小容量赋值给新容量，就是在这里首次添加的时候将容量搞为10的
		newCapacity = minCapacity;
  // 判断新容量-最大数组大小是否>0,如果条件满足就计算出一个超大容量
	if (newCapacity - MAX_ARRAY_SIZE > 0)
    // 计算出一个超大容量，并赋值给新的容量
		newCapacity = hugeCapacity(minCapacity);
	// 调用数组工具类方法,创建一个新数组,将新数组的地址赋值给elementData参看下方的Arrays.copyOf方法源码分析
	elementData = Arrays.copyOf(elementData, newCapacity);
}

hugeCapacity方法

private static int hugeCapacity(int minCapacity) 
  // 最小容量小于0抛OutOfMemoryError异常
	if (minCapacity < 0) // overflow
		throw new OutOfMemoryError();
// 返回超大容量  
	return (minCapacity > MAX_ARRAY_SIZE) ?
			Integer.MAX_VALUE :
			MAX_ARRAY_SIZE;
}

Arrays.copyOf方法

ArrayList.toArray()方法及其实现源码

// ArrayList<E>中的toArray()方法
public Object[] toArray() {
  // 调用数组工具类方法进行拷贝
	return Arrays.copyOf(elementData, size);
}

Arrays.copyOf()方法源码

// Arrays类中的copyOf方法进行数组的拷贝。original原始的数组，newLength新的容量
public static <T> T[] copyOf(T[] original, int newLength) {
  // 再次调用方法进行拷贝
	return (T[]) copyOf(original, newLength, original.getClass());
}

// 将原始的数组copy到新的容量的数组中的具体实现
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
	@SuppressWarnings("unchecked")
  // 用三元运算符进行判断,不管结果如何都是创建一个新数组
	T[] copy = ((Object)newType == (Object)Object[].class)
			? (T[]) new Object[newLength]
			: (T[]) Array.newInstance(newType.getComponentType(), newLength);
	// 将数组的内容拷贝到 copy 该数组中，使用System.arraycopy 将需要插入的位置（index）后面的元素统统往后移动一位
  System.arraycopy(original, 0, copy, 0,
			Math.min(original.length, newLength));
  // 返回拷贝元素成功后的数组
	return copy;
}

arraycopy方法

/*
* @param      src      the source array.原始的数组
* @param      srcPos   starting position in the source array.在原始数组中开始的位置
* @param      dest     the destination array.目标数组
* @param      destPos  starting position in the destination data.在目标数组中的起始位置
* @param      length   the number of array elements to be copied.要copy的元素的个数
*/
public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);

针对上面的方法案例分析

• 不指定位置

arraycopy执行后添加到尾部

• 指定位置

arraycopy执行后拷贝的是插入位置后的元素，拷贝到目标数组，操作的还是一个数组

JDK`版本

源码以及案例演示都是在jdk1.8环境下。