Java ArrayList扩容的原理

简介: Java 的 `ArrayList` 是基于数组实现的动态集合。初始时,`ArrayList` 底层创建一个空数组 `elementData`,并设置 `size` 为 0。当首次添加元素时,会调用 `grow` 方法将数组扩容至默认容量 10。之后每次添加元素时,如果当前数组已满,则会再次调用 `grow` 方法进行扩容。扩容规则为:首次扩容至 10,后续扩容至原数组长度的 1.5 倍或根据实际需求扩容。例如,当需要一次性添加 100 个元素时,会直接扩容至 110 而不是 15。

Java提供了Collection这个集合接口,可以用来作为数据的容器,其子接口分为单列集合List和双列集合Map,本文初略探索一下List集合下ArrayList的扩容原理。

创建时的elementData数组

首先,ArrayList的底层是用数组来实现的,看一下ArrayList的源码:

可以看到当我们创建一个ArrayList对象的时候,它会在底层创建一个名叫elementData的数组,并把DEFAULTCAPACITY_EMPTY_ELEMENTDATA这个用final修饰的空数组赋值给它——可见最开始创建ArrayList的时候是在底层创建了一个空数组的;源码可见,DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个空数组:

size的作用

随着ArrayList的实例化,类中的私有成员变量size被初始化为0,size是一个非常重要的变量,它有两个作用:1.记录当前集合的大小(长度);2.是下一个元素应该加入集合的索引(ArrayList是有索引的)。所以说创建ArrayList对象,size=0,集合此时的大小也是0,同时,下一个(也就是第一个元素)应该加入集合的索引也是0。当这些都准备好了之后,就可以开始加入元素了——

第一次加入元素

调用ArrayList中的add方法,传入想要加入集合的元素,然后接收到返回值(但ArrayList返回值没什么意义),元素就成功加入集合了。但数组的长度发生了什么变化?还是进入源码:

首先modCount这个变量会自增一次(这个变量是用来记录集合的操作次数的,对于扩容原理用处不大。)然后调用add的重载方法,这个方法需要三个参数——第1个参数是需要加入集合的元素,第2个参数是底层的element数组,第3个参数是size,size十分重要,代表了元素应该加入的索引和现在的集合大小(扩容的判断条件),然后就返回true了(可以看到add方法总是返回true,这也间接证明了add的返回值没有意义),现在进入add重载方法的源码:

这个add重载的方法,第1个参数是需要加入集合的元素,第2个参数是底层的element数组,第3个参数是size,进入方法,if语句判断size是否和现在的elementData的长度相等,因为是第一次加入元素,所以说size的值是0,elementData的长度也是0,所以说if会执行,会调用grow方法,而grow方法就是用来给elementList扩容的方法,

可以看见grow方法也是有重载方法的,给这个重载的grow方法传递的参数是size+1,那么继续跟进到grow的重载方法中:

这个重载的grow方法中的参数是minCapacity,其意义是“数组扩容后的最小容量”,现在数组扩容后的最小容量是1(size+1),有一个叫oldCapcity变量,用来记录ArrayList底层数组的长度,顾名思义,也就是老(数组)的容量,然后开始判断老容量(oldCapcity)是否大于0或者elementData数组是否不是一个空数组,很显然,是第一次加入集合,if不会执行,那么就会执行else中的语句:会返回一个新的数组,其容量是DEFAULT_CAPACITY和minCapacity中的较大值(DEFAULT_CAPACITY是一个常量,值为10),很显然,这次会返回一个大小为10的数组。 然后可以回到add方法中,当扩容结束后,就可以在size处加入元素了,加入之后,size会+1,因为此时的集合长度已经是1了,而且下一个要加入集合的元素应该加入的索引也是1。

后续添加的扩容

现在ArrayList中已经有了1个元素了,size也指向了1,elementData的大小也来到了10,所以说当我们再调用9次add方法,都是直接添加元素就成功了(此时是添加到第10个元素),不会涉及到扩容,但是当添加第11个元素的时候,此时的size等于10(相当于arrayList中有10个元素了,并且这次的元素应该添加到索引10),但是回顾add方法——此时的size和elementData的长度又相等了,所以说应该再次用grow方法扩容。

这次的grow方法传递的是size+1,也就是11。

重载的grow方法得到的minCapactiy是11,oldCapacity是10,然后开始判断if——显然oldCapacity是大于0的(这次的elementData也不是空数组,但是因为是||所以说直接就进入if了)。if里面会调用一个newLength方法给数组扩容(实际上是创建了一个新数组并且将原来的元素拷贝过去)里面的参数分别是oldCapacity(老容量);minGrowth(需要扩容的最小容量)——这个参数是数组扩容后的最小容量减去老容量;和oldCapacity>>1(将老容量右移1位)相当于将老容量/2。本次的参数分别是oldCapacity:10;minGrowth:11-10=11;;oldGrowth>>1:5,然后进入newLength的源码分析:

方法中的三个参数上文已经提及,这里不过多的赘述,prefLength(也就是第三个参数)默认是将老容量右移1位的值——也就是刚才传递的值5,但方法一开始就更新这个变量,更新为老容量加上minGrowth和prefGrowth的更大的值,显然prefGrowth更大,那么prefGrowth就被更新为15。进入if判断——prefGrowth>0(这个判断应该是为了防止扩容的大小是0而导致扩容失败)并且prefGrowth<SOFT_MAX_ARRAY_LENGTH这个常量(Integer的最大值-8),if条件满足,直接返回prefCapcity,此时elementData的长度就变为15了,然后再加入元素,“移动”size。

还有一件事

那么还有一件事,假如同时加入100个元素,是否还会将数组扩容成15?通过逻辑思考,这显然不现实,那么同时加入100个元素是如何扩容的呢?其实在newLength第一行就告诉了我们答案——方法第一步就是更新prefCapacity,将它变为老容量加上需要扩容的最小容量和理论上需要扩容的容量(oldCapacity>>1)的最大值,假如同时需要添加100个元素,那么需要扩容的最小容量就是100,而现在的elementData的oldCapacity是10,所以说理论上扩容的容量就是5,显然100远>5,所以说现在扩容的量就是10(oldCapacity)+100(minGrowth)=110

还有一个用于处理数组长度可能溢出的方法hugeLength(oldLength, minGrowth),当prefLenght的大小大于了SOFT_MAX_ARRAY_LENGTH这个常量(Integer的最大值-8)就会进入else,也就是进入了hugeLength(oldLength, minGrowth)方法(但是基本上不可能真用到这个方法吧?):

这个方法主要做了以下几件事:

  1. 计算最小所需长度minLength,即当前长度oldLength加上最小增长量minGrowth。
  2. 如果minLength小于0,说明发生了溢出,抛出OutOfMemoryError异常。
  3. 如果minLength小于等于SOFT_MAX_ARRAY_LENGTH,返回SOFT_MAX_ARRAY_LENGTH。
  4. 否则,返回minLength

总结

创建一个ArrayList对象时,底层先创建了一个长度为0的数组elementDate,创建变量size,size有两个作用:集合的长度(元素的个数)和下一个元素应该添加的位置添加一个元素其实有点复杂:如果现在的size≠数组的长度(数组没有存满),则直接在size所指的位置添加元素,然后size++但是若size=数组的长度(相当于已经存满了),那么就会调用ArrayList中的grow方法,先对数组进行扩容然后再存入元素。

数组扩容的原理:第一次添加元素的时候,数组长度是0,会用grow进行扩容,这时的扩容长度是10(设定的第一次扩容10),但是当10个元素存满之后,想要添加第11个元素,也会进行grow扩容,此刻算出至少需要扩容的长度是1,然后grow方法中可以计算出需要扩容1,然后grow有个默认扩容机制——将老容量左移1位作为扩容的大小,当需要扩容的大小小于默认扩容机制的时候,将使用默认的扩容机制扩容——新数组是原来的1.5倍(长度是原来的1.5倍);但是当需要扩容的长度大于了默认扩容的长度, 则以实际的长度为准。

举个例子:当默认长度为10的数组已经存满了,再想存元素,按理来说默认的扩容是将10扩容为15,但是假如想一次添加100个元素,15显然不够,这时就会以实际需要添加的元素为准,将其扩容为长度为110的数组,而不是默认的1.5倍长度的15的数组。


转载来源:https://juejin.cn/post/7395075429117329443

相关文章
|
1月前
|
存储 Java 关系型数据库
高效连接之道:Java连接池原理与最佳实践
在Java开发中,数据库连接是应用与数据交互的关键环节。频繁创建和关闭连接会消耗大量资源,导致性能瓶颈。为此,Java连接池技术通过复用连接,实现高效、稳定的数据库连接管理。本文通过案例分析,深入探讨Java连接池的原理与最佳实践,包括连接池的基本操作、配置和使用方法,以及在电商应用中的具体应用示例。
64 5
|
1月前
|
存储 算法 Java
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?
本文详解自旋锁的概念、优缺点、使用场景及Java实现。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?
|
1月前
|
Java
Java之CountDownLatch原理浅析
本文介绍了Java并发工具类`CountDownLatch`的使用方法、原理及其与`Thread.join()`的区别。`CountDownLatch`通过构造函数接收一个整数参数作为计数器,调用`countDown`方法减少计数,`await`方法会阻塞当前线程,直到计数为零。文章还详细解析了其内部机制,包括初始化、`countDown`和`await`方法的工作原理,并给出了一个游戏加载场景的示例代码。
Java之CountDownLatch原理浅析
|
1月前
|
存储 Java 索引
Java中的数据结构:ArrayList和LinkedList的比较
【10月更文挑战第28天】在Java编程世界中,数据结构是构建复杂程序的基石。本文将深入探讨两种常用的数据结构:ArrayList和LinkedList,通过直观的比喻和实例分析,揭示它们各自的优势与局限,帮助你在面对不同的编程挑战时做出明智的选择。
|
1月前
|
存储 Java 关系型数据库
在Java开发中,数据库连接是应用与数据交互的关键环节。本文通过案例分析,深入探讨Java连接池的原理与最佳实践
在Java开发中,数据库连接是应用与数据交互的关键环节。本文通过案例分析,深入探讨Java连接池的原理与最佳实践,包括连接创建、分配、复用和释放等操作,并通过电商应用实例展示了如何选择合适的连接池库(如HikariCP)和配置参数,实现高效、稳定的数据库连接管理。
58 2
|
1月前
|
Java 数据格式 索引
使用 Java 字节码工具检查类文件完整性的原理是什么
Java字节码工具通过解析和分析类文件的字节码,检查其结构和内容是否符合Java虚拟机规范,确保类文件的完整性和合法性,防止恶意代码或损坏的类文件影响程序运行。
40 5
|
1月前
|
算法 Java 数据库连接
Java连接池技术,从基础概念出发,解析了连接池的工作原理及其重要性
本文详细介绍了Java连接池技术,从基础概念出发,解析了连接池的工作原理及其重要性。连接池通过复用数据库连接,显著提升了应用的性能和稳定性。文章还展示了使用HikariCP连接池的示例代码,帮助读者更好地理解和应用这一技术。
48 1
|
2月前
|
存储 安全 Java
深入理解Java中的FutureTask:用法和原理
【10月更文挑战第28天】`FutureTask` 是 Java 中 `java.util.concurrent` 包下的一个类,实现了 `RunnableFuture` 接口,支持异步计算和结果获取。它可以作为 `Runnable` 被线程执行,同时通过 `Future` 接口获取计算结果。`FutureTask` 可以基于 `Callable` 或 `Runnable` 创建,常用于多线程环境中执行耗时任务,避免阻塞主线程。任务结果可通过 `get` 方法获取,支持阻塞和非阻塞方式。内部使用 AQS 实现同步机制,确保线程安全。
|
14天前
|
设计模式 Java 开发者
Java多线程编程的陷阱与解决方案####
本文深入探讨了Java多线程编程中常见的问题及其解决策略。通过分析竞态条件、死锁、活锁等典型场景,并结合代码示例和实用技巧,帮助开发者有效避免这些陷阱,提升并发程序的稳定性和性能。 ####
|
12天前
|
存储 监控 小程序
Java中的线程池优化实践####
本文深入探讨了Java中线程池的工作原理,分析了常见的线程池类型及其适用场景,并通过实际案例展示了如何根据应用需求进行线程池的优化配置。文章首先介绍了线程池的基本概念和核心参数,随后详细阐述了几种常见的线程池实现(如FixedThreadPool、CachedThreadPool、ScheduledThreadPool等)的特点及使用场景。接着,通过一个电商系统订单处理的实际案例,分析了线程池参数设置不当导致的性能问题,并提出了相应的优化策略。最终,总结了线程池优化的最佳实践,旨在帮助开发者更好地利用Java线程池提升应用性能和稳定性。 ####