ArrayList扩容问题

最近在看jdk的源码，看到ArrayList的时候发现一个问题，在插入的时候，如果进行扩容，会进行两次数组的copy。

 

第一次：

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;
            // 在此把整个数组copy到一个新的数组
            elementData = Arrays.copyOf(elementData, newCapacity);
	}
    }

 第二次拷贝：

public void add(int index, E element) {
	if (index > size || index < 0)
	    throw new IndexOutOfBoundsException(
		"Index: "+index+", Size: "+size);
	
	// 如果数组长度不足，将进行扩容
	ensureCapacity(size+1);  // Increments modCount!!
        // copy发生在这里，index后边的数据都需要再次copy
	System.arraycopy(elementData, index, elementData, index + 1,
			 size - index);
	elementData[index] = element;
	size++;
    }

 从代码可以看到，从插入点index后边的数据如果需要扩容，则会拷贝两次。一次为拷贝到新的数组，一次为整体向后挪一位。

后来考虑是不是可以创建新数组的时候拷贝两次，把index以前的数据先copy到新数组，然后index以后的数据直接向后挪一位copy入新的数组。

 

修改后的代码：

	public void add(int index, E element) {
		if (index > size || index < 0)
			throw new IndexOutOfBoundsException("Index: " + index + ", Size: "
					+ size);

		// 如果数组长度不足，将进行扩容
		// ensureCapacity(size+1); // Increments modCount!!

		int minCapacity = size + 1;
		modCount++;
		int oldCapacity = elementData.length;
		Object[] newObj = null;
		if (minCapacity > oldCapacity) {
			Object oldData[] = elementData;
			int newCapacity = (oldCapacity * 3) / 2 + 1;
			if (newCapacity < minCapacity)
				newCapacity = minCapacity;
			newObj = new Object[newCapacity];
		}
		if (newObj != null) {
			System.arraycopy(elementData, 0, newObj, 0, index);
			System.arraycopy(elementData, index, newObj, index + 1, size
					- index);
			elementData = newObj;
		} else {
			System.arraycopy(elementData, index, elementData, index + 1, size
					- index);
		}
		elementData[index] = element;
		size++;
	}

 
 因环境问题，过段时间找台测试机器把测试结果贴出来。目前在本机测效率无提升，不知道是因为机器上东西太多还是因为这个思路本身不对。

评论

5 楼 bitray 2015-03-18  

yuxuguang 写道

bambooman 写道

难有显著提高，反而把代码逻辑搞复杂了。
1、System.arraycopy 本身效率很高，多复制一次差不到哪里去

2、确保容量的扩容操作很少能得到执行。 因为每次扩容大约为 50%。 参见
int newCapacity = (oldCapacity * 3)/2 + 1; 

个人认为list扩容操作里数组的复制是最耗性能的，如果不能预估list的大小，list执行扩容的机会很多。而且感觉修改后代码的逻辑并没有复杂化，等有时间搞个压力测试，看看性能的提升。

频繁扩容是耗时的，他拆分成初始化一个更大的数组，元素拷贝。
旧数组的回收不用考虑。
但是扩容几次，其实影响不大。真的担心的话，最好初始化把数组大小调整的差不多状态

4 楼 laogao3232 2015-03-13  

应该看到，数组整体多拷贝了一次。所以数组越大，性能提升越明显。

3 楼 小橙子 2015-03-12  

我觉得理论上是提高了点性能，但是几乎可以忽略吧。扩容几次后，很难有机会扩容了。大部分ArrayList存储的数据都是很少的。

2 楼 yuxuguang 2015-03-12  

bambooman 写道

难有显著提高，反而把代码逻辑搞复杂了。
1、System.arraycopy 本身效率很高，多复制一次差不到哪里去

2、确保容量的扩容操作很少能得到执行。 因为每次扩容大约为 50%。 参见
int newCapacity = (oldCapacity * 3)/2 + 1; 

个人认为list扩容操作里数组的复制是最耗性能的，如果不能预估list的大小，list执行扩容的机会很多。而且感觉修改后代码的逻辑并没有复杂化，等有时间搞个压力测试，看看性能的提升。

1 楼 bambooman 2015-03-12  

难有显著提高，反而把代码逻辑搞复杂了。
1、System.arraycopy 本身效率很高，多复制一次差不到哪里去

2、确保容量的扩容操作很少能得到执行。 因为每次扩容大约为 50%。 参见
int newCapacity = (oldCapacity * 3)/2 + 1;