Java 的 ArrayList 的底层数据结构

 

1. 数据结构--ArrayList源码摘要

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    ......

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer.
     */
    private transient E[] elementData;


    /**
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */
    private int size;
   ......
}

 

 

 

ArrayList 的底层最重要的两个属性：Object 数组和 size 属性。

 

 

2. ArrayList 的底层数组的调整

add方法--ArrayList源码摘要

    public boolean add(E o) {
	ensureCapacity(size + 1);  // Increments modCount!!
	elementData[size++] = o;
	return true;
    }

 

 

ensureCapacity方法--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 = (E[])new Object[newCapacity];
	    System.arraycopy(oldData, 0, elementData, 0, size);
	}
    }

 

 

2点结论：

  a. ArrayList 是通过将底层 Object 数组复制的方式（System.arraycopy方法）来处理数组的增长；

  b. 当ArrayList 的容量不足时，其扩充容量的方式：先将容量扩充至当前容量的1.5倍，若还不够，则将容量扩充至当前需要的数量。

(见代码： int newCapacity = (oldCapacity * 3)/2 + 1;

          if (newCapacity < minCapacity)
           newCapacity = minCapacity;

)

 

 

顺便看看 remove 方法

remove 方法--ArrayList源码摘要

    public boolean remove(Object o) {
	if (o == null) {
            for (int index = 0; index < size; index++)
		if (elementData[index] == null) {
		    fastRemove(index);
		    return true;
		}
	} else {
	    for (int index = 0; index < size; index++)
		if (o.equals(elementData[index])) {
		    fastRemove(index);
		    return true;
		}
        }
	return false;
    }

 

 

fastRemove 方法--ArrayList源码摘要

    private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index, 
                             numMoved);
        elementData[--size] = null; // Let gc do its work
    }

 

 

private void fastRemove(int index) 可见，ArrayList 的元素移除后，也是通过 Object 数组复制的方式（System.arraycopy方法）来处理数组的变化； size 总是记录着当前的数组元素的数量。

 

 

这也就解释了 ArrayList 的特点：增加、删除和移动元素的效率低（数组复制过程消耗资源较多）； 而查找元素和更新元素的效率高。（如下所示）

 

get 方法--ArrayList 源码摘要

    public E get(int index) {
	RangeCheck(index);

	return elementData[index];
    }

 

 

set 方法--ArrayList 源码摘要

    public E set(int index, E element) {
	RangeCheck(index);

	E oldValue = elementData[index];
	elementData[index] = element;
	return oldValue;
    }

 

 

 

3. ArrayList与Vector的区别

 

1） vector 是线程同步的，所以它也是线程安全的，而arraylist 是线程异步的，是不安全的。如果不考虑到线程的安全因素，一般用 arraylist效率比较高。

 

2）如果集合中的元素的数目大于目前集合数组的长度时，vector 增长率为目前数组长度的100%, 而arraylist 增长率为目前数组长度的50% .如果在集合中使用数据量比较大的数据，用vector有一定的优势。

 

3）如果查找一个指定位置的数据，vector和arraylist使用的时间是相同的，都是O(1) ,这个时候使用vector和arraylist都可以。

 

而如果移动一个指定位置的数据花费的时间为O(n-i)n为总长度，这个时候就应该考虑到使用linklist ,因为它移动一个指定位置的数据所花费的时间为0(1),而查询一个指定位置的数据时花费的时间为0(i)。