集合ArrayList分析
- 2019 年 10 月 3 日
- 筆記
ArrayList
描述
- 继承AbstractList类，实现List接口
- 实现了RandmoAccess接口，即提供了随机访问功能
- 实现了Cloneable接口，即覆盖了函数clone()，能被克隆。
- 实现java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。
- 基于泛型动态数组(List
)扩容(碰到数组先想到连续的内存空间，故空间效率不高) ArrayList可以以O(1)的时间复杂度去根据下标访问元素。(时间效率很高)- 线程不安全的，允许元素为null
重要的对象
elementData (Object类型的数组)
size(int 类型)
遍历使用
使用for循环，通过索引随机访问效率最高，其次是foreach循环，最慢是迭代器循环
foreach 最终会被转换成迭代器遍历的形式，所以是不如for循环的
与Collection关系
ArrayList属性
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, Serializable { // 序列化id private static final long serialVersionUID = 8683452581122892189L; // 默认初始的容量 private static final int DEFAULT_CAPACITY = 10; // 一个空对象 private static final Object[] EMPTY_ELEMENTDATA = new Object[0]; // 一个空对象，如果使用默认构造函数创建，则默认对象内容默认是该值 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = new Object[0]; // 当前数据对象存放地方，当前对象不参与序列化 transient Object[] elementData; // 当前数组长度 private int size; // 数组最大长度 private static final int MAX_ARRAY_SIZE = 2147483639; }扩展：什么是序列化(这里序列化又是一大知识点)
序列化是指：将对象转换成以字节序列的形式来表示，以便用于持久化和传输。
实现方法：实现Serializable接口。
然后用的时候拿出来进行反序列化即可又变成Java对象。
transient关键字解析
Java中transient关键字的作用，简单地说，就是让某些被修饰的成员属性变量不被序列化。
有了transient关键字声明，则这个变量不会参与序列化操作，即使所在类实现了Serializable接口，反序列化后该变量为空值。
那么问题来了：ArrayList中数组声明：
transient Object[] elementData;，事实上我们使用ArrayList在网络传输用的很正常，并没有出现空值。
原来：ArrayList在序列化的时候会调用writeObject()方法，将size和element写入ObjectOutputStream；反序列化时调用readObject()，从ObjectInputStream获取size和element，再恢复到elementData。
那为什么不直接用elementData来序列化，而采用上诉的方式来实现序列化呢？
原因在于elementData是一个缓存数组，它通常会预留一些容量，等容量不足时再扩充容量，那么有些空间可能就没有实际存储元素，采用上诉的方式来实现序列化时，就可以保证只序列化实际存储的那些元素，而不是整个数组，从而节省空间和时间。
所以ArrayList的设计者将elementData设计为transient，然后在writeObject方法中手动将其序列化，并且只序列化了实际存储的那些元素，而不是整个数组。
见源码：
// Write out all elements in the proper order.for (int i=0; i<size; i++) { s.writeObject(elementData[i]);}从源码中，可以观察到 循环时是使用i<size而不是 i<elementData.length，说明序列化时，只需实际存储的那些元素，而不是整个数组。
ArrayList构造方法
无参构造
public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }默认无参构建方法创建ArrayList对象
new ArrayList() 创建对象，数组长度size=0，而elementData数组的长度为size+1，
第一次add时，elementData会变成默认长度=10(DEFAULT_CAPACITY)
int类型参数的构造方法
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); } }initialCapacity指定初始数组长度。
Collection对象的构造方法
public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) != 0) { // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; } }- 将collection对象转换成数组，然后将数组的地址赋给elementData。
- 更新size的值，同时判断size的大小，如果是size等于0，直接将空对象EMPTY_ELEMENTDATA的地址赋给elementData
- 如果size的值大于0，则执行Arrays.copyOf方法，把collection对象的内容（可以理解为深拷贝）copy到elementData中。
注意：this.elementData = arg0.toArray(); 这里执行的简单赋值是浅拷贝，所以要执行Arrays.copyOf做深拷贝
ArrayList普通方法
add(E e)方法
/** *增加指定的元素到ArrayList的最后位置 * @param e 要添加的元素 * @return */ public boolean add(E e) { // 确定ArrayList的容量大小---严谨 // 注意：size + 1，保证资源空间不被浪费， // ☆☆☆按当前情况，保证要存多少个元素，就只分配多少空间资源 ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } /** * 私有方法：明确 ArrayList 的容量，提供给本类使用的方法 * - 用于内部优化，保证空间资源不被浪费：尤其在 add() 方法添加时起效 * @param minCapacity 指定的最小容量 */ private void ensureCapacityInternal(int minCapacity) { // 若 elementData == {}，则取 minCapacity 为 默认容量和参数 minCapacity 之间的最大值 // 注：ensureCapacity() 是提供给用户使用的方法，在 ArrayList 的实现中并没有使用 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity= Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } /** * 私有方法：明确 ArrayList 的容量 * - 用于内部优化，保证空间资源不被浪费：尤其在 add() 方法添加时起效 * @param minCapacity 指定的最小容量 */ private void ensureExplicitCapacity(int minCapacity) { // 将“修改统计数”+1，该变量主要是用来实现fail-fast机制的 modCount++; // 防止溢出代码：确保指定的最小容量 > 数组缓冲区当前的长度 // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } /** * 数组缓冲区最大存储容量 * - 一些 VM 会在一个数组中存储某些数据--->为什么要减去 8 的原因 * - 尝试分配这个最大存储容量，可能会导致 OutOfMemoryError(当该值 > VM 的限制时) */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; /** * 私有方法：扩容，以确保 ArrayList 至少能存储 minCapacity 个元素 * - 扩容计算：newCapacity = oldCapacity + (oldCapacity >> 1); 扩充当前容量的1.5倍 * @param minCapacity 指定的最小容量 */ private void grow(int minCapacity) { // 防止溢出代码 int oldCapacity = elementData.length;// 旧容量大小 int newCapacity = oldCapacity + (oldCapacity >> 1); // 新容量为旧容量的1.5倍 if (newCapacity - minCapacity < 0) // 若 newCapacity新容量小于参数指定容量，修改新容量 newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) // 若 newCapacity 大于最大存储容量，则进行大容量分配 newCapacity = hugeCapacity(minCapacity); // 拷贝扩容 elementData = Arrays.copyOf(elementData, newCapacity); } /** * 私有静态方法：大容量分配，最大分配 Integer.MAX_VALUE * @param minCapacity */ private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }1）确保数组已使用长度（size）加1之后足够存下 下一个数据
2）修改次数modCount 标识自增1，如果当前数组已使用长度（size）加1后的大于当前的数组长度，则调用grow方法，增长数组，grow方法会将当前数组的长度变为原来容量的1.5倍。
3）确保新增的数据有地方存储之后，则将新元素添加到位于size的位置上。
4）返回添加成功布尔值。
remove()方法
删除指定位置的元素。
//删除指定位置的元素，返回被删除的元素 public E remove(int index) { rangeCheck(index); modCount++; //被删除时 modCount也会改变 E oldValue = elementData(index); int numMoved = size - index - 1; if (numMoved > 0) // 将 index + 1 及之后的元素向前移动一位，覆盖被删除值 System.arraycopy(elementData, index+1, elementData, index, numMoved); //将最后一个元素置空，并将 size 值减1 elementData[--size] = null; // clear to let GC do its work return oldValue; }直接删除集合中某个元素，如果元素重复，则只删除下标最小的元素
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; }快速删除方法
没有做边界检查，直接进行删除操作
private void fastRemove(int index) { modCount++; 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 }删除操作的步骤：
- 获取指定位置 index 处的元素值
- 将 index + 1 及之后的元素向前移动一位
- 将最后一个元素置空，并将 size 值减 1
- 返回被删除值，完成删除操作
快速失败机制
在 Java 集合框架中，很多类都实现了快速失败机制。该机制被触发时，会抛出并发修改异常ConcurrentModificationException。
- < p > < name = "快速失败" >
*该类的{@link #iterator() iterator}和返回的迭代器
- {@link #listIterator(int) listIterator}方法是fail-fast:
*如果列表在迭代器之后的任何时候在结构上被修改
*创建的，除了通过迭代器自己创建之外的任何方式
{@link ListIterator#remove() remove}或
{@link ListIterator#add(Object) add}方法，迭代器将抛出一个
{@link ConcurrentModificationException}。于是，面对
*并发修改，迭代器会快速而干净地失败
*而不是冒着不确定行为的风险
未来的时间。
注意，不能保证迭代器的快速故障行为
*一般来说，在……方面是不可能作出任何硬性保证的
*存在不同步的并发修改。快速失败迭代器
*尽最大努力抛出{@code ConcurrentModificationException}。
因此，编写依赖于此的程序是错误的
*正确性异常:迭代器的快速故障行为
*应该只用于检测bug。
这个类是
< a href = " {@docRoot} / . . /技术说明/指导/收藏/ index . html " >
Java集合框架。
源码注释总结：
在遇到并发修改时，迭代器会尽最大努力抛出ConcurrentModificationException这个异常，
但不能百分之百的保证，而迭代器的快速失败，会避免程序在将来不确定的时间里出现不确定的行为。
思考
为什么ArrayList继承了AbstractList还要实现List接口 ？
防止在代理时出错
其实没有必要，实现与不实现都是可以的。
System.arraycopy()和Arrays.copyof()
- Arrays.copyOf()内部还调用了System.arraycopy()这个方法
- System.arraycopy()需要传一个数组的参数进行拷贝。
- 而Arrays.copyof()自己内部会创建一个新的数组进行拷贝
