集合类库(三):揭秘 ArrayList 容量的动态增加
2009-09-18 00:00:00 来源:WEB开发网ArrayList 和数组几乎没有区别,唯一的不同就在与ArrayList的容量可以根据添加的元素数量自动的增加。
做到这一点的原因就在于ArrayList封装了一个动态分配的对象数组:
Java代码
//ArrayList的内部数组
public class ArrayList<E>{
private transient E[] elementData; //存储数据的数组
......
}
当我们初始化一个ArrayList的时候,其实内部的数组elementData就已经默认开辟了10个单位的空间。
Java代码
//ArrayList的初始化
public class ArrayList<E>{
public ArrayList() {
this(10); //默认大小10个单位
}
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
this.elementData = (E[])new Object[initialCapacity];//开辟10个单位的数组空间
}
}
虽然内部默认的数组已经有10个单位空间,但是这个时候的ArrayList.size()仍然为0。size()函数返回的是ArrayList类的私有数据size,而且没有赋初值,那么Java会给予默认的初值0。
Java代码
//ArrayList的容量大小
public class ArrayList<E>{
private int size; //默认的值为0
public int size() { //返回容量的大小
return size;
}
}
现在我们正式揭秘这个内部自动增加的秘密:
(1) 首先用ensureCapacity方法来确保新加入一个数据后(size+1)内部数组容量够用,其核心过程是:
第一步:如果内部数组原容量够用,则不另外增加内部数组容量,用原内部数组继续存储数据。否则扩大容量至原容量的1.5倍,如果此时新扩大的容量还是小于最小需求的容量,则将容量扩大到最小需求量。
第二步:如果新容量扩大以后,则根据新容量来重新创建新数组。
第三步:按顺序把原来数组中的数据拷贝进新数组
(2) 存储新数据,并记录新容量(size++)。
Java代码
//ArrayList的自动增加
public boolean add(E o) {
ensureCapacity(size + 1); //确保添加一个新数据的容量足够(如果容量不够,则开辟新数组空间)
elementData[size++] = o;//扩大容量后,添加新数据并将原容量+1
return true;
}
//如有必要,增加此 ArrayList 实例的容量,以确保它至少能够容纳最小容量参数所指定的元素数。
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
//扩大容量的核心逻辑
if (minCapacity > oldCapacity) {
Object oldData[] = elementData; //记录原始数组,便于后面的数据转移操作。
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
//按照新容量,重新开辟elementData 的连续内存空间,并拷贝原始数据
elementData = (E[])new Object[newCapacity];
System.arraycopy(oldData, 0, elementData, 0, size);
}
}
好了,一个动态增加的过程就是这样了,这些大师写的东西太棒了。
更多精彩
赞助商链接