[Java]List、Queue、Setのクラスメモ

Last updated at 2024-04-30Posted at 2024-04-29

Javaでコーディングを行う際に必ずと言ってもよいほど使用するコレクションについて、今まで使用したことがないものも含めて改めて学習したので備忘録としてまとめてみます。

Listインターフェース

コレクションでよく使用するやつ。学習した3つの実現クラスについてまとめます。

Arraylist

内部に配列を持っていて、あらかじめ要素数を決めておかなければならない配列とはことなり、要素数を必要に応じて増やすことが可能です。

要素数が増える場合、最初に内部で持っていた配列より大きな要素数を扱うことができる配列を新たに作成しそこに元の要素をコピーします。そのため、扱う要素数が増えていくにつれて処理が遅くなります。
具体的に言うと値の読み書きは高速ですが、要素の追加、削除は遅いです。

LinkedList

要素それぞれが前要素の情報と後要素の情報を持っており、繋がっているリスト。各要素にアクセスする際には先頭から順に辿っていくことで要素にアクセスする。
そのためArrayListと比べて要素にアクセスする処理が遅くなります。一方、要素を追加する際にArrayListのように新たな配列を作成する必要がないので追加、削除は早いです。

Vector

マルチスレッドでも安全に扱えるスレッドセーフなリスト。安全に扱えますがArraylistやLinkedListに比べるパフォーマンスは低いです。

CopyOnWriteArrayList

こちらもListを実現したスレッドセーフなコレクション。
複数のスレッドでこのインスタンスを共有していて一方で要素の読み取り、一方で要素の追加が行うことができます。
Arraylistなどの場合、上記のようなことを実行しようとするとエラーが発生します。

ArrayList.java

public static void main(String[] arg) throws Exception {
    List<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);
    new Thread(() -> {
      for(int i = 5; i < 1000; i++) {
        list.add(i);
      }
    }).start();;
    list.stream().forEach(System.out::println);
}

出力結果。別スレッドで要素追加中に本スレッドで要素の読み込みを行ったので例外発生。

--前半の要素出力部分は省略--
968
969
970
971
972
973
Exception in thread "main" java.util.ConcurrentModificationException
	at java.base/java.util.ArrayList$ArrayListSpliterator.forEachRemaining(ArrayList.java:1631)
	at java.base/java.util.stream.ReferencePipeline$Head.forEach(ReferencePipeline.java:762)
	at test.test.main(test.java:29)

これをCopyOnWriteArrayListを使用すれば要素の追加、更新、削除時にはリストのコピーを作成して行うので安全に処理を実行することができます。

CopyOnWriteArrayList.java

public static void main(String[] arg) throws Exception {
    CopyOnWriteArrayList<Integer> list = new CopyOnWriteArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);
    list.stream().forEach(System.out::println);
    new Thread(() -> {
      for(int i = 5; i < 1000; i++) {
        list.add(i);
      }
    }).start();;
    list.stream().forEach(System.out::println);
  }

出力結果。要素の追加はコピー先で行っているので出力されるのは最初に追加した4つの要素のみ。

並列処理が終了した後に読み込みを行うと追加要素が反映されているので出力することができます。

CopyOnWriteArrayList.java

public static void main(String[] arg) throws Exception {
    CopyOnWriteArrayList<Integer> list = new CopyOnWriteArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);
    new Thread(() -> {
      for(int i = 5; i < 1000; i++) {
        list.add(i);
      }
    }).start();
    // 別スレッドが終了するまで待機する
    Thread.sleep(6000);
    list.stream().forEach(System.out::println);
  }

出力結果

--前半の要素出力部分は省略--
996
997
998
999

Queueインターフェース

先入先出のデータ構造の機能を定義したインターフェース。文字通り最初に格納した要素を最初に取り出す構造になっています。

Queue.java

public static void main(String[] arg) throws Exception {
    Queue<Integer> queue = new ArrayDeque<>();
    for(int i = 0; i <= 10; i++) {
      queue.add(i);
    }
    queue.stream().forEach(System.out::println);
  }

出力結果

Dequeインターフェース

先頭と末尾の両方から要素を追加ができて取り出すことができるコレクションです。

addFirstで先頭に要素を追加し、addLastで末尾に要素を追加します。

Deque.java

  public static void main(String[] arg) throws Exception {
    Deque<String> deque = new ArrayDeque<>();
    deque.addFirst("A");
    deque.addFirst("C");
    deque.addLast("D");
    deque.addLast("B");

    deque.stream().forEach(System.out::println);
  }

出力結果

C
A
D
B

Setインターフェース

重複する要素を許可しないコレクションです。
重複している要素が追加されると上書きされるようになっています。

Set.java

public static void main(String[] arg) throws Exception {
    Set<String> set = new HashSet<>();
    set.add("A");
    set.add("B");
    set.add("C");
    set.add("D");
    set.add("A");
    set.stream().forEach(System.out::println);
}

出力結果。Aが重複しているので要素数が4つになっています。

A
B
C
D

何をもって重複していると判断するかは下記の2点を①からチェックしていき当てはまれば重複と判断しています。

①ハッシュコードが一致しているか
②equalsメソッドで戻り値がtrueになっているか

hashCodeメソッドとequalsメソッドをオーバーライドし意図的に重複していると判断されるクラスを作成して確かめてみましょう。

Sample.java

public class Sample {
  private String str;

  public Sample(String str) {
    this.str = str;
  }

  public String getStr() {
    return this.str;
  }

  @Override
  public int hashCode() {
    return 1;
  }
  @Override
  public boolean equals(Object obj) {
    return true;
  }
}

Set.java

  public static void main(String[] arg) throws Exception {
    Set<Sample> sample = new HashSet<>();
    sample.add(new Sample("A"));
    sample.add(new Sample("B"));
    sample.add(new Sample("C"));
    sample.add(new Sample("D"));

    sample.stream().forEach(s -> System.out.println(s.getStr()));
  }

出力結果。追加した全ての要素が最初に追加した要素Aと重複していると判断されAしか出力されていない。

HashSet

要素の並び順を保証しないSet。並び替えをしない分、後続で記載するTreeSetに比べて処理が速いです。

TreeSet

自然順序に並び替えるか引数で渡したComparatorのソート処理に従って並び替えを行うことができるSet。

TreeSet.java

  public static void main(String[] arg) throws Exception {
    Set<String> sample = new TreeSet<>();
    sample.add("D");
    sample.add("B");
    sample.add("A");
    sample.add("C");

    sample.stream().forEach(System.out::println);
  }

出力結果。自然順に要素が並び替えられて出力されている。

A
B
C
D

Comparatorを引数に渡した場合

TreeSet.java

public static void main(String[] arg) throws Exception {
    Set<Sample> sample = new TreeSet<>((s1, s2) -> s1.getName().compareTo(s2.getName()));
    sample.add(new Sample("Taro", 10));
    sample.add(new Sample("Ichiro", 33));
    sample.add(new Sample("Yuki", 40));
    sample.add(new Sample("Kanako", 20));

    sample.stream().forEach(s -> System.out.println(s.getName()));
  }

出力結果。引数で指定したアルゴリズムに基づいて並び替えられて出力されている。

Ichiro
Kanako
Taro
Yuki

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up