ArrayList 一个动态数组。本身是基于数组进行封装的列表, 提供了自动扩容的功能: 在容量不够的情况下, 自动扩容。
同时支持存储包括 null 在内的所有数据类型。
1 数组 (Array)
了解 ArrayList 之前, 我们需要先了解一下数组的特点
- 数组的内存是连续的, 不存在相邻元素之间还隔着其他内存
- 数组内存储的数据类型都是一样的
- 数组具备了查询快, 增删慢的特点
- 数组在声明的时候需要知道初始的容量, 一个容量一旦确定了, 就不能再改变了
基于数组实现的 ArrayList, 同理也具备了相同的特性。
了解完 ArrayList 的特性, 下面进入到源码, 看看 ArrayList 的实现。
注: 本文是基于 Java 8 进行分析的。
2 ArrayList 中的几比较重要的属性
public class ArrayList<E>{
transient Object[] elementData;
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private int size;
}2.1 elementData
transient Object[] elementData; ArrayList 是基于 Array 实现的, 对 Array 做的封装。所以其本身还是通过 Array 进行数据的存储的。
而 elementData 就是真正存储数据的地方, 存到 ArrayList 的数据实际就是存在这里。
2.2 DEFAULT_CAPACITY
private static final int DEFAULT_CAPACITY = 10;一个 int 的整数, 表示 ArrayList 默认的初始容量大小。
数组在使用的时候需要提前声明容量, 基于数组实现的 ArrayList 也需要遵循这个规则。
所以在声明 ArrayList 时, 如果没有指定需要的容量大小, 默认是 10 进行声明容量的。
2.3 EMPTY_ELEMENTDATA
private static final Object[] EMPTY_ELEMENTDATA = {};一个静态的空数组变量。
在声明 ArrayList 时, 支持不显示声明容量大小, 则默认为 10。同样也可以手动声明大小, 声明了多少, 那么容量就是多少。
所以用户可以声明容量为 0, 那么 ArrayList 内部需要创建的数组就等于这个 elementData = EMPTY_ELEMENTDATA。
作用: 所有容量为 0 的情况, 都是这一个对象, 减少不必要的对象声明。
2.4 DEFAULTCAPACITY_EMPTY_ELEMENTDATA
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};在声明 ArrayList 时, 不指定容量的声明, 会先将 ArrayList 存储数据的 elementData 先赋值为这个空数组 elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA。
在真正进行数据存储时, 再进行扩容。
同样的, 声明为 static, 可以共用, 节省内存。
同时不在声明时, 就按照默认容量创建一个数组。可以防止声明了 ArrayList, 但是没用到的情况, 浪费内存。
2.5 size
当前 ArrayList 真正存储的数据个数。
3 ArrayList 的构造方法
public class ArrayList<E> {
// 构造函数 1: 不指定容量构造
public ArrayList() {
// 省略
}
// 构造函数 2: 指定容量构造
public ArrayList(int initialCapacity) {
// 省略
}
// 构造函数 3: 给定一个 Collection 的构造
public ArrayList(Collection<? extends E> c) {
// 省略
}
}3.1 不指定容量构造
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}很简单, 将空数组的 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 赋值给存储数据的 elementData。
延迟声明有容量的数组, 防止声明了, 但是没有使用的 ArrayList, 浪费空间。
同时先赋值为静态的 DEFAULTCAPACITY_EMPTY_ELEMENTDATA, 多个 ArrayList 可以共用这个, 节省内存。
3.2 指定容量构造
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);
}
}
- 指定的容量小于 0, 抛异常
- 指定的容量为 0, 将空数组 EMPTY_ELEMENTDATA 赋值给 elementData
- 指定的容量大于 0, 将 elementData 声明指定容量的数组
3.3 给定一个 Collection 的构造
public ArrayList(Collection<? extends E> c) {
// 调用 Collection 的方法, 获取内部存储数据的数组
Object[] a = c.toArray();
if ((size = a.length) != 0) {
if (c.getClass() == ArrayList.class) {
elementData = a;
} else {
elementData = Arrays.copyOf(a, size, Object[].class);
}
} else {
elementData = EMPTY_ELEMENTDATA;
}
}
- 传入的 Collection 的长度为 0, 将空数组 EMPTY_ELEMENTDATA 赋值给 elementData
- 传入的 Collection 的长度不等于 0, 将传入的 Collection 转为数组
- 传入的 Collection 为 ArrayList 类型, 将转换的数组赋值给 elmentData
- 传入的 Collection 不是 ArrayList 类型, 则需要将转换后的数组转换为 Object 数组, 在赋值给 elementData
上面 3, 4 步存在的原因是: Collection.toArray 方法在不同类的实现上有一些差异, 具体的分析可以看最后面的分析。
4 ArrayList 几个常用的方法
public class ArrayList<E> {
// 直接添加数据
public boolean add(E e) {
// 省略
}
// 指定位置, 添加数据
public void add(int index, E element) {
// 省略
}
// 添加一个集合 Collection 数据
public boolean addAll(Collection<? extends E> c) {
// 省略
}
// 指定位置, 添加一个集合 Collection 数据
public boolean addAll(int index, Collection<? extends E> c) {
// 省略
}
// 删除指定位置的数据
public E remove(int index) {
// 省略
}
// 删除指定的数据
public boolean remove(Object o) {
// 省略
}
// 获取指定位置的数据
public E get(int index) {
// 省略
}
}4.1 直接添加数据
public boolean add(E e) {
// 确保容量足够
// 容量够, 不做处理
// 容量不够, 动态的扩容
ensureCapacityInternal(size + 1);
// 放入到数组的最后一位
elementData[size++] = e;
return true;
}
/**
* 确保容量足够, 容量不够, 进行扩容
*
* @minCapacity 当前需要的最小容量
*/
private void ensureCapacityInternal(int minCapacity) {
// calculateCapacity 需要的容量
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
/**
* 计算一下当前 ArrayList 需要的容量
*/
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// DEFAULTCAPACITY_EMPTY_ELEMENTDATA: 前面声明的空数组 {}
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// DEFAULT_CAPACITY: 默认值 10
// 空数组, 创建时默认容量为 10, 但是上游可以指定它需要的最小容量, 2 者进行比较, 取大的
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 直接返回上游需要的最小容量
return minCapacity;
}
/**
* 确保当然数组的长度比需要的最小的容量大, 不够的话, 自动扩容
*/
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 需要的最少容量比当前的数组的容量大, 说明当前的数组容量不够了, 需要进行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* 数组容量扩容, 默认是当前容量的 1.5 倍
* 如果当前容量的 1.5 倍比需要的最小容量还小, 直接取最小容量
*/
private void grow(int minCapacity) {
// 扩容前的容量
int oldCapacity = elementData.length;
// oldCapacity >> 1 相当于 oldCapacity / (2 的一次方), 也就是 oldCapacity * 0.5
// 也就是 数组的扩容 = 原来的容量 * 1.5
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 计算出来的容量比需要的最小的容量还小, 则直接去最小的容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
// 计算出来的新的容量比 Integer 的最大值 - 8 还大
// 这一步主要是为了防止计算出来的容量超过了 Integer 的最大值
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 创建一个新的数组, 同时把当前的数组内容转移到新的数组
elementData = Arrays.copyOf(elementData, newCapacity);
}
/**
* 确保当前的容量不超过 Integer 的最大值
*/
private static int hugeCapacity(int minCapacity) {
// 小于 0, 超过了, 直接抛异常
if (minCapacity < 0)
throw new OutOfMemoryError();
// 容量 > Integer.MAX_VALUE - 8 的话, 直接返回 Integer 最大值, 否则返回 Integer.MAX_VALUE - 8
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}4.2 指定位置, 添加数据
public void add(int index, E element) {
// 判断一下 index 是否正常, index 不能大于 size, index 不能小于 0
rangeCheckForAdd(index);
// 走一遍判断扩容
ensureCapacityInternal(size + 1);
// 新建一个数组 数组的内容和当前的数据一样, 把 index 后面的数据都往后退一位, 然后 index 位置变为 null
System.arraycopy(elementData, index, elementData, index + 1, size - index);
// 设置 index 的元素为要插入的数据
elementData[index] = element;
size++;
}
/**
* 检测 index 是否符合要求
*/
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}指定位置的数据插入会导致数组数据的转移, 影响性能。
4.3 添加一个集合 Collection 数据
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
// 确保容量足够
ensureCapacityInternal(size + numNew);
// 新建一个新的数组, 拷贝原来数组和需要插入的 Collection 转换的数组到新数组
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}4.4 指定位置, 添加一个集合 Collection 数据
public boolean addAll(int index, Collection<? extends E> c) {
// 判断一下 index 是否正常, index 不能大于 size, index 不能小于 0
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
// 确保容量足够
ensureCapacityInternal(size + numNew);
// 计算需要移动的位置
int numMoved = size - index;
if (numMoved > 0)
// 新建一个数组, 将 elementData 从 index 后面的数据移动到 elementData 的 index + numNew 的后面
System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
// 将 a 移动到新数组的 index 和 index + numNex 之间
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}4.5 删除指定位置的数据
public E remove(int index) {
// 判断 index 是否合法
rangeCheck(index);
modCount++;
// 取到需要删除的元素
E oldValue = elementData(index);
// 删除的元素所在的位置后面还有多少个元素
int numMoved = size - index - 1;
if (numMoved > 0)
// 将 elementData index + 1 开始到 numMoved 个元素依次放到 elementData 的 index 处的后面
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
// 设置 site - 1 处的元素为空
elementData[--size] = null;
}
/**
* index 检查
*/
private void rangeCheck(int index) {
// index 不能大于 size
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* 获取需要删除的元素
*/
E elementData(int index) {
return (E) elementData[index];
}4.6 删除指定的元素
public boolean remove(Object o) {
// o 为 null, 则将 0 到 size - 1 之间第一个 null 删除
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++) {
// 调用 Object 的 equals 比较 2 个对象是否为同一个
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
}
return false;
}
/**
* 删除元素和 remove(int) 类似
*/
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
// 将 elementData index + 1 开始到 numMoved 个元素依次放到 elementData 的 index 处的后面
if (numMoved > 0)
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
// 设置 site - 1 处的元素为空
elementData[--size] = null;
}ArrayList 内部还提供了其他的删除元素方法
- removeAll(Collection<?> c): 删除当前 List 中在 Collection c 中有的元素
- removeRange(int fromIndex, int toIndex): 删除指定范围内的元素
- removeIf(Predicate<? super E> filter): 删除当前 List 中符合过滤条件的元素
4.7 获取数据
public E get(int index) {
// 检测 index 是否符合条件
rangeCheck(index);
// 通过索引获取元素, 直接就是 elementData[index]
return elementData(index);
}5 ArrayList 的补充
1. ArrayList 实现了 Serializable 接口, 那么支持序列化的, 但是数据是存放在 elementData 内, elementData 却被 transient (对象序列化时忽略) 修饰了
elementData 本质是一个数组, 使用数组是需要先定义长度, 所以可能存在 **elementData 的长度为 10, 存放的数据为 3 个, 7 个空的位置。
在序列化时, 将这几个没有的数据序列过去, 浪费了空间和浪费时间, 所以 ArrayList 将 elementData 设置为不用序列化的, 然后自身重写了序列化方法 writeObject 和 反序列化方法 readObject,
只把 elementData 内有效的数据序列化过去。
2. ArrayList 的 add, remove, clear 方法的调用, 可以看到有行代码 modCount++, modCount 的作用
这个变量是继承与父类 AbstractList 的, 这个变量记录的是: 当前 ArrayList 的修改次数。
作用: 用于支持 fail-fast 机制 (在遍历中, 发现数据被修改过了, 直接抛出异常)
ArrayList 内部自己实现了一个 Iterator (代码有省略), 通过 ArrayList.iterator() 获取到的就是这个实现类
private class Itr implements Iterator<E> {
int expectedModCount = modCount;
public E next() {
checkForComodification();
...
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}从代码我们可以知道
- Iterator 内部维护了一个 expectedModCount 他的值就是当前 ArrayList 内部数据修改过的次数 modCount
- 每次遍历时, 都会判断 expectedModCount 的值是否等于当前 modCount, 不等于直接抛异常, 不进行后续操作了
- 上面的场景很大概率出现在多线程上, 一个线程在遍历, 另一个线程对 ArrayList 进行了修改, modCount + 1 了, 从而使得 modCount != expectedModCount, 遍历的线程立即抛出异常
- modCount 在 AbstractList 只是被修饰为 transient 的, 没有用 volatile 修饰, 也就是存在一个线程修改了数据但是 modCount 没有及时写到内存中, 遍历线程还是能够继续执行。 所以 fail-fast 机制, 是一种错误检测机制。它只能被用来检测错误, 因为 JDK 并不保证 fail-fast 机制一定会发生
3. ArrayList 不是一个线程安全的集合
ArrayList 是线程不安全的, 如果需要保证线程的安全性, 可以考虑使用 CopyOWriteArrayList 或者使用 Collections.synchronizedList(Lise l) 函数返回一个线程安全的 ArrayList 类
4. ArrayList 实现了 RandomAccess 接口有什么用
首先 RandomAccess 的定义
public interface RandomAccess {
}从定义可以看到 RandomAccess 接口, 没有任何的东西需要我们实现, 它只做一种标识作用。
实现这个接口的类, 表示自身是支持 “随机访问” (如果有 10 个元素, 我们需要访问第 5 个, 就能直接跳到第 5 个进行访问, 忽略掉前面的 4 个元素, 还有一个顺序访问, 无论要访问第几个元素, 都需要从第一个元素开始, 一直往下找, 直到找到了需要的位置为止) 策略的 (官网还特意说明了, 如果是实现了这个接口的 List, 使用 for 循环的方式获取数据会优于用迭代器获取数据)。
官方使用例子:
public class Collections {
/**
* 二分查找
*/
public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) {
// list 支持随机访问或者当前的数据量 小于 5000
if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
// 可以到源码里面看一下这个方法, 内部是通过 white 进行遍历的
return Collections.indexedBinarySearch(list, key);
else
// 这个 是使用 迭代器遍历的
return Collections.iteratorBinarySearch(list, key);
}
}6 Collection.toArray()
可以先查看这里, 了解一下, Collection.toArray() 的问题。
下面做一个简单的整理。
6.1 对象向上转型
private static void test1() {
String str = "123";
Object obj = str;
Object obj2 = obj;
// class java.lang.String
System.out.println(str.getClass());
// class java.lang.String
System.out.println(obj.getClass());
// class java.lang.String
System.out.println(obj2.getClass());
Integer num = 1;
Number obj3 = num;
// class java.lang.Integer
System.out.println(num.getClass());
// class java.lang.Integer
System.out.println(obj3.getClass());
}从上面的代码, 可以发现通过向上转型, 虽然对象已经是转型后的类型了, 但是还是会保留了实际的类型。
6.2 对象为数组时, 向上转型
private static void test2() {
Object[] obj = new Object[2];
obj[0] = new String();
Object[] strObj = new String[2];
// class [Ljava.lang.Object;
System.out.println(obj.getClass());
// class [Ljava.lang.String;
System.out.println(strObj.getClass());
// class java.lang.String
System.out.println(obj[0].getClass());
}从上面的代码, 可以发现声明的数组是什么类型, 那么它的类型就是什么。
但是放入到内部的对象, 通过转型存到了数组里面, 但是它的实际类型还是没变的。
6.3 Collection.toArray()
private static void test3() {
List<String> list = new ArrayList<>();
list.add("123");
Object[] objArray = list.toArray();
List<String> list2 = Arrays.asList("123");
Object[] objArray2 = list2.toArray();
// class [Ljava.lang.Object;
System.out.println(objArray.getClass());
// class [Ljava.lang.String;
System.out.println(objArray2.getClass());
}在上面中通过 Collection.toArray() 方法得到的 2 个 Object[], 一个是类型的 Object 数组, 一个是类型是原来的类型的数组。同样的方法但是返回的 2 种不同的结果。
所以才有通过一个 Collection 创建 ArrayList, 才会判断一下 toArray 方法返回的数据的实际类型。
至于 Object[] toArray(); 返回的 Object[] 是不同的类型, 需要具体到不同的实现。
ArrayList 的 toArray()
public class ArrayList<E> {
// 调用到 Arrays.copyOf 方法
public Object[] toArray() {
// elementData.getClass 是 Object[] 类型, 所以通过 Array.copyOf 得到的为 Object[] 类型
return Arrays.copyOf(elementData, size);
}
}
public class Arrays {
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
}通过 Arrays 创建的 ArrayList 的 toArray()
public class Arrays {
public static <T> List<T> asList(T... a) {
// 通过 Arrays.asList 方法返回的是内部自行实现的 ArrayList
return new ArrayList<>(a);
}
private static class ArrayList<E> {
// 常用的 ArrayList 的数据是使用一个 Object[] elementData 进行保存的, 这里使用的是泛型数组存储
// 区别是 elementData.getClass 返回的是 Object[], 这里 a.getClass 返回的是实际数据的类型
private final E[] a;
ArrayList(E[] array) {
a = Objects.requireNonNull(array);
}
// 自行实现的 ArrayList, 内部不是调用自身的 copyOf 进行转换的, 而是通过 clone 方法
// 通过 clone() 返回结果的是 E[], 然后通过向上转型 (Object[])E[], 所以返回了 Object[], 但是保留了原本的类型。
public Object[] toArray() {
return a.clone();
}
}
}2 种不同的实现, 最终导致了不同的结果。
