ArayList拡大処理

ArayListは、動的配列に基づいて実現されるデータ構造であり、要素を追加する場合、要素の個数がlistの容量を超えると、拡張容量に関わる.
 
ArayListの拡充はどうやって行いますか?コードに沿って行くと分かりやすいです.

    /**
     *      list  
     *
     * @param e      
     * @return         
     */
    public boolean add(E e) {
        //         
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }


    /**
     *   list               
     *        list size + 1         ，  size <= list  capacity
     * size + 1               
     */
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    /**
     *         
     *                ，  list       
     */
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        //         
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            //       10             ，         
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //        ，            ，          size + 1 
        return minCapacity;
    }

    /**
     *       
     *                ，  list       
     */
    private void ensureExplicitCapacity(int minCapacity) {
        // list        1
        modCount++;

        //                ，     
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    /**
     *   list  ，  list      minCapacity   
     * @param minCapacity the desired minimum capacity
     */
    private void grow(int minCapacity) {
        //        
        int oldCapacity = elementData.length;
        //           1.5 ，            2，       
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //         ，minCapacity 10，          newCapacity 0
        if (newCapacity - minCapacity < 0)
            //          minCapacity
            newCapacity = minCapacity;
        //              
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            //         ，          
            newCapacity = hugeCapacity(minCapacity);
        //   elementData            newCapacity    
        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;
    }

上のコードを通して、下記のようにまとめられます.

ArayList無参構造方法のデフォルト容量は10

である.

追加された要素が現在のリスト容量を超えた場合、list容量は半分

に拡張される.

ArayList最大容量はIntegerの最大値

を超えない.
 
コードテスト

    /**
     * ArrayList    
     * @throws Exception
     * @throws SecurityException
     */
    public static void arrayListCapacity() throws Exception, SecurityException {
    	//       
    	List

実行結果

i=9,size=10,      [Ljava.lang.Object;@6d06d69c,elementData=10
i=10,size=11,      [Ljava.lang.Object;@7852e922,elementData=15
i=11,size=12,      [Ljava.lang.Object;@7852e922,elementData=15
i=14,size=15,      [Ljava.lang.Object;@7852e922,elementData=15
i=15,size=16,      [Ljava.lang.Object;@4e25154f,elementData=22
i=22,size=23,      [Ljava.lang.Object;@70dea4e,elementData=33
i=23,size=24,      [Ljava.lang.Object;@70dea4e,elementData=33
**********   ***********
i=5,size=30,      [Ljava.lang.Object;@5c647e05,elementData=6
i=6,size=30,      [Ljava.lang.Object;@33909752,elementData=9
i=9,size=30,      [Ljava.lang.Object;@55f96302,elementData=13
i=13,size=30,      [Ljava.lang.Object;@3d4eac69,elementData=19
i=19,size=30,      [Ljava.lang.Object;@42a57993,elementData=28
i=28,size=30,      [Ljava.lang.Object;@75b84c92,elementData=42
i=29,size=30,      [Ljava.lang.Object;@75b84c92,elementData=42

テストによって、定義された結論を得ることができます.1、ArayListは、配列が大きい時間で自動的に拡張されます.2、拡大サイズが現在の容量の半分を取っています.3、拡張後、現在の配列のすべての要素を新たな拡散配列にコピーします.4、デフォルト容量と指定容量のArayList拡張規則は同じです.