源码：常用集合类之 ArrayList

系统管理员 2022-03-01 07:20 273阅读 0赞

### 文章目录 ###

*   *   *   *  0 前言
             *  1 属性的声明
             *  2 构造方法
             *  3 添加 add
             *  4 扩容 grow
             *  5 Arrays.copyOf
             *  6 指定位置添加 add
             *  7 删除 remove
             *  8 modCount是什么？

--------------------

#### 0 前言 ####

在开发过程中下面这段代码不知道写了多少次，是时候拨开它的外壳，看看内部构造了。

List<T> list = new ArrayList<>();

本文的代码片段均来自jdk1.8源码。

#### 1 属性的声明 ####

![声明][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70]  
每个变量都有详细注释，简单说一下：  
DEFAULT\_CAPACITY：默认容量为10，常量  
EMPTY\_ELEMENTDATA：空数组，常量  
DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA：默认容量的空数组，常量  
elementData：Object\[\]类型的引用，ArrayList的元素就是存在这个引用指向的实例中，用transient修饰表示不参与序列化  
size：用来表示含有元素的数量

#### 2 构造方法 ####

![无参构造][20190321220403965.png]  
无参构造很简单就是让elementData指向默认的空数组实例。  
![构造方法1][1]  
指定一个初始容量值来创建ArrayList。如果初始容量值n大于0，elementData为一个大小为n的数组，如果为0就是空数组EMPTY\_ELEMENTDATA，小于0则不合法抛异常。这里可以看到EMPTY\_ELEMENTDATA和DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA用在不同的地方。  
![构造方法2][2]  
最后这个构造方法，将Collection中的元素数组取出（toArray）给elementData，如果这个数组为空elementData还是指向EMPTY\_ELEMENTDATA，如果不为空并且类型不为Object\[\]时，底层通过调用本地方法返回一个Object\[\]数组。

#### 3 添加 add ####

![添加][20190321223835338.png]  
添加一个元素的时候首先调用了ensureCapacityInternal方法，计算容量  
![扩容][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 1]

a 假设使用无参构造的，elementData是DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA，这时候添加第一元素时，ensureCapacityInternal方法中的minCapacity参数为1，调用calculateCapacity方法计算出的容量为默认大小10。  
b 如果使用第二个构造方法指定了大小n，则直接返回n。

紧接着计算的容量大小作为参数，调用ensureExplicitCapacity方法，该方法使modCount值+1，后面会详细说这个变量。  
然后判断计算的容量大小是否已经超出了elementData数组大小范围，超过则需要调用grow方法扩容。

最后回到add方法，将元素添加到数组对应位置中，这里假设第一次调用add方法，则元素放在数组下标0的位置，然后size自增，表示有一个元素。

#### 4 扩容 grow ####

![扩容][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 2]  
来看看扩容的过程，用例子好理解一点：  
a 假设new ArrayList()创建的对象，那么根据上面add方法介绍可以知道，这时候计算出的容量为10，也就是这个方法的入参minCapacity为10,。先获取原有容量oldCapacity，由于elementData是个空数组，那么oldCapacity为0，newCapacity也0（位运算右移1位即为原值的0.5倍，再加上原值就是1.5倍），小于10，那么新容量就为10，最后使用Arrays.copyOf构建一个大小为10的Object数组。  
b 假设容量为10的ArrayList这时候要添加第11个元素，新容量为15。  
c hugeCapacity方法中显示最大容量为int最大值0x7fffffff。

**总结：每次调用add方法先会判断list容量是否足够，不够的话先扩容，然后再放入元素。另外如果使用无参构造方法实例对象时，第一次添加元素时，才会创建一个容量为10的数组，然后将元素放入。以后每次扩容总是变为原容量的1.5倍，直到达到最大容量2^31-1。**

#### 5 Arrays.copyOf ####

很多地方都用到了这个方法，下面贴出了方法内部实现：  
![在这里插入图片描述][20190322132253778.png]  
![在这里插入图片描述][20190322132305208.png]可以看到又创建了copy数组，使用System方法将原数组中元素复制到copy数组中  
![在这里插入图片描述][20190322132315481.png]System.arraycopy是一个native修饰的方法，表示调用本地方法实现，就是这个方法实现用C/C++实现，JVM运行通过加载共享库，完成库中本地方法调用。  
srcPos表示要从原数组那个下标位置开始copy，destPos表示copy到目标数组从哪个下标位置开始，length表示copy元素的个数。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 3]

#### 6 指定位置添加 add ####

![在这里插入图片描述][20190322135248679.png]  
知道了System.arraycopy方法执行结果，这段代码就很好理解了。先检查指定的下标是否在有效范围，然后检查是否需要扩容，然后将原数组index的位置之后的元素全部向后移一位，类似下面的表示，最后将新元素添加到index位。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 4]  
如果想更新index位置的元素需要使用set（index，e）方法，之前在项目开发时候搞错了这两个方法导致的bug，用了半天时间才定位到，o(╥﹏╥)o都是教训。

#### 7 删除 remove ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][20190322150050888.png]  
根据下标删除，同样还是检查下标是否有效，然后将数组对应位置元素取出，最后index之后的元素整体向前移动一位。将空位补齐。可以用下图表示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 7]  
再看根据元素删除，这里是在遍历元素过程中找到相同元素的下标然后根据下标删除。  
如果不是删除数组最后一个元素，这两种删除方式，每次都涉及到数组的中index位置之后的每个元素都移动一次。  
**总结：ArrayList中的remove方法和add（index）方法每次操作（除特殊情况），就会涉及分部元素的移动，这就是为什么总说ArrayList的修改效率慢的原因。如果知道元素位置，调用get（index）直接取出元素，所以说读取效率快。**（与LinkedList对比）

#### 8 modCount是什么？ ####

最初看了源码中注释也还是有点懵懵的，最后看了一下[Java中modCount的用法，fail-fast机制][Java_modCount_fail-fast]这篇文章。大致意思是这个参数表示list结构上被修改的次数，结构上的修改指的是那些改变了list的长度大小或者使得遍历过程中产生不正确的结果的其它方式。在线程不安全的集合中，在某些方法中，初始化迭代器时会给这个modCount赋值，如果在遍历的过程中，一旦发现这个对象的modCount和迭代器存储的modCount不一样，就会报错。举个栗子：

ArrayList<Double> list = new ArrayList<>();
            list.add(1d);
            list.add(2d);
            list.add(3d);
            list.add(4d);
    
            for (Double aDouble : list) {
                if (aDouble%2 == 0) {
                    list.remove(aDouble);
                }
            }

这段我曾亲手写出来的代码，运行报错如下：

Exception in thread "main" java.util.ConcurrentModificationException
    	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
    	at java.util.ArrayList$Itr.next(ArrayList.java:859)

for-each底层也是使用迭代器遍历元素的，从报错信息可以看到是调用Itr中的方法抛异常的，这里我摘了部分代码：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 8]![在这里插入图片描述][20190322164754546.png]

创建Itr对象时，先记录modCount的值，每遍历到一个元素时都会检查值是否发生改变，如果改变则抛出异常。就拿我的代码来说remove掉元素时，modCount值已经发生变化，取下一个元素时就会抛异常（名称为并发修改异常）。也就是说terator正在遍历的list时，不能修改list。  
改用fori遍历或者以下方式可以规避异常：

Iterator<Double> iterator = list.iterator();
            while(iterator.hasNext()) {
                if (iterator.next() %2 == 0) {
                    iterator.remove();
                }
            }

**最后说一下，ArrayList是线程不安全的，如果有线程安全问题可以用Vector，内部实现与ArrayList相似，其中方法都用synchronized修饰，所以效率肯定低。jdk1.5之后提供的CopyOnWriteArrayList类是线程安全的。**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70]: /images/20220301/187653d5ff6c4297a264c0d7feb0ba84.png
[20190321220403965.png]: /images/20220301/9737e9033ff648828c363b9b98b29849.png
[1]: /images/20220301/cc6aebaebdc34eb5ad4c716369ec7de7.png
[2]: /images/20220301/432854c1cfb14ac4be18c7455dfe417d.png
[20190321223835338.png]: /images/20220301/80eddc15acf64c18b4151e2e06758bb1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 1]: /images/20220301/3446fd6a0eab408db82ab59e79c6be59.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 2]: /images/20220301/d1ba60c38c7e4f97b89b84677f52a826.png
[20190322132253778.png]: /images/20220301/db99be1c906a483e9366db2ae0012f95.png
[20190322132305208.png]: /images/20220301/5bcc22cfa0fd47fb94a4ee76f3fc6651.png
[20190322132315481.png]: /images/20220301/3a68be20a8fb4c0b9c8551e20757a898.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 3]: /images/20220301/b75aec7cff554cdabfe19d188707b96c.png
[20190322135248679.png]: /images/20220301/9b8baf04e3404020aaca19dbc900ad0b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 4]: /images/20220301/6153d1ad6f89479cb71f5e5c005c31b8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 5]: /images/20220301/3ac3b195f322477c98bccd8badee4993.png
[20190322150050888.png]: /images/20220301/802a36b822394ee8b001594fa06aaffb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 6]: /images/20220301/b3dc6ed4f4514e58b5a3e36aba79326a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 7]: /images/20220301/44b4e8d9b24b4c58b4cb05f8ccfd5ab9.png
[Java_modCount_fail-fast]: https://blog.csdn.net/weixin_39800144/article/details/80613738
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20190322164656715.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c=,size_16,color_FFFFFF,t_70
[20190322164754546.png]: /images/20220301/3928b7576c7d42009956c7f7a4313d5f.png