ArrayListと。LinkedListとJavaのHashMap

投稿日: 2022-11-07 2022-11-07
タグ: Data Structures, Java Collections

1. 概要

Javaのコレクションは、いくつかのコアインターフェイスと12を超える実装クラスに基づいています。さまざまな実装を幅広く選択すると、混乱を招くことがあります。

特定のユースケースに使用するコレクションタイプを決定することは、簡単な作業ではありません。この決定は、コードの可読性とパフォーマンスに大きな影響を与える可能性があります。

1つの記事ですべてのタイプのコレクションを説明する代わりに、最も一般的な3つのコレクション（ ArrayList、LinkedList、、 HashMap）について説明します。このチュートリアルでは、次のように説明します。データの保存方法、パフォーマンス、およびそれらをいつ使用するかを推奨します。

2. コレクション

コレクションは、他のオブジェクトをグループ化する単なるJavaオブジェクトです。 Javaコレクションフレームワークには、コレクションを表現および操作するためのデータ構造とアルゴリズムのセットが含まれています。正しく適用された場合、提供されたデータ構造はプログラミングの労力を軽減し、パフォーマンスを向上させるのに役立ちます。

2.1. インターフェース

Javaコレクションフレームワークには、リスト、セット、マップ、およびキューの4つの基本インターフェイスが含まれています。実装クラスを確認する前に、これらのインターフェースの使用目的を理解することが重要です。

この記事で使用する4つのコアインターフェイスのうち3つを簡単に見てみましょう。

List インターフェースは、オブジェクトの順序付けられたコレクションを格納するための専用です。これにより、新しい要素に位置的にアクセスして挿入したり、重複した値を保存したりできます。
Map インターフェースは、データのキーと値のペアのマッピングをサポートします。特定の値にアクセスするには、その一意のキーを知る必要があります
Queue インターフェースは、先入れ先出しの順序に基づいてデータを保存できるようにします。実際のキューラインに似ています

HashMap は、Mapインターフェースを実装します。 List インターフェースは、ArrayListとLinkedListの両方によって実装されます。 LinkedList は、Queueインターフェースを追加で実装します。

2.2. リスト対。マップ

私たちが時々遭遇する一般的なアンチパターンは、マップを使用して順序を維持しようとすることです。したがって、他のコレクションタイプを使用しない方が仕事に適しています。

単一のコレクションタイプで多くの問題を解決できるからといって、そうする必要があるとは限りません。

マップを使用して位置キーに基づいてデータを保存する悪い例を見てみましょう。

Map<Integer, String> map = new HashMap<>();
map.put(1, "Daniel");
map.put(2, "Marko");
for (String name : map.values()) {
    assertThat(name).isIn(map.values());
}
assertThat(map.values()).containsExactlyInAnyOrder("Daniel", "Marko");

マップ値を反復処理する場合、それらを配置したのと同じ順序で取得することは保証されません。これは、マップが要素の順序を維持するように設計されていないためです。

リストを使用して、この例をはるかに読みやすい方法で書き直すことができます。 リストは定義順に並べられているため、挿入したのと同じ順序でアイテムを反復処理できます。

List<String> list = new ArrayList<>();
list.add("Daniel");
list.add("Marko");
for (String name : list) {
    assertThat(name).isIn(list);
}
assertThat(list).containsExactly("Daniel", "Marko");

マップは、一意のキーに基づいてすばやくアクセスおよび検索できるように設計されています。順序を維持したり、位置ベースのインデックスを操作したりする場合は、リストが自然な選択です。

3. ArrayList

ArrayList は、Javaで最も一般的に使用されるListインターフェースの実装です。組み込みの配列に基づいていますが、要素を追加または削除すると、動的に拡大および縮小できます。

リスト要素にアクセスするには、ゼロから始まるインデックスを使用します。リストの最後または特定の位置に新しい要素を挿入できます。

List<String> list = new ArrayList<>();
list.add("Daniel");
list.add(0, "Marko");
assertThat(list).hasSize(2);
assertThat(list.get(0)).isEqualTo("Marko");

リストから要素を削除するには、オブジェクト参照またはそのインデックスを提供する必要があります。

List<String> list = new ArrayList<>(Arrays.asList("Daniel", "Marko"));
list.remove(1);
assertThat(list).hasSize(1);
assertThat(list).doesNotContain("Marko");

3.1. パフォーマンス

ArrayList は、Javaの動的配列を提供します。組み込み配列よりも低速ですが、 ArrayList は、プログラミングの労力を節約し、コードの可読性を向上させるのに役立ちます。

時間計算量について話すときは、Big-O表記を使用します。この表記は、入力のサイズに応じてアルゴリズムを実行する時間がどのように長くなるかを示しています。

ArrayList は、配列がインデックスに基づいているため、ランダムアクセスを許可します。つまり、任意の要素へのアクセスには常に一定の時間がかかります O（1）。

新しい要素の追加にもO（1）の時間がかかります。ただし、特定の位置/インデックスに要素を追加する場合は、 O（n）かかります。指定されたリストに特定の要素が存在するかどうかのチェックは、線形 O（n）時間で実行されます。

要素の削除についても同じことが言えます。削除するために選択された要素を見つけるために、配列全体を繰り返す必要があります。

3.2. 使用法

使用するコレクションの種類がわからない場合は、ArrayListから始めることをお勧めします。インデックスに基づいてアイテムにアクセスするのは非常に高速であることに注意してください。ただし、価値に基づいてアイテムを検索したり、特定の位置でアイテムを追加/削除したりすると、コストがかかります。

ArrayList を使用することは、アイテムの同じ順序を維持することが重要であり、位置/インデックスに基づく迅速なアクセス時間が重要な基準である場合に意味があります。

アイテムの順序が重要でない場合は、ArrayListの使用を避けてください。また、特定の位置にアイテムを追加する必要がある場合は、を避けてください。同様に、特定のアイテム値を検索することが重要な要件である場合、特にリストが大きい場合は、ArrayListが最適なオプションではない可能性があることに注意してください。

4. LinkedList

LinkedList は、二重にリンクされたリストの実装です。 ListとDeque（ Queueの拡張）インターフェースの両方を実装します。 ArrayList とは異なり、 LinkedList にデータを格納すると、すべての要素が前の要素へのリンクを維持します。

標準のリスト挿入メソッドに加えて、 LinkedList は、リストの最後に要素を追加できる追加のメソッドをサポートします。

LinkedList<String> list = new LinkedList<>();
list.addLast("Daniel");
list.addFirst("Marko");
assertThat(list).hasSize(2);
assertThat(list.getLast()).isEqualTo("Daniel");

このリストの実装は、リストの最初または最後から要素を削除するためのメソッドも提供します。

LinkedList<String> list = new LinkedList<>(Arrays.asList("Daniel", "Marko", "David"));
list.removeFirst();
list.removeLast();
assertThat(list).hasSize(1);
assertThat(list).containsExactly("Marko");

実装されたDequeインターフェースは、要素を取得、追加、および削除するためのキューのようなメソッドを提供します。

LinkedList<String> list = new LinkedList<>();
list.push("Daniel");
list.push("Marko");
assertThat(list.poll()).isEqualTo("Marko");
assertThat(list).hasSize(1);

4.1. パフォーマンス

LinkedList は、すべてのノードが前の要素と次の要素への2つの参照を格納するため、ArrayListよりも少し多くのメモリを消費します。

LinkedList では、バックグラウンドで配列のサイズ変更が行われないため、挿入、追加、および削除の操作が高速になります。リストの途中に新しいアイテムが追加された場合、変更する必要があるのは周囲の要素の参照のみです。

LinkedList は、コレクション内の任意の位置での O（1）定数時間挿入をサポートします。ただし、 O（n）の時間がかかるため、特定の位置にあるアイテムにアクセスする効率は低くなります。

要素を削除するには、 O（1）一定の時間がかかります。これは、いくつかのポインターを変更するだけでよいためです。指定されたリストに特定の要素が存在するかどうかを確認するには、ArrayList。の場合と同様に、 O（n）線形時間がかかります。

4.2. 使用法

ほとんどの場合、デフォルトのList実装としてArrayListを使用できます。ただし、特定のユースケースでは、 LinkedListを使用する必要があります。これには、一定のアクセス時間よりも一定の挿入および削除時間、および有効なメモリ使用量を優先する場合が含まれます。

LinkedList を使用することは、アイテムの同じ順序を維持する場合に意味があり、迅速な挿入時間（任意の位置でのアイテムの追加と削除）が重要な基準です。

ArrayList のように、アイテムの順序が重要でない場合は、 LinkedList の使用を避ける必要があります。 LinkedList は、高速アクセス時間またはアイテムの検索が重要な要件である場合、最適なオプションではありません。

5. HashMap

ArrayListやLinkedListとは異なり、HashMapはMapインターフェースを実装します。つまり、すべてのキーが正確に1つの値にマップされます。コレクションから対応する値を取得するには、常にキーを知る必要があります。

Map<String, String> map = new HashMap<>();
map.put("123456", "Daniel");
map.put("654321", "Marko");
assertThat(map.get("654321")).isEqualTo("Marko");

同様に、コレクションから値を削除するには、そのキーを使用する必要があります。

Map<String, String> map = new HashMap<>();
map.put("123456", "Daniel");
map.put("654321", "Marko");
map.remove("654321");
assertThat(map).hasSize(1);

5.1. パフォーマンス

リストを使用して、キーをすべて一緒に削除してみませんか？特にHashMapはキーを保存するためにより多くのメモリを消費し、そのエントリは順序付けられていないためです。その答えは、要素を検索することによるパフォーマンス上の利点にあります。

HashMap は、キーが存在するかどうかを確認したり、キーに基づいて値を取得したりするのに非常に効率的です。これらの操作には、平均して O（1）がかかります。

キーに基づいてHashMapに要素を追加および削除するには、 O（1）が一定時間かかります。キーを知らずに要素をチェックするには、すべての要素をループする必要があるため、線形時間 O（n）、がかかります。

5.2. 使用法

ArrayList と並んで、HashMapはJavaで最も頻繁に使用されるデータ構造の1つです。さまざまなリストの実装とは異なり、 HashMap はインデックスを使用して特定の値にジャンプし、大規模なコレクションの場合でも検索時間を一定にします。

HashMap の使用は、保存するデータに一意のキーが使用できる場合にのみ意味があります。キーに基づいてアイテムを検索するときに使用する必要があり、迅速なアクセス時間が重要な要件です。

コレクション内のアイテムの同じ順序を維持することが重要な場合は、HashMapの使用を避ける必要があります。

6. 結論

この記事では、 Java の3つの一般的なコレクションタイプ、 ArrayList、LinkedList、、HashMapについて説明しました。アイテムの追加、削除、検索のパフォーマンスを調べました。これに基づいて、Javaアプリケーションでそれぞれをいつ適用するかについての推奨事項を提供しました。

例では、アイテムを追加および削除するための基本的な方法のみを取り上げました。各実装APIの詳細については、専用の ArrayList、 ArrayList 、およびHashMapの記事をご覧ください。

いつものように、完全なソースコードはGitHubでから入手できます。

getdocs

13036