代码拉取完成，页面将自动刷新
同步操作将从 flatfish/Java-Review 强制同步，此操作会覆盖自 Fork 仓库以来所做的任何修改，且无法恢复！！！
确定后同步将在后台操作，完成时将刷新页面，请耐心等待。
本篇源码基于以下JDK版本解析：
C:\Users\icanci>java -version
java version "1.8.0_131"
Java(TM) SE Runtime Environment (build 1.8.0_131-b11)
Java HotSpot(TM) 64-Bit Server VM (build 25.131-b11, mixed mode)
ArrayList，是基于[]数组实现的，支持自动扩容。相比较数组来说，其自动扩容成了日常开发中最常用的集合类，没有之一。
ArrayList实现的接口、继承的抽象类如下所示：
实现了4个接口。分别是：
java.util.List接口：提供数组的增加、删除、修改、迭代遍历等操作
java.util.RandomAccess接口：表示ArrayList支持快速的随机访问
RandomAccess接口是一个标记接口，其标记的类表示支持随机访问，因为它只一个空接口，只起到标记作用，但是为了标记什么呢？
提到ArrayList，我们会想到的是LinkedList（LinkedList这部分不讲，会单独拿出来讲），二者实现的原理不同，ArrayList使用数组实现，LinkedList使用链表实现，这就决定了他们访问速度的不一样，那么说到这里，我们就已经很接近RandomAccess接口的作用了，注意：LinkedList没有实现RandomAccess接口！为什么？再来思考一下表示支持随机访问这句话，相信你已经有点眉目了。
为了提升性能，在集合遍历之前，我们可以使用 instanceof做判断，由此选择合适的遍历方式，大大提高性能
对于集合的遍历有两种方式，一种是for循环迭代，一种是迭代器，现在我们来看段代码，立刻见高低
public class RandomAccessTimeTest {
//使用for循环遍历
public static long traverseByLoop(List list) {
long startTime = System.currentTimeMillis();
for (int i = 0; i < list.size(); i++) {
list.get(i);
}
long endTime = System.currentTimeMillis();
return endTime - startTime;
}
//使用迭代器遍历
public static long traverseByIterator(List list) {
Iterator iterator = list.iterator();
long startTime = System.currentTimeMillis();
while (iterator.hasNext()) {
iterator.next();
}
long endTime = System.currentTimeMillis();
return endTime - startTime;
}
public static void main(String[] args) {
//加入数据
List<String> arrayList = new ArrayList<>();
for (int i = 0; i < 30000; i++) {
arrayList.add("" + i);
}
long loopTime = RandomAccessTimeTest.traverseByLoop(arrayList);
long iteratorTime = RandomAccessTimeTest.traverseByIterator(arrayList);
System.out.println("ArrayList:");
System.out.println("for循环遍历时间:" + loopTime + " ms");
System.out.println("迭代器遍历时间:" + iteratorTime + " ms");
List<String> linkedList = new LinkedList<>();
//加入数据
for (int i = 0; i < 30000; i++) {
linkedList.add("" + i);
}
loopTime = RandomAccessTimeTest.traverseByLoop(linkedList);
iteratorTime = RandomAccessTimeTest.traverseByIterator(linkedList);
System.out.println("LinkedList:");
System.out.println("for循环遍历时间:" + loopTime + " ms");
System.out.println("迭代器遍历时间:" + iteratorTime + " ms");
}
}
控制台输出结果如下：
ArrayList:
for循环遍历时间:3 ms
迭代器遍历时间:5 ms
LinkedList:
for循环遍历时间:1411 ms
迭代器遍历时间:1 ms
相信到现在，你就已经明白为什么使用 RandomAccess 接口作为标记，因为我们在实际操作中，可能不确定类型，所以用此接口作为标记，来判断选择的迭代方式
总结：ArrayList 使用for循环遍历有优于迭代器，LinkedList使用迭代器遍历优于for循环
java.io.Serializable接口：表示ArrayList支持序列化的功能
java.lang.Cloneable接口：表示ArrayList支持克隆
继承了 java.util.AbstractList 抽象类，而AbstractList提供了List接口的骨架实现，大幅度减少了 迭代遍历 操作的相关代码。我们可以看一下AbstractList的部分源代码，如下：
public int indexOf(Object o) {
ListIterator<E> it = listIterator();
if (o==null) {
while (it.hasNext())
if (it.next()==null)
return it.previousIndex();
} else {
while (it.hasNext())
if (o.equals(it.next()))
return it.previousIndex();
}
return -1;
}
由以上代码我们可以看出， AbstractList为其他继承它的子类，实现了一套查找遍历的方案，是使用迭代器实现的，所以，如果子类正好适用于此种方式迭代或者查找，就直接使用AbstractList实现的，而不用自己造轮子。
这种迭代方式，不适合ArrayList，在上文我们已经提到过，所以这种方式适合LinkedList等其他链表形式的集合遍历。
ArrayList的属性很少，只有2个，如下图所示：
对应的代码如下：
// ArrayList.java
/**
* 元素数组。
*
* 当添加新的元素时，如果该数组不够，会创建新数组，并将原数组的元素拷贝到新数组。之后，将该变量指向新数组。
*
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData; // non-private to simplify nested class access 不使用 private 修复，方便内嵌类的访问。
/**
* 已使用的数组大小
*
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;
ArrayList一共有三个构造方法
ArrayList(int initialCapacity)
根据传入的初始化容量，·创建ArrayList数组，如果我们在使用的时候，如果预先可以估计使用到的数组大小，一定要使用这个构造方法，可以避免数组扩容提升性能，也是合理的使用内存，代码如下
// ArrayList.java
/**
* 共享的空数组对象。
*
* 在 {@link #ArrayList(int)} 或 {@link #ArrayList(Collection)} 构造方法中，
* 如果传入的初始化大小或者集合大小为 0 时，将 {@link #elementData} 指向它。
*
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
public ArrayList(int initialCapacity) {
// 初始化容量大于 0 时，创建 Object 数组
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
// 初始化容量等于 0 时，使用 EMPTY_ELEMENTDATA 对象
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
// 初始化容量小于 0 时，抛出 IllegalArgumentException 异常
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
比较特殊的是，如果初始化容量为0的时候，我们可以看到，会使用 EMPTY_ELEMENTDATA 空数组。在添加元素的时候，会进行扩容操作
ArrayList(Collection<? extends E> c)
使用传入的 Collection集合c，作为 ArrayList 的elementData ，代码如下
// ArrayList.java
public ArrayList(Collection<? extends E> c) {
// 将 c 转换成 Object 数组
elementData = c.toArray();
// 如果数组大小大于 0
if ((size = elementData.length) != 0) {
// defend against c.toArray (incorrectly) not returning Object[]
// (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
// <X> 如果集合元素不是 Object[] 类型，则会创建新的 Object[] 数组，并将 elementData 赋值到其中，最后赋值给 elementData 。
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
// 如果数组大小等于 0 ，则使用 EMPTY_ELEMENTDATA 。
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
比较让人费解的是，在 <X> 处的代码。它是用于解决 JDK-6260652 的 Bug 。它在 JDK9 中被解决， 也就是说，JDK8 还会存在该问题。比如下面的这段代码：
// ArrayListTest.java
public static void test02() {
List<Integer> list = Arrays.asList(1, 2, 3);
// JDK8 返回 Integer[] 数组，JDK9+ 返回 Object[] 数组。
Object[] array = list.toArray();
System.out.println("array className ：" + array.getClass().getSimpleName());
// 此处，在 JDK8 和 JDK9+ 表现不同，前者会报 ArrayStoreException 异常，后者不会。
array[0] = new Object();
}
在JDK8的环境下执行会报错 如下：但是方法参数给的返回值就是 Object[] 数组，但是JDK8实际上返回的是Integer[] 类型的数组，所以会报错。这个Bug已经在JDK9+的版本被修复。具体怎么修复的，看 JDK-6260652 的最末尾一段。
ArrayList()
无参构造方法，也是我们使用最多的方法，代码如下：
// ArrayList.java
/**
* 默认初始化容量
*
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 共享的空数组对象，用于 {@link #ArrayList()} 构造方法。
*
* 通过使用该静态变量，和 {@link #EMPTY_ELEMENTDATA} 区分开来，在第一次添加元素时。
*
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
在学习ArrayList的时候，一直就被灌输了一个概念，在未设置初始化容量的时候，ArrayList的默认大小是10，但是此处，我们可以看到 初始化为 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 这个空数组，为什么呢？这是为了考虑节省内存，因为有的时候一些场景仅仅是创建了ArrayList，但是却没有使用。所以ArrayList优化为一个空数组，在首次添加元素的时候，才真正初始化为10 的数组
那么为什么单独整一个 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 空数组，而不直接使用 EMPTY_ELEMENTDATA 呢？在下文中，我们会看到 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 首次扩容为10，而EMPTY_ELEMENTDATA 按照1.5倍从0开始而不是10，二者的起点不同。
add(E e) 方法，顺序添加单个元素到数组，代码如下：
// ArrayList.java
@Override
public boolean add(E e) {
// <1> 增加数组修改次数
modCount++;
// 添加元素
add(e, elementData, size);
// 返回添加成功
return true;
}
private void add(E e, Object[] elementData, int s) {
// <2> 如果容量不够，进行扩容
if (s == elementData.length)
elementData = grow();
// <3> 设置到末尾
elementData[s] = e;
// <4> 数量大小加一
size = s + 1;
}
在上述源码中，省略的多个方法之间的跳转，只留了核心的内容，整合在一起，
<1> 处，增加数组修改的次数 modCount ，在父类 AbstractList 定义了 modCount 属性，用于记录数组修改的次数
<2>处，如果元素添加的位置超过末尾(数组下标从0开始，而数组大小比下标大1)，说明容量不够，就需要进行扩容，那么就需要调用 grow() 方法,，进行扩容，稍后会在 **[6.数组扩容]**来讲
<3>处，设置到末尾
<4>处，数组数量大小加1
总体流程来说，抛开扩容功能，和平时向数组中添加元素是有一样的
看完这个方法之后，再来看一下 add(int index,E element) 方法，插入指定元素到指定位置，代码如下
// ArrayList.java
public void add(int index, E element) {
// 校验位置是否在数组范围内
rangeCheckForAdd(index);
// 增加数组修改次数
modCount++;
// 如果数组大小不够，进行扩容
final int s;
Object[] elementData;
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();
// 将 index + 1 位置开始的元素，进行往后挪
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);
// 设置到指定位置
elementData[index] = element;
// 数组大小加一
size = s + 1;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
grow() 方法。扩容数组。整个扩容过程很简单，首先保存之前的数组元素长度，然后通过位运算扩容原来数组的大概1.5倍长度 int newCapacity = oldCapacity + (oldCapacity >> 1);
然后开始比较新的数组长度和所需的最小的数组长度，如果所需的最小长度已经足够了，就是用最小长度，最小长度的计算会涉及到另外一个方法，计算最小扩大，最小长度需要和这个最小扩大进行比较。
如果大于了最大的扩容长度 MAX_ARRAY_SIZE 这个值是 Integer.MAX_VALUE - 8 那么久执行以下方法
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
也就是约束最大大小为 Integer.MAX_VALUE
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
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);
}
最后会拷贝新的大小数组给 elementData
然后下一个方法就是缩减容量的方法，为了就是保证利用率，代码如下
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
同时，提供 ensureCapacity(int minCapacity) 方法，保证 elementData 数组容量至少有 minCapacity 。代码如下：
// 有必要，增加此 ArrayList 实例的容量，以确保它至少可以容纳最小容量参数指定的元素数量。
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// 任何大小（如果不是默认元素表）
? 0
// 大于默认的默认空表。
// 应该是在默认大小。
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
比较简单，我们可以将这个方法理解成主动扩容。
addAll(Collection<? extend E> c) 方法，批量添加多个元素，在我们知道添加多个元素的时候，应该使用此方法，而不是单个添加，单个添加会增加很多次判断，影响性能，切可以避免多次扩容，代码如下：
public boolean addAll(Collection<? extends E> c) {
// 先转化为 a 数组
Object[] a = c.toArray();
// 求出长度
int numNew = a.length;
// 确保有足够的容量，是否进扩容
ensureCapacityInternal(size + numNew); // Increments modCount
// 执行数组拷贝
System.arraycopy(a, 0, elementData, size, numNew);
// 数组大小增加 numNew 的长度
size += numNew;
// 如果 numNew == 0，则添加失败
return numNew != 0;
}
总的看下来，就是 add(E e) 方法的批量版本，优势就正如我们在本节开头说的，避免可能多次扩容。
看懂这个方法之后，来看重载方法 addAll(int index, Collection<? extends E> c)，源码如下
public boolean addAll(int index, Collection<? extends E> c) {
// 先检查插入的位置
rangeCheckForAdd(index);
// 转化数组
Object[] a = c.toArray();
// 求出长度
int numNew = a.length;
// 确保有足够的容量，是否进扩容
ensureCapacityInternal(size + numNew); // Increments modCount
// 计算需要移动的元素，也就是插入点倍占用了
int numMoved = size - index;
if (numMoved > 0)
// 执行数组拷贝
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
// 执行数组拷贝
System.arraycopy(a, 0, elementData, index, numNew);
/ 数组大小增加 numNew 的长度
size += numNew;
// 如果 numNew == 0，则添加失败
return numNew != 0;
}
remove(int index) 方法，移除指定位置的元素，并返回该位置的元素，代码如下：
public E remove(int index) {
// 检查下标
rangeCheck(index);
// 操作次数加1
modCount++;
// 得到需要移除的元素
E oldValue = elementData(index);
// 计算移除的位置 大于0就不是最后一个位置，
int numMoved = size - index - 1;
if (numMoved > 0)
// 数组拷贝
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 移除之后最后一个向前移动，最后一个变为null 等待GC回收
elementData[--size] = null; // clear to let GC do its work
//返回移除的值
return oldValue;
}
remove(Object o) 方法，移除首个为 o 的元素，并放回boolean值，代码如下
// 移除元素 核心在 fastRemove方法
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) {
// 修改次数+1
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
}
removeRange(int fromIndex,int toInedx) 方法，批量移除[fromIndex,toIndex)的多个元素，注意不包括 toIndex 元素，代码如下：
// 批量移除 [fromIndex,toIndex) 的多个元素，注意不包括 toIndex 元素
protected void removeRange(int fromIndex, int toIndex) {
// 修改次数自增
modCount++;
// 计算移动的位置
int numMoved = size - toIndex;
// 数组移动
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// clear to let GC do its work
// 移除之后的元素，设置为 null，等待GC回收
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}
indexOf(Object o) 方法，查找首个为指定元素的位置，代码如下：
// 查找首个为指定元素的位置
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
// 是否包含的方法就是调用上面的方法
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
lastIndexOf(Object o) 方法，查找最后出现的元素，也就是倒过来查找第一个出现的元素
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
get(int index) 方法，获得指定位置的元素，代码如下：
public E get(int index) {
// 检查下标
rangeCheck(index);
// 检查修改的次数
checkForComodification();
return ArrayList.this.elementData(offset + index);
}
// 检查修改的次数，如果不一致，那么就直接抛出异常
private void checkForComodification() {
if (ArrayList.this.modCount != this.modCount)
throw new ConcurrentModificationException();
}
set(int index,E e)方法，设置指定下标的元素，代码如下：
public E set(int index, E e) {
// 检查下标
rangeCheck(index);
// 检查修改的次数
checkForComodification();
E oldValue = ArrayList.this.elementData(offset + index);
ArrayList.this.elementData[offset + index] = e;
// 返回修改之前的结果
return oldValue;
}
toArray 方法，将ArrayList转换为 [] 数组，代码如下:
public Object[] toArray() {
// 调用 Arrays 工具类里面方法
return Arrays.copyOf(elementData, size);
}
// 实际场景下，我们可能想要指定 T 泛型的数组，那么我们就需要使用到 #toArray(T[] a) 方法。代码如下：
public <T> T[] toArray(T[] a) {
// <1> 如果传入的数组小于 size 大小，则直接复制一个新数组返回
if (a.length < size)
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
// <2> 将 elementData 复制到 a 中
System.arraycopy(elementData, 0, a, 0, size);
// <2.1> 如果传入的数组大于 size 大小，则将 size 赋值为 null
if (a.length > size)
a[size] = null;
// <2.2> 返回 a
return a;
}
分成 2 个情况，根据传入的 a 数组是否足够大。
<1> 处，如果传入的数组小于 size 大小，则直接复制一个新数组返回。一般情况下，我们不会这么干。
<2> 处，将 elementData 复制到 a 中
<2.1> 处，如果传入的数组大于 size 大小，则将 size 位置赋值为 null 。额，有点没搞懂这个有啥目的。
<2.2> 处，返回传入的 a 。很稳。
考虑到 <1> 处，可能会返回一个新数组，所以即使 <2> 返回的就是 a 数组，最好使用还是按照 a = list.toArray(a) 。
hashCode() 方法，求ArrayList的哈希值（代码在AbstractList里面），代码如下：
public int hashCode() {
int hashCode = 1;
for (E e : this)
hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
return hashCode;
}
那么新的问题来了，为什么选择数数字31？
在详细说明 String hashCode 方法选择数字31的作为乘子的原因之前，我们先来看看 String hashCode 方法是怎样实现的，如下：
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
上面的代码就是 String hashCode 方法的实现，是不是很简单。实际上 hashCode 方法核心的计算逻辑只有三行，也就是代码中的 for 循环。我们可以由上面的 for 循环推导出一个计算公式，hashCode 方法注释中已经给出。如下：
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
这里说明一下，上面的 s 数组即源码中的 val 数组，是 String 内部维护的一个 char 类型数组。这里我来简单推导一下这个公式：
假设 n=3
i=0 -> h = 31 * 0 + val[0]
i=1 -> h = 31 * (31 * 0 + val[0]) + val[1]
i=2 -> h = 31 * (31 * (31 * 0 + val[0]) + val[1]) + val[2]
h = 31*31*31*0 + 31*31*val[0] + 31*val[1] + val[2]
h = 31^(n-1)*val[0] + 31^(n-2)*val[1] + val[2]
接下来来说说本文的重点，即选择31的理由。从网上的资料来看，一般有如下两个原因：
第一，31是一个不大不小的质数，是作为 hashCode 乘子的优选质数之一。另外一些相近的质数，比如37、41、43等等，也都是不错的选择。那么为啥偏偏选中了31呢？请看第二个原因。
第二、31可以被 JVM 优化，31 * i = (i << 5) - i。
一般在设计哈希算法时，会选择一个特殊的质数。至于为啥选择质数，我想应该是可以降低哈希算法的冲突率
上面说到，31是一个不大不小的质数，是优选乘子。那为啥同是质数的2和101（或者更大的质数）就不是优选乘子呢，分析如下。
这里先分析质数2。首先，假设 n = 6，然后把质数2和 n 带入上面的计算公式。并仅计算公式中次数最高的那一项，结果是2^5 = 32，是不是很小。所以这里可以断定，当字符串长度不是很长时，用质数2做为乘子算出的哈希值，数值不会很大。也就是说，哈希值会分布在一个较小的数值区间内，分布性不佳，最终可能会导致冲突率上升。
上面说了，质数2做为乘子会导致哈希值分布在一个较小区间内，那么如果用一个较大的大质数101会产生什么样的结果呢？根据上面的分析，我想大家应该可以猜出结果了。就是不用再担心哈希值会分布在一个小的区间内了，因为101^5 = 10,510,100,501。但是要注意的是，这个计算结果太大了。如果用 int 类型表示哈希值，结果会溢出，最终导致数值信息丢失。尽管数值信息丢失并不一定会导致冲突率上升，但是我们暂且先认为质数101（或者更大的质数）也不是很好的选择。最后，我们再来看看质数31的计算结果：31^5 = 28629151，结果值相对于32和10,510,100,501来说。是不是很nice，不大不小。
选择数字31是因为它是一个奇质数，如果选择一个偶数会在乘法运算中产生溢出，导致数值信息丢失，因为乘二相当于移位运算。选择质数的优势并不是特别的明显，但这是一个传统。同时，数字31有一个很好的特性，即乘法运算可以被移位和减法运算取代，来获取更好的性能：31 * i == (i << 5) - i，现代的 Java 虚拟机可以自动的完成这个优化。
正如 Goodrich 和 Tamassia 指出的那样，如果你对超过 50,000 个英文单词（由两个不同版本的 Unix 字典合并而成）进行 hash code 运算，并使用常数 31, 33, 37, 39 和 41 作为乘子，每个常数算出的哈希值冲突数都小于7个，所以在上面几个常数中，常数 31 被 Java 实现所选用也就不足为奇了。 \
根本原因就是为了减少冲突
equals(Object o)方法，判断是否相等，方法在AbstractList里，代码如下：
public boolean equals(Object o) {
// 如果是自己，直接返回相等
if (o == this)
return true;
// 如果不为 List 类型，直接不相等
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());
}
clear() 方法，清空数组，方法如下：
public void clear() {
modCount++;
// clear to let GC do its work
// 全部设置为 null 等待 GC 回收
for (int i = 0; i < size; i++)
elementData[i] = null;
// 数组大小设置为0
size = 0;
}
writeObject(java.io.ObjectOutputStream s)方法，实现ArrayList的序列化，代码如下：
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
// 写出元素计数以及任何隐藏的内容
// 获得当前的数组修改次数
int expectedModCount = modCount;
// <1> 写入非静态属性、非 transient 属性
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
// <2> 写入 size ，主要为了与 clone 方法的兼容
s.writeInt(size);
// Write out all elements in the proper order.
// <3> 逐个写入 elementData 数组的元素
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
// 如果 other 修改次数发生改变，则抛出 ConcurrentModificationException 异常
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
<1> 处，调用 ObjectOutputStream#defaultWriteObject() 方法，写入非静态属性、非 transient 属性。 可能有些胖友不了解 Java 的序列化相关的知识，可以看看 《Serializable 原理》 文章。
<2> 处，写入 size ，主要为了与 clone 方法的兼容。不过也觉得挺奇怪的，明明在 <1> 处，已经写入了 size ，这里怎么还来这么一出呢？各种翻查资料，暂时只看到 《源码分析：ArrayList 的 writeobject 方法中的实现是否多此一举？》 有个讨论。
<3> 处，逐个写入 elementData 元素的数组。我们回过来看下 elementData 的定义，它是一个 transient 修饰的属性。为什么呢？因为 elementData 数组，并不一定是全满的，而可能是扩容的时候有一定的预留，如果直接序列化，会有很多空间的浪费，所以只序列化从 [0, size) 的元素，减少空间的占用。
readObject(java.io.ObjectInputStream s)方法，反序列化数组，代码如下：
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// Read in size, and any hidden stuff
// 读取非静态属性、非 transient 属性
s.defaultReadObject();
// Read in capacity
// 读取 size ，不过忽略不用
s.readInt(); // ignored
if (size > 0) {
// be like clone(), allocate array based upon size not capacity
ensureCapacityInternal(size);
// 创建 a 数组 为 elementData
Object[] a = elementData;
// 全部逐个读取
// Read in all elements in the proper order.
// 赋值给 a
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}
clone() 方法，克隆ArrayList对象，代码如下：
public Object clone() {
try {
// 调用父类，进行克隆
ArrayList<?> v = (ArrayList<?>) super.clone();
// 拷贝一个新的数组
v.elementData = Arrays.copyOf(elementData, size);
// 设置数组修改次数为 0
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
注意，elementData 是重新拷贝出来的新的数组，避免和原数组共享。
subList(int fromIndex, int toIndex) 方法，创建子数组，代码如下：
public List<E> subList(int fromIndex, int toIndex) {
// 参数检查
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, 0, fromIndex, toIndex);
}
static void subListRangeCheck(int fromIndex, int toIndex, int size) {
if (fromIndex < 0)
throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
if (toIndex > size)
throw new IndexOutOfBoundsException("toIndex = " + toIndex);
if (fromIndex > toIndex)
throw new IllegalArgumentException("fromIndex(" + fromIndex +
") > toIndex(" + toIndex + ")");
}
// 内部类
private class SubList extends AbstractList<E> implements RandomAccess {
/**
* 根 ArrayList
*/
private final AbstractList<E> parent;
/**
* 父 SubList
*/
private final int parentOffset;
/**
* 起始位置
*/
private final int offset;
/**
* 大小
*/
int size;
SubList(AbstractList<E> parent,
int offset, int fromIndex, int toIndex) {
this.parent = parent;
this.parentOffset = fromIndex;
this.offset = offset + fromIndex;
this.size = toIndex - fromIndex;
this.modCount = ArrayList.this.modCount;
}
}
实际使用时，一定要注意，SubList 不是一个只读数组，而是和根数组 root 共享相同的 elementData 数组，只是说限制了 [fromIndex, toIndex) 的范围。
iterator() 方法，创建迭代器。一般情况下，我们使用迭代器遍历 ArrayList、LinkedList 等等 List 的实现类。代码如下：
// 创建迭代器
public Iterator<E> iterator() {
return listIterator();
}
创建 Itr 迭代器。Itr 实现 java.util.Iterator 接口，是 ArrayList 的内部类。虽然说 AbstractList 也提供了一个 Itr 的实现，但是 ArrayList 为了更好的性能，所以自己实现了，在其类上也有注释“An optimized version of AbstractList.Itr”。
Itr 一共有三个属性，如下：
private class Itr implements Iterator<E> {
/**
* 下一个访问元素的位置，从下标 0 开始。
*/
int cursor; // index of next element to return
/**
* 上 一次访问元素的位置。
*
* 1. 初始化为 -1 ，表示无上一个访问的元素
* 2. 遍历到下一个元素时，lastRet 会指向当前元素，而 cursor 会指向下一个元素。这样，如果我们要实现 remove 方法，移除当前元素，就可以实现了。
* 3. 移除元素时，设置为 -1 ，表示最后访问的元素不存在了，都被移除咧。
*/
int lastRet = -1; // index of last element returned; -1 if no such
/**
* 创建迭代器时，数组修改次数。
*
* 在迭代过程中，如果数组发生了变化，会抛出 ConcurrentModificationException 异常。
*/
int expectedModCount = modCount;
}
下面，让我们来看看 Itr 对 Iterator 的 4 个实现方法。
#hasNext() 方法，判断是否还可以继续迭代。代码如下：
public boolean hasNext() {
return cursor != size;
}
cursor 如果等于 size ，说明已经到数组末尾，无法继续迭代了。
#next() 方法，下一个元素。代码如下：
public E next() {
// 校验是否数组发生了变化
checkForComodification();
// 判断如果超过 size 范围，抛出 NoSuchElementException 异常
int i = cursor; // <1> i 记录当前 cursor 的位置
if (i >= size)
throw new NoSuchElementException();
// 判断如果超过 elementData 大小，说明可能被修改了，抛出 ConcurrentModificationException 异常
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
// <2> cursor 指向下一个位置
cursor = i + 1;
// <3> 返回当前位置的元素
return (E) elementData[lastRet = i]; // <4> 此处，会将 lastRet 指向当前位置
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
<1> 处，记录当前 cursor 的位置。因为我们当前返回的就是要求 cursor 位置的元素。
<2> 处，cursor 指向下一个位置。
<3> 处，返回当前位置的元素。同时在 <4> 处，会将 lastRet 指向当前位置。
#remove() 方法，移除当前元素。代码如下：
// ArrayList.java#Itr
public void remove() {
// 如果 lastRet 小于 0 ，说明没有指向任何元素，抛出 IllegalStateException 异常
if (lastRet < 0)
throw new IllegalStateException();
// 校验是否数组发生了变化
checkForComodification();
try {
// <1> 移除 lastRet 位置的元素
ArrayList.this.remove(lastRet);
// <2> cursor 指向 lastRet 位置，因为被移了，所以需要后退下
cursor = lastRet;
// <3> lastRet 标记为 -1 ，因为当前元素被移除了
lastRet = -1;
// <4> 记录新的数组的修改次数
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
<1> 处，调用 #remove(int index) 方法，移除 lastRet 位置的元素。所以，如果要注意，如果移除元素比较前面，会将后面位置的往前挪，即复制，可能比较消耗性能。
<2> 处，cursor 指向 lastRet 位置，因为被移了，所以需要后退下。
<3> 处，lastRet 标记为 -1 ，因为当前元素被移除了。
<4> 处，记录新的数组的修改次数。因为此处修改了数组，如果不修改下，后续迭代肯定会报错。
#forEachRemaining(Consumer action) 方法，消费剩余未迭代的元素。代码如下：
// ArrayList.java#Itr
@Override
public void forEachRemaining(Consumer<? super E> action) {
// 要求 action 非空
Objects.requireNonNull(action);
// 获得当前数组大小
final int size = ArrayList.this.size;
// 记录 i 指向 cursor
int i = cursor;
if (i < size) {
// 判断如果超过 elementData 大小，说明可能被修改了，抛出 ConcurrentModificationException 异常
final Object[] es = elementData;
if (i >= es.length)
throw new ConcurrentModificationException();
// 逐个处理
for (; i < size && modCount == expectedModCount; i++)
action.accept(elementAt(es, i));
// update once at end to reduce heap write traffic
// 更新 cursor 和 lastRet 的指向
cursor = i;
lastRet = i - 1;
// 校验是否数组发生了变化
checkForComodification();
}
}
可能一些胖友不了解 ListIterator 迭代器，因为平时使用不多。可以先去看看 《Java 集合框架之 Iterator 和 ListIterator》 。简单来说，ListIterator 是为 List 设计的，功能更强大的 Iterator 迭代器。
#listIterator(...) 方法，创建 ListIterator 迭代器。代码如下：
// ArrayList.java
public ListIterator<E> listIterator(int index) {
rangeCheckForAdd(index);
return new ListItr(index);
}
public ListIterator<E> listIterator() {
return new ListItr(0);
}
创建 ListItr 迭代器。ListItr 实现 java.util.ListIterator 接口，是 ArrayList 的内部类。虽然说 AbstractList 也提供了一个 ListItr 的实现，但是 ArrayList 为了更好的性能，所以自己实现了，在其类上也有注释“An optimized version of AbstractList.ListItr”。
ListItr 直接继承 Itr 类，无自定义的属性。代码如下：
// ArrayList.java#ListItr
ListItr(int index) {
super();
cursor = index;
}
可以手动设置指定的位置开始迭代。
// ArrayList.java#ListItr
/**
* @return 是否有前一个
*/
public boolean hasPrevious() {
return cursor != 0;
}
/**
* @return 下一个位置
*/
public int nextIndex() {
return cursor;
}
/**
* @return 前一个位置
*/
public int previousIndex() {
return cursor - 1;
}
/**
* @return 前一个元素
*/
@SuppressWarnings("unchecked")
public E previous() {
// 校验是否数组发生了变化
checkForComodification();
// 判断如果小于 0 ，抛出 NoSuchElementException 异常
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
// 判断如果超过 elementData 大小，说明可能被修改了，抛出 ConcurrentModificationException 异常
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
// cursor 指向上一个位置
cursor = i;
// 返回当前位置的元素
return (E) elementData[lastRet = i]; // 此处，会将 lastRet 指向当前位置
}
/**
* 设置当前元素
*
* @param e 设置的元素
*/
public void set(E e) {
// 如果 lastRet 无指向，抛出 IllegalStateException 异常
if (lastRet < 0)
throw new IllegalStateException();
// 校验是否数组发生了变化
checkForComodification();
try {
// 设置
ArrayList.this.set(lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
/**
* 添加元素当当前位置
*
* @param e 添加的元素
*/
public void add(E e) {
// 校验是否数组发生了变化
checkForComodification();
try {
// 添加元素到当前位置
int i = cursor;
ArrayList.this.add(i, e);
// cursor 指向下一个位置，因为当前位置添加了新的元素，所以需要后挪
cursor = i + 1;
// lastRet 标记为 -1 ，因为当前元素并未访问
lastRet = -1;
// 记录新的数组的修改次数
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
#spliterator()#removeIf(Predicate filter)#replaceAll(UnaryOperator operator)#sort(Comparator c)#forEach(Consumer action)下面，我们来对 ArrayList 做一个简单的小结：
[] 数组实现的 List 实现类，支持在数组容量不够时，一般按照 1.5 倍自动扩容。同时，它支持手动扩容、手动缩容。下一篇：Java 集合框架 - 链表 LinkedList
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。