今天抽空看了一下ArrayList的源码,了解一下扩容机制,将研究过程总结如下.
ArrayList
简介
ArrayList是JDK1.2引入的集合类.ArrayList是非同步的,也就是不是线程安全的.如果需要线程安全,可以使用Vector代替.Oracle官网是这样介绍ArrayList和Vector区别的:This class is roughly equivalent to Vector, except that it is unsynchronized.
同步
ArrayList是非同步的(unsynchronized),如果多个线程同时对ArrayList做结构性修改(structural modification),需要考虑做同步操作,如果不想自己写同步代码,也可以使用JDK自带的方法Collections.synchronizedList:
List list = Collections.synchronizedList(new ArrayList(...));
什么是结构性修改呢?结构性修改指的是添加或删除一个元素,或者对底层使用的数组扩容.仅仅给已经存在的元素赋值不是结构性修改.
数组
ArrayList底层使用数组存储元素,该数组名为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
大小和容量
大小(size)
size表示已经添加的元素的数量.
容量(capacity)
ArrayList有3个构造方法,先来看其中的2个:
ArrayList()
ArrayList(int initialCapacity)
官方对ArrayList()的解释是:
Constructs an empty list with an initial capacity of ten.
也就是默认的构造器会创建一个初始容量为10的List.很显然另一个构造方法可以指定其它的初始容量.
扩容
如果向ArrayList中插入某个元素时ArrayList中size(已经存在的元素数量)刚好等于容量时,会引发自动扩容,底层就是新建一个数组,拷贝原来的数据到新数组并且把该元素插入到新数组,旧的数组会被垃圾回收.JDK1.6之前的扩容计算规则为:
int newCapacity = (oldCapacity * 3)/2 + 1;
JDK1.7之后的扩容计算规则为:
int newCapacity = oldCapacity + (oldCapacity >> 1);
容量操作api
开发者可以使用的api是:
ensureCapacity(int minCapacity)
trimToSize()
来看看ensureCapacity的定义:
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
关于ensureExplicitCapacity方法代码定义参考源码小节.这里对ensureCapacity方法简单解释下,假设扩容以后的容量是newCapacity,如果ArrayList扩容以后newCapacity是16,这里的minCapacity参数是15,那么扩容以后的容量就是16;如果minCapacity参数是17,那么扩容以后的容量就是17,最终的容量是newCapacity还是minCapacity的规则如下:
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
trimToSize方法会把容量更改为和当前的size一样,也就是有多少个元素,容量就是多少,该方法定义如下:
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
源码
首先声明,以下源码来源于Oracle JDK1.8.
先从默认构造方法看起:
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
来看看elementData和DEFAULTCAPACITY_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
可以看到DEFAULTCAPACITY_EMPTY_ELEMENTDATA实际是一个空的数组,只有在第一个元素被添加时才会被扩展成为大小为10的数组.来看看add方法定义:
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
注意初始size值为0,因此传递到ensureCapacityInternal的参数为1.来看看ensureCapacityInternal的定义:
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
可以看到如果elementData值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA,也就是默认的构造方法中赋的值,此时最小容量(minCapacity)会被赋值为DEFAULT_CAPACITY,也就是10.再来看ensureExplicitCapacity方法:
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
minCapacity值为10,elementData.length值为0.满足minCapacity - elementData.length > 0条件,触发了第一次扩容操作.来看看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);
}
在此看到了扩容的规则和数组的拷贝操作.
网友评论