Java コンテナ関連の知識を総合的にまとめた詳細な紹介 (図)-＆＃＆チュートリアル-php.cn

Java PracticalClass Library は、多くの特定の問題を解決するのに役立つ、かなり完全なコンテナのセットを提供します。なぜなら、私自身も Android 開発者であり、私を含む多くの Android 開発者は ListView (RecycleView) + BaseAdapter + ArrayList を最も得意としており、私が通常使用するコンテナーは ArrayList と HashMap だけだからです。その結果、Java コンテナシステム全体の理解と使用はまだ非常に浅いレベルにあります。自分自身を救い、改善について考えたくない場合は、私に従って Java コンテナーに関する関連知識を要約してください。

構造

Javaコンテナクラスの継承構造
詳細な紹介

List
Set
Queue
イテレーター
コレクション
マップ

いくつかの提案
高度な同時コンテナ

CopyOnWriteArrayList と Copy-On-Write 戦略
ConcurrentLinkedQueue
ConcurrentHashMap とロックセグメンテーションテクノロジー
ブロッキングキュー

Java コンテナクラスの継承構造

Java コンテナクラスライブラリは、異なる概念を持つ 2 つのコンテナ、Collection と Map を定義します

Collection 一連の独立した要素、これらの要素はすべて 1 つまたは複数のルールに従います。リストには要素を挿入順に保持する必要があります。セットには重複した要素を含めることはできません。キューは、キューイングルールに従ってオブジェクトが生成される順序を決定します。

(記事内のJdkソースコードのバージョンは特別な指示がなければjdk1.8.0_101です)

    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(java.util.Collection<?> c);

        boolean addAll(java.util.Collection<? extends E> c);

        boolean removeAll(java.util.Collection<?> c);

        ... //省略了其他方法
    }

ログイン後にコピー

ご覧のとおり、JavaはCollectionインターフェースと内部コレクションの基本的な操作メソッドを定義しており、Collectionに要素を追加できます。コレクションの末尾を削除し、デフォルトで要素やその他の操作を指定します。 List、Set、Queue インターフェイスはすべて Collection を継承し、さまざまなメソッドを定義します。

Map キーを使用して値を検索できるようにする「キーと値」オブジェクトのセット。

    public interface Map<K,V> {
        int size();

        boolean containsKey(Object key);

        boolean containsValue(Object value);

        V get(Object key);

        V put(K key, V value);

        V remove(Object key);

        void putAll(java.util.Map<? extends K, ? extends V> m);

        void clear();

        Set<K> keySet();

        Collection<V> values();

        Set<java.util.Map.Entry<K, V>> entrySet();

        interface Entry<K,V> {
            K getKey();

            V getValue();

            V setValue(V value);

            boolean equals(Object o);

            int hashCode();

            ...
        }

        boolean equals(Object o);

        int hashCode();

    }

ログイン後にコピー

Map の内部インターフェイス Entry は、Map のキーと値のペアに対応します。

イテレータの詳細紹介

まず、イテレータを紹介します。イテレータ自体も

設計パターンです。設計の本来の目的は、コンテナを走査したい場合、まず、コンテナの詳細を気にする必要はないということです。次に、コンテナの実装は、トラバース操作の規模が軽い必要があります。イテレータはコンテナへのアクセスを統合し、安価に作成できます。イテレータは一方向にのみ移動できることに注意してください。

    public interface Iterator<E> {
        boolean hasNext();

        E next();

        default void remove() {
            throw new UnsupportedOperationException("remove");
        }

        default void forEachRemaining(Consumer<? super E> action) {
            Objects.requireNonNull(action);
            while (hasNext())
                action.accept(next());
            }
    }

ログイン後にコピー

コンテナの iterator() メソッドを通じてコンテナのイテレータを取得します
イテレータの Next() は次の要素を取得します
hasNext() はまだ要素があるかどうかを判断します
remove() は指定された要素を削除します

ListIterator

ListIterator は Iterator の拡張であり、さまざまな List クラスへのアクセスに使用され、双方向の移動をサポートします。

Collection

List

List は、要素を特定のシーケンスで維持することを約束し、Collection に基づいて多数のメソッドを追加し、要素を List に挿入したり削除したりできるようにします。

    public interface List<E> extends Collection<E> {

        ...

        boolean add(E e);

        boolean remove(Object o);

        boolean containsAll(Collection<?> c);

        boolean addAll(Collection<? extends E> c);

        boolean addAll(int index, Collection<? extends E> c);

        boolean removeAll(Collection<?> c);

        boolean retainAll(Collection<?> c);

        E get(int index);

        E set(int index, E element);

        void add(int index, E element);

        E remove(int index);

        int indexOf(Object o);

        int lastIndexOf(Object o);

        java.util.List<E> subList(int fromIndex, int toIndex);

        ...

    }

ログイン後にコピー

リストには ArrayList と LinkedList の 2 種類があります

リストの種類利点欠点基礎となる実装ArrayList配列LinkedList


ランダム要素へのアクセスが速くなります	中間要素の挿入そして削除が遅い
中間要素の挿入と削除、シーケンシャルアクセスの最適化	ランダムアクセス要素が遅い	二重リンクリスト

セット

「いいえ」を設定重複した要素を保存します。要素をすばやく見つけるためによく使用されます。 Set には Collection とまったく同じインターフェイスがあり、追加機能はありません。格納された要素は、equals（）methodsset type -usageシナリオを定義する必要があります。

TreeSet

は順序を維持し、要素はComparableインターフェースを実装する必要があります赤黒ツリー構造LinkedHashSetはHashSetの順序を維持し、要素はhashCode()を定義する必要がありますリンクリスト

Queue

除了并发应用，Queue仅有的两个实现是LinkedList和PriorityQueue, 其中LinkedList同时实现了List, Deque接口。它们的差异在于排序行为而不是性能。

    public interface Queue<E> extends Collection<E> {
        boolean add(E e);

        boolean offer(E e);

        E remove();

        E poll();

        E element();

        E peek();
    }

ログイン後にコピー

Map

Map类型	使用场景	底层实现
HashMap	快速查询	散列表
LinkedHashMap	迭代遍历具有顺序(插入顺序 or 最近最少使用)	链表
TreeMap	具有排序，唯一可以返回子树的Map(subMap())	红-黑树结构
WeakHashMap	弱键映射，映射之外无引用的键，可以被垃圾回收	散列表
ConcurrentHashMap	线程安全的Map	链表
IdentityHashMap	使用==代替equals()对键进行排序，专位解决特殊问题	链表

容量、初期容量、サイズ、負荷率などの概念を含めて、HashMap を手動で調整してパフォーマンスを調整できます。興味があれば、関連情報を読むことができます。

いくつかの提案

Vector Enumeration Hashtable Stack などの古いコンテナを使用しないでください (はい、これは Java の元の悪い設計です。実際にスタックを使用する場合は、LinkedList をお勧めします)

Advanced Concurrentコンテナ

ここでは実装についてはあまり詳しく説明しませんが、基本的な知識を簡単に紹介しますので、興味があれば「The Art of Java Concurrent Programming」という本を読んでください。

CopyOnWriteArrayList とコピーオンライト戦略

COW と呼ばれるコピーオンライトは、プログラミングで使用される最適化戦略です。基本的な考え方は、全員が最初から同じコンテンツを共有しており、誰かがコンテンツを変更したい場合は、そのコンテンツをコピーして新しいコンテンツを作成し、それを変更するという一種の遅延戦略です。 JDK1.5 以降、Java 同時実行パッケージは、CopyOnWrite メカニズムを使用して実装された 2 つの同時コンテナ (CopyOnWriteArrayList と CopyOnWriteArraySet) を提供します。 CopyOnWrite コンテナは非常に便利で、多くの同時シナリオで使用できます。

CopyOnWrite コンテナは、書き込み時にコピーされるコンテナです。一般に理解されているのは、要素をコンテナに追加するとき、要素を現在のコンテナに直接追加するのではなく、まず現在のコンテナをコピーして新しいコンテナを作成し、要素を追加した後、その新しいコンテナに要素を追加するということです。次に、元のコンテナの参照が新しいコンテナを指すようにします。この利点は、現在のコンテナーは要素を追加しないため、ロックせずに CopyOnWrite コンテナーで同時読み取りを実行できることです。したがって、CopyOnWriteコンテナも読み書き分離の考え方であり、読み書きは別のコンテナです。

CopyOnWrite コンテナはデータの最終的な整合性のみを保証できますが、データのリアルタイムの整合性は保証できません。したがって、書き込まれたデータをすぐに読み出したい場合は、CopyOnWrite コンテナを使用しないでください。

ConcurrentLinkedQueue

同時プログラミングでは、スレッドセーフなキューまたはリストを使用する必要がある場合があります。通常、スレッドセーフを実現するには 2 つの方法があります。1 つはブロッキングアルゴリズムを使用する方法、もう 1 つは非ブロッキングアルゴリズムを使用する方法です。ノンブロッキングアルゴリズム実装の基礎はloopCAS (Compare and Swipe 比較と交換) です。

ConcurrentLinkedQueue の技術的な実装は CopyOnWriteArrayList および Copy に似ていますが、コンテナ全体ではなく、コンテナのコンテンツの一部のみをコピーおよび変更できます。 ConcurrentLinkedQueue はヘッドノードとテールノードで構成され、各ノードはノード要素 (アイテム) と次のノードを指す参照 (ネクスト) で構成されます。ノードは next を介して関連付けられ、リンクリスト構造のキューを形成します。

ConcurrentHashMap とロックセグメンテーションテクノロジー

ConcurrentHashMap は、スレッドセーフで効率的な HashMap です。マルチスレッド環境では、スレッドセーフでない HashMap を使用すると無限ループが発生し、記事で示唆されているように、HashTable などの古いコンテナーは非効率的です (スレッドセーフを確保するには synchronized を使用してください)。 ConcurrentHashMap は、ロックセグメンテーションテクノロジを使用して、同時使用の効率を大幅に向上させます。

ロックセグメンテーションテクノロジ: コンテナーには複数のロックがあり、各ロックはコンテナー内のデータの一部をロックするために使用されると想定します。複数のスレッドがコンテナーの異なるデータセグメント内のデータにアクセスする場合、ロックの競合は発生しません。これにより、同時アクセスの効率が向上します。

ブロックキュー

JDK7 は 7 つのブロックキューを提供します。実装原則はすべて、生産消費モデルの待機通知メカニズムに基づいています。

ブロッキングキューの種類	特徴
ArrayBlockingQueue	配列構造で構成される境界付きブロッキングキュー
LinkedBlockingQueue	Boundリンクされたリスト構造で構成されるブロック Blocking Queue
PriorityBlockingQueue	をサポートpriorityソートされた無制限のブロッキングキュー
DelayQueue	プライオリティキューを使用して実装された無制限のブロッキングキュー
SynchronousQueue	要素を格納しないブロッキングキュー
LinkedTransfer Queue	はリンクされたリストで構成されています。構造体で構成されるキュー
LinkedBlockingQueue	リンクリスト構造体で構成される双方向ブロッキングキュー