ArrayList动态扩容机制--源码解析
mmexport1520334289708.gif
阅读原文
/**
* Default initial capacity.
* 默认容量大小
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 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 = {};
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
* 储存数据的数组
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* The size of the ArrayList (the number of elements it contains).
* ArrayList中元素的个数
* @serial
*/
private int size;
首先我们通过一个具体的例子看一下ArrayList的扩容效果
查看源码可知，ArrayList通过一个elementData对象数组储存数据，也就是说ArrayList的容量就是该数组的长度。所以我们只要得到了elementData数组就可以知道ArrayList的实际容量。
由于elementData是私有的无法直接得到，但是我们可以通过反射的方式获取。
代码如下：
public static Integer getCapacity(ArrayList list) {
Integer length = null;
Class c = ((Object)list).getClass();
Field f;
try {
f = c.getDeclaredField("elementData");
f.setAccessible(true);
Object[] o = (Object[]) f.get(list);
length = o.length;
} catch (NoSuchFieldException ex) {
Logger.getLogger(CollectionDemo.class.getName()).log(Level.SEVERE, null, ex);
} catch (SecurityException ex) {
Logger.getLogger(CollectionDemo.class.getName()).log(Level.SEVERE, null, ex);
} catch (IllegalArgumentException ex) {
Logger.getLogger(CollectionDemo.class.getName()).log(Level.SEVERE, null, ex);
} catch (IllegalAccessException ex) {
Logger.getLogger(CollectionDemo.class.getName()).log(Level.SEVERE, null, ex);
}
return length;
}
我们先看一下ArrayList的初始容量
ArrayList<Integer> array = new ArrayList<>();
Integer capacity = getCapacity(array);
int size = array.size();
System.out.println("容量："+capacity);
System.out.println("大小："+size);
容量：0
大小：0
ArrayList一共有三种初始化方法
- 默认的构造器，将会以默认的大小来初始化内部的数组：public ArrayList();
- 用一个Collection对象来构造，并将该集合的元素添加到ArrayList：public ArrayList(Collection<?
extends E> c) - 用指定的大小来初始化内部的数组： public ArrayList(int initialCapacity)
源码如下：
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
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);
}
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
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中添加一个元素
ArrayList<Integer> array = new ArrayList<>();
array.add(1);
Integer capacity = getCapacity(array);
int size = array.size();
System.out.println("容量："+capacity);
System.out.println("大小："+size);
容量：10 默认容量大小
大小：1
向ArrayList中添加11个元素
ArrayList<Integer> array = new ArrayList<>();
for (int i = 0; i < 11; i ++) {
array.add(i);
}
Integer capacity = getCapacity(array);
int size = array.size();
System.out.println("容量："+capacity);
System.out.println("大小："+size);
容量：15
大小：11
我们发现，当向array中添加11个元素之后，array的容量扩大到原来的1.5倍。
Why does it expansion 1.5 times?
具体为什么，下面我们看一下源码：
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
add方法是通过在array的尾部追加元素的方法，添加数据的。其中，调用ensureCapacityInternal方法用来判断是否需要扩容.
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++; // 操作数 具体看博客
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
参数传的是当前需要的最小容量，方法首先确认当前ArrayList实例是否为空，如果为空则比较所需容量和默认容量，取其大者作为所需最小容量值。然后执行ensureExplicitCapacity进一步确定容量，以及是否需要扩容。当所需最小容量大于当前elementData数组长度时，要进行扩容操作。
modCount是fail fast机制，不了解的可以暂时忽略这条语句，如果想了解可以看这里,如果minCapacity的值大于添加数据之前的大小，就调用grow方法，进行扩容，否则什么也不做。
发生扩容的条件:
根据传入的最小需要容量minCapacity来和数组的容量长度对比，若minCapactity大于或等于数组容量，则需要进行扩容。
(如果实际存储数组是空数组，则最小需要容量就是默认容量)
以上只是真实容量和所需容量的比较，其目的是计算出array的最终容量。真正实现扩容的方法是grow方法。下面具体来了解扩容机制的增长规则
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
这里传过来的minCapacity的值是array的size+1
添加一个元素，首先计算当前的array所需最小的容量大小，判断是否需要扩容等。
当需要扩容时：
- 得到当前的ArrayList的容量(oldCapacity)。
- 计算除扩容后的新容量(newCapacity)，其值(oldCapacity + (oldCapacity >>1))约是oldCapacity 的1.5倍。
- 这里采用的是移位运算。为什么采用这种方法呢？应该是出于效率的考虑。
- 当newCapacity小于所需最小容量，那么将所需最小容量赋值给newCapacity。
- newCapacity大于ArrayList的所允许的最大容量,处理。进行数据的复制，完成向ArrayList实例添加元素操作。
每次array的size到达当前的容量最大值后，再插入数据就会造成扩容。
网友评论