Java集合のArrayListソース解析(下)

要素の変更

//                
public E set(int index, E element) {
 rangeCheck(index);    
 //   index    

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

要素の検索

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

//               ，      null        。
//      -1。      O(N)
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;
}

//                 ，      -1。      O(N)
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;
}

//        ，     ，       
@SuppressWarnings("unchecked")
E elementData(int index) {
 return (E) elementData[index];
}

//        ，                 
public E get(int index) {
 rangeCheck(index);

 return elementData(index); 
 //   return (E) elementData[index]
}

シーケンス化

//             （     ）。              
private void writeObject(java.io.ObjectOutputStream s) 
throws java.io.IOException{
 int expectedModCount = modCount;
 s.defaultWriteObject(); 
 //         /     。                  
 //     
 s.writeInt(size);
 //          
 for (int i=0; i   s.writeObject(elementData[i]);
 }
 if (modCount != expectedModCount) {
   throw new ConcurrentModificationException();
 }
}
//    ，      。
private void readObject(java.io.ObjectInputStream s) 
throws java.io.IOException, ClassNotFoundException {
 elementData = EMPTY_ELEMENTDATA;
 //         /      
 s.defaultReadObject();
 //       
 s.readInt();
 if (size > 0) {
   ensureCapacityInternal(size);
   Object[] a = elementData;
   //      
   for (int i=0; i     a[i] = s.readObject();
   }
 }
}

なぜシーケンス化、逆シーケンス化メカニズムをカスタマイズするのですか?
ArrayListは実質的に動的配列であるため、配列に空きスペースがあることが多いが、デフォルトのシーケンス化メカニズムを採用すると、空きスペースはnullとしてローカルファイルに書き込まれたり、ネットワークで伝送されたりして、不要なリソースを消費する.したがって,ArrayListはカスタムシーケンス化機構を用いて,インデックスが「0,size」の有効要素のみを書き込み,リソースを節約する.
反復器

//  ListIterator，         
public ListIterator listIterator(int index) {
 if (index 0 || index > size)
   throw new IndexOutOfBoundsException("Index: "+index);
 return new ListItr(index);
}

//  ListIterator，     0
public ListIterator listIterator() {
 return new ListItr(0);
}

//       
public Iterator iterator() {
 return new Itr();
}

//        
private class Itr implements Iterator<E> {
 int cursor;       
 //  ，        ，      0
 int lastRet = -1; 
 //          
 int expectedModCount = modCount;
 //           ，       
 //       
 public boolean hasNext() {
   return cursor != size;
 }
 //     
 @SuppressWarnings("unchecked")
 public E next() {
   checkForComodification();//         
   int i = cursor;
   if (i >= size)
     throw new NoSuchElementException();
   Object[] elementData = ArrayList.this.elementData;
   if (i >= elementData.length)
     throw new ConcurrentModificationException();
   cursor = i + 1; //      
   return (E) elementData[lastRet = i];    
   //             
 }
 //    
 public void remove() {
   if (lastRet 0)
     throw new IllegalStateException();
   checkForComodification();//         
   try {
     ArrayList.this.remove(lastRet);
     cursor = lastRet;
     lastRet = -1;
     expectedModCount = modCount;
   } catch (IndexOutOfBoundsException ex) {
     throw new ConcurrentModificationException();
   }
 }
 @Override
 @SuppressWarnings("unchecked")
 public void forEachRemaining(Consumer super E> consumer) {
   Objects.requireNonNull(consumer);
   final int size = ArrayList.this.size;
   int i = cursor;
   if (i >= size) {
     return;
   }
   final Object[] elementData = ArrayList.this.elementData;
   if (i >= elementData.length) {
     throw new ConcurrentModificationException();
   }
   while (i != size && modCount == expectedModCount) {
     consumer.accept((E) elementData[i++]);
   }
   cursor = i;
   lastRet = i - 1;
   checkForComodification();
 }
 //         
 final void checkForComodification() {
   if (modCount != expectedModCount)
     throw new ConcurrentModificationException();
 }
}

//ListIterator     
private class ListItr extends Itr implements ListIterator<E> {
 ListItr(int index) {
   super();
   cursor = index;
 }
 public boolean hasPrevious() {
   return cursor != 0;
 }
 public int nextIndex() {
   return cursor;
 }
 public int previousIndex() {
   return cursor - 1;
 }
 @SuppressWarnings("unchecked")
 public E previous() {
   checkForComodification();
   int i = cursor - 1;
   if (i 0)
     throw new NoSuchElementException();
   Object[] elementData = ArrayList.this.elementData;
   if (i >= elementData.length)
     throw new ConcurrentModificationException();
   cursor = i;
   return (E) elementData[lastRet = i];
 }
 public void set(E e) {
   if (lastRet 0)
     throw new IllegalStateException();
   checkForComodification();
   try {
     ArrayList.this.set(lastRet, e);
   } catch (IndexOutOfBoundsException ex) {
     throw new ConcurrentModificationException();
   }
 }
 public void add(E e) {
   checkForComodification();
   try {
     int i = cursor;
     ArrayList.this.add(i, e);
     cursor = i + 1;
     lastRet = -1;
     expectedModCount = modCount;
   } catch (IndexOutOfBoundsException ex) {
     throw new ConcurrentModificationException();
   }
 }
}

IteratorとListIteratorの違い:
Iteratorは、すべての集合、Set、List、Mapおよびこれらの集合のサブタイプに適用することができる.一方、ListIteratorは、Listおよびそのサブタイプにのみ使用できる.Iteratorは順序の後方ループのみを実現し、ListIteratorは順序の後方ループと逆方向(順序の前方)ループを実現することができる;Iteratorはremove操作のみを実現でき、ListIteratorはremove操作、add操作、set操作を実現できる.その他の方法

//  ArrayList   （    ）
public int size() {
 return size;
}

//  ArrayList    
public boolean isEmpty() {
 return size == 0;
}

//    ArrayList      
//（         ，               ）
public Object clone() {
 try {
   ArrayList> v = (ArrayList>) super.clone();
   v.elementData = Arrays.copyOf(elementData, size);
   v.modCount = 0;
   return v;
 } catch (CloneNotSupportedException e) {
   throw new InternalError(e);
 }
}
/*
           Arrays.copyOf， System.arraycopy，
     ，    N          。
   (    ):       。

   (    ):   +  。
*/

//      ArrayList        
public Object[] toArray() {
 return Arrays.copyOf(elementData, size);
}

//       ，         ，                
//（          ）
//                     
@SuppressWarnings("unchecked")
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;
}

ArrayListに関する質問
Integer.MAX_VALUE-8ここでなぜ8を引くのですか?
主に異なるJVMを考慮して、あるVMはいくつかのデータヘッダを加えて、拡張後の容量がMAX_ARRAY_SIZEより大きい場合、最小需要容量とMAX_ARRAY_SIZEを比較して比較します.それより大きい場合はInteger.MAX_VALUEしか取れません.そうでない場合はInteger.MAX_VALUE-8です.これはjdk 1.7からあります.
jdk 1.8の無パラメトリック構造関数と以前のバージョンの構造関数の違いは何ですか?

jdk1.6
public ArrayList() {    
   this(10);    
} 

jdk1.7
public ArrayList() {    
   super();    
   this.elementData = EMPTY_ELEMENTDATA;    
}

jdk1.8
public ArrayList() {    
   this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;    
}

比較するとjdk 1.6の無パラメトリック構築方法(デフォルト構築方法)で構築されたArrayListの下位配列elementDataサイズ(容量)はデフォルトで10、1.7から無パラメトリック構築方法で構築されたArrayListの下位配列elementDataサイズはデフォルトで0であることがわかる.
JAvaコレクションクラスはjdk 1.7バージョンで基本的に1つの変更があります:怠け者初期化.怠け者初期化とはデフォルトの構造方法で構築されたコレクションクラスで、できるだけ少ないメモリ空間を占有します(ArrayListでは、空の配列を使用してできるだけ少ない空間を占有し、nullを使用しないのはnull判断を避けるためです).本格的な初期化作業は、追加の意味を含む操作が初めて行われるときに行われます.
1.7から始まるArrayListでは、デフォルトの構築方法で構築された例で、下位配列は空の配列であり、容量は0であり、最初のadd/addAllなどの操作を行うと、下位配列にempty以外の値が付与されます.add/addAllが追加した要素が10未満の場合、elementData配列を10要素サイズに拡張します.そうでなければ、適切なサイズを使用します(例えば、最初のaddAllが6個追加されると、10個に拡張され、最初の追加が10個より大きい、例えば24個、24個に拡張されるのが適切である)
1.8バージョンでは、デフォルト構造のインスタンスという動作は変更されず、配列名が変更されただけです.
jdk 1.6における拡張アルゴリズムの欠陥
(jdk 1.7とjdk 1.8は拡張アルゴリズムにおいて大きな差がないため、以下では厳密に区別しない)

//jdk1.6
public void ensureCapacity(int minCapacity) {  
   modCount++;  
   int oldCapacity = elementData.length;  
   if (minCapacity > oldCapacity) {  
       Object oldData[] = elementData;  
       int newCapacity = (oldCapacity * 3)/2 + 1;  
       if (newCapacity < minCapacity)  
           newCapacity = minCapacity;  
       // minCapacity is usually close to size, so this is a win:  
       elementData = Arrays.copyOf(elementData, newCapacity);  
   }  
}

上のコードからjdk 1.6のensureCapacityメソッドは論理的な操作を簡単に行っただけであり,int型オーバーフローの問題をあまり考慮せず,1.7からこれを改善した.
また、入参minCapacityがintオーバーフローによって負数になる可能性は考えられませんでした.この方法は外部から手動で呼び出すことができ、手動で負数を拡張するのは間違いなく遮断すべきです.しかし、自動拡張はintオーバーフローによって負数が発生します.このような状況に遭遇した場合、何もしないのではなく、後ろにArrayIndexOutOfBoundsExceptionが投げ出されるのを待っています.
また、次のコードは早すぎるオーバーフローをもたらします.

int newCapacity = (oldCapacity * 3)/2 + 1;

上の行のコードは1.7から始まるoldCapacity+(oldCapacity>>1)とは差が少なく、いずれも1.5倍に相当しますが、実際には違いがあります.
ここには主に2つの違いがあります
1つ目の違いは、jdk 1.6の乗除演算の数学的結果が、oldCapacity=10、1.6のアルゴリズムのように、後の1つよりも大きく、16、1.7から始まるアルゴリズムのように15を得ることであり、この影響は大きくない.
2つ目の違いは、oldCapacity=10^9など、数字が大きい場合の演算結果が異なることです.この数はInteger.MAX_VALUEビット数と同じで、1.6のアルゴリズムで得られるのは間違いです.-647483647、1.7のアルゴリズムでは正しい1500000000、1.5倍の拡張が可能なのにjdk 1.6はオンデマンド拡張が使われています.
EnsureCapacity(手動と呼ばれるのは、この方法がpublicで外部手動で呼び出すことができるためである).1.6バージョンではこの手動のみの方法であり、内部自動操作もこの方法を呼び出し、1.7は区別を開始し、さらに拡張操作を改善した.
1.7から内部拡張と外部呼び出し可能な拡張方法が分離され、ソースコードから分かるように、外部呼び出しの手動拡張方法ensureCapacityは、負の数のminCapacityをブロックする判断条件minCapacity>minExpandを複数必要とし、内部拡張ensureCapacityInternalメソッドを呼び出すと、minCapacityは必ず正数である;内部拡張方法は直接minCapacity-elementData.length>0で判断し、この条件はint型オーバーフローを検出することができ、オーバーフローに遭遇すると最後にOOMエラーが投げ出される.jdk 1.7はOOMで、jdk 1.6はArrayIndexOutOfBoundsExceptionでより良い.この場合、配列サイズが仮想マシンの配列に対する制限を超えているため、仮想マシンはこのような状況を処理できない.ERRORを投げ出すのは合理的である.
この行のコードを使用

newCapacity = oldCapacity + (oldCapacity >> 1);

この行コードは、ビット演算を用いて実行速度を速めるだけでなく、前述したように、真の1.5倍である.その大きさの違いだけでなく、intオーバーフローが早すぎることを避けることが重要であり、内部自動拡張ができるだけ所定のポリシーで実行されることを保証している.同時に、拡張処理プロセス全体にif判断がいくつか追加され、様々な状況の処理がより完備している.
なぜArrayList自動容量拡張選択が1.5倍拡張されたのですか?
このアルゴリズムにより構築された新しい配列長の増分は,前回よりも大きく(しかもますます大きく)なり,頻繁なnewInstanceを回避する.
なぜArrayListは頻繁な挿入と削除操作に適していないのですか?
以上の解析の追加削除手法から,ArrayListではSystem.arraycopyという効率の低い操作を呼び出して配列をコピーすることがしばしばあるため,ArrayListは挿入と削除操作で効率が悪いことが分かる.