ArrayListソース分析(JDK 1.6ベース)

最近転職するかもしれないので、Javaベースをもう少し固めたいです.まず集合フレームワークを見てみましょう.まず、構築方法から始めます.

    public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
        this.elementData = new Object[initialCapacity];
    }

    public ArrayList() {
        this(10);
    }

    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        size = elementData.length;
        //  c.toArray() Object[].class
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

ArrayListは、このArrayListの初期化サイズをinitialCapacityが表す3つの構成を提供していることがわかる.最初のコンストラクション関数により,ArrayList内部はObject配列を維持することによってデータを格納することが分かった.パラメータがデフォルトで提供されていない場合、ArrayListの初期容量は10になります.もう1つの既存の集合でArrayListを構築すると、その集合の要素が内部配列にコピーされます.なお、もう1つの重要なインスタンス変数はsizeであり、この変数は現在のArrayListの実際の長さ(すなわち、実際の要素の個数であり、内部配列の長さではなく、一般的に内部配列の長さがArrayListの長さよりも大きい)を示すために使用される.
ArrayListのいくつかの重要な方法を見てみましょう.

addメソッド

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

ArrayListは配列でデータを格納するため,addは配列の次のビットにeを格納する.しかし、まず配列の長さが十分に大きいことを保証しなければなりません.そうしないと、オーバーフローする可能性があります.ここでは,内部配列が要素の増加に伴って自動的に拡張される過程も見られる.

    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 = Arrays.copyOf(elementData, newCapacity);
        }
    }

配列の長さが入力されたminCapacityよりも小さい場合は、拡張が必要です.元の長さの1.5倍+1に拡張します.一度拡張した後もminCapacityより小さい場合は、minCapacityに直接拡張します.

getメソッド

    public E get(int index) {
        RangeCheck(index);
        return (E) elementData[index];
    }

まずindexをチェックし、indexがArrayListのsizeよりも大きい場合はIndexOutOfBoundsExceptionエラーを投げ出す.そうでなければ、配列にindexと表示されている要素を返すのは簡単です.ここを見ると、なぜindexがマイナスかどうかをチェックする必要がないのかと聞かれるかもしれません.indexが負数であれば異常を投げ出すが,indexがsizeよりも下位配列の長さよりも大きい場合,elementData[index]はエラーを報告しないが論理に反するため,手動で処理する必要がある.

containsメソッド

    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

indexOf()、StringのindexOf()が考えられるはずですが、oの配列の下付き文字を得るために使われていると推測しにくいです.ソースコードを見て印象を深める:

   public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
        } else {
            for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
        }
        return -1;
    }

ここではnullの場合を特殊に処理するだけで,nullが入力されても配列を巡ってマッチングする.nullではないオブジェクトについてはequalsメソッドを呼び出して比較する.最初に一致する要素の下付き記号を返します.これに対応するもう1つのlastIndexOf(o)方法は、最後の一致要素の下付きスケール(すなわち、後方から前方へ遍歴)を返すために使用される.

removeメソッドremoveは2つの方法に分けられ、1つは下付き文字に基づいてremoveであり、もう1つは入力された要素に一致してremoveであり、まず1つ目は

である.

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

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

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

        return oldValue;
    }

まずindexの有効性も保証しなければならないが,これは前述のget(index)方法についても述べた.では、配列内の要素の削除であり、配列のメモリ領域が割り当てられて固定されていることを知っている以上、配列を新規に作成し、削除されていない要素をコピーするしかありません.

System.arraycopy(elementData, index+1, elementData, index, numMoved);

このコードは、elementDataをindex+1から、numMoved個の要素を合計して、前の位置に順次コピーすることを意味します.この場合、ArrayListのsizeはまだ変化しておらず、elementData[size-1]は以前のelementData[size-1]の値であるため、sizeを1だけ小さくしてnullとする必要がある.その後,そのオブジェクトが占有するメモリ領域を回収する作業はGCに任せる.
第2のremove方式:

    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(index)はremove(index)のような操作ですが、fastRemoveは削除したオブジェクトを返す必要はなく、RangeCheckも必要ありません.しかし、なぜindexOf(o)でindexを得ないのか、効率的にも同じだと思います.

clear()メソッド

    public void clear() {
        modCount++;

        // Let gc do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }

下位配列要素をすべてnullにし、GCに渡してメモリを回収し、sizeを0にします.

toArrayメソッドArrayListをArrayに変換するメソッドは、本来内部に配列を用いてデータを格納しているので、直接下位配列に戻ればよい:

    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }

ただし、ArrayListに保存されている配列にはタイプ情報、すなわちObject[]がありません.これは、取得後にString[]のような形式に強く移行することはできません.ArrayListは、T[]を返すためのtoArray(T[]a)メソッドを提供する.

    public <T> T[] toArray(T[] a) {
        if (a.length < size)
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());

        System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }

受信された配列の長さがArrayListのsizeより小さい場合、新しい配列が直接作成され、受信された配列のタイプに応じて返される配列のタイプが決定されます.そうでなければ、最下位の配列を受信した配列に直接コピーします.受信配列の長さがsizeより大きい場合は、受信配列の下にsizeとマークされている要素をnullに設定します(具体的な意味はよく分かりません).

removeRangeメソッドについてこれはprotected修飾メソッドです:

    protected void removeRange(int fromIndex, int toIndex) {
        modCount++;
        int numMoved = size - toIndex;
            System.arraycopy(elementData, toIndex, elementData, fromIndex,
                             numMoved);

        // Let gc do its work
        int newSize = size - (toIndex-fromIndex);
        while (size != newSize)
            elementData[--size] = null;
    }

どこで呼び出しますか?一つはAbstractListのclearメソッドで呼び出され、もう一つはSubListのremoveRangeメソッド(protected)で呼び出された.ただし、ArrayListはAbstractListのclearメソッドを書き換えているので、第1の場所はもう呼び出されないので、第2の場所のremoveRangeメソッドだけが呼び出されており、SubListはAbstractListを継承しているので、removeRangeは実はclearによって呼び出されている.セグメントコードを書いてテストしてみましょう.

        List<String> list = new ArrayList<String>();
        list.add("a");
        list.add("b");
        list.add("c");
        list.add("d");
        list.add("f");
        list.subList(2, 4).clear();
        System.out.println(list);

実はArrayListのremoveRangeメソッドを呼び出したのです
上記の多くの方法にはmodCount++の操作があります.この属性はAbstractListから継承されています.公式ドキュメントではlist構造が変更された回数を記録するために使用されていますが、実際には正確ではありません.例えば、上記のensureCapacity方法を見てみましょう.

    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 = Arrays.copyOf(elementData, newCapacity);
        }
    }

ここでensureCapacityを呼び出すたびにmodCount++になりますが、list構造は必ずしも変更されるわけではありません.