ソース読解シリーズ——基礎編(ArrayList集合ソース分析)


ArrayListは、スレッドが安全ではないリストの集合としてよく使用されています.ArrayListとVectorはほぼ似ています.私たちはソースコードを読み続けて答えを探します.
1、クラス定義
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final int DEFAULT_CAPACITY = 10; //     
    private static final Object[] EMPTY_ELEMENTDATA = {}; //         ,     1
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //           ,     2
    transient Object[] elementData; //     
    private int size;  //     
   
    //     1:         
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

    //     2
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
}

上のソースコードから、ArrayListのデフォルトは空の配列です.長さを設定する場合にのみ、一定の長さの配列が生成されます.
2、拡張機構
追加された要素の例
public void add(int index, E element) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index); //     index      
    elementData[index] = element;
    size++;
}

ensureCapacityInternal実装を見てみましょう
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); //        DEFAULT_CAPACITY(10)   ,    DEFAULT_CAPACITY
    }

    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    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;
    int newCapacity = oldCapacity + (oldCapacity >> 1);//     ,         (   1.5    )
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0)
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

ソースコードから:1、長さが10未満の場合は、まず10に拡張します.2、長さが10より大きい場合、毎回1.5倍の容量拡張.Vectorの1回あたりの2倍の容量拡張よりも省スペースで、頻繁に容量拡張しなければ効率が悪くなりません.
3、反復器
配列を巡る過程で要素を修正する必要がありますが、次のような書き方をすると、配列の境界を越える問題があります.
public void removeElement(int value){
    for (int i = 0 ; i < elementList.size() ; i++){
        if(value == elementList.get(i).value){
            elementList.remove(i);
        }
    }
}

Javaは、上記の要件を満たすために反復器を提供しています.反復器の主なコードを見てみましょう.
private class Itr implements Iterator<E> {
        protected int limit = ArrayList.this.size;

        int cursor;       //   ,            (    )。
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount; // modCount  List        。(   List       list     ,    1,  List.remove(),List.clear())

        public boolean hasNext() {
            return cursor < limit;  //         
        }

        @SuppressWarnings("unchecked")
        public E next() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException(); //               ,modCount     ,    ,   Fast-fail  
            int i = cursor;
            if (i >= limit)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException(); //         ,   (            ,            )
            cursor = i + 1;  //       ,            
            return (E) elementData[lastRet = i]; // lastRet            
        }

        public void remove() {
            if (lastRet< 0)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();

            try {
                ArrayList.this.remove(lastRet); //           
                cursor = lastRet;//         ,  index   -1
                lastRet = -1;
                expectedModCount = modCount; //   modCount
                limit--;   //    1
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
    }

上のソースコード解析から,反復器の役割を大体発見することができる:彼は実際に閉鎖的な空間を構築し,開発者が遍歴しながら要素を修正し,要素配列の大きさにも影響を及ぼすことを理解することができる.反復器では長さ、インデックスのダイナミックな変更が実現されているため、反復器の外で配列を変更することはできません.