如何理解Java容器中ArrayList的源码解析

发布时间：2023-04-25 12:45:59 所属栏目：教程来源：

导读：这篇文章给大家介绍如何理解Java容器中List的源码分析，内容非常详细，感兴趣的小伙伴们可以参考借鉴，希望对大家能有所帮助。

如果没有特别说明，以下这些源码说明了分析基于 JDK 系统的1.8。

1. 概览

实现

这篇文章给大家介绍如何理解Java容器中List的源码分析，内容非常详细，感兴趣的小伙伴们可以参考借鉴，希望对大家能有所帮助。

如果没有特别说明，以下这些源码说明了分析基于 JDK 系统的1.8。

1. 概览

实现了 RandomAccess 接口，因此支持随机访问。这在我看来是非常理所当然的，因为 ArrayList 实际上是基于相对应的数组描述符实现的。

public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
数组的默认大小为 10。

private static final int DEFAULT_CAPACITY = 10;
2. 扩容

添加元素时使用 ensureCapacityInternal() 方法来保证容量足够，如果不够时，需要使用 grow() 方法进行扩容，新容量的大小为 oldCapacity + (oldCapacity >> 1)，也就是旧容量的 1.5 倍。

扩容操作需要调用 Arrays.copyOf() 把原数组整个复制到新数组中，这个操作代价很高，因此,创建一个数据集列表对象时,要确保指定用户一个大致固定不变的容量,这样就从根本上减少了不必要的扩充数据库操作的次数。

public boolean add(E e) {
//添加元素时使用 ensureCapacityInternal() 方法来保证容量足够，
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscIoUs code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// grow() 方法进行扩容
private void grow(int minCapacity) {
// overflow-conscIoUs code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
//这个操作代价很高，因此最好在创建 ArrayList 对象时就指定大概的容量大小，减少扩容操作的次数。
elementData = Arrays.copyOf(elementData, newCapacity);
}
3. 删除元素

需要调用 System.arraycopy() 将 index+1 后面的元素都向左移动一位，该操作的时间复杂度为 O(N)，可以看出 ArrayList 删除元素的代价是非常高的。

public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
//index+1 后面的元素都向左移动一位即index+1位置的后面元素个数 (size-1)-(index+1)+1
int numMoved = size - index - 1;
if (numMoved > 0)
//将 index+1后面的元素都向左移动一位，原来的（index+1）位置元素就移到 index位置
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
4. fail-fast

modCount 用来记录 ArrayList 结构发生变化的次数。结构发生变化是指添加或者删除至少一个元素的所有操作，或者是调整内部数组的大小，仅仅只是设置元素的值不算结构发生变化。

在无法进行高效的序列化或者迭代等操作实施例时，需要比较操作前后 modCount 是否改变，如果改变了需要抛出 ConcurrentModificationException。

private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
//这里记录操作前的 modCount
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavIoUral compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);//操作
}
//这里的modCount是操作后的 modCount与之前的作比较
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
5. 序列化

ArrayList 基于数组实现，并且具有动态扩容特性，因此保存元素的数组不一定都会被使用，那么就没必要全部进行序列化。

保存元素的数组 elementData 使用 transient 修饰，该关键字声明数组默认不会被序列化。

transient Object[] elementData; // non-private to simplify nested class access
ArrayList 实现了 writeObject() 和 readobject() 来只序列化数组中有元素填充那部分内容。

序列化时需要使用 ObjectOutputStream 的 writeObject() 将对象转换为字节流并输出。

private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavIoUral compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
// 使用 ObjectOutputStream 的 writeObject() 将对象转换为字节流并输出。
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}

（编辑：汽车网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!