Java ArrayList源码深度解析：揭秘数组背后的秘密
在Java编程中，ArrayList是一个非常常用的数据结构，它基于数组实现，提供了动态数组的功能。熟练掌握ArrayList的使用，对于提高编程效率至关重要。本文将从源码的角度，深入解析Java ArrayList的实现原理，帮助读者更好地理解这个常用数据结构。
一、ArrayList的基本概念
ArrayList是Java集合框架中的一个可调整大小的数组实现。它允许用户使用数组的方式操作元素，同时提供了动态扩容的功能。ArrayList的底层是基于数组实现的，因此它具有数组的特点，如随机访问速度快，但插入和删除操作相对较慢。
二、ArrayList的构造方法
在ArrayList的源码中，我们可以看到以下几个构造方法：
1. 无参构造方法
```java
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
```
无参构造方法创建了一个空的ArrayList实例，其底层数组容量为10。
2. 带参数的构造方法
```java
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的初始容量。如果用户指定的容量大于0，则创建一个指定容量的数组；如果用户指定的容量为0，则创建一个空的数组；如果用户指定的容量小于0，则抛出异常。
3. 带集合参数的构造方法
```java
public ArrayList(Collection c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray() might (incorrectly) not include the last element of c, so
// we must explicitly adjust size if it appears to be missing
if (elementData[size - 1] == null) {
size--;
}
}
}
```
带集合参数的构造方法允许用户将一个集合转换为ArrayList。首先，使用集合的toArray()方法将集合中的元素复制到一个数组中，然后创建一个ArrayList实例，并将这个数组作为底层数组。
三、ArrayList的扩容机制
ArrayList的扩容机制是其核心特性之一。当向ArrayList中添加元素时，如果数组已满，则需要扩容。以下是ArrayList扩容的源码：
```java
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
```
1. 计算新的数组容量：先计算旧数组的容量，然后将其增加50%（即oldCapacity >> 1），以确保数组有足够的容量。
2. 检查新的数组容量是否满足最小容量要求：如果新的数组容量小于最小容量，则将新的数组容量设置为最小容量。
3. 检查新的数组容量是否超出最大数组容量：如果新的数组容量大于最大数组容量，则调用hugeCapacity()方法计算新的数组容量。
4. 使用Arrays.copyOf()方法复制旧数组到新的数组中。
四、ArrayList的插入、删除和查找操作
1. 插入操作
```java
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1);
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
```
插入操作首先检查索引是否有效，然后确保数组有足够的容量。接着，使用System.arraycopy()方法将索引位置及之后的元素向后移动一位，最后将新元素插入到指定位置。
2. 删除操作
```java
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index + 1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
```
删除操作首先检查索引是否有效，然后获取要删除的元素。接着，使用System.arraycopy()方法将索引位置之后的元素向前移动一位，最后将数组最后一个元素设置为null，以便GC回收。
3. 查找操作
```java
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
```
查找操作非常简单，只需检查索引是否有效，然后直接返回索引位置的元素。
五、总结
本文从源码的角度深入解析了Java ArrayList的实现原理，包括构造方法、扩容机制、插入、删除和查找操作。通过阅读本文，读者可以更好地理解ArrayList的工作原理，从而在编程实践中更加灵活地使用这个常用数据结构。
