ArrayList扩容原理分析
1:代码解读和分析
1.1:构造方法分析
1:
public ArrayList(int initialCapacity) {
if (initialCapacity > ) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == ) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
指定初始化容量的构造方法,当initialCapacity大于0时,立即new Object[initialCapacity];在一开始的时候就有了指定大小的数组在ArrayList内部;当initialCapacity==0时,则将EMPTY_ELEMENTDATA给elementdata,其中EMPTY_ELEMENTDATA是一个空数组。
这种情况下,size会是几?
2:
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
第二个构造方法是无参构造方法。在这里直接将this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;其中DEFAULTCAPACITY_EMPTY_ELEMENTDATA和EMPTY_ELEMENTDATA一样如下
/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {}; /**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
都是用private static final Object[]定义的两个空数组。
3:
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != ) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
第三种构造方法是用通过放入实现Collection接口的容器来当作该构造方法的初始数据,通过toArray方法将内部的数据拿出来,给
elementData的方法来构建一个ArrayList出来。如果形参集合的数据长度为0,还是要将EMPTIYDATA数组赋给elementData的;
若源集合内的数组长度不为0后,在判断数组类型,如果不为Object基本类型的化,则重新通过Arrays.copyOf方法创建一个新的数组,数据,长度不变,类型设置成Object类型。
注意:这里的size也已经在构造方法中更新了。
1.2:add方法分析
默认在数组尾部增加一个对象。
public boolean add(E e) {
ensureCapacityInternal(size + ); // Increments modCount!!
elementData[size++] = e;
return true;
}
在add放法内部,使用ensureCapacityInternal(size + 1);方法,下面我们看一下该方法的作用。
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
方法名字为:保证内部容量,该方法内部又通过calculateCapacity方法来计算最小的容量,输入的minCapacity是size+1,即在增加数据之前来引入当前数据所用的最小的数据长度+1为计算标准进行判断。
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
上面是calculateCapacity方法的内部的功能,分析如下如果当前ArrayList是通过无参的构造方法创建,且当前是第一次add数据,则返回默认的的DEFAULT_CAPACITY和minCapacity的较大值。其中前者是10,则在第一次add数据,当size+1=1小于DEFAULT_CAPACIT时,都回返回10。显然当不是第一次add数据时,在这里的if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ,显然不会成立了,则返回minCapacity!
private void ensureExplicitCapacity(int minCapacity) {
modCount++; // overflow-conscious code
if (minCapacity - elementData.length > )
grow(minCapacity);
}
经过calculateCapacity方法返回的结果送到ensureExplicitCapacity(int minCapacity)方法中,当第一次add数据时,经过calculateCapacity返回的结果是10,即默认的值,则会执行grow(minCapacity)方法。
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> );
if (newCapacity - minCapacity < )
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > )
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
在grow方法中,将原始数组长度保存在oldCapacity中,将newCapacity取值为oldCapacity的1.5倍。那如果newCapacity小于输入的minCapacity,那么就会将minCapacity的值给newCapacity,则根据newCapacity的大小和原始的elementData通过Arrays.copyOf方法创建一个新的数据即可!
总结:通过无参ArrayList构造函数创建的ArrayList的内部数组是指向DEFAULTCAPACITY_EMPTY_ELEMENTDATA,在第一次add数据时,会通过上面的步骤,创建一个大小为10的elementData的数据在内部!通过指定大小的
1.2.1:非首次add
经过上面分析,我们再来分析一下第二次add数据的情况。此时ensureCapacityInternal(size + 1); size = 1,则ensureCapacityInternal(2),则calculateCapacity(Object[] elementData, int minCapacity),中minCapacity为2,直接返回2。再进入
private void ensureExplicitCapacity(int minCapacity) {
modCount++; // overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
其中,minCapacity为2,显然小于elementData.length,所以不会扩容!
1.2.2:数组已满时add
经过上面分析,我们再来分析一下在内置的数据满的时候的add数据的情况,按照1.2.1中分析的那样,再
private void ensureExplicitCapacity(int minCapacity) {
modCount++; // overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
中如果minCapacity大于elements.length时会进行grow,按照原来数组长度的1.5倍进行,扩容。
2:总结
1:ArrayList在使用无参构造方法创建时,在创建后到add前,其内部是一个空数组,当add第一个数据后,内部数组变成长度为10,当内部数组已满时,就变成原来数组长度的1.5倍!
2:使用指定长度,会立即创建一个指定大小的数据在内部。
3:指定集合参数的构造方法是,会将根据源集合数据创建一个长度,数据与源集合相等的Object类型的内部数组。
3:对比LinkedList
LinkedList底层是用双向链表实现的,所以它对元素的增加、删除效率要比ArrayList好;它是一个双向链表,没有初始化大小,也没有扩容的机制,就是一直在前面或者后面新增就好。
最新文章
- ORACLE误删除ASM磁盘修复
- Mysql优化的几点总结
- javascript内置属性——arguments
- 【转载】IIS7.5(经典模式)访问静态资源(.css和.js文件)提示:未能执行 URL
- Exchanger示例
- OD调试4--绕过nag窗口
- eclipse内使用tomcat项目究竟被部署到了哪里
- 使用 Java 实现 Comet 风格的 Web 应用
- liunx服务器常见监控指标
- Oracle的闪回技术--闪回错误的DML操作
- delphi的TFileStream 内存流
- TCP的连接和建立 图解
- 浅copy 与 深copy
- Android Stdio 如何自定义生成APK的名称
- 多重背包--java
- 关于expect的实战总结
- cocos2dx-lua class解析
- CentOS6.5 安装Nexus配置Maven私服
- 使用three.js开发3d地图初探
- FPGA+ARM or FPGA+DSP?