いろいろガンガンいこうぜ。体も大事に

普段はJavaでAndroidアプリ開発しているプログラマーのブログです。

ArrayListの中身を見てみた(1)

ArrayList

完全修飾名で言うと，

java.util.ArrayList

いつもお世話になっているこのクラスの実装がどうなっているのか？

気になったので中身を見てみました。



参照したのは，Android SDKの以下の
リファレンスは
docs/reference/java/util/ArrayList.html
ソースコードは，
sources/android-16/java/util/ArrayList.java



ArrayListクラスは，
AbstractListを継承していて，

  • Cloneable
  • Serializable
  • RandomAccess

インターフェースを実装しています。

また，スーパークラスが実装しているインターフェースには，

  • Collection
  • List

インターフェースなどがあります。





コンストラクタ

とりあえずコンストラクタから。

  1. public ArrayList(int capacity)

　　引数capacityの値を初期容量とするコンストラクタ

  1. public ArrayList()

　　0を初期容量とするコンストラクタ

  1. public ArrayList(Coolection collection)

　　コレクションを引数に取り，そのコレクションの要素を含むインスタンスを作るコンストラクタ

の3種類があります。


2.と3.のコンストラクタについてですが，
Collectionインターフェースのドキュメントによると，
Collectionインターフェースを実装するクラスは少なくとも二つのコンストラクタを持つべきだそうです。
一つは引数なしで空のコレクションを作るコンストラクタ(2番)。
もう一つは，引数のコレクションと同じ要素を初期構成要素とするコレクションを作るコンストラクタ(3番)

3番のコンストラクタは，以下のように使うことができます．

public static void main(String[] args) {
        ArrayList<String> list;

        Map<String, String> map = new HashMap<String, String>();
        map.put("a", "Taro");
        map.put("b", "Jiro");
        map.put("c", "Saburo");

        list = new ArrayList<String>(map.values());
        System.out.println(list);

        list = new ArrayList<String>(map.keySet());
        System.out.println(list);

        Set<String> set = new HashSet<String>();
        set.add("Tokyo");
        set.add("Aichi");
        set.add("Osaka");
        set.add("Fukuoka");
        list = new ArrayList<String>(set);
        System.out.println(set);
}

容量を表すsize変数とオブジェクトを格納する配列

ArrayListクラスは次のようなフィールドを持ちます．

  • 今いくつの要素を保持しているかを表すint型のsize変数
  • オブジェクトを保持するObject[]型のarray

他にもありますが．．．
それはまた別の機会に。



sizeフィールドは，

例えば
ArrayListが何も保持していなければtrueを返す
public boolean isEmpty()
メソッドの中で，

@Override public boolean isEmpty() {
    return size == 0;
}

のようにs使っていたり，

リスト中の特定の位置の要素を取り出すgetメソッドでは，

@SuppressWarnings("unchecked") @Override public E get(int index) {
    if (index >= size) {
        throwIndexOutOfBoundsException(index, size);
    }
    return (E) array[index];
}

の用に，
不正な引数のチェックに使ったりしています。


arrayフィールドは，
オブジェクトの保持に使っていて，

@Override public boolean add(E object) {
    Object[] a = array;
    int s = size;
    if (s == a.length) 
          Object[] newArray = new Object[s +
                (s < (MIN_CAPACITY_INCREMENT / 2) ?
                 MIN_CAPACITY_INCREMENT : s >> 1)];
        System.arraycopy(a, 0, newArray, 0, s);
        array = a = newArray;
    }
    a[s] = object;
    size = s + 1;
    modCount++;
    return true;
}

addメソッドは，arrayに追加したい要素を加えます。
保持している要素の最後尾に新しい要素を加えます。
必要であればその途中でより大きな配列を生成して，
今まで保持していた要素をコピーすることで，
arrayのサイズをより大きくします。


ArrayList固有のメソッド

addメソッド・addAllメソッドを使うとフィールドarrayはどんどん大きくなっていきます。
ArrayListインスタンスの要素数・内部のarray型の配列長が10000になったとします。
その後removeメソッドで9000個の要素が削除され，要素数が1000になったとします。
この時，要素数1000に対してarrayの配列長は10000のままです。


このように大きくなってしまった内部の配列arrayのサイズを今の要素数のサイズまで小さくするメソッドがあります。
public void trimToSize()メソッドです。

    public void trimToSize() {
        int s = size;
        if (s == array.length) {
            return;
        }
        if (s == 0) {
            array = EmptyArray.OBJECT;
        } else {
            Object[] newArray = new Object[s];
            System.arraycopy(array, 0, newArray, 0, s);
            array = newArray;
        }
        modCount++;
    }





内部のarrayを小さくするメソッドもあれば，大きくするメソッドもあります。
addメソッドでちらっと触れたのですが，
要素を追加するときにArrayList型のインスタンスは必要があれば，
内部の配列arrayを大きくします。

非常に大きい配列を以下のようにArrayListに格納する時に，

// ids Integer型の配列　非常に要素数が多い
// list Integer型を格納するArrayList
for (Integer id : ids) {
    list.add(id);
}

バックグラウンドでは，内部の配列arrayの拡張が複数回実行されてしまいます。
内部の配列の拡張は，より大きな配列の作成と今まで使っていた配列から新たな配列へのコピーが行われます。
内部の配列の拡張は少ないにこしたことはありません。
そこで，この後必要になる要素数が分かっていて，内部の配列がその大きさを確保したいときは，public void ensureCapacity(int minimumCapacity)メソッドが使えます。

public void ensureCapacity(int minimumCapacity) {
    Object[] a = array;
    if (a.length < minimumCapacity) {
        Object[] newArray = new Object[minimumCapacity];
        System.arraycopy(a, 0, newArray, 0, size);
        array = newArray;
        modCount++;
     }
}


以下のようにすれば，複数回内部の配列の拡張が行われることはありません。

// ids Integer型の配列　非常に要素数が多い
// list Integer型を格納するArrayList
list.ensureCapacity(ids.length);
for (Integer id : ids) {
    list.add(id);
}

また，前述したコンストラクタを以下のように使えば，配列の拡張の回数を減らすことができます．

ArrayList<Integer> list = new ArrayList<Integer>(ids.length);
for (Integer id : ids) {
    list.add(id);
}



まだまだ気になることがたくさんありましたので，
何回かArrayListを続けていこうと思います。


では，また会えることを祈りつつ．