文档章节

ArrayList扩容分析

m
 modprobe
发布于 2016/11/08 09:57
字数 455
阅读 4
收藏 0

一段java代码

1 String e = "q3234v";
2 List<String> list = new ArrayList<String>();
3 for (int i = 0; i < 25; i++) {
4     list.add(e);
5 }

执行这段代码,list会扩容几次

查看ArrayList的add方法,在添加元素之前会执行ensureCapacityInternal方法

这个时候size为0

1   public boolean add(E e) {
2         ensureCapacityInternal(size + 1);  // Increments modCount!!
3         elementData[size++] = e;
4         return true;
5     }

 

继续看ensureCapacityInternal方法,DEFAULT_CAPACITY的值为10,此时minCapacity为1

private static final int DEFAULT_CAPACITY = 10;

 

1 private void ensureCapacityInternal(int minCapacity) {
2     if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
3         minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
4     }
5     ensureExplicitCapacity(minCapacity);
6 }

这时候执行:ensureExplicitCapacity

此时minCapacity的值为10,接下来执行扩容方法

1 private void ensureExplicitCapacity(int minCapacity) {
2     modCount++;
3     // overflow-conscious code
4     if (minCapacity - elementData.length > 0)
5         grow(minCapacity);
6 }

 

 

 1  private void grow(int minCapacity) {
 2         // overflow-conscious code
 3         int oldCapacity = elementData.length;
 4         int newCapacity = oldCapacity + (oldCapacity >> 1);
 5         if (newCapacity - minCapacity < 0)
 6             newCapacity = minCapacity;
 7         if (newCapacity - MAX_ARRAY_SIZE > 0)
 8             newCapacity = hugeCapacity(minCapacity);
 9         // minCapacity is usually close to size, so this is a win:
10         System.out.println(minCapacity+"------"+newCapacity);
11 
12         elementData = Arrays.copyOf(elementData, newCapacity);
13 }

minCapacity的值为10

新空间大小的值为 0+0>>1 = 0

所以第一次扩容完 后新空间大小为10

接下当list.add()执行到第11次的时候

minCapacity=11

newCapacity = 10+10>>1 = 15(1010>>1 = 101= 5)

i执行到16的时候,此时又发现空间不够了

minCapacity=16

newCapacity = 15+15>>1 = 22(1111>>1 = 7)

所以容量到25还需要再执行一次扩容

一共会执行4次扩容

这时候可能会发现在扩容的时候会执行 elementData = Arrays.copyOf(elementData, newCapacity)方法

所以为了减少copyOf的操作

在大概知道List的长度的情况下,在创建的时候应该给一个容量,在容量不够的情况下才会执行扩容操作

 1 public ArrayList(int initialCapacity) {
 2         if (initialCapacity > 0) {
 3             this.elementData = new Object[initialCapacity];
 4         } else if (initialCapacity == 0) {
 5             this.elementData = EMPTY_ELEMENTDATA;
 6         } else {
 7             throw new IllegalArgumentException("Illegal Capacity: "+
 8                                                initialCapacity);
 9         }
10     }

 

本文转载自:http://www.cnblogs.com/modprobe/p/4522448.html

共有 人打赏支持
m
粉丝 1
博文 35
码字总数 0
作品 0
私信 提问
Java版数据结构与算法(二):基于数组的实现ArrayList源码彻底分析

版权声明:本文出自汪磊的博客,未经作者允许禁止转载。 本片我们分析基础数组的实现--ArrayList,不会分析整个集合的继承体系,这不是本系列文章重点。 源码分析都是基于"安卓版"的源码,和j...

WangLei_ClearHeart
2018/08/01
0
0
ArrayList (JDK8) 源码解析

ArrayList 源码解析 概述 ArrayList 是一个动态数组,容量可以动态增长。他是线程不安全的,允许元素为null。它的底层数据结构是数组,所以会占用一块连续的内存空间。它实现了 接口。 代表L...

sun_____xin
2018/04/04
0
0
Java集合容器系列02-ArrayList

一、ArrayList介绍 ArrayList是内部基于动态数组的List实现,他继承AbstractList抽象类,并实现了List,RandomAccess,Cloneable和java.io.Serializable。它实现了List接口定义的所有方法,允...

老韭菜
2018/07/24
0
0
ArrayList源码分析

java中的数据结构源码分析的系列文章: ArrayList源码分析 LinkedList源码分析 一、简述 我们知道,数据结构中有两种存储结构,分别是:顺序存储结构(线性表)、链式存储结构(链表),在j...

CSDN_LQR
2017/11/08
0
0
ArrayList 源码分析 -- 扩容问题及序列化问题

目录 一、前言 二、ArrayList 的继承与实现关系 2.1 ArrayList.java 2.2 抽象类AbstractList.java 2.3 接口List.java 2.4 接口RandomAccess.java 2.5 接口Cloneable 2.6 接口Serializable 三......

niaonao
2018/08/16
0
0

没有更多内容

加载失败,请刷新页面

加载更多

聊聊flink的Table API及SQL Programs

序 本文主要研究一下flink的Table API及SQL Programs 实例 // for batch programs use ExecutionEnvironment instead of StreamExecutionEnvironmentStreamExecutionEnvironment env = Stre......

go4it
25分钟前
1
0
mysqldump应用

备份单个库/表数据或库/表结构 命令行下具体用法如下: mysqldump -u用戶名 -p密码 -d 数据库名 表名 > 备份文件名 1、导出数据库为dbname的表结构(其中用戶名為root,密码为dbpasswd,生成的...

阿dai
33分钟前
1
0
shell脚本与Python的交互

1、Python针对shell获取传入,输出参数 传入:"$num" 例如: $0表示文件名,$1表示shell获取的第一个参数 输出:通过打印shell结果的方式,输出参数给Python。 例如: echo "{$iplist}",Python调...

一口今心
35分钟前
1
0
Euler 今日问世!国内首个工业级的图深度学习开源框架,阿里妈妈造

阿里妹导读:千呼万唤始出来!阿里妈妈正式公布重磅开源项目——图深度学习框架Euler。这是国内首个在核心业务大规模应用后开源的图深度学习框架。此次开源,Euler内置了大量的算法供用户直接...

阿里云官方博客
42分钟前
1
0
TiDB 3.0 Beta Release Notes

2019 年 1 月 19 日,TiDB 发布 3.0 Beta 版,对应 master branch 的 TiDB-Ansible。相比 2.1 版本,该版本对系统稳定性、优化器、统计信息以及执行引擎做了很多改进。 TiDB 新特性 支持 Vi...

TiDB
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部