Java 的 ArrayList 的底层数据结构

时间:2022-11-30 16:19:07

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

ublic class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;

    /**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == EMPTY_ELEMENTDATA will be expanded to
     * DEFAULT_CAPACITY when the first element is added.
     */
    private transient Object[] elementData;

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

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

 

2. ArrayList 的底层数组的调整

add方法--ArrayList源码摘要

/**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return <tt>true</tt> (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

grow方法--ArrayList源码摘要

 
 

/**

 
 

     * Increases the capacity of this <tt>ArrayList</tt> instance, if

 
 

     * necessary, to ensure that it can hold at least the number of elements

 
 

     * specified by the minimum capacity argument.

 
 

     *

 
 

     * @param   minCapacity   the desired minimum capacity

 
 

     */

 
 

    public void ensureCapacity(int minCapacity) {

 
 

        int minExpand = (elementData != EMPTY_ELEMENTDATA)

 
 

            // any size if real element table

 
 

            ? 0

 
 

            // larger than default for empty table. It's already supposed to be

 
 

            // at default size.

 
 

            : DEFAULT_CAPACITY;

 
 

 

 
 

        if (minCapacity > minExpand) {

 
 

            ensureExplicitCapacity(minCapacity);

 
 

        }

 
 

    }

 
 

 

 
 

    private void ensureCapacityInternal(int minCapacity) {

 
 

        if (elementData == EMPTY_ELEMENTDATA) {

 
 

            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);

 
 

        }

 
 

 

 
 

        ensureExplicitCapacity(minCapacity);

 
 

    }

 
 

 

 
 

    private void ensureExplicitCapacity(int minCapacity) {

 
 

        modCount++;

 
 

 

 
 

        // overflow-conscious code

 
 

        if (minCapacity - elementData.length > 0)

 
 

            grow(minCapacity);

 
 

    }

 
 

 

 
 

    /**

 
 

     * The maximum size of array to allocate.

 
 

     * Some VMs reserve some header words in an array.

 
 

     * Attempts to allocate larger arrays may result in

 
 

     * OutOfMemoryError: Requested array size exceeds VM limit

 
 

     */

 
 

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

 
 

 

 
 

    /**

 
 

     * Increases the capacity to ensure that it can hold at least the

 
 

     * number of elements specified by the minimum capacity argument.

 
 

     *

 
 

     * @param minCapacity the desired minimum capacity

 
 

     */

 
 

    private void grow(int minCapacity) {

 
 

        // overflow-conscious code

 
 

        int oldCapacity = elementData.length;

 
 

        int newCapacity = oldCapacity + (oldCapacity >> 1);

 
 

        if (newCapacity - minCapacity < 0)

 
 

            newCapacity = minCapacity;

 
 

        if (newCapacity - MAX_ARRAY_SIZE > 0)

 
 

            newCapacity = hugeCapacity(minCapacity);

 
 

        // minCapacity is usually close to size, so this is a win:

 
 

        elementData = Arrays.copyOf(elementData, newCapacity);

 
 

    }

 
 

 

 
 

    private static int hugeCapacity(int minCapacity) {

 
 

        if (minCapacity < 0) // overflow

 
 

            throw new OutOfMemoryError();

 
 

        return (minCapacity > MAX_ARRAY_SIZE) ?

 
 

            Integer.MAX_VALUE :

 
 

            MAX_ARRAY_SIZE;

 
 

    }

 

 

2点结论:

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

  b. 当ArrayList 的容量不足时,其扩充容量的方式:先将容量扩充至当前容量的1.5倍,若还不够,则将容量扩充至当前需要的数量(grow方法)。

 

 

remove 方法--ArrayList源码摘要

/**
     * Removes the element at the specified position in this list.
     * Shifts any subsequent elements to the left (subtracts one from their
     * indices).
     *
     * @param index the index of the element to be removed
     * @return the element that was removed from the list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

  

/**

 
 

     * Removes the first occurrence of the specified element from this list,

 
 

     * if it is present.  If the list does not contain the element, it is

 
 

     * unchanged.  More formally, removes the element with the lowest index

 
 

     * <tt>i</tt> such that

 
 

     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>

 
 

     * (if such an element exists).  Returns <tt>true</tt> if this list

 
 

     * contained the specified element (or equivalently, if this list

 
 

     * changed as a result of the call).

 
 

     *

 
 

     * @param o element to be removed from this list, if present

 
 

     * @return <tt>true</tt> if this list contained the specified element

 
 

     */

 
 

    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;

 
 

    }

 
 

 

 
 

    /*

 
 

     * Private remove method that skips bounds checking and does not

 
 

     * return the value removed.

 
 

     */

 
 

    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; // clear to let GC do its work

 
 

    }

 

这也就解释了 ArrayList 的特点:增加、删除和移动元素的效率低(数组复制过程消耗资源较多); 而查找元素和更新元素的效率高。

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)。