Java 8 ArrayListソース分析

23866 ワード

Java

学習の動機.
ArrayListは私の日常的なAndroid開発で最も使用頻度の高いデータコンテナクラスであり、非常に簡単なインタフェースであり、下層は配列構造であり、秩序性はインデックスに従って私たちが望んでいるデータを取得することを保証することができる.
Javaをステップアップしたい場合でも、データ構造の理解を深めたい場合でも、面接で余裕を持って満点を取りたい場合でも、Javaコンテナ類のソースコードの分析を学ぶのは良い選択です.
Java Collectionライブラリには、List,Queue,Setの3種類があります.一方,Listインタフェースには,ArrayList,Vector,LinkedListの3つのサブ実装クラスがある.
本稿ではArrayListソースコードの解析を行う.
文章の内容が長いので、まじめに読むことをお勧めします.
Java 8オンラインソースアドレスリファレンス(梯子をご用意ください):点我看
構築&メンバーのプロパティ

   //    ：    10   
   private static final int DEFAULT_CAPACITY = 10;

   //   ：           ArrayList  ,      
   private static final Object[] EMPTY_ELEMENTDATA = {};

   //ArrayList             
   transient Object[] elementData;

   //   size
   private int size;

ArrayListにはデフォルトで3つの構築方法があります.

//   ，             
public ArrayList() {
    super();
    this.elementData = EMPTY_ELEMENTDATA;
}

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

//      Collection   ArrayList  
public ArrayList(Collection extends E> c) {
    elementData = c.toArray();
    size = elementData.length;
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
}

我々の日常的な開発では,new Arraylist<>()空構造法によりArrayListコンテナをインスタンス化することが多く,実際には空構造が空の配列を初期化しただけであることが分かる.
ではArrayListはどのようにして配列容量の大きさを動的に変えたのでしょうか.
簡単なAdd()メソッド
空のオブジェクト配列をインスタンス化し、次に最も簡単なadd()方法を見てみましょう.

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  //     &      
    elementData[size++] = e;  //             
    return true;
}

クリックしてEnsureCapacityInternal()メソッドを見てみましょう.

//ensureCapacityInternal ->       
private void ensureCapacityInternal(int minCapacity) {
    //        ，        
    if (elementData == EMPTY_ELEMENTDATA) {
        //DEFAULT_CAPACITY    ，     10
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

引き続きensureExplicitCapacityメソッドを見てみましょう.

//modCount     ，        ，       modCount++
protected transient int modCount = 0;

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

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

単純なadd(E e)方法の背後には、こんなに多くの論理コードの実現が隠されていることがわかりますが、実際には、より細心の仲間がこのコードに疑問を抱いています.

//    ，          elementData
elementData = Arrays.copyOf(elementData, newCapacity);

私たちは最後まで追及する精神に基づいて、最後まで追跡します.

public static  T[] copyOf(T[] original, int newLength) {
    //    
     return (T[]) copyOf(original, newLength, original.getClass());
}

//       
public static  T[] copyOf(U[] original, int newLength, Class extends T[]> newType) {
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

最も重要な配列付与の論理がこの行のコードにあるため、これはまだ十分ではありません.

System.arraycopy(original, 0, copy, 0,Math.min(original.length, newLength));

私たちは深く入り込み続けましたが、結果はあまりよくありませんでした.

/**
 * @param      src      the source array.
 * @param      srcPos   starting position in the source array.
 * @param      dest     the destination array.
 * @param      destPos  starting position in the destination data.
 * @param      length   the number of array elements to be copied.
 */
public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

明らかにこの方法はnativeキーワードを用い,C++で記述された下位関数を呼び出し,JDKにおける下位関数であることがわかる.
注釈から説明を得ることができます.
src-ソース配列.src Pos-ソース配列の開始位置.dest-ターゲット配列.destPos-ターゲットデータの開始位置.length-コピーする配列要素の数.
例を挙げる
例えば配列データがあります

  byte[]  srcBytes = new byte[]{2,4,0,0,0,0,0,10,15,50};  //    
  byte[] destBytes = new byte[5]; //

System.arraycopyを使用して変換します

  System.arrayCopy(srcBytes,0,destBytes ,0,5)

上のコードは、1次元の空の配列を作成し、配列の全長を12ビットとし、src Bytesソース配列の0ビットから5ビットまでの数値copyをdestBytesターゲット配列に、ターゲット配列の0ビットから配置する.
では、この行のコードの実行効果は2,4,0,0,0であるべきです.
参考記事:java System.arrayCopy使用説明@Albin
レビュー
はい、考えとともにここまで来たら、add()の方法を理解すべきだと信じています.今、ここに戻ります.

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  //     &      
    elementData[size++] = e;  //             
    return true;
}

最初に要素を追加すると、配列コンテナ容量は10になり、配列コンテナの最初の要素はelementData[0]、size+=1に追加されます.
その後、2番目の要素を追加し続けると、容量が検出されます.

//modCount     ，        ，       modCount++
protected transient int modCount = 0;

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

    //            2，      10，           
    if (minCapacity - elementData.length > 0)
        //     11    ，       ，    10->15（+50%）
        grow(minCapacity);
}

add/remove/get/setメソッド
リロードadd()
2番目のaddメソッドを見続けます

public void add(int index, E element) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

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

System.arraycopy()メソッドの役割を理解し,容量動的処理後,elementData[]配列をindex位置で2分割し,1つの位置を空け,新しい要素を割り当て,最後にsize++することを学習した.
例を挙げる
Array=[0,1,2,3,4]->index=2の位置に-1を追加
System.arraycopy(elementData, index, elementData, index + 1,size - index);
-> array = [0,1,2,2,3,4] ->elementData[index] = -1; ->array = [0,1,-1,2,3,4]
remove()

public E remove(int index) {
     if (index >= size)//    
         throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    //    +1
     modCount++;
     E oldValue = (E) elementData[index];//       

    //    index    ，         
     int numMoved = size - index - 1;
     if (numMoved > 0)
         //       
         System.arraycopy(elementData, index+1, elementData, index,
                          numMoved);
     //      （--size）                      
     elementData[--size] = null; // clear to let GC do its work

     return oldValue;//        
 }

System.arraycopyの例
Array=[0,1,2,3,4]->削除index=2
System.arraycopy(elementData, index+1, elementData, index,numMoved);
-> array = [0,1,3,4,4] -> elementData[–5] = null; ->array = [0,1,3,4,null]
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;
}

ここでは、indexが小さいものから大きいものまでの最初のoオブジェクトのみを削除します.つまり、1つのセットに2つのオブジェクトがある場合、index値の低いオブジェクトのみを削除します.fastRemoveメソッドを見てみましょう.

private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
}

remove(int index)とは差が少なく、スープを変えても薬を変えない.
get(int index)
set(int index, E element)

public E get(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    return (E) elementData[index];
}

public E set(int index, E element) {
  if (index >= size)
      throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

  E oldValue = (E) elementData[index];
  elementData[index] = element;
  return oldValue;
}

この2つの方法が一緒に置かれているのは、本当に何も言っていないからです.一見わかりますが、配列に対応するindexの要素を取り出して返すだけです.データ構造の変化は設計されていないので、modCountは変わっていません.
その他の方法
contains(Object o)

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

//            ，  ，   index=0     index   
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;
}

//            ，  ，   index=size-1     index   
public int lastIndexOf(Object o) {
    if (o == null) {
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

toArray()

// ArrayList         
public Object[] toArray() {
     return Arrays.copyOf(elementData, size);
}
// ArrayList           
public  T[] toArray(T[] a) {
    if (a.length < size)
        // Make a new array of a's runtime type, but my contents:
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size)
        a[size] = null;
    return a;
}

clear()

//   ，                 null，  size =0 ，     length  。
 public void clear() {
    modCount++;

    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

trimToSize()

//    length>size ，        size，           
public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = Arrays.copyOf(elementData, size);
    }
}

ArrayList分析まとめ
1.ArrayListでは、主に内部配列に1つ追加され、追加された要素を指し、たまに配列の再割り当てを招く可能性があります.
2.ArrayListの中間に1つの要素を挿入または削除することは、リスト内の残りの要素が移動されることを意味する.
3.ArrayListの空間浪費は主にリストの最後に一定の容量空間を予約することに現れる.
ArrayListは、リニアテーブル(配列)get()がいくつ目の下付き文字を直接読み出し、時間複雑度O(1)add(E)が要素を追加し、直接後に追加し、時間複雑度O(1)add(index,E)が要素を追加し、いくつ目の要素の後に挿入し、後の要素は後ろに移動し、時間複雑度O(n)remove()要素を削除し、後の要素を1つずつ移動する必要があり、時間の複雑さO(n)
このように、操作が大量のクエリーと取得である場合、またはその要素にランダムにアクセスする必要がある場合、ArrayListを使用するとパフォーマンスが向上します.
Androidの開発では,ArrayListをコンテナとして用いてデータを格納し,データの読み取りと展示を行うことが多く,ArrayListは重任に値する.

eclipseを使用してAPIヘルプドキュメントを生成する方法

WSL1ではsshfsを使うことができず、WSL2を使わないといけない