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 办法
@Override
public StringBuilder append(Object obj) {return append(String.valueOf(obj));
}
// StringBuilder 的 append 办法的重载办法
@Override
public 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，咱们下期再见！！！
关注公众号：一无是处的钻研僧，理解更多计算机常识。