ArayListの底のデータ構造

3239 ワード

JAVAベース

回転:https://www.cnblogs.com/dassmeta/p/5334960.html

ublic class ArrayList extends AbstractList
        implements List, 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;
}

ArayListの一番重要な2つの属性:Object配列とsize属性.
Addメソッド

	public boolean add(E e) {
		//          ,            
		ensureCapacityInternal(size + 1);
		//        
		elementData[size++] = e;
		return true;
	}

//minCapacity        
 public void ensureCapacity(int minCapacity) {

        int minExpand = (elementData != EMPTY_ELEMENTDATA)  ? 0 : DEFAULT_CAPACITY;
        //             
        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

    private void ensureExplicitCapacity(int minCapacity) {
        //         
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

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

    private void grow(int minCapacity) {

        int oldCapacity = elementData.length;
        //   ＋   /2
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //               
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;

        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);

        //minCapacity      ，        
        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. ArayListは下を通る Object 配列コピー方式(System.arraycopy方法)は、配列の成長を処理する.
b.ArayListの容量が足りない場合、その拡張容量の方式:まず容量を現在の容量の1.5倍に拡張し、足りない場合、容量を現在必要な数量(grow方法)に拡張する.
ArayListとVectorの違い

1) vector スレッドが同期していますので、スレッドも安全です. スレッド非同期です.安全ではありません.スレッドの安全性を考慮しないと、一般的に使用されます. arraylistは効率がいいです.

2)セット内の要素の数が現在のセット配列の長さよりも大きい場合、vector 成長率は現在の配列長の100%であり、 arraylist 成長率は現在の配列長の50%です.集合中にデータ量が大きいデータを使うなら、vectorを使うのが有利です.

3)指定された位置のデータを検索すれば、vectorとarraylistは同じ時間で使用します.全部O(1)です.この時はvectorとarraylistを使ってもいいです.

指定された位置のデータを移動するのにかかる時間がO(n−i)nの総長である場合は、指定された位置のデータを移動するのにかかる時間が0(1)であるため、指定された位置のデータを検索するのにかかる時間が0(i)であることを考慮しなければならない.

IOS Audioデータ構造説明