ArrayList详解

简介

【概述】

List的主要实现类，底层使用Object[]存储，适用于频繁的查找工作，线程不安全。

【特点】

增删慢：每次删除元素，都需要更改数组长度、拷贝以及移动元素位置；
查询快：由于数组在内存中是一块连续空间，因此可以根据地址+索引的方式快速获取对应位置上的元素。

【数据结构】

ArrayList底层是数组队列，相当于动态数组。

二、继承关系

【Serializable】

表示ArrayList支持序列化，能通过序列化去传输。

【Cloneable】

表示ArrayList重写了clone()，表示能被克隆。

【RandomAccess】

此接口的主要目的是允许通用算法更改其行为，以便在应用于随机访问列表或顺序访问列表时提供良好的性能。

//数据量特别大的时候，对返回的集合进行判断。
//如果返回的集合实现了RandomAccess就使用普通for，否则使用迭代器(增强for)
List<Student> list = ew ArrayList<>(); //～～～很多数据的集合
if(list instanceof RandomAccess){for (int i = 0; i < list.size(); i++) {System.out.println(list.get(i));}
}else {for (Student stu : list) {System.out.println(stu);}
}

三、源码分析

1、成员变量

// 默认的初始容量是10
private static final int DEFAULT_CAPACITY = 10;// 空元素数组
private static final Object[] EMPTY_ELEMENTDATA = {};// 默认容量的空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};// 存储元素的数组 
transient Object[] elementData;// 集合最大容量2的31次方-1-8
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;// 集合容量
private int size;// 更改次数
protected transient int modCount = 0;

2、构造方法

// 1.构造一个初始容量的空数组。
public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}// 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);}
}
//3.构造一个包含指定集合的元素的列表，按照它们由集合的迭代器返回的顺序
public ArrayList(Collection<? extends E> c) {// 将集合构造中的集合对象转成数组Object[] a = c.toArray();if ((size = a.length) != 0) {if (c.getClass() == ArrayList.class) {// 类型为ArrayList则直接赋值elementData = a;} else {//如果不一样,使用Arrays的copyOf方法进行元素的拷贝elementData = Arrays.copyOf(a, size, Object[].class);}} else {// replace with empty array.elementData = EMPTY_ELEMENTDATA;}
}

3、成员方法

3.1 添加方法

3.1.1 指定的元素添加

public boolean add(E e) {// 对内部容量进行判断，详情见下方的被调方法ensureCapacityInternal(size + 1);  // Increments modCount!!elementData[size++] = e;return true;
}

3.1.2 指定位置、元素添加

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++;
}

3.1.3 指定集合中的所有元素添加

public boolean addAll(Collection<? extends E> c) {//源数组Object[] a = c.toArray();//源数组长度int numNew = a.length;// 对内部容量进行判断，详情见下方的被调方法ensureCapacityInternal(size + numNew);  // Increments modCount// 实现从源数组的起始位置开始复制全部元素到目标数组的指定位置中System.arraycopy(a, 0, elementData, size, numNew);size += numNew;return numNew != 0;
}

3.1.4 指定位置和集合中的所有元素添加

public boolean addAll(int index, Collection<? extends E> c) {// 检查索引是否在范围内rangeCheckForAdd(index);//源数组Object[] a = c.toArray();//源数组长度int numNew = a.length;// 对内部容量进行判断，详情见下方的被调方法ensureCapacityInternal(size + numNew);  // Increments modCountint numMoved = size - index;if (numMoved > 0)// 实现从源数组的起始位置开始复制全部元素到目标数组的指定位置中System.arraycopy(elementData, index, elementData, index + numNew,numMoved);// 实现从源数组的起始位置开始复制全部元素到目标数组的指定位置中System.arraycopy(a, 0, elementData, index, numNew);size += numNew;return numNew != 0;
}

3.1.5 扩容核心方法（重要）

// 1.主体函数
private void ensureCapacityInternal(int minCapacity) {// 对容量进行判断ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}// 2.通过最小容量和默认容量求出较大值 (用于第一次扩容)
private static int calculateCapacity(Object[] elementData, int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);}return minCapacity;
}// 3.判断是否需要进行扩容
private void ensureExplicitCapacity(int minCapacity) {// 实际修改集合次数+1 (在扩容的过程中没用,主要是用于迭代器中)modCount++;// 判断当前最小容量是否大于数组长度if (minCapacity - elementData.length > 0)// 将计算出来的容量传递给核心扩容方法grow(minCapacity);
}// 4.核心扩容方法
private void grow(int minCapacity) {// 记录数组的实际长度int oldCapacity = elementData.length;// 核心扩容算法，原容量的1.5倍int newCapacity = oldCapacity + (oldCapacity >> 1);// 判断新容量是否小于当前最小容量（第一次调用add方法必然小于）if (newCapacity - minCapacity < 0)newCapacity = minCapacity;// 判断新容量是否大于最大数组长度,如果if (newCapacity - MAX_ARRAY_SIZE > 0)// 条件满足就计算出一个超大容量newCapacity = hugeCapacity(minCapacity);// 调用数组工具类方法,创建一个新数组,将新数组的地址赋值给elementDataelementData = Arrays.copyOf(elementData, newCapacity);
}// 5.超大容量计算
private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;
}

3.1.6 添加方法备注

【ensureCapacity方法】

向ArrayList添加大量元素之前通过该方法预设数组大小，以减少增量重新分配的次数。

// 确保集合至少可以容纳参数指定的元素数。
public void ensureCapacity(int minCapacity) {// 最小扩容int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)? 0: DEFAULT_CAPACITY;if (minCapacity > minExpand) {ensureExplicitCapacity(minCapacity);}
}

3.2 删除方法

3.2.1 根据索引删除

public E remove(int index) {// 检查索引是否在范围内rangeCheck(index);// 实际修改集合次数+1 (在扩容的过程中没用,主要是用于迭代器中)modCount++;// 获取当前索引原来的数据E oldValue = elementData(index);// 计算集合需要移动元素的个数int numMoved = size - index - 1;if (numMoved > 0)System.arraycopy(elementData, index+1, elementData, index,numMoved);、// 将源集合最后一个元素置为null,尽早让垃圾回收机制对其进行回收elementData[--size] = null; //返回当前索引原来的数据return oldValue;
}

3.2.2 根据对象删除

// 1.根据对象删除
public boolean remove(Object o) {if (o == null) {for (int index = 0; index < size; index++)// 遍历并判断集合的元素是否为nullif (elementData[index] == null) {// null则用fastRemove方法快速删除fastRemove(index);return true;}} else {for (int index = 0; index < size; index++)// 用o对象的equals方法和集合每一个元素进行比较if (o.equals(elementData[index])) {// 如果相等,调用fastRemove方法快速删除fastRemove(index);return true;}}// 如果集合没有o该元素,那么就会返回falsereturn false;
}// 2. 
private void fastRemove(int index) {// 实际修改集合次数+1 (在扩容的过程中没用,主要是用于迭代器中)modCount++;// 计算集合需要移动元素的个数int numMoved = size - index - 1;if (numMoved > 0)System.arraycopy(elementData, index+1, elementData, index,numMoved);// 将源集合最后一个元素置为null,尽早让垃圾回收机制对其进行回收elementData[--size] = null; // clear to let GC do its work
}

3.3 获取方法

public E get(int index) {// 检查索引是否在范围内rangeCheck(index);// 获取该索引元素return elementData(index);
}

3.4 修改方法

public E set(int index, E element) {// 检查索引是否在范围内rangeCheck(index);// 获取当前索引原来的数据E oldValue = elementData(index);// 替换后返回旧数据elementData[index] = element;return oldValue;
}