ArrayList の一般的なメソッドのソース コードの詳細な説明

ArrayListとLinkedListの類似点と相違点については、ほぼすべての学生が筆記試験や面接で聞かれると思います。ある程度の準備ができている人はすでにこれらの問題に精通しています。前者は配列の実装に基づいており、後者はリンク リストの実装に基づいています。前者のランダムな方法は高速ですが、後者の場合は指定された位置の削除と挿入が遅くなります。ランダム アクセスは遅く、指定された位置での削除と挿入は高速です。どちらも、リストと配列などの違いがあります。

リストと配列の大きな違いの一つは、配列は初期化中にサイズ変更する必要があり、動的に拡張できないのに対し、リストは動的に拡張できることです。 ArrayList は配列に基づいて実装されていますが、動的な拡張はどのように実現するのでしょうか?
ArrayList を初期化するには 3 つの方法があります:
最初のデフォルトの構築方法では、ArrayList は容量を初期化しませんが、リストの要素データ参照を空の配列にポイントします。

private transient Object[] elementData;private static final Object[] EMPTY_ELEMENTDATA = {};

//1.ArrayList默认构造方法public ArrayList() {    super();this.elementData = EMPTY_ELEMENTDATA;
}

JDK1.6 とは異なり、JDK1.6 はデフォルトのコンストラクターを呼び出すときにも容量を初期化します。JDK1.7 を使用すると、確かにストレージ領域に一定の利点があります。無駄になりますので、追加するまで待ってから容量を初期化してください。

//JDK1.6 ArrayListpublic ArrayList() {this(10);
}

2 番目の構築方法では、指定されたサイズの配列を直接作成し、リストの要素配列参照をそれを指します。

//2.ArrayList带有初始化大小的构造方法public ArrayList(int initialCapacity) {super();if (initialCapacity < 0)throw new IllegalArgumentException("Illegal Capacity: "+   initialCapacity);this.elementData = new Object[initialCapacity];
}

3番目の構築方法ではコレクションをパラメータとして渡すことができますが、コレクション内の要素はArrayList内の要素を継承する必要があります。

//3.可将一个集合作为ArrayList的参数构造成ArrayListpublic ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();    //将集合转换为数组size = elementData.length;    //集合中的元素大小// c.toArray might (incorrectly) not return Object[] (see 6260652) 这里是个bug，参考http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
}

上記のバグがあり、コレクションを配列に変換するときに、誤って Object[] が返されない可能性があります。その例を次に示します。

 1 package com.algorithm.sort; 2  3 import java.util.ArrayList; 4 import java.util.Arrays; 5 import java.util.List; 6  7 /** 8  * bug编号:6260652。toArray有可能不会返回Object[] 9  * Created by yulinfeng on 2017/6/26.10  */11 public class Test {12     public static void main(String[] args) {13         correctly();14         incorrectly();15     }16     17     /**18      * 返回Object[]19      */20     private static void correctly() {21         List<String> list = new ArrayList<String>();22         list.add("test");23         System.out.println(list.getClass());24         Object[] objArray = list.toArray();25         System.out.println(objArray.getClass());26     }27     /**28      * 不返回Object[]29      */30     private static void incorrectly() {31         List<String> list = Arrays.asList("test");32         System.out.println(list.getClass());33         Object[] objArray = list.toArray();34         System.out.println(objArray.getClass());35     }36 }

実行結果:

上記の例は、toArray が常に Object[] を返すわけではないことを示しています。Object[] が返された場合、Object 要素は挿入できないため、JDK は「6260652」になります。このバグは修正されました。

次に、要素の挿入や削除などの他のメソッドを見てみましょう。

//ArrayList#addpublic boolean add(E e) {
    ensureCapacityInternal(size + 1);  //确保容量是否充足elementData[size++] = e;    //将元素添加至数组return true;
}

//ArrayList#ensureCapacityInternalprivate void ensureCapacityInternal(int minCapacity) {if (elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);     //如果此时还没有初始化列表容量大小，则对其初始化，默认容量为10    }
    ensureExplicitCapacity(minCapacity); //检查容量是否充足}

//ArrayList#ensureEcplicitCapacityprivate void ensureExplicitCapacity(int minCapacity) {
    modCount++;    //注意此变量if (minCapacity - elementData.length > 0)
        grow(minCapacity);    //容量不够则进行扩容}

ensureEcplicitCapacityメソッド内でインクリメントされるmodCount（カウント変更）変数があります。

protected transient int modCount = 0;

この変数は add メソッド内で自動的に増加するだけでなく、追加や削除など ArrayList 構造に変更があった場合に記録され、1 ずつ増加します。その理由は Iterator のトラバーサルに関連しています。マルチスレッド化中。 AbstractList$Itr にもそれに対応する変数があります。

//AbstractList$Itrint expectedModCount = modCount;

AbstractList$Itr#nextでcheckForComodificationメソッドが呼び出されます。

//AbstractList$Itr#checkForComodificationfinal void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();
}

現在実行中の環境がシングルスレッドの場合、追加、変更、削除など、リストに対してどのような操作が実行されても、unexpectedModCount は常に modCount と等しくなります。環境がマルチスレッドである場合、1 つのスレッドが反復トラバーサル中に別のスレッドが追加または変更することを許可しない可能性が高く、このとき、ConcurrentModificationException 例外がスローされます。 modCount変数はここにあります。
ArrayList#addメソッドに戻り、リストの容量が足りない場合はgrowメソッドを呼び出して容量を拡張します。

//ArrayList#growprivate void grow(int minCapacity) {int oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1);    //扩容策略为，每次新增容量的大小为旧容量的一半。也就是说如果默认容量为10，则第一次扩容大小为10 / 2 = 5，第二次扩容大小为15 / 2 = 7。if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;    //扩容策略扩得太小if (newCapacity - MAX_ARRAY_SIZE > 0)    //扩容策略扩得太大，大于最大数组大小时，最多等于Integer.MAX_VALUEnewCapacity = hugeCapacity(minCapacity);
    
    elementData = Arrays.copyOf(elementData, newCapacity);
}

ArrayListは指定されたインデックス位置にある要素getメソッドを取得します。

public E get(int index) {
    rangeCheck(index);    //检查索引是否越界return elementData(index);
}

ArrayList は配列に基づいて実装されているため、このメソッドは範囲外かどうかを判断するだけで、そうでない場合は配列の添え字に従って要素を返すだけです。 Remove メソッドは、指定された位置にある要素を削除します。

//ArrayList#removepublic E remove(int index) {
    rangeCheck(index);    //检查索引是否越界modCount++;    //记录modCount，上面已提及E oldValue = elementData(index);    //取出指定索引元素int numMoved = size - index - 1;    //移动的元素个数if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null; //将最后一个数组元素置为null，方便GCreturn oldValue;
}

コードは比較的単純で、指定された要素を削除するときの配列の実践に基づいた ArrayList の効率の問題も反映しています。 Arrays.copyOf メソッドと System.arraycopy メソッドについては、「System.arraycopy(src, srcPos, dest, destPos, length) と Arrays.copyOf(original, newLength) の違い」を参照してください

以上がArrayList の一般的なメソッドのソース コードの詳細な説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。