コレクション·フレームワーク

コレクションの概要

コレクションは、オブジェクトのグループを保存および操作するためのコンテナです。Javaコレクションクラスは、配列、連結リスト、ハッシュテーブル、ツリーなどのデータ構造をカプセル化し、統一されたインターフェイスを提供します。

集合は通常、配列と比較して次のような特徴を持つ。

集合長は動的に変化することができる。
コレクションは参照型のみを直接保持でき、ベース型は自動ボックス化によってラッパークラスに変換されます。
異なるコレクションには、検索、挿入、削除、ソート、重み付けなどの特徴があります。

コレクションを選択する際には、インデックスが必要かどうか、重複が許容されるかどうか、順序が必要かどうか、キーと値のマッピングが必要かどうか、並行性が必要です。

コレクションフレームワークの構造

Collectionは単一列コレクションのトップレベルインタフェースであり、一般的な方法にはadd()、addAll()、contains()、remove()、clear()、size()、iterator()がある。

List、Set、QueueはすべてCollectionアーキテクチャに属します。Mapはキー·値のマッピングを保持し、Collectionを継承しません。

Listインタフェース

Listは順序付けられた反復可能な要素のシーケンスを表し、インデックスベースの操作を提供します。

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add(1, "C");

System.out.println(list.get(0));
System.out.println(list.indexOf("C"));
list.set(0, "AA");
list.remove(1);

ArrayList

ArrayListは内部でスケーラブル配列を使用して要素を保持する。

ArrayListの特長

インデックスに基づく要素へのアクセスは高速であり、時間複雑性は通常O(1)である。
尾部に要素を追加するのは通常高速ですが、スケールアップには配列のコピーが必要です。
途中で要素を挿入または削除するには後続要素の移動が必要で、時間的複雑性は通常O(n)です。
スレッドセーフコレクションではありません

ArrayListの簡易設計

Lite ArrayListを実装する場合は、次のフィールドを使用できます。

private Object[] data;
private int size;

data.lengthは現在の容量を表し、sizeは実際のエレメント数を表します。有効な要素インデックスの范囲は0からsize - 1です。

容量の拡大

要素を追加する前に、size == data.lengthの場合は、より大きな配列を作成し、要素をコピーする必要があります。

private void ensureCapacity() {
    if (size < data.length) {
        return;
    }

    int newCapacity = data.length == 0 ? 10 : data.length + (data.length >> 1);
    data = Arrays.copyOf(data, newCapacity);
}

スケールアップには、コピー数の削減と空きメモリの制御のバランスが必要です。

要素を追加

public boolean add(Object value) {
    ensureCapacity();
    data[size++] = value;
    return true;
}

指定した位置に要素を挿入する場合、許可されるインデックス範囲は0 ~ sizeです。ここで、sizeは尾部挿入を表します。

public void add(int index, Object value) {
    checkPositionIndex(index);
    ensureCapacity();

    System.arraycopy(data, index, data, index + 1, size - index);
    data[index] = value;
    size++;
}

要素の取得、変更、削除

public Object get(int index) {
    checkElementIndex(index);
    return data[index];
}

public Object set(int index, Object value) {
    checkElementIndex(index);
    Object oldValue = data[index];
    data[index] = value;
    return oldValue;
}

public Object remove(int index) {
    checkElementIndex(index);
    Object oldValue = data[index];

    int moved = size - index - 1;
    if (moved > 0) {
        System.arraycopy(data, index + 1, data, index, moved);
    }
    data[--size] = null;
    return oldValue;
}

削除後に空き位置をnullに設定すると、コレクションが不要なオブジェクト参照を保持し続けるのを防ぎます。

検索と空

public int indexOf(Object value) {
    for (int i = 0; i < size; i++) {
        if (Objects.equals(value, data[i])) {
            return i;
        }
    }
    return -1;
}

public boolean contains(Object value) {
    return indexOf(value) >= 0;
}

public void clear() {
    Arrays.fill(data, 0, size, null);
    size = 0;
}

Objects.equals()は通常のオブジェクトとnullを同時に正しく処理できる.

LinkedList

LinkedListは内部的に二重連結リストを使用して要素を保持し、ListとDequeインタフェースを実装している。

各ノードは通常、現在のデータ、前のノード参照、および後のノード参照を保持します。連結リストオブジェクトは、ヘッダーノード、末尾ノード、要素数も保持します。

LinkedListの特徴

ノードの位置がわかっている場合、挿入と削除では近傍参照を修正するだけです。
インデックスによる検索は、先頭または末尾から1つずつ移動する必要があり、時間計算量は通常O(n)である。
各ノードは前後参照を追加保存する必要があり、メモリのオーバーヘッドは通常ArrayListよりも大きくなります。
スレッドセーフコレクションではありません

Liteノード構造

private static class Node {
    private Object data;
    private Node prev;
    private Node next;

    Node(Object data, Node prev, Node next) {
        this.data = data;
        this.prev = prev;
        this.next = next;
    }
}

尾部ノードの追加

public boolean add(Object value) {
    Node oldLast = last;
    Node newNode = new Node(value, oldLast, null);
    last = newNode;

    if (oldLast == null) {
        first = newNode;
    } else {
        oldLast.next = newNode;
    }

    size++;
    return true;
}

インデックスに基づくノードの検索

インデックスをsize / 2と比較して、先頭から探すか末尾から探すかを決定できます。

private Node getNode(int index) {
    checkElementIndex(index);

    if (index < (size >> 1)) {
        Node current = first;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current;
    }

    Node current = last;
    for (int i = size - 1; i > index; i--) {
        current = current.prev;
    }
    return current;
}

ノードを削除

private Object unlink(Node node) {
    Node previous = node.prev;
    Node next = node.next;

    if (previous == null) {
        first = next;
    } else {
        previous.next = next;
        node.prev = null;
    }

    if (next == null) {
        last = previous;
    } else {
        next.prev = previous;
        node.next = null;
    }

    Object oldValue = node.data;
    node.data = null;
    size--;
    return oldValue;
}

LinkedListのキューとスタックの使い方

Queueキュー

キューは通常、先入れ先出し規則に従います。offer()、poll()、およびpeek()を推奨します。これらは、操作が失敗した場合やキューが空の場合に結果を表す戻り値を使用します。

Queue<String> queue = new LinkedList<>();
queue.offer("A");
queue.offer("B");

System.out.println(queue.poll());
System.out.println(queue.peek());

Dequeデュアルエンドキュー

Dequeは、両端から要素を追加および削除することができ、スタックとして使用することもできます。

Deque<String> stack = new LinkedList<>();
stack.push("A");
stack.push("B");

System.out.println(stack.pop());
System.out.println(stack.peek());

新しいコードは通常、古いStackクラスの代わりにDequeを使用します。

ArrayList、LinkedList、およびVector

集合	内部構造	主な特徴
`ArrayList`	動的配列	インデックスアクセスは高速、中間挿入削除には移動要素
`LinkedList`	二重連結リスト	インデックスによるアクセスが遅く、キューまたはデュアルエンドキューとして利用可能
`Vector`	動的配列	レガシー同期集合、同期オーバーヘッド付きの単一メソッド呼び出し

LinkedListのすべての挿入削除がArrayListより速いとは単純には考えられない.インデックスで場所を検索する必要がある場合は、全体的な操作はO(n)のままになります。

ジェネリックス

ジェネリックは型を引数として取るため、コンパイラはコンパイル時に型をチェックし、キャストを減らすことができます。

クラスとインターフェイスジェネリック

public class Test<E, F> {
    public F method(E value) {
        return null;
    }
}

public interface ITest<PK> {
    void method(PK value);
}

一般的な型引数は、T、E、K、Vのように、単一の大文字を使用します。

ジェネリックメソッド

ジェネリックメソッドは戻り値の前に型パラメータを宣言します。

public static <T> T first(T[] values) {
    return values.length == 0 ? null : values[0];
}

メソッドジェネリックはクラスジェネリックとは独立している。

ジェネリック型を指定する

Test<String, Integer> test = new Test<>();

サブクラスがジェネリックな親クラスを継承したり、ジェネリックなインタフェースを実装したりする場合、具体型を指定できます。

public class SubTest extends Test<String, Integer>
        implements ITest<Person> {

    @Override
    public Integer method(String value) {
        return value.length();
    }

    @Override
    public void method(Person value) {
        System.out.println(value);
    }
}

プリミティブ型を使用するとコンパイル時の型チェックが失われ、“unspecified generics”は安全なObjectジェネリックと単純に解釈されるべきではない。

List rawList = new ArrayList(); // 不推荐

ジェネリックには共変性がない

StudentがPersonのサブクラスであっても、List<Student>はList<Person>のサブタイプではない。

// List<Person> people = new ArrayList<Student>(); // 编译错误

配列には共変性がありますが、エラーは実行時まで遅延することがあります。

Person[] people = new Student[3];
// people[0] = new Person(); // 运行时抛出 ArrayStoreException

ワイルドカードワイルドカード

?は未知のタイプを表します。

上界ワイルドカード

? extends Personは未知のPersonサブタイプを表し、データを読み取るのに適している。

public static void printPeople(List<? extends Person> people) {
    for (Person person : people) {
        System.out.println(person);
    }
}

null以外では、実際の要素タイプが不明なため、通常、このコレクションに安全に具体的なオブジェクトを追加することはできません。

下限ワイルドカード#下限ワイルドカード#

? super Studentは、StudentまたはStudentオブジェクトへの書き込みに適した親タイプを表します。

public static void addStudent(List<? super Student> people) {
    people.add(new Student());
}

“生産者はextendsを使用し、消費者はsuperを使用する”を使用して記憶を助けることができる。

Collectionsツールクラス

Collectionsはコレクションアルゴリズムツールクラスであり、Collectionはコレクションインタフェースであり、意味が異なります。

一括追加とソート

List<String> values = new ArrayList<>();
Collections.addAll(values, "cac", "bcd", "abc");
Collections.sort(values);

元素がComparableを実装する場合、自然順序を提供することができる。

public class Person implements Comparable<Person> {
    private int age;
    private double height;

    @Override
    public int compareTo(Person other) {
        int ageResult = Integer.compare(age, other.age);
        if (ageResult != 0) {
            return ageResult;
        }
        return Double.compare(height, other.height);
    }
}

Integer.compare()などの方法を使用すると、直接減算による整数オーバーフローを回避できます。

比較ルールを一時的に変更する必要がある場合は，Comparatorを渡すことができる.

Collections.sort(people, new Comparator<Person>() {
    @Override
    public int compare(Person p1, Person p2) {
        return Integer.compare(p1.getScore(), p2.getScore());
    }
});

compareTo()とcompare()はどちらも負、ゼロ、または正を返す必要があります。-1、0、1を正確に返す必要はありません。

その他一般的な方法

binarySearch()：順序付けられたリストでバイナリ検索を実行します。
replaceAll()：すべての等しい要素を置き換える。
shuffle()：リスト順序をランダムにシャッフルする.
swap()：2つのインデックス位置の要素を交換します。
synchronizedList()同期ラッパー·リストを返します。

同期ラッパーコレクションは、トラバース中にドキュメント要件に従って外部同期が必要であり、単一のメソッド同期は、複合操作のセットが自動的にアトミックであることを意味しません。

Mapインターフェイス

Mapでは、キーと値を使用してマッピング関係を保存します。キーは重複できません。put()を繰り返し呼び出すと、古い値が置き換えられます。値は重複できます。

Map<String, Integer> map = new HashMap<>();
map.put("001", 100);
map.put("002", 200);
map.put("002", 300);

System.out.println(map.get("001"));
System.out.println(map.containsKey("002"));
System.out.println(map.containsValue(300));
map.remove("002");

Mapの実装によって、順序、空キー、ソート、スレッドセーフの規定が異なります。

HashMap

HashMapはハッシュテーブルを使用してキー値マッピングを保持します。理想的には、検索、追加、削除の平均時間複雑性はO(1)に近いですが、ワーストケースと実際のパフォーマンスはハッシュ分布、競合、容量に依存します。

基本的な構造

Java 8のHashMapは主に配列、連結リスト、赤黒木で構成される。

デフォルトの負荷係数は0.75であり、スケーリングスレッショルドは通常容量に負荷係数を掛けた値です。

キーと値のペアはノードオブジェクトとしてカプセル化され、ノードはMap.Entryインタフェースを実装します。

デフォルトのコンストラクタは、長さ16の配列をすぐに作成しません。ストレージテーブルは通常、最初の挿入時にデフォルト容量に初期化されます。

要素を追加するプロセス

HashMapにキーと値のペアを追加する場合の主な手順は次のとおりです。

鍵のハッシュ値を計算し、摂動処理を行う。
配列長とハッシュ値を使用してバケットインデックスを計算します。容量が2の累乗の場合、通常の剰余の代わりにビット演算が使用される。
バケットが空の場合はノードを直接作成します。
バケットが空でない場合は，ハッシュ値とequals()により同じ鍵が存在するか否かを判断する.
キーがすでに存在する場合は値を置き換えます。そうでない場合は、新しいノードをリストまたは赤黒木に追加します。
要素数がしきい値を超えた場合の拡張。

Java 8では、個々のバケットのリストノード数がツリー化閾値に達すると、配列容量もチェックされます。通常、容量不足時に拡張が優先され、必要な容量に達した後に赤黒木に変換されます。単に“特定の長さに達する”とは言えません。

HashMapは、1つのnullキーと複数のnull値を許可するが、スレッドセーフなコレクションではない。

キーオブジェクトの要求

鍵の対象としてequals()を書き換える場合は，同時にhashCode()を正しく書き換える必要がある.キーがHashMapに格納された後、equals()またはhashCode()の計算に関与するフィールドを変更しないでください。

共通のマップ実装

Hashtable

Hashtableはレガシー同期マッピングであり、nullキーまたはnull値は許可されません。新しいコードでは、通常、シナリオに応じてHashMap、同期ラッパー、またはConcurrentHashMapが選択されます。

TreeMap

TreeMapは赤黒木に基づいており、キーの自然な順序または指定されたコンパレータに基づいてソートされる。

TreeMap<Integer, String> map = new TreeMap<>(
        Comparator.reverseOrder()
);
map.put(100, "100");
map.put(80, "80");
map.put(120, "120");
System.out.println(map);

コンパレータが2つのキーが等しいと判断すると、TreeMapはそれらを同じキーとして扱うため、比較ルールはビジネス等価セマンティクスと一致する必要があります。

LinkedHashMap

LinkedHashMapはハッシュテーブルに基づいて二重連結リストを保持する。デフォルトでは挿入順に反復され、コンストラクタによってアクセス順に設定することもでき、単純なLRUキャッシュの実装によく使われる。

Map<String, Integer> map = new LinkedHashMap<>();
map.put("b", 10);
map.put("a", 11);
map.put("c", 12);
System.out.println(map);

Setインターフェース

Setでは、要素の重複は認められません。順序を維持するか順序を維持するかは実装によって決まり、すべてのSetを順序なしにまとめることはできない。

HashSet

HashSet内部ではHashMapを使用して要素を保存し、集合要素をキーとして、値には内部固定オブジェクトを使用します。

Set<String> set = new HashSet<>();
set.add("a");
set.add("b");
set.add("a");
set.add("c");
System.out.println(set);

元素が重複するかどうかは主にhashCode()とequals()によって決定される。

LinkedHashSet

LinkedHashSetは重量を取り除きながら挿入順序を維持する。

Set<String> set = new LinkedHashSet<>();
Collections.addAll(set, "b", "a", "c", "a");
System.out.println(set);

TreeSet

TreeSetは自然順序またはコンパレータに基づいてソートされ、比較結果がゼロかどうかを使用して要素が重複しているかどうかを判断します。

Set<String> set = new TreeSet<>(
        Comparator.comparingInt(String::length)
                .thenComparing(Comparator.naturalOrder())
);
set.add("baaaa");
set.add("a");
set.add("ccc");
set.add("bbb");
System.out.println(set);

コンパレータが文字列の長さのみを比較する場合、同じ長さの異なる文字列は重複要素として扱われるため、二次比較規則を追加する必要があります。

Iteratorイテレータ

Iterableインタフェースはiterator()メソッドを提供し、Iteratorインタフェースは異なるコレクションのトラバースを統一します。

一般的な方法は以下の通り

hasNext()：次の元素があるかどうかを判定する。
next()次の要素を返し、要素がない場合はNoSuchElementExceptionをスローします。
remove()：next()が最後に返した要素を削除します。サポートは特定のイテレータによって決定されます。

Listのトラバーサル

List<String> list = new ArrayList<>();
Collections.addAll(list, "a", "b", "c");

Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String value = iterator.next();
    if ("c".equals(value)) {
        iterator.remove();
    }
}

トラバーサル中にコレクションの構造変更メソッドを直接呼び出し、通常は高速障害チェックをトリガしてConcurrentModificationExceptionをスローします。イテレータ独自のremove()を使用するか、トラバース終了後に統一的に変更してください。

セットを通過する

Set<String> set = new HashSet<>();
Collections.addAll(set, "a", "b", "c");

Iterator<String> iterator = set.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

マップを移動する

Map自体はIterableを実装しておらず、通常はentrySet()、keySet()、またはvalues()を介して反復可能なビューを取得します。

Map<String, String> map = new HashMap<>();
map.put("101", "a");
map.put("102", "b");
map.put("103", "c");

for (Map.Entry<String, String> entry : map.entrySet()) {
    System.out.println(entry.getKey() + "," + entry.getValue());
}

キーのみが必要な場合はkeySet()を、値のみが必要な場合はvalues()をトラバースできます。

ループの強化

Iterableを実装する配列とオブジェクトをトラバースできるforループの拡張。

for (String value : list) {
    System.out.println(value);
}

コレクションをトラバースする際に、forループの低レベルのイテレータ使用が強化され、サポートされていない構造的変更がループ内で直接コレクションに加えられないようになりました。

配列をトラバースするとき、コンパイラはIteratorを使用せずに配列インデックスごとにループロジックを生成します。

String[][] values = {
    {"a", "b"},
    {"c", "d"}
};

for (String[] row : values) {
    for (String value : row) {
        System.out.println(value);
    }
}

インデックスに基づいてList要素を変更する必要がある場合は、通常のforサイクルまたはListIteratorを使用できます。