一、简介
这篇文章主要介绍一下ArrayList的相关细节，它的底层是基于数组实现的，数组是在内存中划分出一块连续的地址空间用来进行元素的存储，它存在一个致命的缺陷，就是在初始化时必须要指定大小，并且不能改变，而ArrayList则解决了这个问题，实现了一个动态的数组（自动扩容机制），与此同时，它也具备了数组的一些特性：查询快，增删慢。下面我们来看一下类图：
ArrayList继承结构
- Serializable接口：类实现此接口以启用其序列化功能。可序列化类的所有子类型本身都是可序列化的。序列化接口没有方法或字段，仅用于标识可序列化的语义。
- Cloneable接口：类实现了 Cloneable 接口，以指示Object.clone()方法可以合法地对该类实例进行按字段复制。按照惯例，实现此接口的类应该使用公共方法重写 Object.clone（它是受保护的）。
- List接口：定义了一个有序、可重复的集合（也称序列）。
- RandomAccess：用来表明其支持快速（通常是固定时间）随机访问。此接口的主要目的是允许一般的算法更改其行为，从而在将其应用到随机或连续访问列表时能提供良好的性能。
二、底层实现
先来看一下它的几个字段，可以发现它的内部维护了一个Object数组用于存储元素，也就是说它可以存储任何类型的元素（最好使用泛型约束存储的类型），当创建一个新的实例时，可以指定初始大小，若不指定则不会分配内存空间而是使用空的对象数组，在添加第一个元素时再进行内存分配。
//默认初始容量
private static final int DEFAULT_CAPACITY = 10;
//空对象数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//默认容量空对象数组（即添加第一个元素时会自动扩容至默认容量）
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//存储ArrayList的元素，它的大小即size大小
transient Object[] elementData;
//此集合的大小（即集合中元素的数量）
private int size;
//集合最大长度，若依然不够会进一步扩容到Integer.MAX_VALUE
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
接下来我们再来看一下它的增删改查方法，emmm。。。基于数组的操作，也没什么可写的。
//在末尾增加一个元素
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
//在指定位置增加一个元素
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++;
}
//移除此列表中首次出现的指定元素（如果存在）。
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;
}
//用指定的元素替代此列表中指定位置上的元素。
public E set(int index, E element) {
//下标合法性检查
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
//获得指定位置元素
public E get(int index) {
//下标合法性检查
rangeCheck(index);
return elementData(index);
}
扩容机制及本人的思考
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
//扩容为原长度的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//扩容后的长度若大于MAX_ARRAY_SIZE，进一步扩容到Integer.MAX_VALUE
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
从源码中可以看到，ArrayList的最大长度为Integer.MAX_VALUE - 8，而数组对象相比标准java对象多了一个用于存储大小的元数据，即 2^31 -8 (for storing size )，若试图分配更大空间可能会导致OutOfMemoryError，下面贴出源码注释：
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
虽然注释上是这么说的，但是仔细看源码还有这么一行：
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
当MAX_ARRAY_SIZE长度的集合也不足够的时候，则会扩容至Integer.MAX_VALUE，那么问题来了，这样操作占用了本用来存储header words的空间，按注释所言可能会报OutOfMemoryError，那这里又是如何处理的呢？？？
三、总结
又到了文章的最后，我们来总结一下ArrayList的特点：
- 增删慢，查询快（增删会导致后续数据移位）
- 不是线程安全的
- 默认初始容量为10，每次扩容为原大小的1.5倍，在初始化时需要指定合适大小，避免频繁扩容导致的性能损耗
- 最大大小为Integer.MAX_VALUE
网友评论