您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
ArrayList是Java集合框架中最常用的数据结构之一，它基于动态数组实现，提供了快速的随机访问能力。本文将深入分析ArrayList的源码，探讨其内部实现机制、常用方法、扩容机制、并发问题以及性能优化等方面的内容。
ArrayList是List接口的一个实现类，它允许存储重复的元素，并且元素的顺序是有序的。ArrayList内部使用一个数组来存储元素，因此它具有快速的随机访问能力。与LinkedList相比，ArrayList在随机访问和尾部插入操作上具有更好的性能，但在中间插入和删除操作上性能较差。
ArrayList的核心数据结构是一个Object类型的数组，用于存储元素。数组的长度会根据元素的增加或减少动态调整。ArrayList还维护了一个size变量，用于记录当前存储的元素数量。
transient Object[] elementData; // 存储元素的数组
private int size; // 当前存储的元素数量
ArrayList提供了多个构造方法，允许用户以不同的方式创建ArrayList实例。
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
无参构造方法创建一个初始容量为10的空ArrayList。实际上，初始时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的初始容量。如果指定的初始容量大于0，则创建一个指定大小的数组；如果初始容量为0，则创建一个空数组；如果初始容量为负数，则抛出IllegalArgumentException异常。
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
this.elementData = EMPTY_ELEMENTDATA;
}
}
该构造方法允许用户使用一个集合来初始化ArrayList。它将集合中的元素复制到elementData数组中，并设置size为集合的大小。
add方法用于向ArrayList中添加元素。ArrayList提供了多个add方法的重载版本，允许在指定位置插入元素或在尾部添加元素。
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 确保容量足够
elementData[size++] = e;
return true;
}
该方法首先调用ensureCapacityInternal方法确保elementData数组有足够的容量来存储新元素，然后将新元素添加到数组的末尾，并增加size的值。
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++;
}
该方法首先检查指定的索引是否合法，然后确保elementData数组有足够的容量来存储新元素。接着，它将index位置及其后面的元素向后移动一位，最后将新元素插入到index位置。
get方法用于获取指定位置的元素。
public E get(int index) {
rangeCheck(index); // 检查索引是否合法
return elementData(index);
}
该方法首先检查指定的索引是否合法，然后返回elementData数组中对应位置的元素。
set方法用于替换指定位置的元素。
public E set(int index, E element) {
rangeCheck(index); // 检查索引是否合法
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
该方法首先检查指定的索引是否合法，然后替换elementData数组中对应位置的元素，并返回被替换的旧元素。
remove方法用于删除指定位置的元素或删除指定的元素。
public E remove(int index) {
rangeCheck(index); // 检查索引是否合法
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
elementData[--size] = null; // 清除引用，帮助GC
return oldValue;
}
该方法首先检查指定的索引是否合法，然后删除elementData数组中对应位置的元素，并将后面的元素向前移动一位。最后，它将数组的最后一个元素设置为null，并返回被删除的元素。
public boolean remove(Object o) {
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;
}
该方法遍历elementData数组，查找与指定元素相等的元素。如果找到，则调用fastRemove方法删除该元素，并返回true；否则返回false。
size方法用于获取ArrayList中元素的数量。
public int size() {
return size;
}
该方法直接返回size变量的值。
isEmpty方法用于判断ArrayList是否为空。
public boolean isEmpty() {
return size == 0;
}
该方法通过判断size是否为0来确定ArrayList是否为空。
contains方法用于判断ArrayList是否包含指定的元素。
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
该方法通过调用indexOf方法来判断ArrayList是否包含指定的元素。
indexOf方法用于查找指定元素在ArrayList中第一次出现的位置。
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i] == null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
该方法遍历elementData数组，查找与指定元素相等的元素。如果找到，则返回该元素的索引；否则返回-1。
lastIndexOf方法用于查找指定元素在ArrayList中最后一次出现的位置。
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size - 1; i >= 0; i--)
if (elementData[i] == null)
return i;
} else {
for (int i = size - 1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
该方法从后向前遍历elementData数组，查找与指定元素相等的元素。如果找到，则返回该元素的索引；否则返回-1。
clear方法用于清空ArrayList中的所有元素。
public void clear() {
modCount++;
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
该方法遍历elementData数组，将所有元素设置为null，并将size设置为0。
toArray方法用于将ArrayList转换为数组。
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
该方法返回一个包含ArrayList中所有元素的新数组。
ArrayList的扩容机制是其核心特性之一。当ArrayList中的元素数量超过当前数组的容量时，ArrayList会自动扩容，以确保能够继续添加新元素。
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
该方法首先检查elementData数组是否为空数组。如果是，则将minCapacity设置为DEFAULT_CAPACITY（默认容量为10）和minCapacity中的较大值。然后调用ensureExplicitCapacity方法。
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
该方法首先增加modCount（用于记录ArrayList结构修改的次数），然后检查minCapacity是否大于当前数组的容量。如果是，则调用grow方法进行扩容。
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);
}
该方法首先计算新的容量newCapacity，通常为当前容量的1.5倍。如果newCapacity小于minCapacity，则将newCapacity设置为minCapacity。如果newCapacity超过MAX_ARRAY_SIZE（最大数组大小），则调用hugeCapacity方法处理。最后，使用Arrays.copyOf方法将elementData数组扩容到newCapacity。
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
该方法用于处理newCapacity超过MAX_ARRAY_SIZE的情况。如果minCapacity小于0，则抛出OutOfMemoryError异常；否则返回Integer.MAX_VALUE或MAX_ARRAY_SIZE。
ArrayList提供了Iterator和ListIterator两种迭代器，用于遍历ArrayList中的元素。
ArrayList的Iterator实现类为Itr，它提供了hasNext、next和remove方法。
private class Itr implements Iterator<E> {
int cursor; // 下一个元素的索引
int lastRet = -1; // 上一个返回的元素的索引
int expectedModCount = modCount;
public boolean hasNext() {
return cursor != size;
}
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
Itr类维护了cursor、lastRet和expectedModCount三个变量。cursor表示下一个元素的索引，lastRet表示上一个返回的元素的索引，expectedModCount用于检测并发修改。
ArrayList的ListIterator实现类为ListItr，它继承了Itr类，并提供了hasPrevious、previous、nextIndex、previousIndex、set和add方法。
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
super();
cursor = index;
}
public boolean hasPrevious() {
return cursor != 0;
}
public E previous() {
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[lastRet = i];
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor - 1;
}
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void add(E e) {
checkForComodification();
try {
int i = cursor;
ArrayList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}
ListItr类允许向前和向后遍历ArrayList，并支持在遍历过程中修改元素。
ArrayList是非线程安全的，因此在多线程环境下使用ArrayList可能会导致数据不一致或抛出ConcurrentModificationException异常。
ArrayList的迭代器在遍历过程中会检查modCount是否与expectedModCount相等。如果两者不相等，则抛出ConcurrentModificationException异常。
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
为了避免并发修改异常，可以使用以下方法：
使用Collections.synchronizedList方法：将ArrayList包装为线程安全的List。
List<String> synchronizedList = Collections.synchronizedList(new ArrayList<>());
使用CopyOnWriteArrayList：CopyOnWriteArrayList是ArrayList的线程安全版本，适用于读多写少的场景。
List<String> copyOnWriteArrayList = new CopyOnWriteArrayList<>();
使用显式锁：在多线程环境下，可以使用ReentrantLock或synchronized关键字来保护ArrayList的操作。
List<String> list = new ArrayList<>();
ReentrantLock lock = new ReentrantLock();
lock.lock();
try {
list.add("element");
} finally {
lock.unlock();
}
ArrayList的性能主要取决于其内部数组的操作。以下是ArrayList常见操作的时间复杂度：
O(1)，因为ArrayList基于数组实现，可以通过索引直接访问元素。O(1)，如果不需要扩容，则直接在数组末尾插入元素。O(n)，因为需要将插入位置及其后面的元素向后移动。O(1)，直接删除数组末尾的元素。O(n)，因为需要将删除位置后面的元素向前移动。O(n)，需要遍历数组查找指定元素。ArrayList和LinkedList都是List接口的实现类，但它们的内部实现和性能特点不同。
| 特性 | ArrayList | LinkedList |
|---|---|---|
| 内部实现 | 动态数组 | 双向链表 |
| 随机访问 | O(1) | O(n) |
| 尾部插入 | O(1) | O(1) |
| 中间插入 | O(n) | O(1) |
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。