专栏首页程序猿杂货铺【集合详解】ArrayList 源码解读之动态扩容

【集合详解】ArrayList 源码解读之动态扩容

本文所使用的 JDK 版本:1.8.0_144

ArrayList 是一个 Java 集合,它的底层数据结构实际上就是一个数组,只不过这个数组长度不固定,动态可变,其中数组元素的类型是 Object 类型的,可以说对 ArrayList 的所有操作底层都是基于数组的。

在阿里巴巴 Java 开发手册第 25 页有这么一句话:

【推荐】在集合初始化时,指定集合初始值大小 阿里巴巴 Java 开发手册

哪么,你有没有想过是为什么呢?大家稍安勿躁,我们先来一个比较有趣的测试:往指定初始化大小的 ArrayList 和 未指定大小的 ArrayList 中填充元素,比较其性能孰优孰劣。

集合性能测试

使用如下测试代码:

测试结果如下:

可以发现,随着集合元素的增加,设置了初始化大小的 ArrayList 在性能上会比没有设置初始化大小的 ArrayList 产生足足一个数量级的差距

为了深入了解一下为什么会出现这样的情况,我们需要先翻一翻 ArrayList 的源码,看下它底层到底是怎么实现的。

初始化

通过查看源码,发现有以下三个构造方法:

  • 用指定的大小来初始化内部数组
public ArrayList(int initialCapacity) 
  • 默认构造器,以默认大小来初始化内部数组
public ArrayList()
  • 接收一个 Collection 对象,并将该集合的元素添加到 ArrayList 中
public ArrayList(Collection<? extends E> c)

动态扩容

以无参构造器为例,ArrayList 内部数组初始长度为 0,源码如下:

其中,方法 ensureCapacityInternal(size+1)是为了保证内部容量,通过判断,当内部容量不足时则进行扩容操作;

这里有两个点需要注意一下:

  • 方法 ensureCapacityInternal() 的参数 size 表示的是在执行添加元素之前的数组元素个数,而不是 ArrayList 的具体容量;
  • ArrayList 的容量本质上是 elementData 数组的长度;

1

确保内部容量

先判断 ArrayList 是否需要扩容:

private static final int DEFAULT_CAPACITY = 10;private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private void ensureCapacityInternal(int minCapacity) {    // 如果 elementData 数组是一个空数组的话,最小需要容量就是默认容量    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);    }
    ensureExplicitCapacity(minCapacity);}
private void ensureExplicitCapacity(int minCapacity) {    modCount++;    // 如果elementData 数组的长度小于最小需要的容量(minCapacity),则进行扩容    // overflow-conscious code    if (minCapacity - elementData.length > 0)        // 扩容方法        grow(minCapacity);}

简而言之,当传入的最小需要容量(也就是数组中的实际元素个数加 1 )大于等于数组容量的时候,就需要进行扩容。

2

扩容

紧接着我们继续看它底层到底是如何扩容的,详细扩容方式参见以下源码注释:

/**     * The maximum size of array to allocate.     * Some VMs reserve some header words in an array.     * Attempts to allocate larger arrays may result in     * OutOfMemoryError: Requested array size exceeds VM limit     */private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {    // overflow-conscious code    int oldCapacity = elementData.length;    // 位运算,向右移动一位 (位运算右移意味着做除法,但是位运算效率更高)    // 用除法表示就相当于 newCapacity = oldCapacity + 0.5 * oldCapacity    // 也就是说 ArrayList 的扩容是每次 1.5 倍数扩容的    int newCapacity = oldCapacity + (oldCapacity >> 1);    if (newCapacity - minCapacity < 0)        // newCapacity 取 minCapacity 和 newCapacity 之间较大的一个值        newCapacity = minCapacity;    if (newCapacity - MAX_ARRAY_SIZE > 0)        // 此处对 MAX_ARRAY_SIZE 的值是 Integer.MAX_VALUE - 8        // 根据注释来看 是说 当数组长度超过 Integer.MAX_VALUE - 8 这个值之后有可能会发生 OutOfMemoryError 异常,但是为啥偏偏减了 8 这个值,尚待研究!        newCapacity = hugeCapacity(minCapacity);    // 元素复制     // minCapacity is usually close to size, so this is a win:    elementData = Arrays.copyOf(elementData, newCapacity);}

3

添加元素

当上述容量判断结束之后,真正开始添加元素到 elementData 数组中,就是 add(E e) 方法中的 elementData[size++]=e 这行代码。

另外可以得到一点,就是 ArrayList 在使用默认构造方法初始化的时候,会延迟分配数组对象空间,只有在第一次真正插入元素的时候才会去分配数组空间(默认初始空间大小是 DEFAULT_CAPACITY = 10)。

用代码说话

我们模拟往 ArrayList 中添加 20 个数据,根据以上我们对 ArrayList 源码的分析可以得出 ArrayList 的容量变化过程是:

  • 往 ArrayList 添加第一个元素的时候,ArrayList 会初始化内部的 elementData 数组,容量使用默认容量(默认容量值为 10);
  • 往 ArrayList 添加第 11 个元素的时候,容量不足(11 > 10),需要扩容,通过上节源码分析可得 ArrayList 是按照 1.5 倍进行扩容的,也就是说此时会扩容到 10 + 10 * 0.5 = 15;
  • 往 ArrayList 添加第 16 个元素的时候,容量再次不足(16 > 15),需要再次扩容,此次扩容结果是 15 + 15 * 0.5 = 22;

哪么实际的扩容结果是不是和我们分析的一致呢 ?请看如下实代码的实际测试结果:

  • 尚未开始添加数据的时候
  • 往 ArrayList 添加第一个元素的时候
  • 往 ArrayList 添加第 11 个元素的时候
  • 往 ArrayList 添加第 16 个元素的时候

综上:我们之前的分析结果是完全 ok 的哈,如果还是不太理解的话大家可以一步一步去亲手调试一下代码,看一下分别在第 10 、第 11、第 15、第 16 个元素添加到 ArrayList 时具体的容量变化,眼过千遍,不如手过一遍,毕竟只有自己撸到手的才算是自己的知识。

经过今天的学习之后,就会很容易理解文章最开始提到的哪个问题,为什么会建议在集合初始化的时候尽量指定大小?

因为在我们根据预估数据量大小之后,指定集合初始化大小,这样会减少扩容次数,进而提高代码执行效率!当然,如果实在不知道容量大小,直接使用默认构造方法即可。

总结

结合本文所述,对于 ArrayList 的自动扩容原理,概括起来就是以下几点:

  • ArrayList 通过无参构造的话,初始数组容量为 0 ;
  • ArrayList 通过无参构造的话,会延迟分配数组对象空间,只有在对数组真正开始添加元素时,才数组对象分配空间(默认初始容量值是 10);
  • 容量不足时每次按照 1.5 倍(位运算)的比率进行扩容;

本篇内容比较简单,如有错误也欢迎大家留言指出。常听大佬说看源码是相当好的一种学习方式,以前不觉得,随着工作越来越长时间,发现单纯的靠 CRUD 的业务代码的确是很难提高自己的编码水平,除非项目是非常具有挑战性的(当然大多数程序员的项目说白了没啥技术难度和挑战性,比如我... ...)。哪么我们就只有通过读源码的方式来学习,来提高自己的代码水平,长路漫漫,共勉吧!

本文分享自微信公众号 - 程序猿杂货铺(zhoudl_l),作者:zhoudl

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-05-28

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 为什么arrayList.removeAll(set)的速度远高于arrayList.removeAll(list)?

    我们知道,对于集合(Collection)都有一个抽象方法removeAll(Collection<?> c)!

    周三不加班
  • 重构一时爽,构错火葬场

    我相信每个接受过老项目的程序员可能都吐槽过 “前人的代码都是屎”。一个已经有些年头的项目,几乎肯定可以看到——到处拷贝来拷贝去的代码,随处可见的拼写错误,头重脚...

    周三不加班
  • 图解 SQL 里的各种 JOIN

    在各种问答社区里谈及 SQL 里的各种 JOIN 之间的区别时,最被广为引用的是 CodeProject 上 C.L. Moffatt 的文章 Visual R...

    周三不加班
  • 【008期】JavaSE面试题(八):集合之List

    大家好,我是Java面试题库的提裤姐,今天这篇是面试系列的第八篇,主要总结了JavaSE中集合相关面试题,集合面试分为四篇来讲,毕竟是重中之重!这是第一篇,主要...

    java进阶架构师
  • Java ArrayList的不同排序方法

    由于其功能性和灵活性,ArrayList是 Java 集合框架中使用最为普遍的集合类之一。ArrayList 是一种 List 实现,它的内部用一个动态数组来存...

    哲洛不闹
  • 【干货】用大白话聊聊JavaSE — ArrayList 深入剖析和Java基础知识详解(一)

    剽悍一小兔
  • 快速学习-什么是分布式文件系统

    分布式文件系统解决了海量文件存储及传输访问的瓶颈问题,对海量视频的管理、对海量图片的管理等。

    cwl_java
  • 「深度」VR一体机之路,核心在于生态

    镁客网
  • 一日一技:re.sub第二个参数使用函数

    在Python的正则表达式模块re中,我们常用的一个方法是 re.sub。它的作用是正则替换。我要把字符串 abc123xyz456中的数字替换为 *号(例如在...

    青南
  • 8266wifi模块开发详解(二)基本用法

    1. 文章说明2. 硬件电路2.1 外观介绍2.2 引脚分布3. 软件设计3.1 闪灯3.2 按键3.3 PWM3.4 SoftAP3.5 STA模式3.6 A...

    bigmagic

扫码关注云+社区

领取腾讯云代金券