Java ArrayList自动扩容机制
Java ArrayList自动扩容机制
动态扩容
1、add(E e)方法中
① ensureCapacityInternal(size+1),确保内部容量,size是添加前数组内元素的数量
② elementData[size++] = e 添加元素到相应位置,元素数量加1
2、 ensureCapacityInternal(size+1)确保内部容量
① 计算最小需要空间(如果传入的是个空数组则最小容量取默认容量与minCapacity之间的最大值)
② 判断是否需要扩容(如果最小需要空间比elementData的内存空间要大,则扩容)
3、扩容 grow(int minCapacity)
newCapacity=oldCapacity + (oldCapacity >> 1),原来元素数量的1.5倍
再与最小需要空间比较,与最大数组长度比较
一 初始化
先看一下ArrayList的两个构造方法
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } }
在无参构造中,我们看到了在用无参构造来创建对象的时候其实就是创建了一个空数组,长度为0
在有参构造中,传入的参数是正整数就按照传入的参数来确定创建数组的大小,否则异常
二 确保内部容量
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }
① ensureCapacityInternal方法名的英文大致是“确保内部容量”,size表示的是执行添加之前的元素个数,
并非ArrayList的容量,容量应该是数组elementData的长度。ensureCapacityInternal该方法通过将现有的元素个数与数组的容量比较。看如果需要扩容,则扩容。
②是将要添加的元素放置到相应的数组中。
可以看出ensureCapacityInternal()是用来扩容的,形参为最小扩容量,进入此方法后:
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); }
通过方法calculateCapacity(elementData, minCapacity)获取最小需要空间
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//如果传入的是个空数组则最小容量取默认容量与minCapacity之间的最大值 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; }
ensureExplicitCapacity方法可以判断是否需要扩容:
private void ensureExplicitCapacity(int minCapacity) {
modCount++; // 如果最小需要空间比elementData的内存空间要大,则需要扩容 if (minCapacity - elementData.length > 0) //扩容 grow(minCapacity); }
三 扩容
ArrayList扩容的关键方法grow():
private void grow(int minCapacity) {
// 获取到ArrayList中elementData数组的内存空间长度 int oldCapacity = elementData.length; // 扩容至原来的1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1); // 再判断一下新数组的容量够不够,够了就直接使用这个长度创建新数组, // 不够就将数组长度设置为需要的长度 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; //若预设值大于默认的最大值检查是否溢出 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // 调用Arrays.copyOf方法将elementData数组指向新的内存空间newCapacity的连续空间 // 并将elementData的数据复制到新的内存空间 elementData = Arrays.copyOf(elementData, newCapacity); }
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }
int newCapacity = oldCapacity + (oldCapacity >> 1);
oldCapacity >> 1 右移运算符 原来长度的一半 再加上原长度也就是每次扩容是原来的1.5倍
之前的所有都是确定新数组的长度,确定之后就是把老数组copy到新数组中,这样数组的扩容就结束了
每次扩容都是通过Arrays.copyOf(elementData, newCapacity) 这样的方式实现的。ArrayList的自动扩容机制底层借助于System实现System.arraycopy(0,oldsrc,0,newsrc,length);
扩展:System源码中的arraycopy()标识为native意味JDK的本地库,不可避免的会进行IO操作,如果频繁的对ArrayList进行扩容,毫不疑问会降低ArrayList的使用性能,因此当我们确定添加元素的个数的时候,我们可以事先知道并指定ArrayList的可存储元素的个数,这样当我们向ArrayList中加入元素的时候,就可以避免ArrayList的自动扩容,从而提高ArrayList的性能。
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
【译】Java SE 14 Hotspot 虚拟机垃圾回收调优指南
【译】Java SE 14 Hotspot 虚拟机垃圾回收调优指南 本文主要包括以下内容: 优化目标与策略(Ergonomics)垃圾收集器实现(Garbage Collector Implementation)影响垃圾收集性能的因素总堆(Total Heap)年轻代可用的收集器(Available Collectors)串行收集器(Serial Collector)并行收集器(Parallel Collector)G1收集器(Garbage-First Garbage Collector)Z收集器(The Z Garbage Collector)选择收集器并行收集器G1垃圾收集器启用G1基本概念G1内部细节G1 GC的默认选项与其它收集器的比较Z垃圾收集器其它考虑因素显式垃圾回收类元数据(Class Metadata)优化目标与策略(Ergonomics)垃圾收集器、堆和运行时编译器默认选择G1(Garbage First)收集器GC线程的最大值受限于堆大小和可用的CPU资源初始堆空间为物理内存的1/64最大堆空间为物理内存的1/4分层编译器,同时使用C1和C2可以将 Java Ho...
- 下一篇
Java后端应用架构方案的演化(架构优化)
前言 一个成熟的大型网站(如淘宝、天猫、腾讯等)的系统架构并不是一开始设计时就具备完整的高性能、高可用、高伸缩等特性的,它是随着用户量的增加,业务功能的扩展逐渐演变完善的,在这个过程中,开发模式、技术架构、设计思想也发生了很大的变化,就连技术人员也从几个人发展到一个部门甚至一条产品线。所以成熟的系统架构是随着业务的扩展而逐步完善的,并不是一蹴而就;不同业务特征的系统,会有各自的侧重点,例如:淘宝,要解决海量的商品信息的搜索、下单、支付,例如腾讯,要解决数亿用户的实时消息传输,百度它要处理海量的搜索请求,他们都有各自的业务特性,系统架构也有所不同。尽管如此我们也可以从这些不同的网站背景下,找出其中共用的技术,这些技术和手段广泛运用在大型网站系统的架构中,下面就通过介绍大型网站系统的演化过程,来认识这些技术和手段。 一、最开始的网站架构 最初的架构,应用程序、数据库、文件都部署在一台服务器上,如图: 上云采购 二、应用、数据、文件分离 随着业务的扩展,一台服务器已经不能满足性能需求,故将应用程序、数据库、文件各自部署在独立的服务器上,并且根据服务器的用途配置不同的硬件,达到最佳的性能效果。...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- CentOS7设置SWAP分区,小内存服务器的救世主
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7
- Linux系统CentOS6、CentOS7手动修改IP地址
- CentOS7,8上快速安装Gitea,搭建Git服务器
- CentOS8安装MyCat,轻松搞定数据库的读写分离、垂直分库、水平分库
- SpringBoot2整合Redis,开启缓存,提高访问速度
- MySQL8.0.19开启GTID主从同步CentOS8
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- Docker使用Oracle官方镜像安装(12C,18C,19C)