配列(一):ArrayListの実装とArraysクラスの使用

10314 ワード

一、配列は長くなりますか?
配列が一定長であることはよく知られていますが、初期化時には必ず長さを与えなければなりません.この長さの問題で、実際の開発では、ArrayListなどの容器を使用する傾向があります.容器クラスを使用する場合、長さの問題を考慮する必要はありません.容器が処理してくれたので、配列は長くなることはできませんか.もちろんそうではありません.ArrayListは配列に基づいて実現されています.ArrayListがどのように処理されているかを見ることができます.
二、ArrayListの実現原理
ArrayListは、内部としてObject配列を使用し、コンテナの長さを表すメンバー変数sizeがあります.
    private transient Object[] elementData;
    private int size;

データを追加する場合、add()メソッドを呼び出します.
public boolean add(E e) {
      ensureCapacityInternal(size + 1);  // Increments modCount!!
      elementData[size++] = e;
      return true;
 }
    private void ensureCapacityInternal(int minCapacity) {
        modCount++;
        //                     ,     
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

拡張コアコードはgrowメソッドに表示されます.
    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);
        //          
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

elementData = Arrays.copyOf(elementData, newCapacity)
APIドキュメントの解釈は、指定された配列をコピーしたり、必要に応じてnullまたは0で切り取ったりして、コピーに指定された長さを持たせることです.
つまりArrays.copyOfは、配列elementDataの長さをnewCapacityに拡大し、拡大した部分の充填は配列タイプによって決まる
例:
        int[] a = new int[]{1,2};
        System.out.println("     :" + a.length);
        a = Arrays.copyOf(a, 3);
        System.out.println("     :" + a.length);
        System.out.println("     :" + a[2]);

出力:拡張前長さ:2拡張後長さ:3充填データ:0
アレックスを見てみましょうcopyOfソースコード、何をしたか見てみましょう.
    public static int[] copyOf(int[] original, int newLength) {
        int[] copy = new int[newLength];
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

  Arrays.copyOfメソッドでは、新しい長さの配列を再作成し、System.arraycopyメソッドは,元の配列を新しい配列にコピーし,最後に返す.System.arraycopyはローカルのシステム方法で、メモリの中のデータブロックを直接コピーすることを採用しています.ブロックごとにコピーするので(オペレーティングシステムで説明されています)、私たちが普段forサイクルしているコピーよりずっと速いです.
三、効率
これらの問題に注意すべきで、いつ拡張しますか?拡張は効率に影響しますか?もし影響があったらどうやって避けますか?要素を増やしたsizeが元のsizeより大きい場合は拡張が必要ですが、拡張には配列をコピーする必要があります.小さなデータ量は大丈夫ですが、大きなデータ量の場合は効率に影響します.ArrayListにはsize関連コンストラクション関数が2つあることに注意してください.
    public ArrayList() {
        this(10);
    }

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

1番目のコンストラクション関数はデフォルト容量sizeが10で、2番目の関数はデフォルトsizeがカスタマイズされています.この2つのコンストラクション関数がビッグデータ量の場合を見てみましょう.
public abstract class Array1 {

    public static void main(String[] args) {
        long b1 = System.currentTimeMillis();
        List list1 = new ArrayList();
        for(int i =0; i < 10000000; i++){
            list1.add(i);
        }
        long e1 = System.currentTimeMillis();

        System.out.println("    : " + (e1-b1));

        long b2 = System.currentTimeMillis();
        List list2 = new ArrayList(10000000);
        for(int i =0; i < 10000000; i++){
            list2.add(i);
        }
        long e2 = System.currentTimeMillis();

        System.out.println("    : " + (e2-b2));
    }

}

結果は、時間:7878時間:283
だから:あなたのArrayListの初期容量を指定してください!
三、Arrays類の使用
Arraysクラスには、配列の操作(ソートや検索など)に使用するさまざまな方法が含まれています.このクラスは熟練して使用する必要があります.このクラスの一般的な方法は、次のとおりです.
方法
説明する
asList(T… a)
指定した配列でサポートされている固定サイズのリストを返します.
copyOf(int[] original,int newLength)
指定した配列をコピーし、入力したデータは配列タイプによって決定され、コピーに指定した長さを持たせる
copyOfRange(long[] original, int from, int to)
指定した配列の指定範囲を新しい配列にコピー
equals(int[] a, int[] a2)
2つの指定されたint型配列が互いに等しい場合はtrueを返します.
fill(int[] a, int val)
指定したint値を指定したint型配列の各要素に割り当てる
sort(int[] a)
指定したint型配列を数値昇順で並べ替える
    int      example,             

四、copyOfの罠、配列の浅いコピー
配列タイプが基本データ型でない場合、配列内にはオブジェクトの参照が格納されます.したがって、copyOfでオブジェクトの配列をコピーする場合は、オブジェクト自体ではなく、コピーされたオブジェクトの参照に注意してください.
class Person{
    int age;

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

}

public class Array2 {

    public static void main(String[] args) {
        Person p = new Person();
        p.setAge(20);
        Person[] a = new Person[]{p};
        Person[] b = Arrays.copyOf(a, a.length);
        a[0].setAge(30);
        System.out.println("a   :" + a[0].getAge());
        System.out.println("b   :" + b[0].getAge());
    }
}

出力:aの年齢:30 bの年齢:30
aが値を変えるとbの値も変わることがわかります.これが浅いコピーの問題です.