一、概述
在实际工作中我们使用最多的集合恐怕就是 ArrayList 了,但是这个集合类该怎么用呢,借此我们通过阅读它的源码来一探究竟
二、ArrayList 成员变量介绍
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
// 8683452581122892189L 唯一的序列化身份标识,主要用于程序的版本控制,如果不显示定义,Jvm 在编译时也会自动生成一个唯一的 serialVersionUID,为了提高工作效率,实际工作中应显示定义
private static final long serialVersionUID = 8683452581122892189L;
// 初始化数组容量
private static final int DEFAULT_CAPACITY = 10;
// 默认大小的空实例数组,在第一次调用 ensureCapacityInternal 时会初始化长度为 10
private static final Object[] EMPTY_ELEMENTDATA = {};
// 默认大小的空实例数组,上面已经有了一个空实例数组 EMPTY_ELEMENTDATA,之所以再多定义一个的目的是为了将其与 EMPTY_ELEMENTDATA 区分开来,以了解添加第一个元素时要扩容多少
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// transient: 字面意思翻译为短暂的,转瞬即逝,使用此关键字修饰后的成员变量不能被序列化;注意使用 static 修饰的成员变量也是天然不能被序列化的(因为 static 是描述类的,序列化是描述实例对象的)
// elementData: 存放元素的数组
transient Object[] elementData;
// 当前数组元素的个数
private int size;
// modCount 是用来记录数组的结构变化次数(添加、删除的时候均会做 modCount++ 操作),ArrayList 不是线程安全的,如果有多个线程同时操作一个共享的 ArrayList
// 可能会导致异常,因此 ArrayList 采用了快速失败的机制,通过记录 modCount 参数来实现,在面对并发修改时,迭代器很快就会完全失败,而不是冒着在将来某个不确定时间发生任意不确定行为的风险
protected transient int modCount = 0;
// Hotspot 虚拟机中数组的对象头需要使用 4 个字节保存长度,以及 4 个填充字节
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
}
例如下面这个数组
数组实例对象为 elementData,数组的容量大小为 10,数组中元素个数为 7,需要注意的是数组的起始索引位置是 0
三、构造方法
// List list = new ArrayList();
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; // 创建对象时如果没有显示指定容量,那么使用默认的空数组
}
// List list = new ArrayList(initialCapacity);
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity]; // 如果传入的初始化容量大于 0 则创建一个容量为 initialCapacity 的新数组,并把该新数组赋值给 elementData
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA; // 如果传入的初始化容量等于 0 则使用空数组实例对象
} else {
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); // 如果传入的参数小于 0,则抛出异常
}
}
// List list = new ArrayList(HashSet hashSet)
public ArrayList(Collection<? extends E> c) {
Object[] a = c.toArray(); // 将传入的集合对象转成 Object 类型数组
if ((size = a.length) != 0) { // 将数组的容量赋值给 size,如果数组不是空数组
if (c.getClass() == ArrayList.class) { // 判断传入的集合类型是否是 ArrayList 类型,如果是直接赋值即可,不需要任何转换
elementData = a;
} else {
elementData = Arrays.copyOf(a, size, Object[].class); // 如果不是 ArrayList 类型,那么需要创建一个新的 Object 类型数组,初始化容量为 size,并且把数组 a 中的元素复制到新的 Object 类型数组中
}
} else {
elementData = EMPTY_ELEMENTDATA; // 如果集合 c 中原先没有任何元素,直接返回一个空的 Object 类型的数组
}
}
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
T[] copy = ((Object)newType == (Object)Object[].class)? (T[]) new Object[newLength]: (T[]) Array.newInstance(newType.getComponentType(), newLength); // 创建一个传入参数类型的数组,容量为 newLength
// original: 源数组
// 第一个 0: 从源数组索引位置 0 开始
// copy: 目标数组
// 第二个 0: 目标数组的 0 开始
// Math.min(original.length, newLength): 需要复制的元素个数
// 例如有两个数组 original = [1,3,5,7,9] copy = [2,4,6,8,10,12]
// 调用 System.arraycopy(original, 1, copy, 2,3) 之后, 它会将源数组(original)从索引位置为 1 开始,复制 3 个元素(即 3,5,7) 到新的数组(copy)从索引位置为 2 的地方开始(注意: 数组的长度是不可变的,这里是覆盖,而不是增加)
// 操作完成之后源数组不会发生改变,目标数组会有 3 个元素被覆盖(3,5,7),两个数组最终如下: original = [1,3,5,7,9] copy = [2,4,3,5,7,12],源数组不会改变
System.arraycopy(original, 0, copy, 0,Math.min(original.length, newLength));
return copy;
}
ArrayList 有三个构造方法
1、如果创建对象时不显示指定容量,那么会创建一个默认长度为 10 的数组
2、如果创建对象时显示指定了容量,那么会根据显示指定的初始化容量创建对应长度的数组
3、以其它集合对象作为原材料创建数组,数组长度为其它集合的 size 大小
下面就以第三种构造方法为例
四、查询、修改方法
// 根据指定索引位置获取数组元素
public E get(int index) {
rangeCheck(index); // 校验索引下标是否越界
return elementData(index); // 根据数组的索引下标直接获取元素
}
// 将指定索引位置的元素修改为 element
public E set(int index, E element) {
rangeCheck(index); // 校验索引下标是否越界
E oldValue = elementData(index); // 获取 index 位置的旧值
elementData[index] = element; // 使用新值替换旧值
return oldValue; // 将旧值返回
}
// 调用 get 和 set 方法时都需要调用此方法来判断数组下标是否合法
private void rangeCheck(int index) {
if (index >= size) // 正常情况下 index 的最大值是 size - 1
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
从上面可以看出查询和修改方法都是基于索引下标直接操作的,性能比较好
五、添加方法
添加元素有 4 个方法,add(E e)、add(int index,E element)、addALL(Collection<? extends E> c)、addAll(int index, Collection<? extends E> c),前两个方法是添加单个元素,后两个是将传入的整个集合都添加进去
上述所有的添加方法都需要调用 ensureCapacityInternal(int minCapacity) 进行扩容判断
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 扩容判断
elementData[size++] = e; // 在数组的尾部添加元素 e,添加完成之后执行 size++ 操作
return true; // 添加成功之后返回 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; // 指定索引位置的元素使用新传入的值 element 进行覆盖
size++; // 添加成功之后,数组中元素的个数加 1
}
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray(); // 将传入的集合转成 Object 类型数组
int numNew = a.length; // 计算需要操作的元素个数
ensureCapacityInternal(size + numNew); // 扩容判断
System.arraycopy(a, 0, elementData, size, numNew); // 将集合转成的数组 a 中的元素复制到 elementData 的指定位置
size += numNew; // 操作完成之后数组元素增加 numNew
return numNew != 0; // 返回添加成功的元素数量
}
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index); // 校验索引是否越界
Object[] a = c.toArray(); // 将原集合转成 Object 类型数组,并添加对应元素
int numNew = a.length; // 计算需要操作的元素个数
ensureCapacityInternal(size + numNew); // 扩容判断
int numMoved = size - index; // 计算需要移动的元素个数
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,numMoved); // 移动指定索引及其后面的元素
System.arraycopy(a, 0, elementData, index, numNew); // 将集合转成的数组 a 中的元素复制到 elementData 的指定位置
size += numNew; // 操作完成之后数组元素增加 numNew
return numNew != 0; // 返回添加成功的元素数量
}
// 确保数组内部容量可用
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 计算数组最小需要的容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity); // 如果创建 ArrayList 对象时未指定容量,使用默认容量 10 进行初始化数组
}
return minCapacity; // 如果显示传入了最小容量,直接返回
}
// 确保显示容量
private void ensureExplicitCapacity(int minCapacity) {
modCount++; // 该变量用于记录数组结构的变化次数(调用 添加、移除 方法均会做加 1 操作)
if (minCapacity - elementData.length > 0)
grow(minCapacity); // 如果计算出来的数组最小需要的容量大于数组实际的容量,则需要进行扩容操作
}
// 扩容逻辑
private void grow(int minCapacity) {
int oldCapacity = elementData.length; // 老容量
int newCapacity = oldCapacity + (oldCapacity >> 1); // 新容量 = 老容量 + 老容量 / 2 (例如老容量为 5,扩容后的新容量是 5 + 5/2 = 7,老容量为 10,扩容后的新容量是 10 + 10/2 = 15
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity; // 如果扩容之后的新容量还是小于数据实际需要的最小容量,则新容量为数组最小需要的容量
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity); // 如果新容量 > Integer.MAX_VALUE - 8,则调用 hugeCapacity() 方法来设置合适的容量
elementData = Arrays.copyOf(elementData, newCapacity); // 将原数组中的元素复制到扩容后的新数组中,数组元素的索引保持不变
}
// 大容量设置
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) throw new OutOfMemoryError(); // 数组需要的最小容量不可能小于 0,如果是则抛出异常
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; // 如果 minCapacity > MAX_ARRAY_SIZE 则设置数组容量为 MAX_VALUE,否则设置为 Integer.MAX_VALUE - 8
}
// 复制数组元素
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
// 创建一个新的数组用于存放原数组中的元素
T[] copy = ((Object)newType == (Object)Object[].class)? (T[]) new Object[newLength]: (T[]) Array.newInstance(newType.getComponentType(), newLength);
// 将原数组中的元素复制到扩容后的新数组中,原数组和新数组中元素的索引相同
System.arraycopy(original, 0, copy, 0,Math.min(original.length, newLength));
// 返回新创建的数组
return copy;
}
示例代码 1
public class ArrayListSourceRead {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
}
}
示例代码 2
public class ArrayListSourceRead {
public static void main(String[] args) {
List<String> list = new ArrayList<>(3);
list.add("A");
list.add("B");
list.add("C");
list.add(1,"Y");
}
}
示例代码 3
public class ArrayListSourceRead {
public static void main(String[] args) {
Set<String> hashSet = new HashSet<>();
hashSet.add("a");
hashSet.add("b");
hashSet.add("c");
hashSet.add("d");
hashSet.add("e");
List<String> list = new ArrayList<>(3);
list.add("A");
list.add("B");
list.add("C");
list.addAll(1, hashSet);
}
}
六、删除方法
public void clear() {
modCount++;
// 循环遍历数组,将每个元素都置为 null,等待垃圾回收器进行回收
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
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; // 将 index = size -1 处的元素置空,等待垃圾回收器进行回收
return oldValue; // 返回被移除的旧值
}
public boolean remove(Object o) {
if (o == null) { // 当指定要移除的元素是 null
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else { // 当指定要移除的元素不为 null
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) { // 循环遍历数组 elementData,找出符合条件的元素
fastRemove(index); // 根据指定元素在数组中的索引位置进行 fastRemove 操作
return true;
}
}
return false;
}
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1; // 计算出要移动的元素的个数
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,numMoved); // 将指定元素所在的索引后面的元素向前移动 1 位
elementData[--size] = null; // 将 index = size -1 处的元素置空,等待垃圾回收器进行回收
}
示例代码
public class ArrayListSourceRead {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");
list.add("D");
list.remove("B");
}
}
