ArrayList
一、继承体系
ArrayList继承自AbstractList,AbstractList实现了List接口的部分方法,为List的具体实现类提供了方便。AbstractList是一个抽象类,它实现了Collection接口,也就间接实现了Iterable接口。
二、接口继承
List接口继承自Collection接口,Collection继承自Iterable接口。List接口代表有序的队列
三、标记接口
RandomAccess是一个标记接口,标识ArrayList支持快速随机访问,可以通过索引直接访问元素。Cloneable和Serializable也是标记接口,前者表示可复制克隆,后者表示可序列化。
四、设计目的
- Java 集合框架的设计目的是为了更好地对集合数据进行操作,统一了访问方式,增强了代码的可读性、简洁性和可扩展性。
- 使用接口和抽象类来定义规范,然后由具体实现类来实现不同的数据结构和算法。
- 标记接口则用来对类型进行标记和区分,以便采取不同的算法和优化。
五、框架总体结构
- 最顶层是
Collection接口,定义了集合的基本操作。 - 然后分为
List、Set、Queue等子接口,分别定义了有序、无序、队列等特性。 - 再通过
AbstractList、AbstractSet等抽象类为子接口提供部分方法实现。 - 最后是具体的实现类,如
ArrayList、LinkedList、HashMap等。
六、工作原理
ArrayList 底层是通过动态数组(可自动扩容)实现的,它的工作原理如下:
- 初始化时,为一个初始容量为0的数组
- 当添加元素时,容量不够则自动扩容(默认扩容为原来的1.5倍)
- 插入和访问元素通过索引直接操作数组,性能较高
- 删除元素需要移动其他元素以保证连续存储
- 由于自动扩容,在末尾插入元素效率很高,但在中间位置插入效率较低
ArrayList 的源码注释如下:
/**
* 默认初始容量为 10
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 用于储存元素的数组缓冲区
*/
transient Object[] elementData;
/**
* ArrayList 中元素的数量
*/
private int size;
// 其他方法...
可以看出，ArrayList 内部通过一个 Object 数组存储元素,size 变量记录当前元素数量,通过自动扩容机制来支持动态增长。这种基于动态数组的实现,决定了 ArrayList 查询快、增删慢的特点。
七、创建List对象初始化？还是add()添加元素初始化?
在 Java JDK 1.8 中,ArrayList 的默认初始容量 10 是在第一次通过无参构造函数创建 ArrayList 对象时初始化的,而不是在添加第一个元素时初始化。
ArrayList 有三种构造方式:
ArrayList()/** * 构造一个初始容量为10的空列表 */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }使用无参构造函数时,底层会初始化一个初始容量为 10 的空数组
DEFAULTCAPACITY_EMPTY_ELEMENTDATA。ArrayList(int initialCapacity)/** * 构造一个具有指定初始容量的空列表 */ 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(Collection<? extends E> c)/** * 构造一个包含指定collection的元素的列表,按迭代器返回元素的顺序 */ public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) != 0) { // c.toArray可能(错误地)不同时使用Object[]... if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // 使用空数组替换以允许缓冲区进行正常增长 this.elementData = EMPTY_ELEMENTDATA; } }使用这个构造函数会根据提供的集合的大小创建底层数组。
使用无参构造函数 ArrayList() 时,底层数组的初始容量才会被初始化为 10。其他两种构造函数要么根据用户指定的容量初始化,要么根据提供的集合大小初始化。而添加元素时则不会再初始化容量,只是在容量不足时按照需求扩容。
七、add(E e)添加元素
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
ensureCapacityInternal(size + 1): 这一行代码调用了ensureCapacityInternal方法，它用于确保ArrayList内部数组的容量足够来存放新增的元素。如果需要增加ArrayList的容量，它会创建一个新的更大的数组，并将原来的元素复制到新数组中。elementData[size++] = e;: 这一行代码将新的元素e添加到ArrayList的内部数组elementData中，并且将size变量递增，表示列表中的元素数量增加了一个。这里使用size++是因为要先将元素添加到size所指示的位置，然后再递增size，以便下次添加元素时能够添加到正确的位置。return true;: 最后，方法返回true，表示添加操作成功。
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
这段代码是ArrayList中的ensureCapacityInternal(int minCapacity)方法的部分源码
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {: 这一行代码用于检查elementData是否是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，该常量表示一个空数组。如果是空数组，说明当前ArrayList没有初始化容量，需要根据默认容量和需要添加的最小容量来确定实际容量。minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);: 如果elementData是空数组，则会根据默认容量DEFAULT_CAPACITY和需要添加的最小容量来确定实际的最小容量。DEFAULT_CAPACITY是ArrayList默认的初始容量大小。ensureExplicitCapacity(minCapacity);: 接下来调用ensureExplicitCapacity(minCapacity)方法来确保ArrayList的内部数组容量能够容纳至少minCapacity个元素。这个方法会比较当前数组的容量和需要的最小容量，如果当前容量不足，则会扩大内部数组的容量以满足需求。
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
-这段代码是ArrayList中的ensureExplicitCapacity(int minCapacity)方法的部分源码
modCount++;: 这一行代码递增了modCount变量的值。modCount用于记录结构修改次数，主要用于在迭代过程中检测并发修改。每当进行结构性修改时（如添加或移除元素），modCount会递增，表示ArrayList的结构发生了变化。if (minCapacity - elementData.length > 0) grow(minCapacity);: 这里使用了溢出安全的计算方式来判断是否需要扩容内部数组。如果当前容量不足以容纳最小容量minCapacity个元素，则需要调用grow(minCapacity)方法来扩大内部数组的容量。grow(int minCapacity): 当需要扩容时，会调用grow(int 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);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
这段代码是ArrayList中的grow(int minCapacity)方法的部分源码
int oldCapacity = elementData.length;: 获取当前内部数组的容量，即原来的容量大小。int newCapacity = oldCapacity + (oldCapacity >> 1);: 原来的容量大小计算出新的容量大小。新的容量大小会是原来容量的1.5倍，通过右移一位实现了除以2的操作。原来容量大小 + 容量大小的一半if (newCapacity - minCapacity < 0) newCapacity = minCapacity;: 如果新的容量仍然小于需要的最小容量minCapacity，则将新的容量调整为minCapacity，确保容量能够满足需求。if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity);: 检查新的容量是否超出了最大数组大小MAX_ARRAY_SIZE，如果超出则调用hugeCapacity()方法来确定合适的容量大小，这是为了避免数组大小超出Java虚拟机的限制。elementData = Arrays.copyOf(elementData, newCapacity);: 最后，使用Arrays.copyOf()方法将原来的元素复制到新的更大的数组中，完成了内部数组的扩容过程。
grow()方法主要负责处理ArrayList内部数组的扩容问题。它会根据旧的容量大小计算出新的容量大小，并根据需要调整为满足最小容量要求的合适大小。然后将原来的元素复制到新的更大的数组中，完成数组的扩容操作。这样可以确保在需要添加大量元素时，ArrayList内部数组能够容纳足够多的元素。
八、remove（int index）删除元素
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;
}
这段代码是ArrayList中的remove(int index)方法的部分源码
rangeCheck(index): 这一行代码调用了rangeCheck方法来检查索引是否越界，确保要移除的元素在有效范围内。如果索引不在有效范围内，会抛出IndexOutOfBoundsException。modCount++: 这里递增了modCount变量的值。modCount用于记录结构修改次数，主要用于在迭代过程中检测并发修改。每当进行结构性修改时（如添加或移除元素），modCount会递增，表示ArrayList的结构发生了变化。E oldValue = elementData(index): 这一行代码获取要移除的元素，并将其保存为oldValue。int numMoved = size - index - 1;: 计算需要向前移动的元素个数，即原始数组中位于被删除元素后面的元素个数。System.arraycopy(elementData, index+1, elementData, index, numMoved): 如果存在需要向前移动的元素，则使用System.arraycopy方法将这些元素向前移动，以填补被删除元素的位置。elementData[--size] = null: 将列表中最后一个元素置空，以便让GC进行清理工作。返回
oldValue：返回被删除的元素的值。
通过以上步骤，remove()方法实现了在指定位置上删除元素的功能。它首先进行了参数的合法性检查，然后递增了modCount，接着移动需要向前移动的元素，将列表中最后一个元素置空，并返回被删除的元素的值。
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;
}
这段代码是ArrayList中的remove(Object o)方法的部分源码
如果传入的对象
o为空（null）：- 通过 for 循环遍历
elementData数组，寻找为 null 的元素。 - 当找到第一个为 null 的元素后，调用
fastRemove(index)方法进行删除，并返回 true。
- 通过 for 循环遍历
如果传入的对象
o不为空（non-null）：- 通过 for 循环遍历
elementData数组，寻找与传入对象相等的元素。 - 当找到第一个与传入对象相等的元素后，调用
fastRemove(index)方法进行删除，并返回 true。
- 通过 for 循环遍历
如果未找到符合条件的元素，则直接返回 false。
fastRemove(index) 方法用于快速删除指定索引位置的元素。通过这种方式，remove(Object o) 方法能够在列表中移除满足特定条件的第一个元素，并返回是否成功移除的布尔值。
八、线程安全问题
ArrayList存在线程安全问题的本质在于其内部的elementData、size和modCount等变量，在进行各种操作时没有加锁，并且这些变量的类型也不是volatile的。因此，如果多个线程对这些变量进行操作，则可能出现值被覆盖的情况。需要强调的是，只有当ArrayList作为共享变量时，才会出现线程安全问题；当ArrayList是方法内的局部变量时，则不存在线程安全问题。
