ArrayListソースコードの理解

5307 ワード
しゅうごう
ArrayListはよく使われる集合である.普段使っている時にメモを取った.
一:まずArrayListの継承基盤を見てみましょう.
public class ArrayList extends AbstractList
        implements List, RandomAccess, Cloneable, java.io.Serializable

ArrayListはAbstractListを継承する.リストが実現する.ダイナミック配列に相当し、追加、修正、削除、遍歴機能を提供します.
RandomAccessを実現した.ランダムアクセス機能を提供します.すなわちget(i)メソッドである.
Cloneableが実装され、クローン化が可能になります.
Serializable.シーケンス化できます.
二:ソースコードを分析する:
  1.List list=new ArrayList()の2つの構成方法がある.デフォルトでは、サイズ10のコレクションが作成されます.                    List list=new ArrayList(2);サイズ2のコレクションを作成します.
         
 //ArrayList 
    public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity]; // elementData
    }
  
    // 
    public ArrayList() {
        super();
        this.elementData = EMPTY_ELEMENTDATA;//  
                                         //elementData，EMPTY_ELEMENTDATA 10
    }

  2.コレクションがオブジェクトを追加するたびに、コレクションのサイズが満たされているかどうかをチェックします.ensureCapacity(size+1)メソッドが呼び出されます.コレクションが要素を収容できることを確認します.
// e ArrayList 
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

毎回1/2容量が追加されます.ソースコード:int newCapacity=oldCapacity+(oldCapacity>>1);
// ， ， public ， private 
    public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != EMPTY_ELEMENTDATA)
            // any size if real element table
            ? 0
            // larger than default for empty table. It's already supposed to be
            // at default size.
            : DEFAULT_CAPACITY;
 
        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }
 
    private void ensureCapacityInternal(int minCapacity) {
	// 
        if (elementData == EMPTY_ELEMENTDATA) {
	    // minCapacity 10 
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
	// 
        ensureExplicitCapacity(minCapacity);
    }

  3.ArrayList:指定された場所に要素を追加する場合、その後ろの要素は全体的に1つ移動する必要があります.1つの要素を削除する場合、後ろの要素も同じように1つ前に移動する必要があります.したがって、相対的な比較消費リソースを削除し、追加します.
// element ArrayList 
    public void add(int index, E element) {
        rangeCheckForAdd(index);// 
 
        ensureCapacityInternal(size + 1);  // Increments modCount!!
	// index index index+1 ， index 
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index); 
        elementData[index] = element; // index element
        size++;
    }

そしてクエリーが違います.挿入時に下付き文字がマークされているので、直接下付き文字に基づいて取得できます.だからスピードは速いです.remove(Object obj)とremove(int one)を比較した.後ろの1つはスピードが速い.前の1つはまず集合を巡回する必要があるので、その要素の下付きを見つけてからremove(int one)を呼び出す.         4.contains(Object obj)という方法も,等しい要素があるかどうかを調べるために集合を巡回する必要がある.
 public boolean contains(Object o) {
        return indexOf(o) >= 0;
    } 



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;
    }

5.fail-fastメカニズムについて.
すなわち、Aスレッドが反復器によって集合xを遍歴するときに、Bスレッドが集合xの構造を変更すると、C o n c u r r e ntModificationException異常が報告される.
private class Itr implements Iterator {  
           int cursor;  
           int lastRet = -1;  
           int expectedModCount = ArrayList.this.modCount; //expectedModCount   
      
           public boolean hasNext() {  
                return (this.cursor != ArrayList.this.size);  
            }  
      
            public E next() {  
                checkForComodification();  
                /**   */  
            }  
      
            public void remove() {  
                if (this.lastRet < 0)  
                    throw new IllegalStateException();  
                checkForComodification();  
                /**   */  
            }  
      
            final void checkForComodification() {  
                if (ArrayList.this.modCount == this.expectedModCount)  
                    return;  
                //expectedModCount  ， modCount  ， 。
                throw new ConcurrentModificationException();  
            }  
}

ArrayListの構造を変更するたびに、追加、削除など、ensureExplicitCapacity(int one)が呼び出されます.modCountの値を変更します.
private void ensureExplicitCapacity(int paramInt) {  
        this.modCount += 1;    // modCount  
        /**   */  
    }

そこで、上記の結論を検証しました.遍歴すると,別のスレッドがその集合を修正し,異常を投げ出す可能性がある.
解決策:
シナリオ1:modCountの変更に関わるすべての場所にsynchronizedを追加するか、Collectionsを直接使用する.synchronizedList、これで解決できます.ただし、削除による同期ロックがループ操作をブロックする可能性があるため、推奨されません.
シナリオ2:ArrayListの代わりにCopyOnWriteArrayListを使用します.このシナリオを推奨します.
総じて言えば.ランダムアクセスは、下付き(配列と同じ)から直接取得されます.だからスピードが速い.追加、削除は全体的に移動する必要があります.だから資源を消費します.
効率比較というのは、原理さえ分かれば、比較しやすいのです
mapboxノート
Ubuntuがノートを振り回す