【Java集合】系列一：详解ArrayList的底层原理（本篇源码基于Java11）

引言

ArrayList集合类在面试、开发中饱受关注，用起来也是真香。本篇文章有针对性的归纳整理ArrayList的常见问题，如有遗漏，欢迎留言或评论。

面试开始

小伙子，说下ArrayList的底层数据结构吧？

ArrayList的底层数据结构就是一个数组，数组元素的类型为Object类型，对ArrayList的所有操作底层都是基于该数组的。

程序清单1： ArrayList的底层数组

transient Object[] elementData;

由源码可以看出，底层是个Object类型的数组，并且是用关键字transient修饰的，表示数组不可被序列化。

那结合刚刚说的底层数组实现说下ArrayList有哪些优缺点？

• ArrayList的优点

1. ArrayList底层以数组实现，是一种随机访问模式，再加上它实现了RandomAccess接口，因此查找也就是get的时候非常快。
2. ArrayList在顺序添加一个元素的时候非常方便，只是往数组里面添加了一个元素而已。
3. 根据下标遍历、访问元素，效率高。
4. 可以自动扩容，默认为每次扩容为原来的1.5倍。

• ArrayList的缺点

1. 插入和删除元素的效率较低。
2. 根据元素下标查找元素需要遍历整个元素数组，效率不高。
3. 线程不安全。

好，刚刚你有提到扩容，可以说下ArrayList的扩容机制吗？

主要从构造函数和add()方法扩容两个层面进行分析。

程序清单2： ArrayList的构造函数源码

private static final Object[] DEFAULTCAPACITY_EMPTY_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);
}
}

由上述源码可发现，当用无参构造初始化ArrayList时，默认初始化为一个空的数组。

程序清单3： ArrayList的扩容源码

public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}
private Object[] grow() {
return grow(size + 1);
}
/* 扩容代码 */
private Object[] grow(int minCapacity) {
/* 集合扩容完成后，需要将旧集合中的元素全部复制到新集合中 */
return elementData = Arrays.copyOf(elementData,
newCapacity(minCapacity));
}
/* 新的容量 */
private int newCapacity(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
/* 扩容为1.5倍 */
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity <= 0) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
/* 返回默认大小（10）和扩容后的大小的最大值 */
return Math.max(DEFAULT_CAPACITY, minCapacity);
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return minCapacity;
}
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? newCapacity
: hugeCapacity(minCapacity);
}

由上述源码可发现，当添加元素时每次都会校验数组大小。当初始化一个空的集合时，第一次add元素时集合的大小会被初始化为10。然后随着集合元素不断增加，当第11个元素插入时，这个时候集合需要扩容，扩容后的容量就是10+10>>1=15。扩容完成后，需要将员集合的元素复制到新的集合中。

注意：根据以上源码分析可以知道，ArrayList每次扩容都会在堆内存里开辟一个新的集合空间，将旧的集合中的所有元素都拷贝到新的集合中，旧的集合等待JVM回收。实际上这种不断复制需要内存和时间开销，所以最好在ArrayList初始化的时候就指定容量，并尽量保证之后不会扩容。

ArrayList是线程安全的么？为什么？

ArrayList是线程不安全的。体现在add()方法和迭代器里，具体的这里将结合源码说明。

来呀，先给国师上源码：

程序清单4： ArrayList的add()源码

public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}

注意看modCount++（该成员变量记录着ArrayList的修改次数）这里，我们知道自增、自减操作都是非原子操作，并发条件下必然有安全性问题。

add(e, elementData, size)这个方法的作用就是将当前的新元素加到列表后面，ArrayList底层数组的大小是否满足，如果size 长度等于底层数组的长度，那么就要对这个数组进行扩容。注意看，这个方法是没有任何的线程安全性保障的，假设现在ArrayList只剩一个元素可以添加了，此时线程1判断无需扩容进行正常添加操作；当添加尚未完成时，线程2也进入到这里，进行判断，也是返回还剩一个元素可以添加（但实际上这个位置已经被线程1占用了），此时线程2操作会报数组越界异常:ArrayIndexOutOfBoundsException。

程序清单5： ArrayList的迭代器源码

public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
SubList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = root.modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (root.modCount != expectedModCount)
throw new ConcurrentModificationException();
}

注意看checkForComodification()方法的实现，会对ArrayList的modCount参数（该成员变量记录着ArrayList的修改次数）进行判断，如果实际修改次数和预期修改次数expectedModCount不一致（并发条件下会出现），则会抛出并发修改异常ConcurrentModificationException。

怎样让ArrayList成为线程安全的呢？

有两种方案：

1. 使用synchronized关键字
2. 创建ArrayList对象的时候采用Collections类中的静态方法synchronizedList(new ArrayList<>())

ArrayList、Vector和LinkedList的区别？

面试结束

好的，小伙子表现不错，对ArrayList的掌握较好，下轮面试再见！悄悄给你透露一下哦，下一轮面试官喜欢考察HashSet，回去好好备战!

好嘞，谢谢面试官的提醒，下一回合我也会再接再厉。

最后

以上就是欣喜火龙果为你收集整理的【Java集合】系列一：详解ArrayList的底层原理（本篇源码基于Java11）的全部内容，希望文章能够帮你解决【Java集合】系列一：详解ArrayList的底层原理（本篇源码基于Java11）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。