本文研究的主要是Java ArrayList扩容问题实例详解的相关内容,具体介绍如下。
首先我们需要知道ArrayList里面的实质的其实是一个Object类型的数组,ArrayList的扩容问题其实就是这个Object类型的数组的扩容问题。
1
|
transient Object[] elementData; |
一、创建时,ArrayList的容量分配
创建一个ArrayList有三种情况
1、默认大小创建(默认为0)
1
|
ArrayList al = new ArrayList(); |
创建完成之后,al的容量为0。从下面代码就可以知道。
1
2
3
4
5
6
|
transient Object[] elementData; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; public ArrayList() { this .elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } |
2、指定大小创建
1
|
ArrayList al = new ArrayList( 5 ); |
创建一个容量为5的ArrayList对象,其实就是一个长度为5的Object数组,从下面代码就可以知道。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
transient Object[] elementData; private static final Object[] 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); } } |
3、指定元素集合创建
1
|
ArrayList al = new ArrayList<Integer>(Arrays.asList( 1 , 2 , 3 , 4 , 5 )); |
上面创建了ArrayList对象,并使用一个List为[1,2,3,4,5]来进行初始化。其实就是创建了一个长度为5的Object数组,数组的内容为[1,2,3,4,5]。从下面代码就可以知道。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
private int size; transient Object[] elementData; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) != 0 ) { // 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; } } |
二、插入元素时,ArrayList的容量扩充
1
2
3
|
ArrayList<Integer> collection = new ArrayList<Integer>(Arrays.asList( 1 , 2 , 3 , 4 , 5 )); Integer[] moreInts = { 6 , 7 , 8 , 9 , 10 }; collection.addAll(Arrays.asList(moreInts)); |
上面过程如下:
1、创建一个size为5的ArrayList,内容为[1,2,3,4,5]。——初始容量为5
2、向这个ArrayList对象里面添加集合{ 6, 7, 8, 9, 10 }。——-这个时候,就需要对这个ArrayList对象容量进行扩充了。
查看源码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
public Boolean addAll(Collection<? extends E> c) { // 得到插入数组 Object[] a = c.toArray(); // 得到插入内容长度 int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount System.arraycopy(a, 0 , elementData, size, numNew); size += numNew; return numNew != 0 ; } private void ensureCapacityInternal( int minCapacity) { //如果ArrayList里面的内容为空 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity( int minCapacity) { modCount++; // 进一步计算扩充后的大小minCapacity if (minCapacity - elementData.length > 0 ) grow(minCapacity); } private void grow( int minCapacity) { // ArrayList的原始大小 int oldCapacity = elementData.length; // 在原始大小的基础上计算扩充后的大小,扩充后的大小是元素大小的1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1 ); //跟前面计算的扩充后长度minCapacity比较,取较大的那个为扩充后长度 if (newCapacity - minCapacity < 0 ) newCapacity = minCapacity; // 如果扩充后长度大于最大长度 if (newCapacity - MAX_ARRAY_SIZE > 0 ) newCapacity = hugeCapacity(minCapacity); // 扩充 elementData = Arrays.copyOf(elementData, newCapacity); } private static int hugeCapacity( int minCapacity) { // minCapacity小于0,说明溢出,否则将最大整数作为最终扩充长度 if (minCapacity < 0 ) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } |
上面的过程可以这样总结:
1、ArrayList的原始大小size + 将要插入集合的大小numNew = 得到扩充后ArrayList的最小长度minCapacity
2、如果ArrayList的原始大小size为0,即ArrayList为空,ArrayList扩充后的最小长度minCapacity= Math.max(10, minCapacity),也就是说扩充后的最小长度minCapacity,并不仅仅是原始长度size加上插入集合的长度numNew。
3、上面得到的扩充后最小长度minCapacity,并不是最终扩充后的长度,还需要进一步进行计算。
(1)得到ArrayList的原始大小oldCapacity
(2)得到新的扩充后的大小:newCapacity = oldCapacity*1.5;
(3)将上面计算的扩充后的最小长度minCapacity与这里得到的扩充后的大小newCapacity进行比较,取较大的那个最为最终扩充后的大小。
总结
以上就是本文关于ArrayList扩容问题实例详解的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!
原文链接:http://blog.csdn.net/hp910315/article/details/50801823