ArrayList简介
ArrayList 的底层是数组队列，相当于动态数组。与 Java 中的数组相比，它的容量能动态增长。在添加大量元素前，应用程序可以使用ensureCapacity操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。
它继承于 AbstractList，实现了 List, RandomAccess, Cloneable, java.io.Serializable 这些接口。
在我们学数据结构的时候就知道了线性表的顺序存储，插入删除元素的时间复杂度为O（n）,求表长以及增加元素，取第 i 元素的时间复杂度为O（1）
ArrayList 继承了AbstractList，实现了List。它是一个数组队列，提供了相关的添加、删除、修改、遍历等功能。
ArrayList 实现了RandomAccess 接口， RandomAccess 是一个标志接口，表明实现这个这个接口的 List 集合是支持快速随机访问的。在 ArrayList 中，我们即可以通过元素的序号快速获取元素对象，这就是快速随机访问。
ArrayList 实现了Cloneable 接口，即覆盖了函数 clone()，能被克隆。
ArrayList 实现java.io.Serializable 接口，这意味着ArrayList支持序列化，能通过序列化去传输。
和 Vector 不同，ArrayList 中的操作不是线程安全的！所以，建议在单线程中才使用 ArrayList，而在多线程中可以选择 Vector 或者 CopyOnWriteArrayList。
ArrayList核心源码
1 | package java.util; |
ArrayList源码分析
System.arraycopy()和Arrays.copyOf()方法
通过上面源码我们发现这两个实现数组复制的方法被广泛使用而且很多地方都特别巧妙。比如下面add(int index, E element)方法就很巧妙的用到了arraycopy()方法让数组自己复制自己实现让index开始之后的所有成员后移一个位置:
1 | /** |
又如toArray()方法中用到了copyOf()方法
1 |
|
两者联系与区别
联系：
看两者源代码可以发现copyOf()内部调用了System.arraycopy()方法
区别：
- arraycopy()需要目标数组，将原数组拷贝到你自己定义的数组里，而且可以选择拷贝的起点和长度以及放入新数组中的位置
- copyOf()是系统自动在内部新建一个数组，并返回该数组。
ArrayList 核心扩容技术
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38//下面是ArrayList的扩容机制
//ArrayList的扩容机制提高了性能，如果每次只扩充一个，
//那么频繁的插入会导致频繁的拷贝，降低性能，而ArrayList的扩容机制避免了这种情况。
/**
* 如有必要，增加此ArrayList实例的容量，以确保它至少能容纳元素的数量
* @param minCapacity 所需的最小容量
*/
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);
}
}
//得到最小扩容量
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 获取默认的容量和传入参数的较大值
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
//判断是否需要扩容,上面两个方法都要调用
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 如果说minCapacity也就是所需的最小容量大于保存ArrayList数据的数组的长度的话，就需要调用grow(minCapacity)方法扩容。
//这个minCapacity到底为多少呢？举个例子在添加元素(add)方法中这个minCapacity的大小就为现在数组的长度加1
if (minCapacity - elementData.length > 0)
//调用grow方法进行扩容，调用此方法代表已经开始扩容了
grow(minCapacity);
}扩容机制代码已经做了详细的解释。另外值得注意的是大家很容易忽略的一个运算符：移位运算符1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22/**
* ArrayList扩容的核心方法。
*/
private void grow(int minCapacity) {
//elementData为保存ArrayList数据的数组
///elementData.length求数组长度elementData.size是求数组中的元素个数
// oldCapacity为旧容量，newCapacity为新容量
int oldCapacity = elementData.length;
//将oldCapacity 右移一位，其效果相当于oldCapacity /2，
//我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍，
int newCapacity = oldCapacity + (oldCapacity >> 1);
//然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量，
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//再检查新容量是否超出了ArrayList所定义的最大容量，
//若超出了，则调用hugeCapacity()来比较minCapacity和 MAX_ARRAY_SIZE，
//如果minCapacity大于MAX_ARRAY_SIZE，则新容量则为Interger.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE。
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);
}
简介：移位运算符就是在二进制的基础上对数字进行平移。按照平移的方向和填充数字的规则分为三种:<<(左移)、>>(带符号右移)和>>>(无符号右移)。
作用：对于大数据的2进制运算,位移运算符比那些普通运算符的运算要快很多,因为程序仅仅移动一下而已,不去计算,这样提高了效率,节省了资源
比如这里：int newCapacity = oldCapacity + (oldCapacity >> 1);
右移一位相当于除2，右移n位相当于除以 2 的 n 次方。这里 oldCapacity 明显右移了1位所以相当于oldCapacity /2。
另外需要注意的是：
java 中的length 属性是针对数组说的,比如说你声明了一个数组,想知道这个数组的长度则用到了 length 这个属性.
java 中的length()方法是针对字 符串String说的,如果想看这个字符串的长度则用到 length()这个方法.
.java 中的size()方法是针对泛型集合说的,如果想看这个泛型有多少个元素,就调用此方法来查看!
内部类
1 | (1)private class Itr implements Iterator<E> |
ArrayList有四个内部类，其中的Itr是实现了Iterator接口，同时重写了里面的hasNext()， next()， remove() 等方法；其中的ListItr 继承 Itr，实现了ListIterator接口，同时重写了hasPrevious()， nextIndex()， previousIndex()， previous()， set(E e)， add(E e) 等方法，所以这也可以看出了 Iterator和ListIterator的区别: ListIterator在Iterator的基础上增加了添加对象，修改对象，逆向遍历等方法，这些是Iterator不能实现的。
ArrayList经典Demo
1 | package list; |
一 先从 ArrayList 的构造函数说起
ArrayList有三种方式来初始化，构造方法源码如下：
1 | /** |
细心的同学一定会发现 ：以无参数构造方法创建 ArrayList 时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为10。 下面在我们分析 ArrayList 扩容时会讲到这一点内容！
二 一步一步分析 ArrayList 扩容机制
这里以无参构造函数创建的 ArrayList 为例分析
1. 先来看 add 方法
1 | /** |
2. 再来看看 ensureCapacityInternal() 方法
可以看到 add 方法 首先调用了ensureCapacityInternal(size + 1)
1 | //得到最小扩容量 |
当 要 add 进第1个元素时，minCapacity为1，在Math.max()方法比较后，minCapacity 为10。
3. ensureExplicitCapacity() 方法
如果调用 ensureCapacityInternal() 方法就一定会进过（执行）这个方法，下面我们来研究一下这个方法的源码！
1 | //判断是否需要扩容 |
我们来仔细分析一下：
- 当我们要 add 进第1个元素到 ArrayList 时，elementData.length 为0 （因为还是一个空的 list），因为执行了
ensureCapacityInternal()方法 ，所以 minCapacity 此时为10。此时，minCapacity - elementData.length > 0成立，所以会进入grow(minCapacity)方法。 - 当add第2个元素时，minCapacity 为2，此时e lementData.length(容量)在添加第一个元素后扩容成 10 了。此时，
minCapacity - elementData.length > 0不成立，所以不会进入 （执行）grow(minCapacity)方法。 - 添加第3、4···到第10个元素时，依然不会执行grow方法，数组容量都为10。
直到添加第11个元素，minCapacity(为11)比elementData.length（为10）要大。进入grow方法进行扩容。
4. grow() 方法
1 | /** |
int newCapacity = oldCapacity + (oldCapacity >> 1),所以 ArrayList 每次扩容之后容量都会变为原来的 1.5 倍！（JDK1.6版本以后） JDk1.6版本时，扩容之后容量为 1.5 倍+1！详情请参考源码
“>>”（移位运算符）：>>1 右移一位相当于除2，右移n位相当于除以 2 的 n 次方。这里 oldCapacity 明显右移了1位所以相当于oldCapacity /2。对于大数据的2进制运算,位移运算符比那些普通运算符的运算要快很多,因为程序仅仅移动一下而已,不去计算,这样提高了效率,节省了资源
我们再来通过例子探究一下grow() 方法 ：
- 当add第1个元素时，oldCapacity 为0，经比较后第一个if判断成立，newCapacity = minCapacity(为10)。但是第二个if判断不会成立，即newCapacity 不比 MAX_ARRAY_SIZE大，则不会进入
hugeCapacity方法。数组容量为10，add方法中 return true,size增为1。 - 当add第11个元素进入grow方法时，newCapacity为15，比minCapacity（为11）大，第一个if判断不成立。新容量没有大于数组最大size，不会进入hugeCapacity方法。数组容量扩为15，add方法中return true,size增为11。
- 以此类推······
这里补充一点比较重要，但是容易被忽视掉的知识点：
- java 中的
length属性是针对数组说的,比如说你声明了一个数组,想知道这个数组的长度则用到了 length 这个属性. - java 中的
length()方法是针对字符串说的,如果想看这个字符串的长度则用到length()这个方法. - java 中的
size()方法是针对泛型集合说的,如果想看这个泛型有多少个元素,就调用此方法来查看!
5. hugeCapacity() 方法。
从上面 grow() 方法源码我们知道： 如果新容量大于 MAX_ARRAY_SIZE,进入(执行) hugeCapacity() 方法来比较 minCapacity 和 MAX_ARRAY_SIZE，如果minCapacity大于最大容量，则新容量则为Integer.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 Integer.MAX_VALUE - 8。
1 | private static int hugeCapacity(int minCapacity) { |
三 System.arraycopy() 和 Arrays.copyOf()方法
阅读源码的话，我们就会发现 ArrayList 中大量调用了这两个方法。比如：我们上面讲的扩容操作以及add(int index, E element)、toArray() 等方法中都用到了该方法！
3.1 System.arraycopy() 方法
1 | /** |
我们写一个简单的方法测试以下：
1 | public class ArraycopyTest { |
结果：
1 | 0 1 99 2 3 0 0 0 0 0 |
3.2 Arrays.copyOf()方法
1 | /** |
个人觉得使用 Arrays.copyOf()方法主要是为了给原有数组扩容，测试代码如下：
1 | public class ArrayscopyOfTest { |
结果：
1 | 10 |
3.3 两者联系和区别
联系：
看两者源代码可以发现 copyOf() 内部实际调用了 System.arraycopy() 方法
区别：
arraycopy() 需要目标数组，将原数组拷贝到你自己定义的数组里或者原数组，而且可以选择拷贝的起点和长度以及放入新数组中的位置 copyOf() 是系统自动在内部新建一个数组，并返回该数组。
四 ensureCapacity方法
ArrayList 源码中有一个 ensureCapacity 方法不知道大家注意到没有，这个方法 ArrayList 内部没有被调用过，所以很显然是提供给用户调用的，那么这个方法有什么作用呢？
1 | /** |
最好在 add 大量元素之前用 ensureCapacity 方法，以减少增量重新分配的次数
我们通过下面的代码实际测试以下这个方法的效果：
1 | public class EnsureCapacityTest { |
运行结果：
1 | 使用ensureCapacity方法前：4637 |
通过运行结果，我们可以很明显的看出向 ArrayList 添加大量元素之前最好先使用ensureCapacity 方法，以减少增量重新分配的次数