首页 » 编写高质量代码:改善Java程序的151个建议 » 编写高质量代码:改善Java程序的151个建议全文在线阅读

《编写高质量代码:改善Java程序的151个建议》建议63:在明确的场景下,为集合指定初始容量

关灯直达底部

我们经常使用ArrayList、Vector、HashMap等集合,一般都是直接用new跟上类名声明出一个集合来,然后使用add、remove等方法进行操作,而且因为它是自动管理长度的,所以不用我们特别费心超长的问题,这确实是一个非常好的优点,但也有我们必须要注意的事项。

下面以ArrayList为例深入了解一下Java是如何实现长度的动态管理的,先从add方法的阅读开始,代码如下。


public boolean add(E e){

//扩展长度

ensureCapacity(size+1);

//追加元素

elementData[size++]=e;

return true;

}


我们知道ArrayList是一个大小可变的数组,但它在底层使用的是数组存储(也就是elementData变量),而且数组是定长的,要实现动态长度必然要进行长度的扩展,ensureCapacity方法提供了此功能,代码如下:


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=Arrays.copyOf(elementData, newCapacity);

}

}


注意看新数组的长度计算方法,并不是增加一个元素,elementData的长度就加1,而是在达到elementData长度的临界点时,才将elementData扩容1.5倍,这样实现有什么好处呢?好处是避免了多次调用copyOf方法的性能开销,否则每加一个元素都要扩容一次,那性能岂不是非常糟糕?!

可能有读者要问了,这里为什么是1.5倍,而不是2.5倍、3.5倍?这是一个好问题,原因是一次扩容太大(比如扩容2.5倍),占用的内存也就越大,浪费的内存也就越多(1.5倍扩容,最多浪费33%的数组空间,而2.5倍则最多可能浪费60%的内存);而一次扩容太小(比如每次扩容1.1倍),则需要多次对数组重新分配内存,性能消耗严重。经过测试验证,扩容1.5倍即满足了性能要求,也减少了内存消耗。

现在我们知道了ArrayList的扩容原则,那还有一个问题:elementData的默认长度是多少呢?答案是10,如果我们使用默认方式声明ArrayList,如new ArrayList(),则elementData的初始长度就是10。我们来看ArrayList的无参构造:


//无参构造,我们通常用得最多的就是这个

public ArrayList(){

//默认是长度为10的数组

this(10);

}

//指定数组长度的有参构造

public ArrayList(int initialCapacity){

super();

if(initialCapacity<0)

throw new IllegalArgumentException(/"Illegal Capacity:/"+initialCapacity);

//声明指定长度的数组,容纳element

this.elementData=new Object[initialCapacity];

}


默认初始化时声明了一个长度为10的数组,在通过add方法增加第11个元素时,ArrayList类就自动扩展了,新的elementData数组长度是(10×3)/2+1,也就是16,当增加到第17个元素时再次扩容为(16×3)/2+1,也就是25,依此类推,实现了ArrayList的动态数组管理。

从这里我们可以看出,如果不设置初始容量,系统就按照1.5倍的规则扩容,每次扩容都是一次数组的拷贝,如果数据量很大,这样的拷贝会非常耗费资源,而且效率非常低下。如果我们已经知道一个ArrayList的可能长度,然后对ArrayList设置一个初始容量则可以显著提高系统性能。比如一个班级的学生,通常也就是50人左右,我们就声明ArrayList的默认容量为50的1.5倍(元素数量小,直接计算,避免数组拷贝),即new ArrayList<Studeng>(75),这样在使用add方法增加元素时,只要在75以内都不用做数组拷贝,超过了75才会按照默认规则扩容(也就是1.5倍扩容)。如此处理,对我们的开发逻辑并不会有任何影响,而且还可以提高运行效率(在大数据量下,是否指定容量会使性能相差5倍以上)。

弄明白了ArrayList的长度处理方式,那其他集合类型呢?我们先来看Vector,它的处理方式与ArrayList相似,只是数组的长度计算方式不同而已,代码如下:


private void ensureCapacityHelper(int minCapacity){

int oldCapacity=elementData.length;

if(minCapacity>oldCapacity){

ObjectoldData=elementData;

//若有递增步长,则按照步长增长;否则,扩容2倍

int newCapacity=(capacityIncrement>0)?(oldCapacity+capacityIncrement)

:(oldCapacity*2);

//越界检查,否则超过int最大值

if(newCapacity<minCapacity){

newCapacity=minCapacity;

}

elementData=Arrays.copyOf(elementData, newCapacity);

}

}


Vector与ArrayList不同的地方是它提供了递增步长(capacityIncrement变量),其值代表的是每次数组拓长时要增加的长度,不设置此值则是容量翻倍(默认是不设置递增步长的,可以通过构造函数来设置递增步长)。其他集合类的扩容方式与此相似,如HashMap是按照倍数增加的,Stack继承自Vector,所采用的也是与其相同的扩容原则等,读者有兴趣可以自行研读一下JDK的源码。

注意 非常有必要在集合初始化时声明容量。