JAvaにおけるListインタフェースの実装クラスArrayList,LinkedList,Vectorの違いlist実装クラスソースコード解析


JAva面接ではリストでよく使われるクラスや内部実装メカニズムをよく聞かれ、普段開発でもリスト集合クラスをよく使うので、ソースレベルの分析と比較の違いをします.
まずリストインタフェースの継承関係を見てみましょう.
ListインタフェースはCollectionインタフェースを継承し、CollectionインタフェースはIterableインタフェースを継承します.
Iterableインタフェースの定義方法:
public interface Iterable<T> {
    /**
     * Returns an iterator over a set of elements of type T.
     *
     * @return an Iterator.
     */
    Iterator<T> iterator();
}

Collectionインタフェースで定義されたメソッド:
package java.util;
public interface Collection<E> extends Iterable<E> {
    int size();
    boolean isEmpty();
    boolean contains(Object o);
    Iterator<E> iterator();
    Object[] toArray();
    <T> T[] toArray(T[] a);
    boolean add(E e);
    boolean remove(Object o);
    boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c);
    boolean removeAll(Collection<?> c);
    boolean retainAll(Collection<?> c);
    void clear();
    boolean equals(Object o);
    int hashCode();
}
ですのでlistインタフェースを実装するサブクラスは実装する必要があります
IterableとCollectionインタフェースのメソッド.Iterableは要素の反復を行うことができます.
List特性:
  • は、同じタイプの要素を格納することができる.
  • 内部メンテナンス要素間の順序は、秩序化された集合である.
  • 要素は繰り返し可能である.

  • JavaにおいてListインタフェースには,ArrayList,LinkedList,Vectorの3つの一般的な実装クラスがある.
    違いは次のとおりです.
  • ArrayList内部に格納されるデータ構造は配列格納である.配列の特徴:要素はすばやくアクセスできます.各要素の間には隣接する間隔がありません.欠点:配列空間が足りない要素の記憶が拡張する必要がある場合、新しい配列を開いて古い配列要素をコピーし、性能を比較します.ArrayListの中間位置から要素を挿入、削除するには、要素の位置を循環移動する必要があるため、配列特性は配列の特徴を決定します:ランダムな検索と遍歴に適しており、挿入と削除操作が常に必要ではありません.
  • Vector内部実装はArrayListと同様に配列記憶であり、最大の違いはスレッドの同期をサポートすることであるため、ArrayListよりアクセスは遅いがデータは安全であるため、要素に対する操作が同時操作されていない場合はArrayListの方が速い.
  • LinkedList内部記憶用のデータ構造はチェーンテーブルである.チェーンテーブルの特徴:動的な挿入と削除に適しています.アクセスが遅い.またget,remove,insertListメソッドはサポートされていません.スタック、キュー、および双方向キューとして使用できます.LinkedListはスレッドが安全ではありません.したがって、同期が必要な場合は自分で手動で同期する必要があり、手間がかかり、提供された集合ツールクラスを使用してインスタンス化できる場合は同期:具体的にはListspringokList=Collections.synchronizedCollection(newが同期を必要とするクラス)を使用する.

  • まとめ
    1.内部ストレージ構造の違い:
     ArrayList,Vectorは配列格納である.LinkedListはチェーンテーブルストレージです.
              2.スレッドのセキュリティの違い:
    ArrayList、LinkedListスレッドは安全ではありません.Vectorスレッドは安全です.
    3.シーンの違いを使う:
    スレッド同期を使用する場合はVectorクラスが優先されるか、Collectionsツールクラスを使用して初期化する場合は同期されます.
    LinkedList(チェーンテーブル構造)の使用を頻繁に削除し、追加する必要があり、ArrayList(配列構造)の反復使用を頻繁にクエリーする必要がある
    ソース分析:
    ArrayListクラス:
     public boolean add(E e) {
    //              ,    
            ensureCapacityInternal(size + 1);  // Increments modCount!!
    	//       
            elementData[size++] = e;
            return true;
        }
    private void grow(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
        }

    Vector:
    private void ensureCapacityHelper(int minCapacity) {  
       
         int oldCapacity = elementData.length;  
       
         if (minCapacity > oldCapacity) {  
       
             Object[] oldData = elementData;  
       
             int newCapacity = (capacityIncrement > 0) ?  
       
            (oldCapacity + capacityIncrement) : (oldCapacity * 2);  
       
             if (newCapacity < minCapacity) {  
       
            newCapacity = minCapacity;  
       
             }  
       
              elementData = Arrays.copyOf(elementData, newCapacity);  
       
         }  
       
     }  

    ArrayListとVectorの主な違いは以下の通りです.
    (1)同期性:
    Vectorはスレッドが安全で、つまりそのメソッド間はスレッド同期であり、ArrayListはラインプログラムが安全ではなく、そのメソッド間はスレッドが同期していない.1つのスレッドだけがコレクションにアクセスする場合は、スレッドのセキュリティを考慮せずに効率が高いため、ArrayListを使用することが望ましい.複数のスレッドがコレクションにアクセスする場合は、スレッドの安全なコードを自分で考え、作成する必要がないため、Vectorを使用することが望ましい.
    備考:Vector&ArrayList、Hashtable&HashMapについては、スレッドセキュリティの問題を覚えておくには、VectorとHashtableは古いものでjavaが誕生すると提供され、スレッドセキュリティであり、ArrayListとHashMapがjava 2である場合に提供されるものであり、スレッドが安全ではないことを覚えておく.(2)データ増加:
    ArrayListとVectorには初期の容量サイズがあり、それらに格納されている要素の個数が容量を超えると、ArrayListとVectorの記憶空間を増やす必要があり、記憶空間を増やすたびに、1つの記憶セルだけを増やすのではなく、複数の記憶セルを増やす必要があり、増加するたびに増加するメモリセルの個数は,メモリ空間利用とプログラム効率との間で一定のバランスをとる.Vectorはデフォルトで2倍に増加していますが、ArrayListの成長戦略はドキュメントに明確に規定されていません(ソースコードから見ると1.5倍に増加しています).ArrayListとVectorはいずれも初期の空間サイズを設定することができ、Vectorは成長の空間サイズを設定することもできるが、ArrayListは成長の空間を設定する方法を提供していない.
        まとめ:つまり、Vectorは元の倍に、ArrayListは元の0.5倍に増加します.空説はソースコードに基づいて見てください.
    ArrayListでの成長定義:
        private void grow(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
        }

    Vectorの成長定義:
     int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                             capacityIncrement : oldCapacity);
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            elementData = Arrays.copyOf(elementData, newCapacity);

    ArrayListでクローン配列がトリガーされるタイミング:
    コンストラクションパラメータは、Collectionコレクションのサブクラスがトリガーする可能性があります.
    trimToSizeの時にトリガーします.
    growの時にトリガーします.
    cloneの時にトリガーします.
    toArrayの時にトリガーします.
    大体の内容はこれだけで本当に分からないので、私に連絡してください.間違いがあれば、指摘を歓迎します.
    以上の文章に問題があれば、指摘を歓迎します.javaアーキテクチャのグループ番号523988350に参加してください.中には大牛の構造師がたくさんいます.