ArrayList源码深度分析
本篇文章次要跟大家剖析一下ArrayList的源代码。浏览本文你首先得对ArrayList有一些根本的理解，至多应用过它。如果你对ArrayList的一些根本应用还不太熟悉或者在浏览本文的时候感觉有点艰难，你能够先浏览这篇文章ArrayList设计与实现，本人入手写ArrayList。
ArrayList继承体系剖析
RandomAccess，这个接口的含意示意能够随机拜访ArrayList当中的数据，拿什么是随机拜访呢？随机拜访就是示意咱们能够在常量工夫复杂度内拜访数据，也就是工夫复杂度是O(1)。因为在ArrayList当中咱们应用的最根本的数据类型是数组，而数组是能够随机拜访的，比方像上面这样。
public static void main(String[] args) { int[] data = new int[10]; for (int i = 0; i < 10; i++) data[i] = i; System.out.println("data[5] = " + data[5]); }而链表是不能够随机拜访的，比如说咱们想通过下标拜访链表当中的某个数据，须要从头结点或者尾节点开始遍历，直到遍历到下标对应的数据，比方下图中的单链表找到第3个数据，须要从头开始遍历，而这个工夫复杂度为O(n)。
Serializable，这个接口次要用于序列化，所谓序列化就是能将对象写入磁盘，反序列化就是可能将对象从磁盘当中读取进去，如果想序列化和反序列化ArrayList的实例对象就必须实现这个接口，如果没有实现这个接口，在实例化的时候程序执行会报错，比方上面就是一个序列化的例子。
import java.io.*;import java.util.Objects;class TestPerson implements Serializable{ String name; Integer age; private static final long serialVersionUID = 9999L; @Override public String toString() { return "TestPerson{" + "name='" + name + '\'' + ", age=" + age + '}'; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; TestPerson that = (TestPerson) o; return that.age.equals(this.age) && that.name.equals(this.name); } @Override public int hashCode() { return Objects.hash(name, age); } public TestPerson(String name, Integer age) { this.name = name; this.age = age; }}public class SerialTest { public static void main(String[] args) throws IOException, ClassNotFoundException { TestPerson leHung = new TestPerson("LeHung", 18); FileOutputStream os = new FileOutputStream("objtest"); ObjectOutputStream outputStream = new ObjectOutputStream(os); // 序列化数据 outputStream.writeObject(leHung); FileInputStream is = new FileInputStream("objtest"); ObjectInputStream stream = new ObjectInputStream(is); // 反序列化数据 TestPerson object = (TestPerson) stream.readObject(); System.out.println(object); System.out.println(object == leHung); System.out.println(object.equals(leHung)); }}如果下面程序当中的TestPerson没有implements Serializable，则上述代码会报异样java.io.NotSerializableException:。
Cloneable，实现Cloneable接口那么实现Cloneable的类就可能调用clone这个办法，如果没有实现Cloneable接口就调用办法，则会抛出异样java.lang.CloneNotSupportedException。List，这个接口次要定义了一些汇合罕用的办法让ArrayList进行实现，比方add，addAll，contains，remove，set，size，indexOf等等办法。AbstractList，这个抽象类也实现了List接口外面的办法，并且为其提供了默认代码实现，比如说AbstractList中对indexOf的实现如下：
// 这个办法的作用就是返回对象 o 在容器当中的下标public int indexOf(Object o) { // 通过迭代器去遍历数据 ListIterator<E> it = listIterator(); if (o==null) { while (it.hasNext()) if (it.next()==null) // 返回数据 o 的下标 return it.previousIndex(); } else { while (it.hasNext()) if (o.equals(it.next())) // 返回数据 o 的下标 return it.previousIndex(); } return -1;}汇合的addAll办法实现如下：
// 这个函数的作用就是在 index 的地位插入汇合 c 当中所有的元素public boolean addAll(int index, Collection<? extends E> c) { rangeCheckForAdd(index); boolean modified = false; for (E e : c) { add(index++, e); modified = true; } return modified;}ArrayList关键字段剖析
在ArrayList当中次要有以下这些字段：
// ArrayList 当中默认初始化容量，也就是初始化数组的大小private static final int DEFAULT_CAPACITY = 10;// 寄存具体数据的数组 ArrayList 底层就是应用数组进行存储的transient Object[] elementData; // size 示意容器当中数据的个数 留神和容器的长度辨别开来private int size;// 当容器当中没有元素的时候将 elementData 赋值为以下数据（不同状况不一样）private static final Object[] EMPTY_ELEMENTDATA = {};private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};// 上面两个函数是 ArrayList 的构造函数，从上面两个函数当中// 咱们能够看出 EMPTY_ELEMENTDATA 和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 应用区别// EMPTY_ELEMENTDATA 是容器当中没有元素时应用，DEFAULTCAPACITY_EMPTY_ELEMENTDATA// 是默认结构的时候应用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); }}public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}ArrayList次要办法剖析
add办法，这个办法用于往容器的开端减少数据，也是ArrayList当中最外围的办法。他的次要工作流程如下图所示：
他首先调用函数ensureCapacityInternal确保ArrayList当中的数组长度可能满足需要，不然数组会报数组下标越界异样，add函数调用过程当中所波及到的函数如下。
public boolean add(E e) { // 这个函数的次要目标是确保 elementData 的容量有 size + 1 // 否则存储数据的时候数组就会越界 ensureCapacityInternal(size + 1); // size 示意容器当中数据的个数 留神和容器的长度辨别开来 // 退出数据之后 容器当中数据的个数也要 + 1 elementData[size++] = e; return true;}// minCapacity 示意 ArrayList 中的数组最小的长度private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity( // 这个函数计算数组的最小长度 calculateCapacity(elementData, minCapacity) );}private static int calculateCapacity(Object[] elementData, int minCapacity) { // 如果是无参结构的话，取默认长度和需要长度 minCapacity 中比拟大的值 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity;}private void ensureExplicitCapacity(int minCapacity) { // 这个示意容器产生扭转的次数，咱们在后续剖析迭代器的时候进行剖析 // 它跟容器扩容没关系，当初能够不必管他 modCount++; // 如果最小的需要容量 minCapacity 大于当初容器当中数组的长度，则须要进行扩容 if (minCapacity - elementData.length > 0) grow(minCapacity);}private void grow(int minCapacity) { int oldCapacity = elementData.length; // 新数组的长度为原数组的长度的1.5倍，右移一位相当于除以2 int newCapacity = oldCapacity + (oldCapacity >> 1); // 如果新数组的长度，小于须要的最小的容量，则更新数组的长度为 minCapacity if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) // 这个函数的次要目标是判断整数是否产生溢出 newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity);}private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;}上述代码的调用流程如下：
get函数，获取对应下标的数据。
public E get(int index) { // 进行数组下标的查看，如果下标超过 ArrayList 中数据的个数，则抛出异样 // 留神这里是容器当中数据的个数 不是数组的长度 rangeCheck(index); return elementData(index);}private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}E elementData(int index) { // 返回对应下标的数据 return (E) elementData[index];}remove函数，删除ArrayList当中的数据。
// 通过下标删除数据，这个函数的意义是删除下标为 index 的数据public E remove(int index) { // 首先查看下标是否非法，如果不非法，抛出下标越界异样 rangeCheck(index); modCount++; E oldValue = elementData(index); // 因为删除某个数据，须要将该数据前面的数据往数组后面挪动 // 这里须要计算须要挪动的数据的个数 int numMoved = size - index - 1; if (numMoved > 0) // 通过拷贝挪动数据 // 这个函数的意义是将 index + 1和其之后的数据整体挪动到 index // 的地位 System.arraycopy(elementData, index+1, elementData, index, numMoved); // 因为最初一个数据曾经拷贝到前一个地位了，所以能够设置为 null // 能够做垃圾回收了 elementData[--size] = null; return oldValue;}// 这个函数的意义是删除容器当中的第一个等于 o 的数据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;}// 这个办法和第一个 remove 办法原理统一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}set办法，这个办法次要是用于设置指定下标的数据，这个办法比较简单。
public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue;}ArrayList中那些鲜为人知的办法
ensureCapacity办法
public void ensureCapacity(int minCapacity) { int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) // any size if not default element table ? 0 // larger than default for default empty table. It's already // supposed to be at default size. : DEFAULT_CAPACITY; if (minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); }}这个办法咱们在后面曾经提到过了，不晓得大家有没有察看到他的拜访修饰符是public，为什么要设置为public呢？这个意思很显著，咱们能够在应用ArrayList的时候本人调用这个办法，避免当咱们在往容器中退出数据的时候频繁因为数组长度不够从新申请内存，而原来的数组须要从新开释，这会给垃圾回收器造成压力。咱们在ArrayList设计与实现，本人入手写ArrayList这篇文章当中写过一段测试程序去测试这个办法，感兴趣的同学能够去看看！！！
toString办法
咱们首先来看一下上面代码的输入
public class CodeTest { public static void main(String[] args) { LinkedList<Integer> list = new LinkedList<>(); for (int i = 0; i < 10; i++) { list.add(i); } System.out.println(list); }}// 输入后果：// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]执行下面一段代码咱们能够在控制台看见对应的输入，咱们晓得最终打印在屏幕上的是一个字符串，那这个字符串怎么来的呢，咱们打印的是一个对象，它是怎么失去字符串的呢？咱们能够查看System.out.println的源代码：
public void println(Object x) { String s = String.valueOf(x); synchronized (this) { print(s); newLine(); }}从上述代码当中咱们能够看见通过String s = String.valueOf(x);这行代码失去了一个字符串，而后进行打印，咱们在进入String.valueOf办法看看是如何失去字符串的：
public static String valueOf(Object obj) { return (obj == null) ? "null" : obj.toString();}咱们能够看到如果对象不为 null 最终是调用对象的toString办法失去的字符串。因而当打印一个对象的时候，最终会打印这个对象的toString办法返回的字符串。
toString办法没有间接在ArrayList当中实现，而是在它继承的类AbstractList当中实现的，toString的源代码如下所示：
public String toString() { // 失去 ArrayList 的迭代器 这个迭代器咱们稍后细说 Iterator<E> it = iterator(); // 如果容器当中没有数据则返回空 if (! it.hasNext()) return "[]"; // 额，写这个代码的工程师应该不懂中文 哈哈哈 StringBuilder sb = new StringBuilder(); sb.append('['); for (;;) { E e = it.next(); // 将对象退出到 StringBuilder 当中，这里退出的也是一个对象 // 然而在 append 源代码当中会同样会应用 String.ValueOf // 失去对象的 toString 办法的后果 sb.append(e == this ? "(this Collection)" : e); if (! it.hasNext()) return sb.append(']').toString(); sb.append(',').append(' '); }}上述代码的整个过程还是比拟清晰的，大抵过程如下：
- 如果容器当中没有数据，间接返回[]。
- 如果容器当中有数据的话，那么通过迭代每个数据，调用
StringBuilder的append办法，将数据退出到输入的StringBuilder对象当中，上面是append的源代码。
// StringBuilder 的 append 办法@Overridepublic StringBuilder append(Object obj) { return append(String.valueOf(obj));}// StringBuilder 的 append 办法的重载办法@Overridepublic StringBuilder append(String str) { super.append(str); return this;}// String 类中的 valueOf办法public static String valueOf(Object obj) { return (obj == null) ? "null" : obj.toString();}咱们能够发现最终append到StringBuilder当中的字符串依然是ArrayList当中数据对象的toString办法返回的数据。
equals办法
在ArrayList当中的equals办法和toString办法一样，equlas办法也是在类AbstractCollection当中实现的，其源代码如下：
public boolean equals(Object o) { if (o == this) return true; if (!(o instanceof List)) return false; ListIterator<E> e1 = listIterator(); ListIterator<?> e2 = ((List<?>) o).listIterator(); while (e1.hasNext() && e2.hasNext()) { E o1 = e1.next(); Object o2 = e2.next(); if (!(o1==null ? o2==null : o1.equals(o2))) return false; } return !(e1.hasNext() || e2.hasNext());}下面代码的次要流程：
- 首先判断
o和this是否是同一个对象，如果是则返回true，比方上面这种状况：
ArrayList<Object> list = new ArrayList<>();list.equals(ArrayList);- 如果对象没有实现
List接口返回false。 - 一一判断链表外面的对象是否相等（调用链表当中存储的对象的
equals办法），如果两个链表当中节点数目一样而且都相等则返回true否则返回false。
通过下面的剖析咱们能够发现ArrayList办法并没有让比拟的对象是ArrayList对象，只须要实现List接口并且数据数目和内容都雷同，这样equals办法返回的后果就是true，比方上面代码就验证的这个后果：
LinkedList<Integer> list = new LinkedList<>();ArrayList<Integer> arrayList = new ArrayList<>();for (int i = 0; i < 10; i++) { list.add(i); arrayList.add(i);}System.out.println(arrayList.equals(list)); // 后果为 trueclone办法
ArrayList的办法比较简单，就是拷贝了原ArrayList当中的数组中的数据。
public Object clone() { try { ArrayList<?> v = (ArrayList<?>) super.clone(); v.elementData = Arrays.copyOf(elementData, size); v.modCount = 0; return v; } catch (CloneNotSupportedException e) { // this shouldn't happen, since we are Cloneable throw new InternalError(e); }}整个拷贝过程如下如所示：
尽管产生了数组的拷贝，然而拷贝之后的数组中数据的指向并没有发生变化，也就是说两个数组指向的内容是一样的，如果一个数组扭转了所指向的数据，另外一个数组当中的数据也会发生变化。比方上面的代码：
package makeyourowncontainer.test;import java.util.ArrayList;class Person { String name; public String getName() { return name; } public void setName(String name) { this.name = name; } @Override public String toString() { return "Person{" + "name='" + name + '\'' + '}'; }}public class ArrayListTest { public static void main(String[] args) { ArrayList<Person> o1 = new ArrayList<>(); Person person = new Person(); person.setName("一无是处的钻研僧"); o1.add(person); Object o2 = o1.clone(); System.out.println("o1 = " + o1); System.out.println("o2 = " + o2); ((ArrayList<Person>) o2).get(0).setName("LeHung"); System.out.println("扭转数据之后"); System.out.println("o1 = " + o1); System.out.println("o2 = " + o2); }}// 输入后果o1 = [Person{name='一无是处的钻研僧'}]o2 = [Person{name='一无是处的钻研僧'}]扭转数据之后o1 = [Person{name='LeHung'}]o2 = [Person{name='LeHung'}]神秘的迭代器Iterator
Iterator介绍
咱们在剖析toString办法的时候，有上面这样一行代码：
Iterator<E> it = iterator();而后一直通过迭代器的hasNext和next办法对数据进行迭代，比方上面这个例子：
public void testArrayList() { ArrayList<Integer> list = new ArrayList<>(); for (int i = 0; i < 10; i++) list.add(i); Iterator<Integer> iterator = list.iterator(); while (iterator.hasNext()) { System.out.println(iterator.next()); }}// iterator 办法返回的对象public Iterator<E> iterator() { return new Itr();}Iterator字段剖析
Itr类是ArrayList的外部类，接下来咱们仔细分析Itr类的实现。
在Itr类当中次要有一下几个字段：
int cursor; // 下一个元素的下标 当咱们 new 这个对象的时候这个值默认初始化为0 // 咱们应用的时候也是0这个值，因而不必显示初始化int lastRet = -1; // 上一个通过 next 办法返回的元素的下标int expectedModCount = modCount; // modCount 示意数组当中数据扭转的次数 modCount 是// ArrayList 当中的类变量 expectedModCount 是 ArrayList// 外部类 Itr 中的类变量 而后将这个变量保留到 expectedModCount当中// 应用 expectedModCount 次要用于 fast-fail 机制这个咱们前面会剖析咱们当初来花点工夫好好谈一下modCount（英文全称为：modifications count，批改次数）这个字段。当ArrayList当中产生一次构造批改(Structural modifications)时，modCount就++。所谓构造批改就是那些让ArrayList当中数组的数据个数size发生变化的操作，比如说add、remove办法，因为这两个办法一个是减少数据，一个是删除数据，都会导致容器当中数据个数发生变化。而set办法就不会是的modCount发生变化，因为没有扭转容器当中数据的个数。
Iterator的初始化办法：
private class Itr implements Iterator<E> { int cursor; // index of next element to return int lastRet = -1; // index of last element returned; -1 if no such int expectedModCount = modCount; Itr() {}}在初始化办法当中，没有任何操作也就印证了咱们后面在剖析字段的时候说的 cursor的初始化的值为0。
Iterator重要办法
接下来剖析迭代器当中比拟重要的两个办法next和hasNext。
public boolean hasNext() { // 这个 size 是外部类 ArrayList 当中的 size 示意的是 ArrayList // 当中数据元素的个数，cursor 的初始值为 0 每调用一个 next cursor // 的值就+1，当等于 size 是容器当中的数据曾经遍历实现了 hasNext 就返回 false 了 return cursor != size;}@SuppressWarnings("unchecked")public E next() { // 这个办法次要是用于检测在数据迭代的过程当中 ArrayList 是否产生 `构造批改` // 如果产生构造批改就抛出 ConcurrentModificationException 异样 checkForComodification(); int i = cursor; if (i >= size) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); // 更改 cursor 的值 并将其设置为下一个返回元素的下标 这一点咱们在 // 字段剖析的时候曾经谈到过了 cursor = i + 1; // 返回数据 表达式 lastRet = i 的返回值为 i // 这个表达式不仅将 lastRet 的值赋值为 i 同时返回 i // 因而能够返回下标为 i 的数据 return (E) elementData[lastRet = i];}// 这个办法次要是用于检测在数据迭代的过程当中 ArrayList 是否产生 `构造批改`// 如果产生构造批改就抛出 ConcurrentModificationException 异样final void checkForComodification() { // 如果产生 `构造批改` 那么 modCount 的值会++ 那么就和 expectedModCount 不相等了 // expectedModCount 初始化的时候令其等于 expectedModCount if (modCount != expectedModCount) throw new ConcurrentModificationException();}为什么要抛出ConcurrentModificationException异样呢，咱们先想想是什么导致modCount发生变化。必定迭代器在进行遍历的同时，批改了modCount的值，通常这种景象的产生呈现在并发的状况下，因而抛出ConcurrentModificationException异样。像这种通过迭代器遍历过程进行查看并且当产生不符合条件的状况下抛出异样的景象就称作Fast-fail。
其实咱们也能够在不应用并发的状况让迭代器抛出这个异样，咱们只须要在迭代器迭代的时候咱们对ArrayList进行add和remove操作即可。比方像上面这样就会抛出ConcurrentModificationException：
public void testArrayList() { ArrayList<Integer> list = new ArrayList<>(); for (int i = 0; i < 10; i++) list.add(i); Iterator<Integer> iterator = list.iterator(); while (iterator.hasNext()) { System.out.println(iterator.next()); list.add(55); }}Iterator中的remove办法
public void remove() { if (lastRet < 0) throw new IllegalStateException(); // 进行合法性检查，看是否须要抛出异样 checkForComodification(); try { // 调用 ArrayList 的remove办法实现 ArrayList.this.remove(lastRet); cursor = lastRet; lastRet = -1; // 因为 remove 会扭转 modCount 的值，因而须要将 expectedModCount 从新赋值 expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); }}ArrayList杂谈
工夫复杂度剖析
- 因为
ArrayList是随机存取的，因而咱们通过下标查找数据的工夫复杂度是O(1)。 - 插入数据的工夫复杂度是
O(n)。
证实（插入工夫复杂度）：
假如数组的长度为n，咱们能够在0~n-1的地位都能够插入数据，假如每个地位插入数据的概率都雷同，即均为$\frac{1}{n}$，咱们在第i个地位插入数据，须要挪动的数据个数为n - i。
那么咱们均匀挪动次数为：
$$m = \frac{1}{n}\sum_{i = 0}^{n - 1}(n - i) \\= \frac{1}{n}(n + n - 1 + \cdots + 1) \\ = \frac{1}{n}\dot {\frac{n(n + 1)}{2}} \\ = \frac{n + 1}{2}$$
依据下面的剖析咱们晓得，工夫复杂度为$O(\frac{n + 1}{2})\\ = O(n)$。
扩容机制
还记的咱们在ArrayList设计与实现，本人入手写ArrayList当中本人实现ArrayList应用的扩容机制吗？咱们本人的扩容机制为扩容为原来长度的两倍，而ArrayList当中的扩容机制为扩容为原来的1.5倍。
假如咱们在应用ArrayList的时候没有指定初始化的时候数组的长度，也就是说初始长度为ArrayList的默认长度也就是10。那么当咱们不停地往容器当中减少数据，扩容导致的数组长度的变动如上图所示，横轴示意扩容次数，纵轴示意数组长度，蓝色的扩容为原数组长度的1.5倍，另外一条是2倍。咱们很清晰的发现扩容为原来的2倍在前期的数组长度将会远大于扩容1.5倍。这很可能会导致咱们会节约很大的数组空间，比如说刚好退出最初一个数据的时候导致ArrayList进行扩容操作，这可能是ArrayList在设计时候的考量。
本篇文章咱们仔细分析介绍了ArrayList的源码，心愿大家有所播种，我是LeHung，咱们下期再见！！！
关注公众号：一无是处的钻研僧，理解更多计算机常识。
本文由mdnice多平台公布