ArrayList源码解析

我会带着你远行 2022-03-29 04:31 378阅读 0赞

# 1.类图 #

文章使用的源码是JDK 1.8.0\_181版本

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xldF9tZV90ZWxsX3lvdQ_size_16_color_FFFFFF_t_70][]

分析主要从下面几个点入手：

1.  体系结构
2.  构造方法
3.  和LinkedList，Vector的区别
4.  扩容

# 2.ArrayList的体系结构 #

ArrayList直接实现了下面这几个接口：

1.  List         有序集合接口，定义了一些基础方法，自实现了sort方法和replaceAll方法

1.  RandomAccess  标记接口，实现这个接口可以实现快速随机访问
2.  Cloneable       用来重写clone方法
3.  java.io.Serializable  序列化接口
4.  继承AbstractList

# 3.构造方法 #

## 字段属性 ##

ArrayList提供了三个构造方法，在解析这几个构造方法之前，需要先说一下ArrayList中的几个重要的属性。

/**
         * Default initial capacity.
    	   默认初始容量
         */
        private static final int DEFAULT_CAPACITY = 10;
    
        /**
         * Shared empty array instance used for empty instances.
    		用于空实例的共享空数组实例。
         */
        private static final Object[] 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.
    	 
    	 用于默认大小的空实例的共享空数组实例。 我们将此与EMPTY_ELEMENTDATA区分开来，以便了解在添加第一个元素时要膨胀多少。
         */
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
        /**
         * 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.
    	 存储ArrayList元素的数组缓冲区.ArrayList的容量是此数组缓冲区的长度。添加第一个元素时，任何带有elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空ArrayList都将扩展为DEFAULT_CAPACITY。
    	 这个数组是ArrayList对象实际保存数据的地方
         */
        transient Object[] elementData; // 非私有，以简化嵌套类访问
    
        /**
         * The size of the ArrayList (the number of elements it contains).
         *	ArrayList的大小（它包含的元素数）。
         * @serial
         */
        private int size;

## 无参构造 ##

![2019010723154651.png][]

这个构造方法对应的实例化方法是下面这种写法，也是最常见的写法。

![20190107231553105.png][]

### 方法逻辑 ###

无参构造里对elementData数组进行实例化，将elementData数组指向常量空数组DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA，长度为0，当第一次添加数据时，数组的长度会变成10。

对象创建时的elementData数组的长度

![20190107231605876.png][]

添加一个元素之后elementData数组的长度

![20190107231613576.png][]

## 指定初始容量的构造方法 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xldF9tZV90ZWxsX3lvdQ_size_16_color_FFFFFF_t_70 1][]

对应下面这种写法：

![20190107231628212.png][]

### 方法逻辑 ###

指定长度如果大于0，将elementData数组实例化为指定长度的数组。

指定长度如果等于0，将elementData指向长度为0的空数组常量。

指定长度如果小于0，抛出 IllegalArgumentException 异常

指定长度初始化之后elementData数组的长度：

![20190107231636573.png][]

添加元素之后elementData数组的长度：

![20190107231640893.png][]

可以看到指定长度初始化的ArrayList对象在添加元素之后elementData数组长度也不会变化。

## 使用Collection对象构造 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xldF9tZV90ZWxsX3lvdQ_size_16_color_FFFFFF_t_70 2][]

这种写法比较多，这里给出一个简单的例子

![20190107231706915.png][]

### 方法逻辑 ###

传入一个实现了Collection接口的对象（下文简称为c），然后将这个对象转成数组，并且将elementData数组指向这个这个数组。然后判断elementData数组的长度是否等于0，如果不等于0，并且c.toArray()返回的不是Object\[\]对象，则把c的内容copy到elementData中。如果长度等于0，则将elementData指向一个空数组。

1.  1.  和LinkedList，Vector的区别

这是一个经典的面试题和笔试题。先说一下这三个集合类的相同点。

### 相同点： ###

1.  都实现了Collection，List，Serializable接口
2.  ArrayList和Vector都是使用数组存储数据
3.  都是有序集合
4.  ArrayList和LinkedList都是线程不安全的

### 不同点: ###

1.  ArrayList是基于动态数组的数据结构，LinkedList是基于双向链表数据结构
2.  Vector是线程安全的
3.  随机get和set时ArrayList 性能要优于LinkedList
4.  add和remove时LinkedList 性能要优于ArrayList

# 5.扩容 #

add方法的源码

![20190107231716487.png][]

可以看到在add方法之前调用了ensureCapacityInternal方法，传入的参数是size+1，size就是当前集合中的参数个数，可以确定这个方法就是扩容的方法了

![2019010723172497.png][]

![20190107231728974.png][]

![20190107231733309.png][]

在calculateCapacity 方法中先判断了elementData数组是否为空，如果为空判断则返回minCapacity 和10中最大的数值，如果不为空，则直接返回minCapacity。然后进入到ensureExplicitCapacity方法，对modCount做++操作，这个参数用于集合的Fail-Fast机制判断中。方法里判断新增元素之后大小是否超过当前集合元素个数，如果超过，则调用grow方法。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xldF9tZV90ZWxsX3lvdQ_size_16_color_FFFFFF_t_70 3][]

这个方法就是真正用于集合扩容的方法了，可以看到集合新容量的计算公式为：

新容量 = 现有容量 + 现有容量 / 2

如果新容量小于minCapacity ，则新长度等于minCapacity，如果新容量大于最大长度（2147483639），调用hugeCapacity 方法，传入参数为minCapacity，也就是数组扩容后需要最小容量。如果minCapacity大于MAX\_ARRAY\_SIZE，则返回Integer的最大值。否则返回MAX\_ARRAY\_SIZE。

![20190107231751460.png][]

![20190107231808634.png][]

![20190107231813630.png][]

调用完grow方法之后将elementData中的元素复制到一个新的大容量数组中。Arrays.copy方法是  System.arraycopy 方法。因为方法是native修饰的，所以无法查看源码。

![2019010723182115.png][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xldF9tZV90ZWxsX3lvdQ_size_16_color_FFFFFF_t_70]: /images/20220329/38e0867a453f4fdeb8807305194a8d22.png
[2019010723154651.png]: /images/20220329/f249d0caf9e94a02ab9a97cef4f94cd4.png
[20190107231553105.png]: /images/20220329/095892eab22947b392493aadedc9e784.png
[20190107231605876.png]: /images/20220329/28aca25cd8d04dcf878bf4ce2aeb5d5b.png
[20190107231613576.png]: /images/20220329/21154230ccdd45e0a598cfe6a87aac2f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xldF9tZV90ZWxsX3lvdQ_size_16_color_FFFFFF_t_70 1]: /images/20220329/b70a75f22e764bd9b521dcc9c9a84edf.png
[20190107231628212.png]: /images/20220329/b7958288cdb14194935c7f815efcb709.png
[20190107231636573.png]: /images/20220329/8acce9681faa46aaae6648f0075cb017.png
[20190107231640893.png]: /images/20220329/4b458f0e00f1466b9af8c90d8712ad41.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xldF9tZV90ZWxsX3lvdQ_size_16_color_FFFFFF_t_70 2]: /images/20220329/f23f60dee65041dcb0690eafafd3e234.png
[20190107231706915.png]: /images/20220329/d56d9650a0514ed49c0e8258c9472f67.png
[20190107231716487.png]: /images/20220329/ea02ba63054747fe8c27adafa33c4850.png
[2019010723172497.png]: /images/20220329/e7383ea983994197a184d5462e4319fd.png
[20190107231728974.png]: /images/20220329/0bb55016814a4d8ab7bdd1e75f9a2bd6.png
[20190107231733309.png]: /images/20220329/f4a02f29005f44b6af5d170ca8140a39.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xldF9tZV90ZWxsX3lvdQ_size_16_color_FFFFFF_t_70 3]: /images/20220329/af18c6295958466f9dc34e23c05e4052.png
[20190107231751460.png]: /images/20220329/d1f424c0703949cfb4e25733da58ef7b.png
[20190107231808634.png]: /images/20220329/7d204dc69655476386d155d337c754da.png
[20190107231813630.png]: /images/20220329/26b5768efadd4a14bc6637c6a924fd48.png
[2019010723182115.png]: /images/20220329/bc2aa07084504d04a9c61f81190b61ca.png