文档章节

ArrayList扩容分析

m
 modprobe
发布于 2016/11/08 09:57
字数 455
阅读 5
收藏 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自动扩容机制

注意: 不同的JDK版本的扩容机制可能有差异 实验环境:JDK1.8 扩容机制: 当向ArrayList中添加元素的时候,ArrayList如果要满足新元素的存储超过ArrayList存储新元素前的存储能力,ArrayList...

ZeroneLove
02/09
22
0