死磕Jdk源码之ArrayList
:
本博客目前所有 死磕 Jdk 源码系列都是使用 jdk1.8
版本。
简介
List
接口的可调整大小的数组实现。实现所有可选的列表操作,并允许所有元素,包括null
。除了实现List
接口之外,该类还提供了一些方法来操作数组的大小,该数组在内部用于存储List
。(这个类大致相当于Vector
,只是它是不同步的。)size
、isEmpty
、get
、set
、iterator
和listIterator
操作在常数时间内运行。添加操作在平摊常数时间内运行,也就是说,添加n个元素需要O(n)个时间。所有其他操作都在线性时间内运行(粗略地说)。与LinkedList
实现相比,常量因子较低。
以上是官方docs对ArrayList
的描述
特性
ArrayList
实现List
,得到了List
集合框架基础功能ArrayList
实现RandomAccess
,获得了快速随机访问存储元素的功能,RandomAccess
是一个标记接口,没有任何方法ArrayList
实现Cloneable
,得到了clone()
方法,可以实现克隆功能ArrayList
实现Serializable
,表示可以被序列化,通过序列化去传输,典型的应用就是hessian
协议。
它具有如下特点:
- 容量不固定,随着容量的增加而动态扩容(阈值基本不会达到)
- 有序集合(插入的顺序 == 输出的顺序)
- 插入的元素可以为
null
- 增删改查效率更高(相对于
LinkedList
来说) - 线程不安全
数据结构
ArrayList
的底层数据结构就是一个数组,对ArrayList
的所有操作底层都是基于数组的。
线程安全性
如果非要在多线程的环境下使用ArrayList
,就需要保证它的线程安全性,通常有两种解决办法:
- 使用
synchronized
关键字 - 使用
Collections
类中的静态方法synchronizedList()
对ArrayList
进行调用即可。
成员变量
ArrayList
有两个关键的成员变量
还有一个记录集合修改次数的变量,由
iterator
和listIterator
,如果在迭代过程中,modCount
的值变更,就会抛出ConcurrentModificationException
异常。
1 | protected transient int modCount = 0; |
- elementData
存储
ArrayList
元素的数组缓冲区。ArrayList
的容量是这个数组缓冲区的长度。任何空ArrayList
与elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
,将在添加第一个元素时扩展为DEFAULT_CAPACITY
。
elementData
就是实际维护的数组,对于一个空ArrayList
来说,elementData
就是一个空数组。会在第一次add
元素时扩容为长度为DEFAULT_CAPACITY
的数组。
- size
ArrayList
的大小(它包含的元素的数量)。这里的size
指的是元素的个数,而不是数组的大小。
死磕源码
构造函数
无参构造函数,elementData 等于默认的空数组
1 | /** |
根据给定的初始化容量大小创建
ArrayList
1 | public ArrayList(int initialCapacity) { |
从一个
Collection
集合创建ArrayList
1 | public ArrayList(Collection<? extends E> c) { |
添加元素
ArrayList
提供两个方法添加单个元素,一个可以指定索引的添加元素方法,一个不需要指定索引的添加元素方法。
add(E e)
将指定的元素追加到此列表的末尾。
1 | public boolean add(E e) { |
在
ensureCapacityInternal
方法中对modCount
成员变量 +1,表示集合的修改次数,检查数组容量,是否需要扩容。
1 | private void ensureCapacityInternal(int minCapacity) { |
calculateCapacity
方法是为了计算最小扩容量
1 | private static int calculateCapacity(Object[] elementData, int minCapacity) { |
ensureExplicitCapacity
方法需要判断数组是否需要扩容
1 | private void ensureExplicitCapacity(int minCapacity) { |
grow方法,
ArrayList
扩容的核心方法。
1 | private void grow(int minCapacity) { |
add(int index, E element)
将指定元素插入其中的指定位置列表。移动当前处于该位置的元素(如果有)并向右的任何后续元素(将一个元素添加到它们的索引中)。
1 | public void add(int index, E element) { |
移除元素
remove(int index)
根据指定索引移除元素
1 | public E remove(int index) { |
remove(Object o)
从列表中删除指定元素的第一个匹配项
1 | public boolean remove(Object o) { |
与
remove(int index)
方法逻辑相同,只是这里没有进行索引检查,因为索引本来就是从数组中遍历出来的
1 | private void fastRemove(int index) { |
总结
ArrayList
底层维护一个数组ArrayList
默认数组是一个空数组{}
ArrayList
第一次添加元素时才会扩容到capacity
大小ArrayList
扩容为原容量到1.5
倍ArrayList
通过索引添加元素可能会导致内存拷贝ArrayList
移除元素可能需要内存拷贝
所以尽量不要使用索引去添加元素,索引添加元素的效率取决于索引的位置。理论上
size
-index
的值越大,效率越低,因为需要拷贝的元素越多。(移除元素同理)