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++;
	}

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

ArrayList扩容问题

原文：http://yuxuguang.iteye.com/blog/2191735