老猿説-ARrayList

27561 ワード

1概要
ArrayList全体のアーキテクチャは比較的簡単で、1つの配列構造である.例えば、長さが10の配列で、1からカウントし、indexは配列の下付きを表し、0からカウントし、
ElementDataは配列そのものを表し、ソースコードにはこの2つの概念のほかに、以下の3つの基本概念があります.

DEFAULT_CAPACITYは配列の初期サイズを表し、デフォルトは10で、この数字は覚えておいてください.

sizeは現在の配列の大きさ、タイプintを表し、volatile修飾を使用せず、スレッドではなく安全である.

modCountは現在の配列が修正されたバージョン数を統計し、配列構造が変動すると+1になります.

クラスコメント
ソースコードを見て、まずクラス注釈を見て、私たちはクラス注釈の上で何を言っているのかを見て、以下のようにします.

はput null値を許可し、自動的に拡張する.

size、isEmpty、get、set、addなどの方法の時間複雑度はすべてO(1)である.上記の注釈で述べた4点に加えて,初期化,拡張の本質,反復器などの問題もしばしば聞かれ,次にソースコードから解析する.

2ソース解析
2.1初期化
パラメータなしで直接初期化、サイズを指定して初期化、初期データを指定して初期化する3つの初期化方法があります.ソースコードは次のようになります.

private static final ObjectD DEFAULTCAPACITY_EMPTY_ELEMENTDATA = 0;
  //        ，      
  public ArrayList(){
     
    this.elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  }
  //         
  public ArrayList(Collection<? extends E> c){
     
      //elementData        ，   null
      elementData=c.toArray();
      //       （c)    
      if((size=elementData.length)!=0){
     
        //c.toArray might(incorrectly)not return Object[](see 6260652)
        //          Object  ，     Object
      if(elementData.getClass()!=Object[].class){
     
        elementData=Arrays.copyOf(elementData,size,Object].class);
      }
    }else{
     
      //    （c)  ，      
      this.elementData=EMPTY_ELEMENTDATA
    }
  }
}

ソースコードの中国語の注釈を除いて、私たちは2つの点を補充します.

ArrayList無パラメトリックコンストラクタが初期化された場合、デフォルトサイズは空の配列であり、一般的に言われている10,10が最初のaddで拡張された配列値ではない.

初期化データを指定すると、Javaのバグであり、所与の集合内の要素がObjectタイプでない場合、Objectタイプに変換されるという注釈see 6260652が発見される.通常、このバグはトリガーされません.ArrayListの初期化後(ArrayList要素がObjectタイプではありません)、toArrayメソッドを再度呼び出してObject配列を取得し、Object配列に値を割り当てると、ドキュメントアドレスが公式に表示されます.https://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652、問題はJava 9で解決されます.

2.2新機能と拡張機能の実現
新規は配列に要素を追加し、主に2つのステップに分けます.

拡張が必要かどうかを判断し、拡張操作が必要であれば.

直接付与.

2つのステップのソースコードは以下の通りです.

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

まず、拡張(ensureCapacitylnternal)のソースコードを見てみましょう.

private void ensureCapacitylnternal(int minCapacity){
     
  //          ，      ，        ，  if  
  if(elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA){
     
    minCapacity=Math.max(DEFAULT_CAPACITY,minCapacity);
  }
  //      
  ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity){
     
  //       
  modCount++;
  //                    ，     
  if(minCapacity-elementData.length>0)
    grow(minCapacity);
}

//  ，                
private void grow(int minCapacity){
     
  int oldCapacity = elementData.length;
  //oldCapacity>>1  oldCapacity  2   
  int newCapacity=oldCapacity+(oldCapacity>>1);
  //       
  if(newCapacity-minCapacity<0)
    newCapacity = minCapacity;
  //       >jvm           ，    Integer    
  if(newCapacity-MAX_ARRAY_SIZE>0)
    elementData=Arrays.copyOf(elementData,newCapacity);
}

注釈は比較的詳細であるべきで、注意しなければならない4つの点は:

拡張のルールは2倍ではなく、元の容量サイズ+容量サイズの半分であり、率直に言えば、拡張後のサイズは元の容量の1.5倍である;

ArrayListの配列の最大値はInteger.MAX_VALUEです.この値を超えると、JVMは配列にメモリ領域を割り当てません.

が追加された場合、値の厳密な検証は行われないため、ArrayListはnull値を許可する.

新しいソースコードと拡張ソースコードから、以下の点を参考にします.

ソースコードは拡張する時、配列の大きさのオーバーフロー意識があって、つまり拡張後の配列の大きさの下限は0より小さくてはいけなくて、上界はIntegerの最大値より大きくてはいけなくて、このような意識は私達は

を学ぶことができます
拡張が完了すると、付与は非常に簡単で、配列に直接要素を追加すればよい:elementData[size+]=eもこのような単純な付与によって、ロック制御がないため、ここでの操作はスレッドが安全ではない
2.3拡張の本質
拡張はこの行のコードによって実現される:Arrays.copyOf(elementData,newCapacity);この行のコード記述の本質は配列間のコピーであり、拡張はまず私たちの予想される容量に合致する新しい配列を作成し、それから古い配列のデータをコピーし、System.arraycopy方法によってコピーし、この方法はnativeの方法であり、ソースコードは以下の通りである.

/**
*@param src       
*@param srcPos        
*@param dest     
*@param destPos               
*@param length      
*          ，  dest       
*/
public static native void arraycopy(Object src, int srcPos,Object dest, int destPos,int length);

次の行のコードで呼び出すことができます.newElementDataは新しい配列を表します.

System.arraycopy(elementData,0,newElementData,0,Math.min(elementData.length,newCapcity));

2.4削除
ArrayList削除要素には、配列インデックスによる削除、値による削除、または一括削除など、さまざまな方法がありますが、原理と考え方が異なります.値による削除方法を選択してソースコードの説明を行います.

public boolean remove(Object o) {
     
  //        null,       null   
  if(o==null){
     
    for(int index=0;index<size;index++)
      if(elementData[index]==null){
     
        fastRemove(index)
        return true
      }
  }else{
     
    //         null,                
    for(int index=0;index<size;index++)
      //      equals       ，              
      if(o.equals(elementData[index]){
     
        fastRemove(index)
        return true;
      }
  }
  return false
}

私たちが注意しなければならない2つの点は、

が新たに追加されたときはnullを検証していないので、削除するときもnull値の削除を許可する;

配列内の値のインデックス位置は、equalsによって判断されます.配列要素が基本タイプでない場合は、equalsの具体的な実装に注目する必要があります.

上のコードは、削除する要素のインデックスの場所を見つけました.次のコードは、インデックスの場所に基づいて要素の削除を行います.

private void fastRemove(int index){
     
  //             
  nodCount++;
  //numMoved    index      ，   index            
  // 1   ，   size 1    ，index 0    
  int numMoved=size-index-1;
  if(numMoved>0)
    // index+1       ，        index,   numMoved
    System.arraycopy(elementData, index+1, elementData, index, numMoved);
  //          null,  GC
  elementData[--size] = null;
}

ソースコードから、ある要素が削除された後、配列構造を維持するために、配列の後ろの要素を前に移動することがわかります.
2.5反復器
自分で反復器を実現するにはjava.util.lteratorクラスを実現すればいいのですが、ArrayListもそうしています.反復器のいくつかの必須パラメータを見てみましょう

int cursor;//     ，        ，   0  。
int lastRet=-1;//    ：          ，     ；    ： -1。
int expectedModCount=modCount;//expectedModCount       ，

反復器には一般的に3つの方法があります

hasNextはまだ

を反復することができる値がありますか?

next値が反復できる場合、反復の値は

です.

remove現在の反復の値

を削除
次の3つの方法のソースコードを見てみましょう.
hasNext

public boolean hasNext0{
     
  return cursor!=size;//cursor          ，size      ，      ，       
}

public E next(){
     
  //     ，          ，    ， ConcurrentModificationException  
  checkForComodification();
  //       ，       
  int i=cursor;
  if(i>=size)
    throw new NoSuchElementException();
  Object[] elementData = Array List. this. elementData;
  if(i>=elementData.length)
    throw new ConcurrentModificationException0;
  //      ，     ，         
  cursor=i+1;
  //     
  return (E)elementData[lastRet=i];
}
  //     
final void checkForComodification(){
     
  if(modCount!=expectedModCount)
    throw new ConcurrentModificationException0;
}

ソースコードからnext法は,反復を継続できるかどうかを検証することと,反復の値を見つけて次の反復に備えることの2つのことを行ったことがわかる(cursor+1).
remove

public void remove(){
     
  //        ，         0 ，           
  if(lastRet<0)
    throw new IllegalStateException();
  checkForComodification();
  try {
     
    ArrayList.this.remove(lastRet);
    cursor=lastRet;
    //-1         ，         
    lastRet=-1;
    //     modCount        ，     expectedModCount
    //       ，         
    expectedModCount=modCount;
  } catch (IndexOutOfBoundsException ex){
     
    throw new ConcurrentModificationException();
  }
}

ここで注意しなければならないのは、

lastRet=-1の操作目的は、重複削除操作を防止する

である.

要素の削除に成功すると、配列は現在modCountで変化し、ここではexpectedModCountを再割り当て、次回の反復では

の値が一致します.
2.6時間複雑度
我々の上の新規または削除方法のソースコード解析から,配列要素の操作は,配列インデックスに基づいて直接新規および削除するだけであるため,時間複雑度はO(1)である.
2.7スレッドセキュリティ
ArrayListが共有変数である場合のみスレッドセキュリティの問題があり、ArrayListがメソッド内のローカル変数である場合、スレッドセキュリティの問題がないArrayListにスレッドセキュリティの問題の本質があるのは、ArrayList自身のelementData,size,modConutが様々な操作を行う際にロックされておらず、これらの変数のクラス型は可視ではない(volatile)のため、複数のスレッドがこれらの変数を操作する場合、値が上書きされる場合があります.クラスアノテーションではCollections#synchronizedListを使用してスレッドのセキュリティを保証することを推奨しています.SynchronizedListはメソッドごとにロックをかけることで実現されています.スレッドのセキュリティは実現されていますが、パフォーマンスは大幅に低下しています.具体的にはソースコードを実現します.

public boolean add(E e){
     
  synchronized(mutex){
     //synchronized      ，mutex      SynchronizedList
    return c.add(e);
  }
}

まとめ
本文はArrayList全体のアーキテクチャから出発して、着地から初期化、新規化、拡張、削除、反復などの核心ソースコードの実現まで、私達はArrayListが実は底層の配列構造をめぐっていることを発見して、各APIはすべて配列の操作に対してパッケージを行って、使用者に底層の実現を感知する必要がなくて、どのように使うことに関心を持つだけでよい.

HDU-1556 Color the ball-区間更新単点クエリ

Yubikey を Linux で使用する方法ーFirefox 編ー