一、ArrayList的属性分析
我们先认识一下ArrayList这个类中定义的一些属性
// 定义数组的初始容量 private static final int DEFAULT_CAPACITY = 10; // 定义一个空的数组 private static final Object[] EMPTY_ELEMENTDATA = {}; // 定义一个默认的空数组 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 定义存储元素的数组，transient：表述序列化的时候该修饰符修饰的属性不被序列化 transient Object[] elementData; // non-private to simplify nested class access // 数组最大容量 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; // 数组中元素的个数 private int size; // 数组被修改的次数，如添加删除元素都会加 1 protected transient int modCount = 0;
看了这些属性，是不是有些疑问?
问题 1 ：为什么要定义两个空的数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA和EMPTY_ELEMENTDATA？
问题 2 ：为什么ArrayList中的数组要用 transient 修饰，并且我们序列化的时候数组还是可以被序列化与反序列化？
这两个问题是我们看了这个类中的所有属性时候有的疑虑，那么我们先别急，接着往后看，这些在后面都会给你们解答出来。
二、构造器分析
我们都知道，使用一个类的第一步那就是需要创建对应的对象出来才可以使用它，而创建一个对象的正常步骤（不考虑反射等方法创建对象）就是通过其构造方法创建对象，那么我们的第一步就是分析ArrayList的构造器。
ArrayList向我们提供了三种构造器：
- 无参构造器：public ArrayList()
- 带初始容量构造器：public ArrayList(int initialCapacity)
- 带集合参数的构造器：public ArrayList(Collection<? extends E> c)
2.1 无参构造器
public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }
从源代码中我们可以看出，如果我们不带任何参数的去创建对象那么其内部会直接将一个默认的空数组赋值给ArrayList的数组（elementData）
那么问题来了：为什么不是赋值这个空数组：EMPTY_ELEMENTDATA，way？
别急我们接着看带参构造，在那里我会说明这个问题。
2.2 带初始容量构造器
// 带参构造，initialCapacity：传入的初始容量 public ArrayList(int initialCapacity) { // 1. 判断是否大于 0 if (initialCapacity > 0) { // 2. 创建一个对应大小的数组 this.elementData = new Object[initialCapacity]; // 3. 是否等于 0 } else if (initialCapacity == 0) { // 4. 赋值一个空的数组 this.elementData = EMPTY_ELEMENTDATA; } else { // 5. 传入的容量不合法 throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } }
在这里其它的步骤我们都好理解，但，是不是就是这个3，4两步是不是就有点不明所以呀！那我们来分析分析。
从上面两个构造器来看：
- 空参的时候ArrayList中的数组是它：DEFAULTCAPACITY_EMPTY_ELEMENTDATA
- 容量是 0 的时候ArrayList中的数组是它：EMPTY_ELEMENTDATA
那么问题就简化到空容量和0容量的问题了，有的人会说这不一样的嘛！有什么好区别的。
其实不是的，这两个的区别还是蛮大的，我们一贯的思维就是不传值就是空容量数组，传值就是对应的容量数组，那我们有没有想过如果一个人他就是想创建一个容量为 0 的数组，而不是一来就给我默认扩容到 10 这个容量。
怎么样是不是有点道理了。
所以我们可以得一个结论，DEFAULTCAPACITY_EMPTY_ELEMENTDATA和EMPTY_ELEMENTDATA就是在扩容得时候区别出来到底是扩容为 10 还是从 0 开始一步步得扩容。（这是上面问题 1 的解释）
具体可以看这个方法
private static int calculateCapacity(Object[] elementData, int minCapacity) { // 判断ArrayList中的数组是哪种类型 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // DEFAULTCAPACITY_EMPTY_ELEMENTDATA类型，直接扩容到 10 return Math.max(DEFAULT_CAPACITY, minCapacity); } // EMPTY_ELEMENTDATA类型，从 0 开始一步步扩容上去 return minCapacity; }
2.3 带集合参数的构造器
public ArrayList(Collection<? extends E> c) { // 将传入得集合变成数组，赋值给ArrayList的数组 elementData = c.toArray(); if ((size = elementData.length) != 0) { // 将类型转为Object然后再次调用copyOf进行赋值 if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // 传入的是空的集合，那么赋值一个容量为EMPTY_ELEMENTDATA类型的空数组 this.elementData = EMPTY_ELEMENTDATA; } }
这个带集合参数的构造器，也很好理解，唯一要说明的地方就是这个
if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class);
明明已经赋过值了elementData = c.toArray()，那为什么还要整出上面的一个逻辑？
其实关键在于toArray()方法，它返回的不是一个 Object[] ，而是 E[] 类型，意味着如果不转成 Object[] ，你想某个位置add一个Object的子类时，这个时候就会出现异常。
@Test public void demoTest03() { // 字符串类型 String[] strings = new String[8]; strings[0] = "a"; strings[1] = "b"; // 向上转型为Object类型 Object[] objects = strings; // 定义一个Object类型数据 Object obj = 1; // 赋值给Object类型数组，在这会出错：java.lang.ArrayStoreException objects[3] = obj; System.out.println(Arrays.toString(objects)); }
总结：该代码的功能就是将elementData数组中的所有元素变为Object类型，防止在向ArrayList中添加数据的时候抛错（ArrayStoreException）
三、添加分析
ArrayList中向我们提供了四种添加元素的方法
向末尾添加元素：public boolean add(E e)
指定位置添添加元素：public void add(int index, E element)
添加一个集合元素：public boolean addAll(Collection<? extends E> c)
在指定位置添加集合元素：public boolean addAll(int index, Collection<? extends E> c)
我们先不急着分析这四种方法的源码，我们先来试者去猜想一下它们实现的时候会考虑到那些方面：
ArrayList底层也是一个数组，那么无限的添加是不是要考虑容量的问题（扩容）
既然是扩容，那么改扩多少，怎么扩容
向指定地方添加元素的时候 ，是不是要考虑下标合理问题
如果指定下标中已经有元素，那么该如何操作，是添加失败还是覆盖
以上这些就是ArrayList在添加元素的方法内部应该注意的点，而在ArrayList中这些点主要的实现逻辑就是下面两个方法
ensureCapacityInternal(int minCapacity)：数组容量判断，容量够就不做处理，容量不足就进行相应的扩容
rangeCheckForAdd(index)： 检查下标时候合理，如果合理不做处理，否则抛出异常
那么我们先来分析这两个方法
3.1 ensureCapacityInternal(int minCapacity)
private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); }
我们可以看出它中间又调用了两个方法
- calculateCapacity(elementData, minCapacity)：确定数组容量
- ensureExplicitCapacity(object)：进行相应的扩容
3.1.1 calculateCapacity(elementData, minCapacity)
// 确定数组容量 private static int calculateCapacity(Object[] elementData, int minCapacity) {、 // 如果数组是默认的空数组 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 返回连个容量的最大值，就是DEFAULT_CAPACITY = 10 return Math.max(DEFAULT_CAPACITY, minCapacity); } // 否者，数组不空，返回minCapacity return minCapacity; }
我们可以看出该方法有两个参数
elementData：存放元素的数组
minCapacity：可以放下元素的最小的容量
根据我写的注释可以看出，该方法的功能就是确定数组的容量，空数组就是 10 ，数组不空就是数组中元素个数加 1
3.1.2 ensureExplicitCapacity(object)
// 进行相应的扩容 private void ensureExplicitCapacity(int minCapacity) { // 数组修改次数加一 modCount++; // 计算的最小容量是否大于数组的长度 if (minCapacity - elementData.length > 0) // 扩容 grow(minCapacity); }
可以看出，该方法主要是判断其内部的数组是否允许再添加元素，如果容量不够则进行扩容从而保证元素的正常添加而不溢出。
那我们具体来分析一下grow(minCapacity)方法
3.1.3 grow(minCapacity)
// 真正扩容方法 private void grow(int minCapacity) { // 获取数组的长度 int oldCapacity = elementData.length; // 计算新得长度，新长度为旧长度的1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1); // 判断计算的新长度与传入的最小容量的大小 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // 开始扩容 elementData = Arrays.copyOf(elementData, newCapacity); }
从这个方法，我们就可以知道如果ArrayList中如果数组容量不足，则会扩容到原来的1.5倍，而具体的扩容操作这是要看Arrays.copyOf(elementData, newCapacity)这个方法的具体实现了。
那我们点进去瞅瞅
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) { // 创建指定长度的某种类型的数组。 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; }
在这里我们可以看到，它会先创建一个指定容量大小的数组，该数组就是扩容后的数组，并且需要被返回出去。
然后这个本地方法System.arraycopy()作用就是将旧数组元素移动到新数组中，那为什么用非Java所写的C++方法呢！我想应该就是为了追求效率，因为扩容会移动很多元素用C++显然是比较快的。
由于我们不能看到native所写的方法，那么我就画个图来解释一下这个方法的原理
3.2 rangeCheckForAdd(index)
经过了上面的主流方法的分析，这个方法就相对来说简单了很多，具体如下
private void rangeCheck(int index) { // 如果传入的下标大于等于数组中的元素个数，溢出 if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }
怎么样，简单吧！就是一个简单的判断，满足则不做处理否则抛错
3.3 add(E e)
有了上面两个重量级的方法讲解，我相信现在对于添加方法来说，挺简单的，那往下看咯！
public boolean add(E e) { // 确保数组容量 ensureCapacityInternal(size + 1); // Increments modCount!! // 在数组末尾添加元素 elementData[size++] = e; // 返回添加成功 return true; }
怎么样，简单吧！ensureCapacityInternal这个方法我已经分析过了，它会确保我们添加元素的时候容量是充足的，然后就会直接添加元素到数组末尾，最后再返回成功标识。
在这里，我们也可以解释ArrayList为什么可以添加重复的值并且输出的值与我们输入的值顺序一致的问题。
3.4 add(int index, E element)
ublic void add(int index, E element) { // 1. 检查下标 rangeCheckForAdd(index); // 2. 保证容量 ensureCapacityInternal(size + 1); // Increments modCount!! // 3. 开始移动元素，空出指定下标的位置出来 System.arraycopy(elementData, index, elementData, index + 1, size - index); // 4. 在指定下标出赋值 elementData[index] = element; // 5. 数组元素值加 1 size++; }
1 - 5步前面都已经介绍过了，就不多说了而且我注释已经写的很清楚了，如果我们细心点可以得知，如果下标处有元素，则直接覆盖。
3.5 addAll(Collection<? extends E> c)
// 添加一个集合到数组中 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; }
向ArrayList中直接添加一个集合方法中我们可以看出集合元素会直接添加在末尾，和add方法基本类似。
3.6 addAll(int index, Collection<? extends E> c)
public boolean addAll(int index, Collection<? extends E> c) { // 1. 检查下标 rangeCheckForAdd(index); // 2. 将集合转为数组 Object[] a = c.toArray(); // 3. 获取数组长度 int numNew = a.length; // 4. 保证容量 ensureCapacityInternal(size + numNew); // Increments modCount // 5. 计算需要移动元素的开始下标 int numMoved = size - index; if (numMoved > 0) // 6. 开始移动元素 System.arraycopy(elementData, index, elementData, index + numNew, numMoved); // 7. 开始向目标数组中添加元素 System.arraycopy(a, 0, elementData, index, numNew); // 8. 设置元素个数 size += numNew; // 9. 返回结果 return numNew != 0; }
在指定下标处添加一个集合的元素，关键点在于要计算出一个区间的下标出来，存放添加的集合数据，该实现代码在步骤5，6处可以看出。
四、设置方法
public E set(int index, E element) { // 检查下标 rangeCheck(index); // 获取对应下标数据 E oldValue = elementData(index); // 在对应下标处赋值 elementData[index] = element; // 返回原始数据 return oldValue; }
下面是rangeCheck方法
private void rangeCheck(int index) { // 下标是否大于ArrayList中的元素个数 if (index >= size) // 下标越界错误 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }
看到设置方法，是不是也很简单，大致步骤：
检查下标，下标如果比存储的元素个数大，那就是溢出需要抛错，否者不处理
然后就是保存旧值，然后再将新值赋上去
最后返回旧值
五、获取方法分析
5.1 get(int index)
public E get(int index) { // 检查下标 rangeCheck(index); // 返回对应下标值 return elementData(index); }
这就没什么好分析了，看看就行了😁
六、移除方法分析
对于移除方法，ArrayList中提供了挺多的，但是有些我也没怎么用过，所以就只分析下面几种：
- 移除对于下标元素：remove(int index)
- 移除对应元素：remove(Object o)
- 移除一个集合的元素：removeAll(Collection<?> c)
- 清空集合：clear()
不过相较于添加，移除操作还是挺简单的，不需要考虑容量问题，只需要将对应的元素移除，然后移动元素即可，那我们往下面分析吧！
5.1 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; }
怎么样，是不是有些熟悉，对于这样的实现步骤（addAll(int index, Collection<? extends E> c)）。
其实这两个方法有很多共同点，都需要检查下标，记录旧值，计算移动的开始下标，返回旧值。不同的就是在添加方法的时候它需要将元素往后移，留出一个范围出来，然后再填充值。而移除方法则需要将元素往前移来覆盖需要移除的元素，最后再将元素的末尾一个元素置空并且size减一。下面我画个图便于理解：
5.2 remove(Object o)
// 根据元素移除对应的数据 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 { // 遍历，移除对应元素 for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { // 移除 fastRemove(index); // 返回成功 return true; } } // 返回失败 return false; }
中间调用fastRemove方法移除
// 移除第一个遇到的相等的值 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 }
从remove(Object o)方法我们可以知道，它只会移除第一个与对应的值相同的元素。
5.3 removeAll(Collection<?> c)
public boolean removeAll(Collection<?> c) { // 判断集合时候为null Objects.requireNonNull(c); // 批量移除 return batchRemove(c, false); }
移除ArrayList中对应集合中的元素，共分为两个步骤
- 判断入参是否为null
- 开始批量移除
5.3.1 判断为null方法
public static <T> T requireNonNull(T obj) { if (obj == null) throw new NullPointerException(); return obj; }
这个非常简单，就是简单的判空，如空则抛出空指针
5.3.2 批量移除方法
private boolean batchRemove(Collection<?> c, boolean complement) { // 定义一个指向元素数组的对象 final Object[] elementData = this.elementData; int r = 0, w = 0; boolean modified = false; try { // 开始遍历 for (; r < size; r++) // 如果要删除的集合中，不存在ArrayList中的元素 if (c.contains(elementData[r]) == complement) // 将集合中的元素放入elementData中，complement=true就是放入存在的元素，否者就是不存在的元素 // w是元素个数 elementData[w++] = elementData[r]; } finally { // c.contains()会抛出异常 // 在c.contains()抛出异常的时候将异常抛出之前确定的元素进行处理 if (r != size) { System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; } if (w != size) { // 将 w 下标以后的元素置空，方便垃圾回收，w下标以前的元素就是我们需要的结果 for (int i = w; i < size; i++) elementData[i] = null; // 记录修改次数 modCount += size - w; // 元素个数 size = w; // 成功 modified = true; } } return modified; }
可以看出这个批量移除元素的方法还是有点复杂的，不急，我们结合注释来慢慢分析：
- 定义一个中间变量（Object数组），指向装有元素的数组
- 遍历数组，找出需要的元素，complement = true则找出存在入参集合c中的元素，否则就找出不存在的元素
- r != size判断是为了在出现异常的情况下也可以正常的进行元素移除
- w != size判断是为了进行元素置空，在移除一个集合中如果 w = size 时则表示ArrayList中没有集合中的元素，不需要进行处理，反之则需要通过置空进行移除
- 记录修改次数然后设置元素个数
分析到这里可能有些伙伴还是不怎么理解上述的步骤，那我们接下来一段代码一段代码的来解读分析
代码片段一：
for (; r < size; r++) // 如果要删除的集合中，不存在ArrayList中的元素 if (c.contains(elementData[r]) == complement) // 将集合中的元素放入elementData中，complement=true就是放入存在的元素，否者就是不存在的元素 // w是元素个数 elementData[w++] = elementData[r];
首先这是一个循环操作，又因为c.contains()是一个可能抛出错误的函数，所以这里可以分为两种情况：
正常走完
- r 等于 size
- w 等于 ArrayList 中元素不存在c集合中的元素个数
异常退出
- r 不等于 size
- w 只等于异常出现之前满足条件时记录的元素
代码片段二：
if (r != size) { System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; }
我们看条件可以发现，这是一个出现异常情况时才会满足的情况
- r 等于出现异常时，循环遍历的下标
- w 等于出现异常时，循环记录ArrayList中不存在c集合中的元素个数
然后就是调用移动函数将已经判断且满足条件的元素和未判断的元素进行合并
代码片段三：
if (w != size) { // 将 w 下标以后的元素置空，方便垃圾回收，w下标以前的元素就是我们需要的结果 for (int i = w; i < size; i++) elementData[i] = null; // 记录修改次数 modCount += size - w; // 元素个数 size = w; // 成功 modified = true; }
这个代码片段就好理解了，就是将合并后的集合末尾没有用的元素置空并将一些属性设置到正确的值就行
5.3.5 流程图
异常情况如下，正常情况只是减少了元素移动的步骤，大致流程都差不多
5.4 clear()
清空方法，可以看出非常的简单，简单的我都不想做过多的解释了，你们看代码就行。
public void clear() { modCount++; // clear to let GC do its work for (int i = 0; i < size; i++) // 赋空 elementData[i] = null; // 元素个数设为 0 size = 0; }
七、elementData数组被修饰transient问题
我们知道ArrayList是支持序列化的，那为什么其中关键的存储元素的数组要被修饰成transient（序列化时忽略该数组），矛盾了。
其实不然，我们点进源码可以发现，ArrayList中自己重写了序列化和反序列化的方法，代码如下：
// 序列化 private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{ // Write out element count, and any hidden stuff int expectedModCount = modCount; s.defaultWriteObject(); // Write out size as capacity for behavioural compatibility with clone() s.writeInt(size); // Write out all elements in the proper order. for (int i=0; i<size; i++) { s.writeObject(elementData[i]); } if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } } // 反序列化 private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { elementData = EMPTY_ELEMENTDATA; // Read in size, and any hidden stuff s.defaultReadObject(); // Read in capacity s.readInt(); // ignored if (size > 0) { // be like clone(), allocate array based upon size not capacity int capacity = calculateCapacity(elementData, size); SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity); ensureCapacityInternal(size); Object[] a = elementData; // Read in all elements in the proper order. for (int i=0; i<size; i++) { a[i] = s.readObject(); } } }
那为什么要自己实现一套序列化呢！
ArrayList底层是基于动态数组实现的，数组的长度是动态变化的，当数组的长度扩容到很大的时候，其中的元素却是寥寥几个的话，那要是将这些没有用的空元素也序列化到内存中就有点非内存了。所以就是考虑到这一点，ArrayList才会自己实现一套序列化标准，只序列化有用的元素，这样可以节省空间。（开头问题 2的答案）
好了，今天的内容到这里就结束了，关注我，我们下期见
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
