文档章节

ArrayList扩容分析

m
 modprobe
发布于 2016/11/08 09:57
字数 455
阅读 4
收藏 0
点赞 0
评论 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
ArrayList (JDK8) 源码解析

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

sun_____xin
04/04
0
0
ArrayList源码分析

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

CSDN_LQR
2017/11/08
0
0
(周期计划-7)常用集合的源码分析:ArrayList

写在前面 最近因为拥抱变换,所以开始无奈的面试之路。因为在集合的源码分析上,出了些问题,所以这段时间,好好重新理一理常用的集合源码。(版本基于JDK1.7) ArrayList 毫无疑问,提到常用...

MDove
04/28
0
0
ArrayList、Vector、HashMap、HashSet的默认初始容量、加载因子、扩容增量

这里要讨论这些常用的默认初始容量和扩容的原因是: 当底层实现涉及到扩容时,容器或重新分配一段更大的连续内存(如果是离散分配则不需要重新分配,离散分配都是插入新元素时动态分配内存)...

小萝卜_
2016/12/10
92
0
Java集合之ArrayList源码解析

ArrayList是我们在开发中经常使用的一个集合,继续按照以前的风格来解析源码(JDK1.7)。 ArrayList简要概括: 1.ArrayList的底层数据结构是一个数组,确切地说是一个动态数组,每次扩容的时...

GeneralAndroid
2017/11/30
0
0
Java之ArrayList源码浅析

ArrayList特点 优点:有序,访问元素速度快. 缺点:插入,删除速度慢。 JDK1.8.131版本。 首先查看ArrayList实例化方法相关代码。 默认无参构造方法。elementData实际存放数据元素,从这些可以...

墨宇hz
06/26
0
0
集合操作(一)ArrayList,LinkedList源码分析

ArrayList: 构造函数: ArrayList提供了三种方式的构造器,可以构造一个默认初始容量为10的空列表、构造一个指定初始容量的空列表以及构造一个包含指定collection的元素的列表,这些元素按照...

centrald
2016/01/21
14
0
Collection源码分析(七):Vector源码分析

点开Vector的源码 可以看到 这个类继承自AbstractList 实现了List<E>, RandomAccess, Cloneable, java.io.Serializable三个接口,是不是感觉和ArrayList很像 注意到 Vector主要的三个变量 el...

Twelve_ZX
05/28
0
0
JDK1.8 ArrayList 源码分析

类示意图: ArrayList : 构造函数:ArrayList() ArrayList(int initialCapacity) ArrayList(Collection<? extends E> c) 初始化好的成员变量:DEFAULT_CAPACITY=10.如果使用默认的无参数构造......

zheng_pat
2016/06/11
120
0
Java容器类框架分析(1)ArrayList源码分析

概述 在分析ArrayList源码之前,先看一下ArrayList在数据结构中的位置,常见的数据结构按照逻辑结构跟存储结构如下: 数据结构分类 先看看源码的注释: Resizable-array implementation of ...

wustor
2017/11/06
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

50 行 Python 代码,带你追到最心爱的人

程序员世纪难题 人们一提到程序员第一反应就是:我知道!他们工资很高啊!但大部分都是单身狗,不懂得幽默风趣,只是每天穿格子 polo 衫的宅男一个。甚至程序员自己也这样形容自己:钱多话少...

猫咪编程
4分钟前
0
0
JAVA知识点随心记

1.Switch case具体的支持类型? Q:支持byte、short、char、int基本类型,枚举类型和String类型(JDK7以上支持),四种基本类型的包装类型也支持,但是原因在于触发了自动拆箱,将包装类型拆成了基本...

勤奋的蚂蚁
14分钟前
0
0
NoSQL

一、NoSQL介绍 NoSQL属于非关系型数据,mysql属于关系型数据库。 对于关系型数据库来说,是需要把数据存储到库、表、行、字段里,查询的时候根据条件一行一行地去匹配,当数据量非常大的时候...

人在艹木中
19分钟前
0
0
第17章MySQL主从配置

mysql安装总结 mysql主从准备工作: 准备两台机器,每台机器安装msyql服务,并启动mysql服务 mysql详细安装 1.首先下载二进制免编译的包,下载到/usr/local/src/目录下 2.解压压缩包 3.解压完...

Linux学习笔记
23分钟前
0
0
Redis高可用及分片集群

一、主从复制 使用异步复制 一个服务器可以有多个从服务器 从服务器也可以有自己的从服务器 复制功能不会阻塞主服务器 可以通过服务功能来上主服务器免于持久化操作,由从服务器去执行持久化...

Java大蜗牛
27分钟前
0
0
前端面试题汇总

最近在复习,准备找工作了,特此总结一下前端的相关知识。 1.获取浏览器URL中查询字符的参数: function getQuery(name){    var reg = new RegExp("(^|&)"+name+"=([^&]*)"(&|$));...

凛冬来袭
今天
0
0
可持续发展的学习道路

与其要求别人,不如提升自己 内心渴望进步 经常做出改变现有模式,不断学习 寻找资源,整合资源,不断熟练这种模式 渠道很重要 先打开新世界的航路

狮子狗
今天
0
0
apollox-lua开源项目 示例codepen2

今天在示例上增加了几个功能, 首先添加js array的标准库。 所有js array的方法目前都支持了。 添加查看code模式。 点击查看code可以看到生成的lua代码。默认web模式需要把标准库连接进来, ...

钟元OSS
今天
0
0
javascript性能优化之避免重复工作

javascript最重要也最根本的性能优化标准之一是避免工作,避免工作又包括两点,第一,不做不必要的工作,第二,不做重复的已经完成的工作。第一部分可以通过代码重构完成,第二部分不做重复的...

老韭菜
今天
0
0
缓存穿透、并发和雪崩那些事

0 题记 缓存穿透、缓存并发和缓存雪崩是常见的由于并发量大而导致的缓存问题,本文讲解其产生原因和解决方案。 缓存穿透通常是由恶意攻击或者无意造成的;缓存并发是由设计不足造成的;缓存雪...

Java填坑之路
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部