竟然还有人说 ArrayList 是 2 倍扩容,今天带你手撕 ArrayList 源码
作者:一灯架构
- 2022 年 10 月 06 日 北京
本文字数:3214 字
阅读完需:约 11 分钟
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 的源码。
划线
评论
复制
发布于: 刚刚阅读数: 2
一灯架构
关注
还未添加个人签名 2020.11.20 加入
还未添加个人简介
评论